CodeforcesRound#201(Div.2)ABC水题3道

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#201(Div.2)ABC水题3道，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3236字，纯文字阅读大概需要5分钟。

内容图文

这场的题目也很水，但是我竟然在第二题浪费了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;
}

定义一个全排列上，如果该位置上的数和序号一样为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;
}

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 举报，一经查实，本站将立刻删除。

内容手机端