E. Edward Gaming, the Champion(签到题)
题意： 求一个字符串s中有多少个"edgnb"
Solution： EDGNBEDGNBEDGNB
#include
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< return 0; } F. Encoded Strings I（签到题/模拟） 题意： 队友A的，待补。 Solution： 队友A的，待补。 #include #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] 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< } } //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+1/−1）。 求由A变为B的最小操作次数。 Solution： 因为所有的两组状态都可以转化成 起始状态为 0000。因此对于 0000 开始，其实只有 10000 种状态。 预处理：利用 bfs 求最少步数。同时对已经得到的状态进行标记即可。 然后即可对每组询问 O(1) 输出。 #include #define PII pair 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 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（铜牌题） 题意： 一段长度为 nnn 的数。给定 mmm 组关系。每组关系 (u,v,w)(u,v,w)(u,v,w) 描述了：au⊕av=wa_u \oplus a_v=wau⊕av=w 求这组数 各元素和 的最小值。 Solution： 可以根据每组关系建边，随意以一个有出边的点为树根进行遍历。 定义 dis[u]dis[u]dis[u] 为 从根节点到 uuu 的边权异或和。根据异或性质易知：art⊕au=disua_{rt} \oplus a_u = dis_uart⊕au=disu 如果出现两个不同值的 dis[u]dis[u]dis[u] 则数据出现矛盾输出 -1。 对该森林的其中一个树，tot[i]tot[i]tot[i] 表示所有 dis[u]dis[u]dis[u] 的第 iii 位为1的数量。超过一半则让根该位为1更优，否则让根该位为0。 #include #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< } 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 #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< } } s+=sz[v]; } } signed main() { n=read()*2; for(int i=1;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< 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< } M. String Problem（KMP） 题意： 给定一个长度为 nnn 的字符串s。输出 nnn 行 (li,ri)(l_i, r_i)(li,ri) 表示： 对 s 的前缀 s1...is_{1...i}s1...i 中字典序最大的子串。 Solution： 首先容易得到 ri=ir_i = iri=i。然后做了一个神奇的 KMP 。 #include 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; }