E. Edward Gaming, the Champion(签到题)

题意： 求一个字符串s中有多少个"edgnb"

Solution： EDGNBEDGNB

#include <bits/stdc++.h>
using namespace std;
/**/
const int N = 2e5 + 5;
char s[N];
/**/
int main()
{
	scanf("%s", s);
	int len = strlen(s), ans = 0;
	for(int i = 0; i < len; i++)
	{
		if(i+4>=len) break;
		if(s[i]=='e'&&s[i+1]=='d'&&s[i+2]=='g'&&s[i+3]=='n'&&s[i+4]=='b') ans++, i = i + 4;
	}
	cout<<ans;
	return 0;
}

F. Encoded Strings I（签到题/模拟）

题意： 队友A的，待补。

Solution： 队友A的，待补。

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 1005
#define int ll
using namespace std;
il ll read()
{
	char c=getchar();
	ll x=0,f=1;
	while(c>'9'||c<'0')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[Max],c[Max],id[Max];
char s[Max],t[Max][Max];
il bool cmp(int x,int y)
{
	int l=min(strlen(t[x]+1),strlen(t[y]+1));
	for(int i=1;i<=l;i++)
	{
		if(t[x][i]<t[y][i]) return 0;
		if(t[x][i]>t[y][i]) return 1;
	}
	return strlen(t[x]+1)>strlen(t[y]+1);
}
signed main()
{
	n=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=26;j++) c[j]=0;
		int tot=0;
		for(int j=i;j>=1;j--)
		{
			if(!c[s[j]-'a'+1]) t[i][j]=tot+'a',c[s[j]-'a'+1]=++tot;
			else t[i][j]=c[s[j]-'a'+1]+'a'-1;
			//cout<<j<<' '<<c[s[j]-'a'+1]<<' '<<s[j]<<' '<<tot<<" qwq\n";
		}
	}
	//for(int i=1;i<=n;i++) puts(t[i]+1);
	for(int i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+1+n,cmp);
	puts(t[id[1]]+1);
}

J. Luggage Lock（bfs）

题意： 一个四位数密码。给定起始状态 A 和终止状态 B 。每次可以选择一段区间向上拧或向下拧（即+1/−1+1/-1）。

求由A变为B的最小操作次数。

Solution： 因为所有的两组状态都可以转化成 起始状态为 0000。因此对于 0000 开始，其实只有 10000 种状态。

预处理：利用 bfs 求最少步数。同时对已经得到的状态进行标记即可。

然后即可对每组询问 O(1) 输出。

#include <bits/stdc++.h>
#define PII pair<string,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 string opt[15] = {"0001","0011","0111","1111","0010","0110","1110","0100","1100","1000"};
int vis[10005], ans[10005];
/**/
inline int get(string s)
{
	int ret = 0;
	for(int i=0;i<4;i++) ret=(ret<<3)+(ret<<1)+s[i]-'0';
	return ret;
}
inline string work(string s,int p,int flag)
{
	string ret = s;
	for(int i=0;i<4;i++)
	{
		if(opt[p][i]=='0') continue;
		ret[i]=(ret[i]-'0'+flag+10)%10+'0';
	}
	return ret;
}
int main()
{
	queue<PII>q;
	q.push(PII("0000",0));
	vis[0] = 1;
	while(!q.empty())
	{
		PII t = q.front(); q.pop();
		string u = t.first;
		int step = t.second;
		for (int i = 0; i < 10; i++)
		{

			string s1 = work(u,i,1);
			string s2 = work(u,i,-1);
			int num1 = get(s1), num2 = get(s2);
			if(!vis[num1])
			{
				vis[num1]=1;
				ans[num1]=step + 1;
				q.push(PII(s1, step + 1));
			}
			if(!vis[num2]) vis[num2] = 1, ans[num2] = step + 1, q.push(PII(s2, step + 1));
		}
	}
	int t;
	read(t);
	string S1, S2, T;
	while(t--)
	{
		cin >> S1 >> S2;
		int ret = 0;
		for(int i=0;i<4;i++)
		{
			ret = ret * 10 + (S2[i]-S1[i]+10)%10;
		}
		cout << ans[ret] << '\n';
	}
	return 0;
}

B. Bitwise Exclusive-OR Sequence（铜牌题）

题意： 一段长度为 nn 的数。给定 mm 组关系。每组关系 (u,v,w)(u,v,w) 描述了：au⊕av=wa_u \oplus a_v=w

求这组数 各元素和 的最小值。

Solution： 可以根据每组关系建边，随意以一个有出边的点为树根进行遍历。

定义 dis[u]dis[u] 为 从根节点到 uu 的边权异或和。根据异或性质易知：art⊕au=disua_{rt} \oplus a_u = dis_u

如果出现两个不同值的 dis[u]dis[u] 则数据出现矛盾输出 -1。

对该森林的其中一个树，tot[i]tot[i] 表示所有 dis[u]dis[u] 的第 ii 位为1的数量。超过一半则让根该位为1更优，否则让根该位为0。

#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, M = 4e5 + 5;
int n, m, head[N], cnt, dis[N], tot[N], vis[N], sum;
bool err;
ll ans;
struct edge
{
	int nxt, to, w;
}e[M];
/**/
inline void add(int u, int v, int w)
{
	e[++cnt] = (edge){head[u], v, w};
	head[u] = cnt;
}
void dfs(int u, int fa, int ti)
{
	if(err) return;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa) continue;
		if(vis[v])
		{
			if((dis[u] ^ e[i].w) == dis[v]) continue;
			else {err = 1; return;}
		}
		vis[v] = ti;
		dis[v] = (dis[u] ^ e[i].w);
		sum++;
		for(int j = 0; j <= 30; j++)
		{
			if(dis[v] & (1<<j)) tot[j]++;
		}
		dfs(v, u, ti);
		if(err) return;
	}
}
int main()
{
	read(n); read(m);
	for(int i = 1, u, v, w; i <= m; i++)
	{
		read(u); read(v); read(w);
		if(u==v)
		{
			if(w) err = 1;
			continue;
		}
		add(u, v, w);
		add(v, u, w);
	}
	if(err) {puts("-1");return 0;}
	for(int i = 1; i <= n; i++)
	{
		if(!head[i]) continue;
		if(vis[i]) continue;
		vis[i] = i;
		dfs(i, 0, i); sum++;
		for(int j = 0; j <= 30; j++)
		{
			ans += 1ll * min(tot[j], sum - tot[j]) * (1 << j);
			tot[j] = 0;
		}
		sum = 0;
		if(err) {puts("-1"); return 0;}	
	}
	if(err) {puts("-1"); return 0;}
	cout << ans << '\n';
	return 0;
}

L. Perfect Matchings（树形dp+容斥）

题意： 队友A的，待补。

Solution： 队友A的，待补。

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 4010
#define Mod 998244353
#define int ll
using namespace std;
il ll read()
{
	char c=getchar();
	ll x=0,f=1;
	while(c>'9'||c<'0')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node
{
	int t,nt;
}e[Max<<1];
int n,head[Max],tot,f[Max][Max][2],g[Max],sz[Max],ans;
il void add(int u,int v)
{
	e[++tot].t=v;
	e[tot].nt=head[u];
	head[u]=tot;
}
il void dfs(int u,int fa)
{
	sz[u]=1;
	for(int i=head[u];i;i=e[i].nt)
	{
		int v=e[i].t;
		if(v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
	int s=1;
	//f[u][0][0]=1;
	f[u][0][0]=1;
	for(int i=head[u];i;i=e[i].nt)
	{
		int v=e[i].t;
		if(v==fa) continue;
		for(int j=s/2+1;j>=0;j--)
		{
			for(int k=1;k<=sz[v]/2+1;k++)
			{
				//if(j==0&&k==0) continue;
				f[u][j+k][0]=(f[u][j+k][0]+f[u][j][0]*f[v][k][0]+f[u][j][0]*f[v][k][1])%Mod;
				//f[u][0][0]=1;
				f[u][j+k][1]=(f[u][j+k][1]+f[u][j][0]*f[v][k-1][0]+f[u][j][1]*(f[v][k][0]+f[v][k][1]))%Mod;
				//cout<<u<<' '<<v<<' '<<j<<' '<<k<<' '<<f[1][1][1]<<" qwq\n";
			}
		}
		s+=sz[v];
	}
}
signed main()
{
	n=read()*2;
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	g[0]=1;
	for(int i=2;i<=n;i+=2) g[i]=(i-1)*g[i-2]%Mod;
	dfs(1,0);
	//for(int i=0;i<=n/2;i++) cout<<f[1][i][1]<<' '<<f[1][i][0]<<endl;
	for(int i=0;i<=n/2;i++)
	{
		ans=ans+(g[n-i*2]*(f[1][i][1]+f[1][i][0])%Mod*(i&1?-1:1)+Mod);
		ans=(ans+Mod)%Mod;
	}
	cout<<ans<<endl;
}

M. String Problem（KMP）

题意： 给定一个长度为 nn 的字符串s。输出 nn 行 (li,ri)(l_i, r_i) 表示：

对 s 的前缀 s1...is_{1...i} 中字典序最大的子串。

Solution： 首先容易得到 ri=ir_i = i。然后做了一个神奇的 KMP 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int nxt[N];
int main()
{
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	puts("1 1");
	int pos = 1, j = 1;
	for(int i = 2; i <= len; i++)
	{
		while(j && s[i] > s[pos + nxt[j]])
		{
			pos += (j - nxt[j]);
			j = nxt[j];
		}
		if(j && s[i] == s[pos + nxt[j]])
		{
			j++;
			nxt[j] = nxt[j - 1] + 1;
		}
		else nxt[++j] = 0;
		printf("%d %d\n", pos, i);
	}
	return 0;
}