SRM #653 div2

VictorWonder posted @ 2015年3月18日 16:24 in TopCoder with tags 动态规划 解题报告 , 1400 阅读
省选就要到了,结果还是很弱,估计就要滚粗了。
最近都在坑带花树,本来以为已经考虑到所有细节了,结果现实很骨感,出现了一个不知道该怎么解决的情况。
因为脑中一片乱麻,所以决定先扔掉带花树,等心情好一点了在搞。所以打算把昨天晚上的Single Round Match 653 Round 2(其实就是SRM #653 div2啦)的题解给写出来。
因为是蒟蒻,只能参加div2,div1的神题又懒得去艹了,所以干脆只写div2的题解了。
 
Easy-250pts
题意大意:有一些人,来自不同的国家,相同国家的站在一起,你问每个人他的国家来了多少人,如果符合要求输出国家数,不符合要求输出-1。
直接搞就行了,结果同房间排我前面那位莫名其妙地FST了,好后悔,当初要是仔细看一下估计就可以cha掉他了。
我的做法是这样的,用num记录当前国家来了多少个人,对于第i个人,num为0时num++,num不为0时,如果a[i]=a[i-1],那么num++,否则范围-1。当a[i]==num时,表示一个国家已经结束了,重置num。
 
Medium-500pts
题目大意:两个人玩石头剪刀布,你通过作弊知道对方每次要出什么,每局如果你赢了得1分,否则不得分,问你拿到某个分值的方案数有多少。
比较水的DP,一直不知道给出Bob的序列除了告诉你序列长度以外有什么用。
转移方程是这样的:f[i][j]表示前i轮拿到j的分数有多少种方案。f[i][0]=f[i-1][0]*2,f[i][j]=f[i-1][j]*2+f[i-1][j-1],不要忘了取模就行了。
 
Hard-1000pts
题目大意:给出一个序列,请你找出两个没有交且并为全集的子序列,使得每个子序列相邻两位之间的数字差的绝对值之和最小。
还是DP,开始的时候把复杂度想成了[tex]O(n^3)[/tex],纠结了很久,后来发现好像我的做法复杂度就是[tex]O(n^2)[/tex]的。
f[i][j]表示没有选择第i个数的序列上一次选择了第几个数。
f[i][0]=f[i-1][0]+Abs(c[i]-c[i-1]),表示一个序列始终不选。
f[i][j]=f[i-1][j]+Abs(c[i]-c[i-1]),表示第i-1次选了数的那个序列继续选数。
f[i][i-1]=f[i-1][0],表示一直没有选数的那个序列在这一次选了一个数。
f[i][i-1]=min(f[i][i-1],f[i-1][j]+Abs(c[i]-c[j])),表示让上一次没有选数的那个序列选数,其实上面一条和这一条应该是归类到一起的,但是如果是空序列选择第一个数的话,是不需要增加值的,也就是说,f[i-1][0]+Abs(c[i]-c[0])是错的,所以需要分出来特判一下。
据说这道题在div1中加上了一些条件,要用网络流做,按理说,这题也可以用网络流做,但是我这个网络流渣渣当然不会啦,所以就不说了吧。
 
Code:(好像都很短的样子啦啦啦)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class CountryGroup {
public:
	int solve(vector <int>);
};

int CountryGroup::solve(vector <int> a) {
	int i,j,n=a.size(),ans=0,num=0;
	for (i=0;i<n;i++) {
	    if (num==0) num=1;
	    else if (a[i]==a[i-1]) num++;
	    else if (a[i]!=a[i-1]) return -1;
	    if (a[i]==num) {
	        ans++;
	        num=0;
	    }
	} return (num==0)?ans:-1;
}


//Powered by [KawigiEdit] 2.0!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
typedef long long ll;
const int P=1000000007;
const int N=2010;

class RockPaperScissorsMagicEasy {
public:
	int count(vector <int>, int);
};
int f[N][N];
int RockPaperScissorsMagicEasy::count(vector <int> card, int score) {
    int n=card.size(),i,j; f[0][0]=1;
    for (i=1;i<=n;i++) {
        f[i][0]=f[i-1][0]*2%P;
        for (j=1;j<=n;j++) f[i][j]=(f[i-1][j-1]+(f[i-1][j]*2%P))%P;
    } return f[n][score];
}


//Powered by [KawigiEdit] 2.0!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
typedef long long ll;
const int N=2010;
const int infi=2000000008;
class SingingEasy {
public:
	int solve(vector <int>);
};
int f[N][N],sum[N],c[N];
int Abs(int x) {return x>0?x:-x;}
int SingingEasy::solve(vector <int> pitch) {
	int n=pitch.size(),i,j,k,ans;
	for (i=1;i<=n;i++) c[i]=pitch[i-1];
	for (i=2;i<=n;i++) {
	    f[i][0]=f[i-1][0]+Abs(c[i]-c[i-1]);
	    for (j=1;j<i-1;j++) f[i][j]=f[i-1][j]+Abs(c[i]-c[i-1]);
	    f[i][i-1]=f[i-1][0];
	    for (j=1;j<i-1;j++) f[i][i-1]=min(f[i][i-1],f[i-1][j]+Abs(c[i]-c[j]));
	} ans=f[n][0];
	for (i=1;i<n;i++) ans=min(ans,f[n][i]);
	return ans;
}


//Powered by [KawigiEdit] 2.0!
PureFrog 说:
2015年3月22日 16:19

仰慕楼主Orz

Avatar_small
VictorWonder 说:
2015年3月23日 12:58

@PureFrog: ?? shenmegui?

PureFrog 说:
2015年3月23日 15:37

@VictorWonder: 从谷歌上搜题解过来的。楼主好强Orz

Avatar_small
VictorWonder 说:
2015年3月23日 19:40

@PureFrog: 这。。我是蒟蒻求不黑。。

PureFrog 说:
2015年3月24日 16:46

@VictorWonder: 楼主方便留一下QQ吗?有时候有些问题想请教下QAQ

Avatar_small
VictorWonder 说:
2015年4月01日 20:06

@Johnson Yip: 你凑什么热闹……

Johnson Yip 说:
2015年4月01日 21:15

@VictorWonder:
从谷歌上搜题解过来的。楼主好强Orz
楼主方便留一下QQ吗?有时候有些问题想请教下QAQ


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter