Codeforces

Codeforces Round #403 (Div. 2)

以下是题解. 6/6 比赛时只完成了前三道. # A. Andryusha and Socks n双袜子, 每次取出一只, 如果桌子上没有和它配对的, 就把它放到桌子上, 否则将这双袜子收进衣橱. 问桌上最多同时有多少只袜子. (1≤n≤10^5)

模拟即可, 然而第一次提交时只读入了n个数......

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;

const int N = 1e5;
bool f[N+1];

int main()
{
	int n, cnt = 0, mx = 0;
	cin >> n;
	Rep (i, 0, 2*n) {
		int x;
		cin >> x;
		if (f[x]) {
			f[x] = false;
			--cnt;
		} else {
			f[x] = true;
			++cnt;
		}
		mx = max(mx, cnt);
	}
	cout << mx << endl;
	return 0;
}

B. The Meeting Place Cannot Be Changed

n个朋友在一个数轴位于1~10^9的某些整点上, 每人有自己的最大速率, 可以往任意方向走. 问它们在某点集合的最短时间 (实数范围) 是多少. (2≤n≤60000)

看到答案是实数, 我想是不是得二分. 这是可行的. 每个人的移动范围是[x-vt, x+vt], 如果这些线段有交, 则最短时间不超过t. 单调性由生活情景可得......

WA了两发, 都是输出格式的锅TAT 第一次是cout保留的位数时多时少, 第二次是CF不支持printf输出long double.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
const int N = 6e4;
typedef long double ld;

int n, x[N], v[N];

inline bool check(ld t)
{
	ld l = x[0] - v[0]*t, r = x[0] + v[0]*t;
	Rep (i, 1, n) {
		l = max(l, x[i] - v[i]*t);
		r = min(r, x[i] + v[i]*t);
		if (l-r > 1e-9)
			return false;
	}
	return true;
}

int main()
{
	cin >> n;
	Rep (i, 0, n)
		cin >> x[i];
	Rep (i, 0, n)
		cin >> v[i];

	ld l = 0, r = 1e9;
	while (r-l > 1e-7) {
		ld m = (l+r)/2;
		if (check(m))
			r = m;
		else
			l = m;
	}

	printf("%.7lf\n", (double)(l+r)/2);
	return 0;
}

C. Andryusha and Colored Balloons

给一棵树的结点染色, 要求若u,v相邻, v,w相邻, 则u,v,w三者不同色, 求最小的颜色数和一种方案. (3≤结点数≤2*10^5)

DFS, 设现在访问u, 父亲是p, u,p的颜色已确定. 贪心地给u的儿子染色 (颜色编号尽量小, 又不与u,p或它的兄弟相同), 递归下去. 时间复杂度. 暂时不知道如何证明.

UPDATE 2017.3.8 官方教程学到证明: 设D为最大度数, 则解不会优于(D+1). 可以看出本算法不会使用大于(D+1)的编号: 根至多有D个儿子, 一种颜色禁用; 其他结点至多有(D-1)个儿子, 两种颜色禁用. 
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define pb push_back
using namespace std;
const int N = 2e5;

vector<int> adj[N+1];
int c[N+1];

void dfs(int u, int p)
{
	int j = 1;
	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (v != p) {
			while (j == c[u] || j == c[p])
				++j;
			c[v] = j++;
			dfs(v, u);
		}
	}
}

int main()
{
	int n;
	cin >> n;
	Rep (i, 0, n-1) {
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	c[1] = 1;
	dfs(1, 0);

	int k = 0;
	For (i, 1, n)
		k = max(k, c[i]);

	cout << k << endl;
	For (i, 1, n)
		cout << c[i] << " ";
	cout << endl;

	return 0;
}
# D. Innokenty and a Football League 给一些球队的名称确定缩写, 有plan A和plan B. 如果某球队x选择B, 则不允许其他球队y选择和A(x)同名的A(y) (如果A(x)=B(y), B(y)还是可以选择的). 问是否有解, 如果有, 输出一组. (1≤n≤1000)
把上面的奇怪限制翻译一下: 如果一些球队的plan A相同, 它们都只能选择plan B.
写了一个自己以为能过的暴力, 又加了一些自己以为有用的优化, T了两发, GG. 隐约觉得这个模型有点熟悉, 2-SAT?
看了杜教的代码, 这种调整以前的选择的思想怎么似曾相识呢......不就是匈牙利嘛......
把球队和名称各作为一个集合, 则本题就是二分图匹配. 边数是的, 直接跑匈牙利时间复杂度.
2-SAT也是可以的, 把每个球队的选择作为点, 向有plan和它同名的其他球队的另一个plan连边.
贪心也是可以的 (来自yp同学), 先确定那些只有一种选择的球队, 对于其他的, 迭代, 同样每次寻找只有一种选择的球队. 如果目前所有球队都有两种选择, 现在就随便挑一个球队选A, 因为 (根据题目中的奇怪限制首先对一些球队做出选择后) A是两两不同的.

UPDATE 2017.3.8 官方教程类似于2-SAT和yp同学的贪心: A相等的球队, 都只能选择B. 如果所有球队的A不等, 或者现在没有A(k)=B(i), 那么得到答案. 否则, 用类BFS过程进行调整. (一个仔细实现的) 时空复杂度.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
const int N = 1000;

int m = 0, X[2*N], ans[N];
map<string, int> id, cnt;
string s[N][2], str[2*N];
vector<int> adj[N];
bool vis[N];

bool dfs(int u)
{
	vis[u] = true;
	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (X[v] == -1 || !vis[X[v]] && dfs(X[v])) {
			X[v] = u;
			return true;
		}
	}
	return false;
}

inline int ID(const string& s)
{
	if (!id.count(s)) {
		id[s] = m;
		str[m] = s;
		return m++;
	}
	return id[s];
}

int main()
{
	int n;
	cin >> n;
	Rep (i, 0, n) {
		string a, b;
		cin >> a >> b;
		s[i][0] = a.substr(0, 3);
		s[i][1] = a.substr(0, 2) + b[0];
		++cnt[s[i][0]];
	}

	Rep (i, 0, n) {
		if (cnt[s[i][0]] == 1)
			adj[i].push_back(ID(s[i][0]));
		adj[i].push_back(ID(s[i][1]));
	}

	fill_n(X, m, -1);
	
	Rep (i, 0, n) {
		fill_n(vis, i, false);
		if (!dfs(i)) {
			cout << "NO" << endl;
			return 0;
		}
	}

	cout << "YES" << endl;
	Rep (i, 0, m)
		ans[X[i]] = i;
	Rep (i, 0, n)
		cout << str[ans[i]] << endl;
	
	return 0;
}
# E. Underground Lab 用k条路径覆盖n个点m条边的无向图的每个顶点, 点可被多次覆盖, 要求每条路径中点的数目不超过, 至少为1. 求一种方案, 保证图连通且有解. (1≤n≤2*10^5, n-1≤m≤2*10^5, 1≤k≤n)
保证有解是这个问题本身总是有解, 还是数据保证这一点呢? 先看看它的生成树的情况. 2n暴露了一切. 树的欧拉环游经过每条树边恰好两次, 序列中共有(2n-1)个点. 分成k段即可.
cout不关闭流同步会TLE. 
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
const int N = 2e5;

vector<int> adj[N+1];
bool vis[N+1];
int tot, seq[2*N];

void dfs(int u)
{
	vis[u] = true;
	seq[tot++] = u;
	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (!vis[v]) {
			dfs(v);
			seq[tot++] = u;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	Rep (i, 0, m) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs(1);
	int d = (2*n+k-1)/k, j = 0;
	Rep (i, 0, k) {
		if (j == tot)
			cout << "1 1";
		else {
			int t = min(d, tot-j);
			cout << t << " ";
			Rep (l, 0, t)
				cout << seq[j++] << " ";
		}
		cout << endl;
	}
	return 0;
}
# F. Axel and Marston in Bitland n个点m条边的有向图, 每条边上标有0或1. 从点1出发, 走这样生成的无穷序列: 0 0 1 01 10 0110 1001 01101001 10010110 ......
求最长路径的长度. 如果该长度大于10^18, 输出-1. (1≤n≤500, 0≤m≤2n^2, 允许重边自环, 但是不存在起点, 终点, 标号均相同的两条边)
很像有限状态自动机.
序列的构造方式, 又使人联想到倍增算法. 而背景是有向图, 使人想到矩阵乘法.
设f[t][i][j][k]为长度在(2^(i-1), 2^i]的, 以t开头的, j->k的最长路径长度, 容易递推计算 (类似于矩阵乘法). 问题的答案也可以直接得到. 但是时间复杂度, 5s不允许.
我猜测要压位 (后来发现题目中有Bitland, 是不是在提示这一点呢? ), 但是不知道怎么搞 (如果只存0-1, 怎么统计答案呢? ) 学习了一下dls的做法. 修改上述定义, 设f[t][i][j][k]为是否存在以t开头, 走2^i, j到k的路径. 计算出f之后, 贪心地从高位往低位确定答案: 倒序枚举i, 维护集合S表示目前所有可行的起点, t表示路径开头的数字.
求邻接矩阵的积, 压位后可以这样做: 设r[i]为第i行的bitset, c[j]为第j行的bitset, r[i], c[j]按位与, P[i][j]=1当且仅当结果非0. 但是有点麻烦, 而且dls的代码中并没有发现类似的步骤 - 全是按位或.
看来我的思路没放开啊......对于路径i->k->j, 为什么一定要枚举i, j, 而不学学Floyd呢? 如果i->k存在长为l的路径, 则从k出发长度为l的路径的终点, 都是从i出发长为2l的路径的终点.

UPDATE 2017.3.8 这个就是布尔矩阵乘法.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;
const int N = 500;
bitset<N> f[2][61][N], s;

int main()
{
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Rep (i, 0, m) {
		int u, v, t;
		cin >> u >> v >> t;
		--u;
		--v;
		f[t][0][u][v] = 1;
	}
	For (i, 1, 60) {
		Rep (u, 0, n) {
			Rep (v, 0, n) {
				if (f[0][i-1][u][v])
					f[0][i][u] |= f[1][i-1][v];
				if (f[1][i-1][u][v])
					f[1][i][u] |= f[0][i-1][v];
			}
		}
	}
	
	ll ans = 0;
	int t = 0;
	s[0] = 1;
	Down (i, 60, 0) {
		bitset<N> tmp;
		Rep (u, 0, n)
			if (s[u])
				tmp |= f[t][i][u];
		if (tmp.any()) {
			ans |= 1LL<<i;
			t ^= 1;
			s = tmp;
		}
	}

	cout << (ans > (ll)1e18 ? -1 : ans) << endl;
	
	return 0;
}

本次比赛有四个问题: 1. 太想快速通过A题先发制人, 然而心急吃不了热豆腐, 竞速也不是我擅长的 (看懂英文题面都需要3min). 2. 对于不熟悉的东西, 要谨慎使用, 切忌想当然. 3. 理论上复杂度不对的算法谨慎使用. 4. 做题不一定得按字典序 (不过我读一次题的开销有点大, 需要权衡 -_-b).

yp同学变紫啦......我要努力 QAQ