首页 > 代码库 > Codeforces Round #258 (Div. 2)[ABCD]
Codeforces Round #258 (Div. 2)[ABCD]
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 <iilluzen[at]gmail.com> * File: A.cpp * Create Date: 2014-07-24 23:32:17 * Descripton: */ #include <cstdio> #include <algorithm> 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 <iilluzen[at]gmail.com> * File: B.cpp * Create Date: 2014-07-24 23:49:35 * Descripton: */ #include <cstdio> #include <cstring> #include <algorithm> 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 < n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(b, b + n); beg = 0; end = n - 1; while (beg < n && a[beg] == b[beg]) beg++; while (end >= 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 <= end - beg; i++) { // cout << b[beg + i] << ' ' << a[end - i] << endl; if (b[beg + i] != a[end - i]) { flag = false; break; } } if (flag) { printf("yes\n"); printf("%d %d\n", beg + 1, end + 1); } else { printf("no\n"); } return 0; }
C - Predict Outcome of the Game
题意:
三支球队要进行n场足球比赛,已经进行了k场,已知一二两队胜局相差d1,二三两队胜局相差d2,问接下去有没可能出现三队胜局都一样,也就是平局的情况。
分析:
我们只知道是相差d1,d2,而不知道是那边比较多,所以有四种情况,判断四种情况就行了:
- 判断已比赛场数的合法性: 判断已经进行的比赛场数s是否已经超过k了,如果没有超过,判断(k-s)是否能被3整除
- 判断剩余场数: 判断剩余场数能否把三队胜局填平,如果可以,看扣掉填平后的剩余场数是否能被3整除。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: C.cpp * Create Date: 2014-07-25 00:34:20 * Descripton: */ #include <iostream> 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 < s || (k - s) % 3) return 0; ll t = n - k - (3 * max(max(a, b), c) - s); if (t < 0 || t % 3) return 0; return 1; } int main() { cin >> 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 << "yes" << endl; else cout << "no" << endl; } return 0; }
D - Count Good Substrings
题意:
由a和b构成的字符串,如果压缩后变成回文串就是Good字符串。问一个字符串有几个长度为偶数和奇数的Good字串。
分析:
可以发现,不管怎么样,压缩后的字符串是...ababab...
这种格式的,所以首尾字符相同,那就是Good字符串了。
我们还要证明下任意good字串的首尾字符串都是一样的,这不难。
奇偶问题的话,可以发现任意两个奇数位置上的a及中间的字符组成的字符串都是奇数长度的,同理偶数位置和b。奇数位置上的a和偶数位置上的a的字符串是偶数长度的。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: D.cpp * Create Date: 2014-07-25 10:49:46 * Descripton: */ #include <iostream> #include <string> #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 << r[0][0] * r[1][0] + r[0][1] * r[1][1] << ' ' << f(r[0][0]) + f(r[0][1]) + f(r[1][0]) + f(r[1][1]) + s.length() << endl; return 0; }
总结:Orz帆神AK,E题涉及逆元,回头补上~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。