CodeforcesRound#201(Div.2)ABC水题3道
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#201(Div.2)ABC水题3道,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3236字,纯文字阅读大概需要5分钟。
内容图文
![CodeforcesRound#201(Div.2)ABC水题3道](/upload/InfoBanner/zyjiaocheng/565/15f3651923e14c2bbe9dc144d345f685.jpg)
这场的题目也很水,但是我竟然在第二题浪费了5次提交,罚时严重啊T T 果然还是太水了,姑且写个题解。。。 A - Difference Row 手速题,我还蛋疼把最大和最小提取出来重新排序了。。。 其实只要全部排序,让最大和最小位置调换下就行了。 复杂度为sort的O(nl
这场的题目也很水,但是我竟然在第二题浪费了5次提交,罚时严重啊T T
果然还是太水了,姑且写个题解。。。
A - Difference Row
手速题,我还蛋疼把最大值和最小值提取出来重新排序了。。。
其实只要全部排序,让最大和最小位置调换下就行了。
复杂度为sort的O(nlogn)
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: a.cpp * Create Date: 2013-09-20 23:32:37 * Descripton: a */ #include#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) const int MAXN = 1001; int n, ra, ri, a[MAXN]; int Max = -1000, Min = 1001; int main() { scanf("%d", &n); rep(i, n) { scanf("%d", &a[i]); if (Max < a[i]) { Max = a[i]; ra = i; } if (Min > a[i]) { Min = a[i]; ri = i; } } a[ra] = 1001; a[ri] = 1001; sort(a, a + n); if (n == 2) printf("%d %d\n", Max, Min); else { printf("%d", Max); rep(i, n - 2) printf(" %d", a[i]); printf(" %d\n", Min); } return 0; }
B - Fixed Points
定义一个全排列上,如果该位置上的数和序号一样为fixed point,比如0,1,2就有3个,0,2,1就只有1个了。(这个序列一定是排列)
给出一个序列,最多交换一次任意两个数,求交换后fixed point最多多少。
如果达到上限就不用交换了。
否则,我们可以发现,如果一个数是fixed point,那它就没有必要交换了,因为这样不会产生更好的结果,我们只要交换位置不对的数。
如果直接枚举不对的数肯定会超时。
位置不对的数,直接找它位置上的数对应的位置,那个位置肯定也不对,和它交换能够得到1或2的fixed point增量。
于是遍历不对的数,尝试和对应的位置交换,如果交换后增量为2就可以直接退出了,否则增量为1。
复杂度为O(n)。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: b.cpp * Create Date: 2013-09-20 23:43:46 * Descripton: b */ #include#define rep(i, n) for (int i = 0; i < (n); i++) const int MAXN = 100100; int a[MAXN], n, cnt; int rec[MAXN], r; int main() { scanf("%d", &n); rep(i, n) { scanf("%d", &a[i]); if (a[i] == i) cnt++; else rec[r++] = i; } int cg = r > 0 ? 1 : 0; rep(i, r) if (a[a[rec[i]]] == rec[i]) { cg = 2; break; } printf("%d\n", cnt + cg); return 0; }
C - Alice and Bob
A 和 B玩游戏,A每次先手,游戏规则:在一个集合中找到两个数,他们的差不在集合中,然后添加到集合里。如果找不到那个人就是输了。
模拟肯定超时的。。。
于是在纸上模拟了一遍样例和想出来的一个简单样例,发现其实最后集合里就只剩1-max了。
后来又想到如果都是10的倍数就不一样了。
然后题目就出来了,求出全部值的gcd,最后游戏的操作数就是max/gcd - n,然后就知道谁赢了。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: c.cpp * Create Date: 2013-09-21 00:41:09 * Descripton: gcd */ #include#include #include using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) typedef long long LL; LL g, t; LL gcd(LL a, LL b) { if(b == 0) return a; return gcd(b, a % b); } int main() { int n; LL Max = 0; cin >> n; rep(i, n) { cin >> t; if (i) g = gcd(g, t); else g = t; Max = max(Max, t); } LL cnt = Max / g - n; if (cnt % 2 == 0) printf("Bob\n"); else printf("Alice\n"); return 0; }
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#201(Div.2)ABC水题3道全部内容,希望文章能够帮你解决CodeforcesRound#201(Div.2)ABC水题3道所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。