codeforces round #258 (div. 2)[abcd] acm 题目地址:codeforces round #258 (div. 2) a - game with sticks 题意 ： akshat and malvika两人玩一个游戏，横竖n,m根木棒排成#型，每次取走一个交点，交点相关的横竖两条木棒要去掉，akshat先手，给出n,m问谁赢
codeforces round #258 (div. 2)[abcd]acm
题目地址:codeforces round #258 (div. 2)
a - game with sticks题意： 
akshat and malvika两人玩一个游戏，横竖n,m根木棒排成#型，每次取走一个交点，交点相关的横竖两条木棒要去掉，akshat先手，给出n,m问谁赢。
分析： 
水题，很明显不管拿掉哪个点剩下的都是(n-1,m-1)，最后状态是(0,x)或(x,0)，也就是拿了min(n,m)-1次，判断奇偶即可。
代码：
/** author: illuz * file: a.cpp* create date: 2014-07-24 23:32:17* descripton: */#include #include using namespace std;const int n = 0;int a, b;int main() { scanf(%d%d, &a, &b); if (min(a, b) % 2) { puts(akshat); } else { puts(malvika); } return 0;}
b - sort the array题意： 
给一个序列，求是否能够通过翻转中间一段数使得整个序列递增，并给翻转区间。
分析： 
数为10^5个，所以直接排序，然后找出区间验证即可。
代码：
/** author: illuz * file: b.cpp* create date: 2014-07-24 23:49:35* descripton: */#include #include #include using namespace std;const int n = 1e5 + 10;int n, beg, end, flag;int a[n], b[n];bool cont;int main() { scanf(%d, &n); for (int i = 0; i = 0 && a[end] == b[end]) end--; if (beg == n) { printf(yes\n); printf(1 1\n); return 0; } flag = true; for (int i = 0; i
c - predict outcome of the game题意： 
三支球队要进行n场足球比赛，已经进行了k场，已知一二两队胜局相差d1，二三两队胜局相差d2，问接下去有没可能出现三队胜局都一样，也就是平局的情况。
分析： 
我们只知道是相差d1,d2，而不知道是那边比较多，所以有四种情况，判断四种情况就行了：
判断已比赛场数的合法性： 判断已经进行的比赛场数s是否已经超过k了，如果没有超过，判断(k-s)是否能被3整除判断剩余场数： 判断剩余场数能否把三队胜局填平，如果可以，看扣掉填平后的剩余场数是否能被3整除。代码：
/** author: illuz * file: c.cpp* create date: 2014-07-25 00:34:20* descripton: */#include using namespace std;typedef long long ll;ll t, k, n, d1, d2, md;bool jg(ll a, ll b, ll c) { ll s = a + b + c; if (k > t; while (t--) { cin >> n >> k >> d1 >> d2; md = max(d1, d2); if (jg(0, d1, d1 + d2) || jg(d1 + d2, d2, 0) || jg(d1, 0, d2) || jg(md - d1, md, md - d2)) cout
d - count good substrings题意： 
由a和b构成的字符串，如果压缩后变成回文串就是good字符串。问一个字符串有几个长度为偶数和奇数的good字串。
分析： 
可以发现，不管怎么样，压缩后的字符串是...ababab...这种格式的，所以首尾字符相同，那就是good字符串了。 
我们还要证明下任意good字串的首尾字符串都是一样的，这不难。 
奇偶问题的话，可以发现任意两个奇数位置上的a及中间的字符组成的字符串都是奇数长度的，同理偶数位置和b。奇数位置上的a和偶数位置上的a的字符串是偶数长度的。
代码：
/** author: illuz * file: d.cpp* create date: 2014-07-25 10:49:46* descripton: */#include #include #define f(a) (a*(a-1)/2)using namespace std;string s;long long r[2][2];int main() { cin >> s; for (int i = 0; s[i]; i++) r[i&1][s[i]-'a']++; cout
总结：orz帆神ak，e题涉及逆元，回头补上～