2024/12/27 总结

模拟赛 T1 取石子游戏

A和B两人玩取石子游戏。一共有n堆石子，第堆有α个石子。A和B轮流取石子，A先取,每次选择一堆然后取任意数量的石子（不能不取）。但是B必须取两次，即取石子的顺序是,ABBABB...。当一方无法取石子，则输掉游戏。假设A和B均绝顶聪明，请判断A是否可以获,胜，若A可以获胜则输出win，否则输出Lose。

序列全1的话，n % 3 != 0时先手必胜

如果序列有n-1个1，1个x的话，先手可以选择取到n个1或者n-1个1，总有一种方法能使得自己必胜。

如果序列中有k个数大于1.

对于后手：

• k = 2时，后手可以选择把序列化为n个1 ， 化为n-1个1或者n-2个1.一定有一种获胜
• k = 1时，后手可以选择把序列化为n个1（大于1的数大于2），化为n-1个1或n-2个1. 在大于1的数大于2时一定有一种获胜。

在先手拿到的状态k = 2时，先手只能在状态为形如[1,1,1...,2,x(x%3 != 2)]时赢，即把x取干净或变为1。

当先手拿到的状态k > 2时，后手肯定可以有操作使得先手再次拿到时不存在x(x%3 != 2)，也就是说这种情况中先手必败。

题就做完了，如果实在推不了的话其实也可以打表。

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		int n, cnt1 = 0, cnt2 = 0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			if (x == 1) cnt1++;
			if (x == 2) cnt2++;
		}
		
		// 全为1的情况
		if (cnt1 == n) {
			cout << (n % 3 == 0 ? "Lose\n" : "Win\n");
		} else {
			// 存在非1的情况
			int non_ones = n - cnt1;
			if (non_ones == 1 || (non_ones == 2 && cnt2 > 0 && n % 3 != 2)) {
				// 1个非1数字或2个非1数字且至少有1个是2
				cout << "Win\n";
			} else {
				// 其他情况
				cout << "Lose\n";
			}
		}
	}
	return 0;
}

树上字符串

有一棵n个节点的树，树上每个节点都有一个字母，再给定一个字符串S。,有q次询问，每次询问给出到，令T表示到简单路径上每个节点字符依次拼起来组成的,字符串。你需要求出T有多少个子序列和S相等，答案对998244353取模。

求出两个点的lca w。求出u到w的路径上，能匹配s的长度为x的前缀数量，令其为a[x]，同理求出v到w路径上能匹配s的长度为|s| - x的后缀数量，令其为b[l - x]。

答案就是a[x] * b[l - x]。要特判一下w这个点，由于我们求的是子序列，同时考虑包含w的答案和不包含w的答案加起来即可。

接下来问题就在于如何处理a和b了。(有一些很难理解)

考虑一个dp, 设F l,r,u 为从u到根节点的路径匹配了s[l,r]子串的子序列数量，那么a[i]就等于u到根匹配了长度为i的前缀的数量， 减去a[u] (小到大递推a[i],a[u]必然已求出) 乘F u+1w,i(s[u+1,i]的子串匹配在w到根的路径的情况数)(容斥画图可理解，我不会证)，同理也可以求出b[x]的。

总复杂度n * |S| ^ 2，很tm卡空间。

优化：发现dp数组中r一定会大于l，所以写个索引就可以节省一半空间，注意优化一下常数。

代码(没加优化，MLE声一片)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn = 1e5,maxs = 35;
constexpr ll mod = 998244353;
int_least32_t dp[2][maxs][maxs][maxn];//从u节点到根的路径匹配了s0[i,j]这段子串的子序列有多少种。
ll c[maxs],d[maxs];
char s[maxn],s1[maxs];

vector<int> mp[maxn];
int p[50][maxn],fa[maxn],deep[maxn];
namespace LCA {
	void dfs(ll u){
		if(u == 1)fa[u] = 0;
		p[0][u] = fa[u];
		deep[u] = deep[fa[u]] + 1;
		for(ll i = 1;i < 20;i ++)p[i][u] = p[i-1][p[i-1][u]];
		ll sz = mp[u].size();
		for(ll i = 0;i < sz;i ++){
			ll v = mp[u][i];
			if(v == fa[u])continue;
			fa[v] = u;
			dfs(v);
		}
	}
	ll getf(ll u,ll k){
		for(ll i = 0;i < 20;i ++)
			if(k &(1 << i))
				u = p[i][u];
		return u;
	}
	ll query(ll a,ll b){
		if(deep[a] > deep[b])swap(a,b);
		b = getf(b,deep[b] - deep[a]);
		if(a == b)return a;
		for(ll i = 19;i >= 0;i--){
			if(fa[a] == fa[b])break;
			if(p[i][a] != p[i][b]){
				a = p[i][a];
				b = p[i][b];
			}
		}
		return fa[a];
	}
};

ll l;
void dfs(int u,int x,int c){
	for(int i = x;i <= l;i ++){
		dp[c][x][i][u] += dp[c][x][i][fa[u]];
		if(dp[c][x][i][u] >= mod) dp[c][x][i][u] -= mod;
		
		if(s[u] == s1[i])
			dp[c][x][i][u] += dp[c][x][i-1][fa[u]];
		if(dp[c][x][i][u] >= mod) dp[c][x][i][u] -= mod;
	}
	int sz = mp[u].size();
	for(int i = 0;i < sz;i ++){
		int v = mp[u][i];
		if(v == fa[u])continue;
		dfs(v,x,c);
	}
}

void init(ll n,ll c){
	for(int i = 0;i <= l + 1;i ++){
		for(int j = 0;j <= n;j ++){
			for(int k = 0;k <= i;k ++)
				dp[c][k][i][j] = 0;
			if(i) dp[c][i][i-1][j] = 1;
		}
	}
	for(ll i = 1;i <= l;i ++)
		dfs(1,i,c);
}

signed main() {
	//freopen("treestr2.in","r",stdin);
	ll n,q;
	cin>>n>>q;
	for(ll i = 1;i <= n;i++)mp[i].clear();
	for(ll i = 1;i < n;i ++){
		ll a,b;
		cin>>a>>b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}	
	cin>>(s + 1)>>(s1 + 1);
	l = strlen(s1 + 1);
	LCA::dfs(1);
	reverse(s1 + 1,s1 + l + 1);
	init(n,0);
	reverse(s1 + 1,s1 + l + 1);
	init(n,1);
	while(q --){
		ll a,b;
		cin>>a>>b;
		if(a == b){
			if(l == 1 && s[a] == s1[1]) cout<<1<<endl;
			else cout<<0<<endl;
			continue;
		}
		ll w = LCA::query(a,b);
		ll ans = 0;
		for(ll i = 0;i < maxs;i++) c[i] = 0;
		for(ll i = 0;i < maxs;i++) d[i] = 0;
		for(ll i = 0;i <= l;i ++){
			c[i] = dp[0][l-i+1][l][a];
			d[i] = dp[1][l-i+1][l][b];
			for(ll j = 0;j < i;j ++){
				c[i] -=(c[j] * dp[0][l-i+1][l-j][w] % mod);
				d[i] -=(d[j] * dp[1][l-i+1][l-j][w] % mod);
				c[i] += mod;
				if(c[i] >= mod)c[i] -= mod;
				d[i] += mod;
				if(d[i] >= mod)d[i] -= mod;
			}
		}
		for(ll i = 0;i <= l;i ++){
			ans += c[i] * d[l-i] % mod;
			if(ans >= mod)ans -= mod;
		}
		for(ll i = 0;i < l;i ++){
			if(s[w] == s1[i+1]){
				ans += c[i] * d[l-i-1] % mod;
				if(ans >= mod)ans -= mod;
			}
		}
		cout<<ans<<endl;
	}
	
}

一些构造好题

Black and White Tree

给您一棵 \(n\) 个节点的树，树边有边权，每个节点都有颜色，且只可能是黑色或白色（用 \(0\) 或 \(1\) 表示）。原树不存在树边连接 \(2\) 个同色的节点。

现给出每个节点的颜色和与这个节点相连的边的权值和，请您还原这棵树。

思路

一些启发/结论: 边权可以为0，整个树就相当于一个没有环的二分图。黑点所连边的权值和与白点所连边的权值和相同。

我们可以每次取出一个黑点和一个白点，将权值小的那个点权值清零，大的那个减去另一个点的权值，也就是说，一个点将他的所有权值连接到了另一个点，剩下的边权值就会为0了，我们就把权值变为0的点删掉。

一直这样做，直到没有点可以选了，由于题目保证有解，所以我们就构造完了。