SRM #653 div2
省选就要到了，结果还是很弱，估计就要滚粗了。
最近都在坑带花树，本来以为已经考虑到所有细节了，结果现实很骨感，出现了一个不知道该怎么解决的情况。
因为脑中一片乱麻，所以决定先扔掉带花树，等心情好一点了在搞。所以打算把昨天晚上的Single Round Match 653 Round 2（其实就是SRM #653 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!
2015年3月22日 16:19
仰慕楼主Orz
2015年3月23日 12:58
@PureFrog: ？？ shenmegui？
2015年3月23日 15:37
@VictorWonder: 从谷歌上搜题解过来的。楼主好强Orz
2015年3月23日 19:40
@PureFrog: 这。。我是蒟蒻求不黑。。
2015年3月24日 16:46
@VictorWonder: 楼主方便留一下QQ吗？有时候有些问题想请教下QAQ
2015年3月31日 20:59
仰慕楼主Orz
2015年4月01日 20:06
@Johnson Yip: 你凑什么热闹……
2015年4月01日 21:15
@VictorWonder:
从谷歌上搜题解过来的。楼主好强Orz
楼主方便留一下QQ吗？有时候有些问题想请教下QAQ
2022年9月04日 19:39
Here are the complete details about PSC Result 2022 Rajshahi Board or Division, and students you are at the correct location to check total PSC Exam GPA Grade marks 2022 with downloading of full mark sheet, Grade 5 Result Rajshahi Board as per DPE announcement there are lacks of students participate in this year like previous years, and this year this number is reached up to 30 lacks from all divisions in the country. This year also the Primary School Certificate Examination has completed as per schedule for all divisions and those terminal exams are held without delay under Rajshahi education board functioning under DPE, now they are ready to announce PSC Result 2022 with Full Marksheet for all education boards in the country.