CCPC-2020 秦皇岛站记录

总第109，铜牌第37……CCPC首铜，XCPC第二块铜牌……

第一场CCPC没能旅游成，呜呜呜～～～

A. A Greeting from Qinhuangdao

签到。

#include<bits/stdc++.h>

using namespace std;

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

int main(){
	int T, CASES = 0; for(scanf("%d", &T); T; T--){
		int r, b; scanf("%d%d", &r, &b);
		int up = r * (r - 1) / 2;
		int dn = (r + b) * (r + b - 1) / 2;
		int g = gcd(up, dn);
		up /= g, dn /= g;
		printf("Case #%d: %d/%d\n", ++CASES, up, dn);
	}
	return 0;
}

---

C. Cameraman

这是一道假题……然而我比赛时没想到那一层，顺理成章地认为 Bob 就在 Alex 的位置，于是沿着出题人的思路做了（还写了一堆 bug……最后时刻调出来的）

---

E. Exam Results

把所有分数从小到大排序，枚举最大分，问题可以转化成求区间内不重复的数的数量，拿一个 cnt 数组计数即可。然而，最开始我们忽略了一点，就是枚举的这个最大分之前，每一个数都至少得出现一次，否则是不能计入答案的！因为这个送了 2 发罚时，唉。。。

#include<bits/stdc++.h>

using namespace std;

const int N = 400005;

int n, p;

struct Node{
	int id, val;
	bool operator < (const Node &A) const{
		return val < A.val;
	}
}a[N];
int sum = 0, presum = 0;
int cnt[N], precnt[N];

int main(){
	int T, CASES = 0; for(scanf("%d", &T); T; T--){
		scanf("%d%d", &n, &p);
		sum = presum = 0;
		for(int i = 1; i <= n; i++)	cnt[i] = precnt[i] = 0;
		for(int i = 1; i <= n; i++){
			int u, v; scanf("%d%d", &u, &v);
			a[i*2-1] = (Node){i, u};
			a[i*2] = (Node){i, v};
		}
		sort(a+1, a+n*2+1);
		int ans = 0;
		for(int i = 1, j = 1; i <= n * 2; i++){
			if(cnt[a[i].id] == 0)	sum++;
			cnt[a[i].id]++;
			if(precnt[a[i].id] == 0)	presum++;
			precnt[a[i].id]++;
			while(a[j].val * 100ll < a[i].val * 1ll * p){
				cnt[a[j].id]--;
				if(cnt[a[j].id] == 0)	sum--;
				j++;
			}
			if(presum == n)	ans = max(ans, sum);
		}
		printf("Case #%d: %d\n", ++CASES, ans);
	}
	return 0;
}

---

F. Friendly Group

容易发现，对于一个连通分量，要么不选它（贡献为 $0$），要么把里面的点全选上（贡献为边数减点数）。

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
#define pb(x) emplace_back(x)

const int N = 300005;

int n, m, deg[N];
vi edge[N];
bool vis[N];

int degSum, verSum;
void dfs(int x){
	degSum += deg[x], verSum++;
	vis[x] = true;
	for(auto &to : edge[x])
		if(!vis[to])	dfs(to);
}

int main(){
	int T, CASES = 0; for(scanf("%d", &T); T; T--){
		scanf("%d%d", &n, &m);
		int ans = 0;
		for(int i = 1; i <= n; i++){
			edge[i].clear();
			vis[i] = false;
			deg[i] = 0;
		}
		for(int i = 1; i <= m; i++){
			int u, v; scanf("%d%d", &u, &v);
			edge[u].pb(v), edge[v].pb(u);
			deg[u]++, deg[v]++;
		}
		for(int i = 1; i <= n; i++){
			if(vis[i])	continue;
			degSum = verSum = 0;
			dfs(i);
			ans += max(0, degSum / 2 - verSum);
		}
		printf("Case #%d: %d\n", ++CASES, ans);
	}
	return 0;
}

---

G. Good Number

喜闻乐见的推式子时间：

$$\sum_{i=1}^n\left[\left\lfloor \sqrt[k]{i}\right\rfloor\mid i\right]=\sum_{d=1}^\sqrt[k]{n} \sum_{i=d^k}^{\min(n,(d+1)^k-1)}[d\mid i]=\sum_{d=1}^{\sqrt[k]{n}}\left\lfloor\frac{\min(n,(d+1)^k-1)}{d}\right\rfloor-\left\lfloor\frac{d^k-1}{d}\right\rfloor$$

所以特判掉 $k=1$ 后，枚举 $d$ 即可。

然而因为大指数的快速幂 WA 了很久，后来急中生智才想到取对数判断……

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n, k;

inline LL fpow(LL bs, LL idx){
	LL res = 1;
	while(idx){
		if(idx & 1)	res *= bs;
		bs *= bs;
		idx >>= 1;
	}
	return res;
}

int main(){
	int T, CASES = 0; for(scanf("%d", &T); T; T--){
		scanf("%lld%lld", &n, &k);
		printf("Case #%d: ", ++CASES);
		if(k == 1){
			printf("%lld\n", n);
			continue;
		}
		int ans = 0;
		for(int d = 1; k * log(d) <= log(n); d++){
			LL t = fpow(d + 1, k) - 1;
			if(k * log(d+1) > log(n+1))	t = n;
			ans += t / d - (fpow(d, k) - 1) / d;
		}
		printf("%d\n", ans);
	}
	return 0;
}

---

K. Kingdom’s Power

一个比赛时没发现的贪心性质：如果一个军队遍历了整颗树，那它一定是按照子树高度从小到大遍历的，于是对子树排序后，考虑每一个点的军队来源——要么是从根节点直接下来的，要么是从前一颗子树的最深处上来的。所以比较两种方案的代价，选小者即可。

隔壁大一队伍用了一个树形 $\text{dp}$ 过的这道题。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
#define pb(x) emplace_back(x)
#define mp(x, y) make_pair(x, y)

const int N = 1000005;

int n, ans;
vector<int> edge[N];

int dep[N], h[N];
bool ex[N];
void dfs(int x, int f, int depth){
	dep[x] = depth;
	for(auto &to : edge[x]){
		if(to == f)	continue;
		dfs(to, x, depth + 1);
		h[x] = max(h[x], h[to] + 1);
	}
}
void dfs(int x, int f){
	int pre = -1;
	for(auto &to : edge[x]){
		if(to == f)	continue;
		if(pre == -1 || h[pre] + 2 > dep[to]){
			// get an army from root
			if(ex[x])	ans++, ex[x] = false;
			else	ans += dep[to];
		}
		else // get an army from previous subtree
			ans += h[pre] + 2;
		ex[to] = true;
		pre = to;
		dfs(to, x);
	}
}

int main(){
	int T, CASES = 0; for(scanf("%d", &T); T; T--){
		scanf("%d", &n);
		ans = 0;
		for(int i = 1; i <= n; i++){
			dep[i] = h[i] = 0;
			ex[i] = false;
			edge[i].clear();
		}
		for(int i = 2; i <= n; i++){
			int f; scanf("%d", &f);
			edge[f].pb(i), edge[i].pb(f);
		}
		dfs(1, 0, 0);
		for(int i = 1; i <= n; i++)
			sort(edge[i].begin(), edge[i].end(), [&](int a, int b){ return h[a] < h[b]; });
		dfs(1, 0);
		printf("Case #%d: %d\n", ++CASES, ans);
	}
	return 0;
}