ICPC2021上海部分题解

· 2021-12-01 · # icpc # 2021

场外一共做了六道题，罚时大概是银末的位置、场上的话估计只能铜。
题目质量还是挺高的很有意思。

E Strange Integers（签到题）

题意： 一段长度为n的序列。从中选出尽可能多的数，使任意两个数之间的绝对值相差大于k。

Solution： 对序列排序后从小到大。最小的数一定选，之后的从小到大能选就选。

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
const int N = 1e5 + 5;
int n, k, a[N], ans, rec;
/**/
int main()
{
	read(n); read(k);
	for(int i = 1; i <= n; i++) read(a[i]);
	sort(a + 1, a + 1 + n);
	rec = -1000000000;
	for(int i = 1; i <= n; i++)
	{
		// cout << 
		if(a[i] - rec >= k) rec = a[i], ans++;
	}
	cout << ans << '\n';
	return 0;
}

D Strange Fractions（签到题）

题意： 给定p和q。求一组合法的a和b满足：

\frac{p}{q} = \frac{a}{b} + \frac{b}{a}

Solution：

先推式子：

\frac{p}{q} = \frac{a^2+b^2}{ab}\\ \frac{p+2q}{q} = \frac{(a+b)^2}{ab}\\ \frac{(p+2q)^2}{q(p+2q)} = \frac{(a+b)^2}{ab}\\

得 $a + b = p + 2q\quad{}ab = q(p + 2q)$

联立即可得到 $a$ 和 $b$ 。同除以 $gcd$ 约分一下即可。

注： $p + 2q$ 是完全平方数则有解，否则无解。

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
int t, p, q, num1, num2, num3, num4, a, b, g;
/**/
signed main()
{
	read(t);
	while(t--)
	{
		read(p); read(q);
		num1 = p + 2 * q;// a + b
		num2 = num1 * q;// ab
		num3 = num1 * num1 - 4 * num2;// (a - b) ^ 2
		num4 = sqrt(num3);// a - b
		if(num4 * num4 != num3) puts("0 0");
		else
		{
			a = (num1 + num4) / 2;
			b = num1 - a;
			g = __gcd(a, b);
			a /= g; b /= g;
			cout << a << ' ' << b << '\n';
		}
	}
	return 0;
}

G Edge Groups（树形dp）

题意： n（奇数）个点的树，n-1条边分成 $\frac{n-1}{2}$ 组，每组两条边并且两条边要有一个公共点。求分组的方案数。

Solution： 首先。n个元素两两分组的方案数是 $f[n]$ ，则有递推式 $f[n] = f[n- 2] * (n - 1)$

设 $dp[u]$ 为 $u$ 子树的方案数。 $b$ 表示 $u$ 子树中点数为奇数的个数。

dp[u] = \begin{cases} f[b]*\prod f[v] \quad\quad\;\; \text{b is even} \\ f[b+1]*\prod f[v] \quad \text{b is odd} \end{cases}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
const int N = 1e5 + 5, mod = 998244353;
int n, sz[N];
ll f[N], dp[N];
vector<int>g[N];
/**/
void dfs(int u, int fa)
{
	sz[u] = 1; dp[u] = 1;
	int cnt = 0;
	for(auto &v : g[u])
	{
		if(v == fa) continue;
		dfs(v, u);
		sz[u] += sz[v];
		dp[u] = dp[u] * dp[v] % mod;
		if(sz[v] & 1) cnt++;
	}
	if(cnt & 1) cnt++;
	dp[u] = dp[u] * f[cnt] % mod;
}
signed main()
{
	read(n);
	for(int i = 1, x, y; i < n; i++)
	{
		read(x); read(y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	f[0] = 1;
	for(int i = 2; i <= n; i += 2)
	{
		f[i] = f[i - 2] * (i - 1) % mod;
	}
	dfs(1, 0);
	cout << dp[1];
	return 0;
}

I Steadily Growing Steam（签到题/背包）

题意： n 个物品。每个物品有价值w[i] 和体积 v[i]，求从中选出两个无交集的集合，两个集合的体积和相等，价值和最大。

注：可以将这n个物品中至多k个物品的体积翻倍。

Solution： 对选入两个集合分别用正负进行表示即可，注意边界问题的处理正常背包即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
int n, k, w[105], v[105], m;
ll f[105][3000][105], ans;
/**/
int main()
{
	read(n); read(k);
	ans = 0;
	for(int i = 1; i <= n; i++) {read(w[i]); read(v[i]);}
	memset(f, -0x3f, sizeof(f));
	f[0][1400][0] = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= 2800; j++)
		{
			f[i][j][0] = max(max(f[i][j][0], f[i-1][j][0]), f[i-1][j+v[i]][0]+w[i]);
			if(j>=v[i]) f[i][j][0] = max(f[i][j][0], f[i-1][j-v[i]][0]+w[i]);
			for(int t = 1; t <= min(i, k); t++)
			{
				f[i][j][t] = max(max(f[i][j][t], f[i-1][j][t]), max(f[i-1][j+2*v[i]][t-1], f[i-1][j+v[i]][t])+w[i]);
				if(j>=v[i]) f[i][j][t] = max(f[i][j][t], f[i-1][j-v[i]][t]+w[i]);
				if(j>=2*v[i]) f[i][j][t] = max(f[i][j][t], f[i-1][j-2*v[i]][t-1]+w[i]);
			}
		}
	}
	for(int i = 0; i <= k; i++) ans = max(ans, f[n][1400][i]);
	cout << ans << '\n';
	return 0;
}

K Circle of Life（银牌题/构造）

题意： 一个n位的由0和1组成的串。对每秒，1（星星）变成0向两边发射1，两个扩散的星星相撞则变成0。

Solution： 暴力打表找规律。找出某一循环的特殊性质后输出。

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
int n;
/**/
int main()
{
    cin >> n;
    if(n == 3) {puts("Unlucky"); return 0;}
    else
    {
        if(n&1) printf("100"),n-=3;
        n/=2;
        for(int i=1;i<=n;i++)
        {
            if(i&1) printf("01");
            else printf("10");
        }
    }
    return 0;
}

M Harmony in Harmony(银牌题/构造)

题意： 待补。

Solution： 瞎猜的。待补。

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
int n,m;
signed main()
{
	read(n);
	for(int i=1;i<=n;i++)
	{
		m=max(m,(n*(i)*(n-i+1)));
	}
	printf("%.9f",1.0/m);
}

H Life is a Game(铜牌题/kruscal重构树|可并堆)

题意： 对于n个点m条边的无向图有q个询问。图有点权和边权，每个询问 x,k 表示从 x 出发，初始能力值为k，当能力值大于边权则能通过这条边，第一次到达一个点可以获得该点点权的能力值。求可以获得的最大能力。

Solution： 对边按边权从小到大排序。询问离线，用n个堆维护每个点的询问（按k从小到大维护）。

枚举边，对边（无向）的两个端点，分别取出能力值不能通过这条边的询问，记录答案。

对于剩下的结点（全部能够通过这条边），利用并查集合并这两个节点，同时将堆按并查集的思路启发式合并（小堆并大堆）。

枚举完边后对于剩余没有得到答案的询问（即合并完成的询问），单独取出并记录答案。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
const int N = 1e5 + 5;
int n, m, t, sum[N], fa[N], ans[N];
struct edge
{
	int from, to, w;
	bool operator < (const edge &b) const {return w < b.w;}
}e[N];
priority_queue<PII, vector<PII>, greater<PII> >q[N];
/**/
inline int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
int main()
{
	read(n); read(m); read(t);
	for(int i = 1; i <= n; i++) read(sum[i]), fa[i] = i;
	for(int i = 1, u, v, w; i <= m; i++) read(u), read(v), read(w), e[i] = (edge){u, v, w};
	sort(e + 1, e + 1 + m);
	for(int i = 1, x, k; i <= t; i++) read(x), read(k), q[x].push(PII(k, i));
	for(int i = 1; i <= m; i++)
	{
		int u = find(e[i].from), v = find(e[i].to);
		if(u == v) continue;
		while(!q[u].empty() && q[u].top().first + sum[u] < e[i].w)
		{
			int id = q[u].top().second;
			ans[id] = q[u].top().first + sum[u];
			q[u].pop();
		}
		while(!q[v].empty() && q[v].top().first + sum[v] < e[i].w)
		{
			int id = q[v].top().second;
			ans[id] = q[v].top().first + sum[v];
			q[v].pop();
		}
		if(q[u].size() > q[v].size()) swap(u, v);
		while(!q[u].empty()) q[v].push(q[u].top()), q[u].pop();
		fa[u] = v; sum[v] += sum[u];
	}
	for(int i = 1; i <= n; i++)
	{
		int u = find(i);
		while(!q[u].empty())
		{
			PII x = q[u].top(); q[u].pop();
			ans[x.second] = x.first + sum[u];
		}
	}
	for(int i = 1; i <= t; i++) cout << ans[i] << '\n';
	return 0;
}

J Two Binary Strings Problem（银牌题/bitset）

题意： 给定长度为n的两个01串A和B。 $f(l,r)!$ 表示区间 $l$ 到 $r$ 的众数。（01数量相等时为0）

求一个长度同样为n的01串 $ans$ ， $ans_k$ 为 1 时当且仅当：对所有 $1\le i\le n\quad{有}f(max(i-k+1, 1), i) = B_i$ 成立

Solution：

A\quad\;\; 0\; 1\; 1\; 0\; 1\; 0\; 1\\ K1\quad 0\; 1\; 1\; 0\; 1\; 0\; 1\\ K2\quad 0\; 0\; 1\; 0\; 0\; 0\; 0\\ K3\quad 0\; 0\; 1\; 1\; 1\; 0\; 1\\ K4\quad 0\; 0\; 1\; 0\; 1\; 0\; 0\\ K5\quad 0\; 0\; 1\; 0\; 1\; 1\; 1\\ K6\quad 0\; 0\; 1\; 0\; 1\; 0\; 1\\ K7\quad 0\; 0\; 1\; 0\; 1\; 0\; 1\\

对于每一行，若 $C_i = B$ ，则 $ans_i = 1$

由于行之间的关系不好找，转成列。

对于第i列，找到最近的 $j$ 使 $j+1...i$ 的0和1相等。因为是最近的， $故f(j+1,i)=0, 而f(j+k,i)=A_i (1\le k \le i-j)$

故对于 $C_i$ 的 $1...(i-j-1)$ 项均 $=A_i$ ，第 $i-j$ 项恰好 $=0$ 。第 $(i-j+1)...n$ 可由 $C_j$ 转移。

若找不到 $j$ ，则 $C_i$ 全部等于 $A_i$ 。

难点其实在位运算的转移上。需要思考一下。

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
const int N = 5e4 + 5;
int t, n, tot[N*2];
char A[N], B[N];
bitset<N>C[N], ans, all1;
/**/
int main()
{
	read(t);
	while(t--)
	{
		read(n);
		scanf("%s%s", A, B);
		for(int i = 0; i < n; i++) all1[i] = 1, C[i] = 0; ans = all1;
		for(int i = 0; i <= 2*n; i++) tot[i] = -2; tot[n] = -1;
		int rec = n;
		for(int i = 0; i < n; i++)
		{
			A[i] == '1' ? ++rec : --rec;
			int j = tot[rec];
			// printf("i = %d, j = %d\n", i + 1, j);
			if(j == -2) A[i] == '1' ? C[i] = all1 : C[i] = 0;
			else
			{
				//1 -> (i - j - 1) 位 = A[i] , 第 i - j 位 = 0 ( 0和1 恰好 相等) , 剩下的由之前的递推而来
				if(A[i] == '1') C[i] |= all1 >> (n - (i - j - 1) ); //原来n位，变成(i-j-1)位
				if(j != -1) C[i] |=  C[j] << (i - j);
				else if(C[i][i]) C[i] |= all1 << i; // K > (i - j);
			}
			// for(int k = 0; k < n; k++) cout << C[i][k]; puts("");
			tot[rec] = i;
			ans &= (B[i]=='1' ? C[i] : ~C[i]);
		}
		for(int i = 0; i < n; i++) cout << ans[i]; putchar('\n');
	}
	return 0;
}

ICPC2021上海 部分题解