Codeforces Round #397 (Div. 1 + Div. 2 combined)

上个星期打的, 做出了4道题, 由于WA几发, 并且最后10分钟才提交C还交错代码一次, Rank 908, +48 rating. 以下是A~D的题解.

A. Neverending competitions

给出某兄乘坐的n班飞机, 判断他是在家还是在外地. 此兄只乘坐两种航线: 从家到某地, 从某地回家.

头脑清醒的人会判断n的奇偶性, 头脑不清醒的人会用string+set搞半天, 写完之后发现可以判断n的奇偶性......

忧郁, 不贴代码了 QAQ

B. Code obfuscation

某兄决定将他的代码混淆: 用a替换第一个标识符, 用b替换后面第一个未被替换的标识符, 以此类推. 保证标识符不超过26种. 给一个字符串S (1 ≤ |S| ≤ 500), 问S能否是该兄混淆某份代码得到的结果.

S的首字母必须是a. 如果出现c, b必须在它之前出现过; 如果出现d, c必须在它之前出现过. 反过来, 对于任何一个满足此规律的字符串, 我们都能构造出一份可能的混淆前的代码 (比如它自己).

开一个布尔数组, 边扫边判断即可.

#include <iostream>
#include <string>
using namespace std;
bool f[27];
int main()
{
	string s;
	cin >> s;
	f[0] = true;
	for (int i = 0; i < s.size(); ++i)
		if (!f[s[i]-'a']) {
			cout << "NO" << endl;
			return 0;
		} else {
			f[s[i]-'a'+1] = true;
		}
	cout << "YES" << endl;
	return 0;
}

C. Table Tennis Game 2

两人打乒乓球, 每盘包含许多轮, 赢得此轮者获得1分, 一个人获得k分后赢得此盘, 这一盘结束, 得分清零. 甲总共获得a分, 乙总共获得b分. 给出k, a, b(1≤k≤10^9, 0≤a,b≤10^9, a+b<0), 已知它们结束了最后一盘, 问最多打了多少盘, 或者判断这种情形不可能出现.

一开始看错了, 以为是最少, 虽然过了一会儿修正了, 但是一时没想出来, 就先去搞D.

每盘要不甲获得k分, 要不乙获得k分. 不妨假设前面全是甲赢, 后面全是乙赢.

先考虑a, b ≤ k的情形. 甲最多赢盘, 乙最多赢盘. 这是可以达成的. 只需将甲多出来的分任意分配到后面, 乙多出来的分任意分配到前面, 由于两人都至少赢了一盘, 这样的分配总是可行的.

如果a, b < k, 则无解.

如果两者有个得分小于k, 不妨设是甲, 那么乙必须全赢, 他的得分必须是k的正整数倍, 反之无解.

#include <iostream>
using namespace std;
int main()
{
	int k, a, b;
	cin >> k >> a >> b;
	if (a < k && b < k || a < k && b % k != 0 || b < k && a % k != 0)
		cout << "-1" << endl;
	else
		cout << a/k + b/k << endl;
	return 0;
}

D. Artsem and Saunders

记, 给一个函数, 寻找一个正整数m和两个函数: , , 满足, , 任意输出一组解即可, 或报告无解. (1≤n≤10^5, 1≤m≤10^6, 输入保证如果有解, 则存在一个满足m的限制的解)

3个小时的比赛大多数时间在搞这一题. 其实我是很虚的......

在外面套一个, 得, 结合(2), 知, 这说明, 的值域是的不动点的子集.

记为的不动点的集合. 再观察, 发现, 于是.

推测是不动点的数目, 是的一个排列到不动点的映射. 证明: 如果, 则, , 所以是一个一一映射.

不妨给中元素从1到编号, 令=编号为的不动点, 由知是不动点到其编号的映射. 然而对于某些数还是没有定义的. 比赛时没想清楚, 就直接结合来了个二分搜索, 由于漏判了一些无解的情形, WA两发. 事实上, 根据定义和, =编号为的不动点, 也就是说, 是的编号. 对于不动点, 是到自己编号的映射, 也是到自己编号的映射.

整理一下思路: 有解当且仅当. . =编号为的不动点, =的编号. 两个条件用人话讲出来: 对于1~m中的某个数x, (f(编号为x的不动点)=编号为x的不动点)的编号是x; 对于1~n中的某个数x, 编号为(f(x)的编号)的不动点是f(x).

实现一: 从小到大枚举, 如果还没编号, 就给它编号, 设编为, 则, .

实现二: 从小到大给的不动点编号, 第个不动点为, 则. 对二分查找, 寻找, 令. 不如实现一简洁.

一开始只是胡乱地变换条件等式, 没什么方向, 做出一些猜想, 比如m=n, 或者g, h中的一个是随意指定的......一个有用的联想: 波哥讲不动点, 印给我们的资料里有类似的函数复合, 得出某种奇妙的结论, 还告诉我们这个结论很重要. 这样的有趣构造题, 还是得挖掘性质. 可以考虑一下满足什么条件才有解.

以下代码最后一个检查循环是冗余的.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5;
int f[MAX_N+1], h[MAX_N+1], g[MAX_N+1];
int main()
{
	int n, m = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> f[i];
		if (f[i] == i)
			h[++m] = i;
	}
	if (m == 0) {
		cout << "-1" << endl;
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		int x = lower_bound(h+1, h+m+1, f[i]) - h;
		if (x > m || h[x] != f[i]) {
			cout << "-1" << endl;
			return 0;
		}
		g[i] = x;
	}
	for (int i = 1; i <= m; ++i)
		if (g[h[i]] != i) {
			cout << "-1" << endl;
			return 0;
		}
	cout << m << endl;
	for (int i = 1; i <= n; ++i)
		cout << g[i] << " ";
	cout << endl;
	for (int i = 1; i <= m; ++i)
		cout << h[i] << " ";
	cout << endl;
	return 0;
}