Home > Database > Mysql Tutorial > body text

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

WBOY
Release: 2016-06-07 15:25:14
Original
1100 people have browsed it

这场的题目也很水,但是我竟然在第二题浪费了5次提交,罚时严重啊T T 果然还是太水了,姑且写个题解。。。 A - Difference Row 手速题,我还蛋疼把最大和最小提取出来重新排序了。。。 其实只要全部排序,让最大和最小位置调换下就行了。 复杂度为sort的O(nl

这场的题目也很水,但是我竟然在第二题浪费了5次提交,罚时严重啊T T

果然还是太水了,姑且写个题解。。。

A - Difference Row

手速题,我还蛋疼把最大值和最小值提取出来重新排序了。。。

其实只要全部排序,让最大和最小位置调换下就行了。

复杂度为sort的O(nlogn)

代码:

/*
*  Author:      illuz <iilluzen>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        a.cpp
*  Create Date: 2013-09-20 23:32:37
*  Descripton:  a 
*/

#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i  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;
}

</algorithm></cstdio></iilluzen>
Copy after login

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>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        b.cpp
*  Create Date: 2013-09-20 23:43:46
*  Descripton:  b 
*/

#include <cstdio>
#define rep(i, n) for (int i = 0; i  0 ? 1 : 0;
	rep(i, r)
		if (a[a[rec[i]]] == rec[i]) {
			cg = 2;
			break;
		}
	printf("%d\n", cnt + cg);
	return 0;
}

</cstdio></iilluzen>
Copy after login

C - Alice and Bob

A 和 B玩游戏,A每次先手,游戏规则:在一个集合中找到两个数,他们的差不在集合中,然后添加到集合里。如果找不到那个人就是输了。

模拟肯定超时的。。。

于是在纸上模拟了一遍样例和想出来的一个简单样例,发现其实最后集合里就只剩1-max了。

后来又想到如果都是10的倍数就不一样了。

然后题目就出来了,求出全部值的gcd,最后游戏的操作数就是max/gcd - n,然后就知道谁赢了。

代码:

/*
*  Author:      illuz <iilluzen>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        c.cpp
*  Create Date: 2013-09-21 00:41:09
*  Descripton:  gcd 
*/

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i > 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;
}

</algorithm></iostream></cstdio></iilluzen>
Copy after login


Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template