本文共 7335 字，大约阅读时间需要 24 分钟。

2019CCPC江西省赛（重现赛）

第一次组队（和队内dalao：hzf）参加比赛，这次比赛使用的是我的笔电，但因为我来的比较晚，没有提前磨合：比如我的64键位键盘导致hzf突然上手不习惯。

Solved	A	B	C	D	E	F	G	H	I	J	K
4 / 11	Ø	O	Ø	O	Ø	O	-	-	-	O	Ø

• O 在比赛中通过
• Ø 赛后通过
• ! 尝试了但是失败了
• - 没有尝试

A - Wave

题目链接：

题意：

找一个最长的'wave'，要求满足以下限制：

• 序列长度大于等于\(2\)
• 所有奇数位置上的数相同
• 所有偶数位置上的数相同
• 奇数位置和偶数位置的数不同

思路：

因为值域只有\([1,100]\) ，那么暴力枚举奇数位置上的数和偶数位置上的数即可。时间复杂度\(O(nc)\)

#include
   
    using namespace std;const int N = 100010;int n, c, a[N];int dp[N][110], nx[110];int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	cin >> n >> c;	for (int i = 1; i <= n; ++i)cin >> a[i];	for (int i = 1; i <= c; ++i)nx[i] = n + 1, dp[n + 1][i] = n + 1;	for (int i = n; i >= 0; --i) {		for (int j = 1; j <= c; ++j)			dp[i][j] = nx[j];		if (i)nx[a[i]] = i;	}	int res = 0;    for (int i = 1; i <= c; ++i)		for (int j = 1; j <= c; ++j) {			if (i != j) {				int tmp = 0, it = 0;				while (it <= n) {					it = dp[it][i];					if (it <= n) {						tmp += 1;					}					else break;					it = dp[it][j];					if (it <= n) {						tmp += 1;					}					else break;				}				if (tmp > 1) {					res = max(res, tmp);				}			}		}	cout << res << endl;}
   

B - String

题目链接：

题意：

给出一个字符串，只包含'a', 'v', 'i', 'n', 要求从中等概率可重复的取出四个字符，问恰好是 'avin'的概率是多少。

思路：

一开始理解错了题意导致WA 2发，最后重新梳理一下：根据乘法原理计算即可。

有一个坑点：

得到的分数需要最简化（求最小公约数）

#include
   
    using namespace std;typedef long long ll;ll n, m;string s;ll gcd(ll a, ll b) {	return b == 0 ? a : gcd(b, a % b);}int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	while (cin >> n) {		cin >> s;		ll a[30] = { 0 }, cnt = 0;		for (int i = 0; i < n; ++i)a[s[i] - 'a']++;		cnt = a['a' - 'a'] * a['v' - 'a'] * a['i' - 'a'] * a['n' - 'a'];		ll sum = pow(n, 4);		if (cnt == 0) {			cout << "0/1" << endl;		}		else {			ll tmp = gcd(sum, cnt);			cout << cnt / tmp << "/" << sum / tmp << endl;		}	}}
   

C - Traffic

题目链接：

题意：

在一个十字路口，有\(n\)辆东西走向的车，他们会在\(a_i\) 时刻到达，有\(m\)辆南北走向的车，他们会在\(b_i\)时刻到达。问需要让\(m\)辆南北走向的车整体等待多少秒，使得他们的开始行动之后不会和东西走向的车相撞？

思路：

考虑\(a_i\)和\(b_i\) 只有 1000，那么等待时间不会超过1000，暴力枚举即可。

#include
   
    using namespace std;const int N = 5010;int a[N], b[N], n, m;bool f(int x) {	for (int i = 1; i <= m; ++i) 		if (a[b[i] + x]) 			return 0;	return 1;}int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	while (scanf("%d%d", &n, &m) != EOF) {		memset(a, 0, sizeof a);		for (int i = 1, x; i <= n; ++i) {			scanf("%d", &x);			a[x] = 1;		}		for (int i = 1; i <= m; ++i) scanf("%d", b + i);		for (int i = 0; i <= 2000; ++i) 			if (f(i)) {				cout << i << endl;				break;			}	}}
   

D - Budget

题目链接：

这道题理解错题目意思 然后一直想不通为啥就WA了

一开始队友和我都认为应该直接将三位小数进位，也就是处理1000。

其实是 将第三位小数位进位到前一位 所增加的数之和(可以为负

#include
   
    using namespace std;int main() {    int n, a, c;    char b;    while (cin>>n) {        double sum = 0;        for (int i = 0; i < n; i++) {            scanf("%d%c%d", &a, &b, &c);            //cin >> a >> c >> b;            c = c % 10;            if (c <= 4) sum -= 0.001 * c;            else sum += 0.001 * (10 - c);        }        printf("%.3lf\n", sum);    }}
   

E - Worker

题目链接：

题意：

有\(n\)个销售点，有\(m\)个销售员，每个销售员在第\(i\)个销售点会产生\(a_i (1 <= a_i <= 10)\)的订单，问如何分配销售员使得每个销售点产生的订单相同。

思路：

首先单个销售点的订单量肯定是所有销售点\(a_i\)的最小公倍数的倍数。那么判断\(m\)能否整除其最小公倍数即可，然后按比例分配。

#include 
   
    using namespace std;const int N = 1100;typedef long long ll;ll n, a[N], m, lcm;ll __gcd(ll a, ll b) {	return b == 0 ? a : __gcd(b, a % b);}void solve() {	ll sum = 0;	for (int i = 1; i <= n; ++i) {		sum += lcm / a[i];	}	if (m % sum) {//不能整除说明不能均匀分配，直接输出no即可		puts("No");		return;	}	ll cur = m / sum;	puts("Yes");	for (int i = 1; i <= n; ++i) printf("%lld%c", cur * (lcm / a[i]), " \n"[i == n]);}int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	while (cin >> n >> m) {		for (int i = 1; i <= n; ++i) cin >> a[i];		lcm = a[1];//最小公倍数		for (int i = 2; i <= n; ++i) 			lcm = lcm * a[i] / __gcd(lcm, 1ll * a[i]);		solve();	}}
   

F - Class

题目链接：

签到题

题意：

计算$a * b $

#include
   
    #define ms(a,b) memset(a,b);using namespace std;typedef long long ll;int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	ll x, y;	cin >> x >> y;	ll a = (x + y) / 2;	ll b = (x - y) / 2;	cout << a * b << endl;}
   

G - Packing

题目链接：

G题开始都是一些没接触和不熟练的知识点，就导致无法动手解题了。

补题中

H - Trap

题目链接：

I - Math

J - Cotree

题目链接：

题意：

有两棵树，一共有\(n\)个点，现在要求在两棵树中连一条边，使得他们变成一棵树，如何连边使下式最小：

思路：

我们可以单独考虑边的贡献，一条边的贡献是这条边两边的点数乘积。那么新加的边的贡献是固定的。我们考虑怎么减少已存在的边的贡献，其实我们可以感性的理解一下，我们最后选出的两个点相连，我们强制让它们成为他们各自树中的根，那么这么考虑：

• 令\(f[i]\)表示以\(i\)为根的子树中的边的贡献
  那么转移有：

• 令\(g[i]\)表示以\(i\)为根的非子树中的边的贡献
  那么转移有：

其中 \(S\) 代表另外一棵树的大小，最后那两部分主要是\(u→fa[u]\)那条边的贡献变了

刚好赛前看过类似的题，不过因为没有把握迟迟没提交，最后卡点交了一发，没想到直接AC了

#include 
   
    using namespace std;typedef long long ll;const int N = 100010;int n, S, T, fa[N], Size[N];vector 
    
     
      > G;ll f[N], g[N];void init() {	for (int i = 1; i <= n; ++i) fa[i] = -1;}void dfs(int u) {	Size[u] = 1, f[u] = 0;	for (auto v : G[u])		if (v != fa[u]) {			fa[v] = u; dfs(v);			Size[u] += Size[v];			f[u] += f[v];			f[u] += 1ll * Size[v] * (n - Size[v]);		}}ll dfs2(int u, int rt, int S) {	if (u != rt) {		g[u] = g[fa[u]] + f[fa[u]] - f[u] + 1ll * (n - Size[u] - S) * (Size[u] + S) - 1ll * Size[u] * (n - Size[u]);	}	else g[u] = 0;	ll res = f[u] + g[u];	for (auto v : G[u]) if (v != fa[u]) {		res = min(res, dfs2(v, rt, S));	}	return res;}int main() {	//freopen("in.txt", "r", stdin);	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	while (cin >> n) {		G.clear();		G.resize(n + 1);		init();		for (int i = 1, u, v; i < n - 1; ++i) {			cin >> u >> v;			G[u].push_back(v);			G[v].push_back(u);		}		int tr[2] = { 1,0 };		fa[1] = 1;		dfs(1); S = Size[1]; T = n - S;		for (int i = 1; i <= n; ++i) {			if (fa[i] == -1) {				tr[1] = fa[i] = i;				dfs(i); break;			}		}		ll res = dfs2(1, 1, T) + dfs2(tr[1], tr[1], S) + (ll)S * T;		cout << res << endl;	}}
     
    
   

K - Rng

概率DP问题，赛后补题，思路来自 博客园大佬

题意：

考虑随机选择一个区间的过程：

• 先从\([1,n]\)等概率选择\(r\)
• 再在\([1,r]\)中等概率选择出\(l\)
  问随机选择两个区间，它们相交的概率？

思路：

考虑枚举 \(r\)：

• 考虑RR落在\([r+1,n]\)的概率，即为：

• 考虑RR落在[l,r][l,r]之间的概率，即为：

#include 
   
    using namespace std;#define ll long long#define N 1000010const ll p = 1e9 + 7;ll qmod(ll base, ll n) {	ll res = 1;	while (n) {		if (n & 1) {			res = res * base % p;		}		base = base * base % p;		n >>= 1;	}	return res;}int n;ll f[N], g[N], inv[N]; ll Sf(int l, int r) {	if (l > r) return 0;	return (f[r] - f[l - 1] + p) % p;}ll Sg(int l, int r) {	if (l > r) return 0;	return (g[r] - g[l - 1] + p) % p; }void add(ll &x, ll y) {	x += y;	if (x >= p) x -= p;}int main() {	inv[1] = 1;	for (int i = 2; i < N; ++i) inv[i] = inv[p % i] * (p - p / i) % p;	for (int i = 1; i < N; ++i) {		f[i] = (f[i - 1] + i) % p;		g[i] = (g[i - 1] + inv[i]) % p;	}	while (scanf("%d", &n) != EOF) {		ll res = 0;		for (int i = 1; i <= n; ++i) {			add(res, 1ll * i * inv[n] % p * inv[n] % p * Sg(i + 1, n) % p);			add(res, 1ll * inv[i] * inv[n] % p * inv[n] % p * (1ll * i * (i + 1) % p - Sf(1, i) + p) % p);		}		printf("%lld\n", res);	}	return 0;}
   

参考

题解风格和思路参考：