2017-03-19

Codeforces Round #405 (Div. 2, based on VK Cup 2017 Round 1)

题解: 5/5 试图理解Div.1的D题, fail...算上这一题应该是: 5/6 # A. Bear and Big Brother 小熊, 大熊的初始体重分别为a, b. 每年小熊的体重变为原来的3倍, 每年大熊的体重变为原来的2倍, 问多少年后小熊的体重严格大于大熊. (1≤a≤b≤10)

模拟即可, 经过实验, 循环次数很少.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
	ll a, b;
	cin >> a >> b;
	ll n = 0;
	while (a <= b) {
		a *= 3;
		b *= 2;
		++n;
	}
	cout << n << endl;
	return 0;
}

B. Bear and Friendship Condition

a是b的朋友当且仅当b是a的朋友. 每个人不能是自己的朋友. 给出n个人间m对朋友关系, 问是否满足: a是b的朋友, b是c的朋友 => a是c的朋友. 每对朋友关系在输入中不会出现两次. (3≤n≤150000, 0≤m≤min(150000, n(n-1)/2), 保证输入合法)

画图, 发现按照题面所描述的性质, 一个连通块变成了完全图. 证明: 设存在路径. 和有边, 和有边 => 和有边 () 于是和有边. DFS, 验证每个连通块内结点度数之和是否为等于(点数-1)*点数/2, 因为题目保证不存在重边, 且不考虑自环.

#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)

using namespace std;
const int N = 150000;
typedef long long ll;
vector<int> adj[N + 1];
bool vis[N + 1];
ll cnt, num;

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

int main()
{
	int n, m;
	cin >> n >> m;
	Rep (i, 0, m) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	For (i, 1, n)
		if (!vis[i]) {
			num = cnt = 0;
			dfs(i);
			if (cnt != (ll)num*(num-1)) {
				puts("NO");
				return 0;
			}
		}
	puts("YES");
	return 0;
}

C. Bear and Different Names

下标从1开始. 一个长度为n的字符串序列s, 一个大于1的整数k. 已知s[i..i+k)内是否存在两个相等的字符串 (i=1,...,n-k+1) (记为y[i]), 构造一个满足题意的序列. 可以证明总是存在解. (2≤k≤n≤50) 方便起见等价改动了一下描述.

出题人良心啊......误导大众可以改成 "无解输出'IMPOSSIBLE' (不含引号)".

手动模拟, 发现可以从左往右依次构造. 以下用数代替字符串. 循环不变式: s[i, i+k-1)两两不等. 如果y[i]=true, 那么令s[i+k-1] = s[i], 否则, 令s[i+k-1] = s[i+k-2] + 1; 这样不但满足输入的限制, 还保证s[i+1, i+k)两两不等, 下一次循环开始的时候假设为真. 初始化, 令s[i]=i (i=1,...,k-1).

比赛的时候我的初始化稍微麻烦了些. 找第一个y[i]=false, 前面的都赋为1.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define pb push_back
using namespace std;
const int N = 50;
vector<string> name;
int id[N], cnt;
string s[N];

int main()
{
	Rep (i, 0, 26) {
		char t1[2] = {char('A' + i), 0}, t2[3] = {char('A' + i), 'x', 0};
		name.pb(t1);
		name.pb(t2);
	}
	int n, k;
	cin >> n >> k;
	Rep (i, 0, n-k+1)
		cin >> s[i];
	int fst = n-k+1;
	Rep (i, 0, n-k+1) {
		id[i] = cnt;
		if (s[i] == "YES") {
			fst = i;
			++cnt;
			Rep (j, 1, k)
				id[fst + j] = cnt++;
			break;
		}
	}
	Rep (i, fst+1, n-k+1)
		id[i+k-1] = s[i] == "YES" ? cnt++ : id[i];
	Rep (i, 0, n)
		cout << name[id[i]] << " ";
	cout << endl;
	return 0;
}

D. Bear and Tree Jumps

一棵无根树, 所有边权为1, 定义f(s,t)=ceil(s,t之间简单路径上边权之和/k), 求所有f(s,t) (s<t) 之和. (2≤n≤200000, 1≤k≤5)

做完前3题排名500+, 发现此时D题只有5个人过, E题没人过. 一方面, 说明这题有一定难度; 另一方面, 如果我把它切掉不就翻盘了吗? 然而1小时过去, 并没有搞出来.

比赛时yy的树上启发式合并是错的......虽然改做点分治就对了.

据说是树上DP, 事后yy了一个这样的做法:

首先, 取上整运算是分段的. 有这样一条链: 0 1 ... x, 则

, 于是,

同样的关系可以推广到树上. 转有根树. 递推计算

, 也就是说, 只考虑满足v在u的子树中的(u,v),

表示子树u中第j层的答案之和.

满足递推式:

考虑完子树, 再考虑外面的部分. 令

表示u的第j个祖先 (0≤j≤k), 那么, 外面的结点v要么和u有

, 要么

Missing \left or extra \rightv \in V - subtree(fa[u][k]) + \left\\{u\right\\}

. 令

, 容易用减法把它们通通求出来. 最后,

即为所求.

一直觉得树上DP子树外面的部分不好处理. 这个例子告诉我们可以利用减法.

时间复杂度

Editorial给了一个时间复杂度的算法, 很好写, 正常情况下很好想, 由于常数跑得比上面的做法快.

令k=1, 则本问题变成一个经典 (唉, 见识浅薄的人不知道啊) 问题: 求树上所有路径长度之和. 有一个很简单的做法: 考虑每一条边对答案的贡献. (比赛的时候想过这个问题, 但只想到DP, 还不知道子树外面怎么处理)

本题每条路径的长度要除以k, 再取上整. 也就是说, 要加上一个最小的非负数, 把长度凑成k的倍数, 再除以k. 不妨最后再做除法, 并把被除数拆成两部分: 原长之和, 按经典问题的做法来求; 用于凑倍数的非负数之和, DP.

设表示子树u中, 长度 mod k=j的路径数 (包含u到自己). 一开始令, 然后地统计lca(x,y)=u的路径(x,y)的答案. 每处理完一棵子树, 将其与合并. 注意防止乘法溢出.

代码中的变量可能和上面叙述中的不同.

做法一

#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)
#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif
#define pb push_back
using namespace std;
const int N = 200000, K = 5;
typedef long long ll;
int n, k, fa[N + 1][K + 1], sz[N + 1];
ll f[N + 1][K], g[N + 1];
vector<int> adj[N + 1], ord;

void dfs(int u, int p)
{
	fa[u][0] = u;
	For (i, 1, k) fa[u][i] = fa[p][i-1];

	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (v != p) {
			dfs(v, u);
			sz[u] += sz[v];
			Rep (j, 1, k) f[u][j] += f[v][j-1];
			f[u][0] += f[v][k-1];
		}
	}

	f[u][0] += sz[u]++;
	ord.pb(u);
}

int main()
{
	scanf("%d%d", &n, &k);
	Rep (i, 0, n-1) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1, 0);

	ll ans = 0;
	Down (i, n-1, 0) {
		int u = ord[i];
		g[u] = f[u][0];
		Rep (j, 1, k) {
			if (!fa[u][j]) break;
			g[u] += f[fa[u][j]][k-j] - f[fa[u][j-1]][k-j-1] + sz[fa[u][j]] - sz[fa[u][j-1]];
		}
		if (fa[u][k])
			g[u] += g[fa[u][k]] - f[fa[u][k-1]][k-1] + n - 2*sz[fa[u][k-1]];
		ans += g[u];
	}

	printf("%"LLFORMAT"d\n", ans/2);
	return 0;
}

做法二

#include <bits/stdc++.h>
#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)

using namespace std;
const int N = 200000, K = 5;
typedef long long ll;
int n, k, f[N + 1][K];
vector<int> adj[N + 1];
ll ans;

int dfs(int u, int p)
{
	int sz = 1;
	f[u][0] = 1;
	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (v != p) {
			sz += dfs(v, u);
			Rep (x, 0, k) Rep (y, 0, k) ans += (2*k-x-y-1) % k * (ll)f[u][x] * f[v][y];
			Rep (y, 0, k) f[u][(y+1) % k] += f[v][y];
		}
	}
	ans += (ll)sz * (n - sz);
	return sz;
}

int main()
{
	scanf("%d%d", &n, &k);
	Rep (i, 0, n-1) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 0);
	printf("%"LLFORMAT"d\n", ans / k);
	return 0;
}

# E. Bear and Company 一个长度为n的字符串, 一次操作可以交换相邻两个字母. 问最少多少次操作后, 不存在子串"VK". (1≤n≤75)

首先, 只存在三类字母: 'V', 'K', 其他 (记为'X').

不妨从左到右构造最终的字符串, 设使用前v个'V', 前k个'K', 前x个'X'构造前缀(v+k+x)的最小操作次数为dp[v][k][x][0/1], 最后一维标记末尾是否为'V'. 如果是, 则不能添加'K'. 转移的代价=前面未使用的字母的数量. 记录pos[ch][i]表示第i个ch在原串中的下标, 统计cnt[i][ch]表示原串前i个字符中有多少个ch, 则可做到

转移.

我觉得解法中最奥妙重重的是不妨从左到右构造最终的字符串. 想不到这点没法入手......暂时不知道怎么证明这样不妨的合理性, 虽然直观上是正确的.

#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)
using namespace std;
const int N = 75;
vector<int> pos[3];
int dp[N + 1][N + 1][N + 1][2], cnt[N + 1][3]; // V K X

template<typename T>
inline void upmin(T& x, T v) { x = min(x, v); }

inline int type(char c) { return c == 'V' ? 0 : 1 + (c != 'K'); }

inline int cost(int i, int j, int k, int x)
{
	int* t = cnt[x-1];
	return max(0, t[0]-i) + max(0, t[1]-j) + max(0, t[2]-k);
}

int main()
{
	int n;
	char s[N + 2];
	scanf("%d%s", &n, s + 1);
	For (i, 1, n) {
		Rep (j, 0, 3) cnt[i][j] = cnt[i-1][j];
		int t = type(s[i]);
		++cnt[i][t];
		pos[t].push_back(i);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0][0][1] = 0;
	int mxi = cnt[n][0], mxj = cnt[n][1], mxk = cnt[n][2];
	For (i, 0, mxi) For (j, 0, mxj) For (k, 0, mxk) {
		For (l, 0, 1) {
			int now = dp[i][j][k][l];
			if (i < mxi)
				upmin(dp[i+1][j][k][0], now + cost(i, j, k, pos[0][i]));
			if (l && j < mxj)
				upmin(dp[i][j+1][k][1], now + cost(i, j, k, pos[1][j]));
			if (k < mxk)
				upmin(dp[i][j][k+1][1], now + cost(i, j, k, pos[2][k]));
		}
	}
	printf("%d\n", min(dp[mxi][mxj][mxk][0], dp[mxi][mxj][mxk][1]));
	return 0;
}

收获: 想问题可以先从退化/特殊情形入手.