2023牛客暑期多校第二场部分题解

A

队友开的题，说是其实就是问能不能用若干个数异或出来某个数。

应该就是线性基板子，然后他写了一下就过了。

B

一开始看没什么人过不是很敢开，结果到后面一看题——这不是最大权闭合子图板子吗？？

我还愣了一小会儿，只是发现边数有点儿多，要用个树剖+线段树优化建图，然后就开始咣咣一顿写，极限40min写完……然后没debug出来。

后来发现一个变量ID 写成了Id。再也不起这么抽象的变量名了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define inf 999999999999999999ll//开大了，忘记改了，问题不大int n,m,N;
struct edge{int y,next;long long z;
}e[20000000];
int first[maxn],et=1;
void buildroad(int x,int y,long long z){e[++et]=(edge){y,first[x],z};first[x]=et;
}
void addedge(int x,int y,long long z){// printf("   %d->%d : %lld\n",x,y,z);buildroad(x,y,z);buildroad(y,x,0);
}
vector<pair<int,int>> to[maxn];
int fa[maxn],Fa[maxn],dep[maxn];
int sz[maxn],mson[maxn];
void dfs_init(int x){sz[x]=1;for(auto i:to[x]){int y=i.first;if(y==fa[x])continue;fa[y]=x;Fa[y]=i.second;dep[y]=dep[x]+1;dfs_init(y);sz[x]+=sz[y];if(sz[y]>sz[mson[x]])mson[x]=y;}
}
int top[maxn],bot[maxn],id[maxn],old[maxn],Id=0;
struct node{int l,r,mid,ID;node *zuo,*you;node(int x,int y,int L):l(x),r(y),mid(l+r>>1){ID=++N;if(l==r){if(L<l)addedge(ID,Fa[old[l]]+m,inf);//就是这个ID写错了……return;}zuo=new node(l,mid,L);you=new node(mid+1,r,L);addedge(ID,zuo->ID,inf);addedge(ID,you->ID,inf);}void link(int x,int y,int From){if(l==x&&r==y){addedge(From,Id,inf);return;}if(y<=mid)zuo->link(x,y,From);else if(x>mid)you->link(x,y,From);else zuo->link(x,mid,From),you->link(mid+1,y,From);}
}*rt[maxn];
void dfs2(int x,int tp){id[x]=++Id;old[Id]=x;top[x]=tp;if(mson[x]){dfs2(mson[x],tp);for(auto i:to[x]){int y=i.first;if(y==fa[x]||y==mson[x])continue;dfs2(y,y);}}else bot[tp]=x;if(x==tp)rt[x]=new node(id[x],id[bot[x]],id[x]);
}
int S,T;
int q[maxn],st,ed,h[maxn],cur[maxn];
bool bfs(){memset(h,0,sizeof(h));q[st=ed=1]=S;h[S]=1;while(st<=ed){int x=q[st++];cur[x]=first[x];for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(e[i].z&&!h[y]){h[y]=h[x]+1;q[++ed]=y;}}}return h[T]>0;
}
long long dfs(int x,long long flow){if(x==T)return flow;long long re=0;for(int i=cur[x];i;i=e[i].next){int y=e[i].y;cur[x]=i;if(e[i].z&&h[y]==h[x]+1){long long p=dfs(y,min(e[i].z,flow));re+=p;e[i].z-=p;e[i^1].z+=p;if(re==flow)break;}}if(!re)h[x]=0;return re;
}
void go(int x,int y,int From){if(dep[top[x]]>dep[top[y]])swap(x,y);while(top[x]!=top[y]){rt[top[y]]->link(id[top[y]],id[y],From);addedge(From,Fa[top[y]]+m,inf);y=fa[top[y]];if(dep[top[x]]>dep[top[y]])swap(x,y);}if(id[x]>id[y])swap(x,y);rt[top[x]]->link(id[x],id[y],From);
}int main()
{scanf("%d %d",&n,&m);S=n+m;T=S+1;N=T+1;for(int i=1;i<n;i++){int x,y,z;scanf("%d %d %d",&x,&y,&z);to[x].push_back(make_pair(y,i));to[y].push_back(make_pair(x,i));addedge(i+m,T,z);}dfs_init(1);dfs2(1,1);long long ans=0;for(int i=1;i<=m;i++){int x,y,z1,z2;scanf("%d %d %d %d",&x,&y,&z1,&z2);if(z1-z2>0){ans+=z1-z2;addedge(S,i,z1-z2);go(x,y,i);}}while(bfs())ans-=dfs(S,inf);printf("%lld",ans);
}

C

把欧拉路径先限制成欧拉回路，虽然看起来更难了但其实这样不需要考虑图的实际连通情况了，只需要保证每个点的度都是偶数。

那么很容易想到把图里的奇数点先拎出来，构造完剩余的图之后再把这个点尝试加进去。但实际上剩余的图构造完之后这个点怎么加都会破坏和他相连的点的度的奇偶性。

官方题解的方法就很妙，把奇度点 $x$ 拎出来之后，让与他相连的点集 $P$ 构成的子图取一个补图，然后再让剩下的图去做构造，然后看看 $P$ 内染 $0$ 和 $1$ 的点分别有多少，数量必然是一奇一偶，将 $x$ 加入偶数的那个集合即可，手算一下此时的度就能发现都变成偶数了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 110int n,m;
int d[maxn][maxn],r[maxn];
int ans[maxn];
bool v[maxn];
int fa[maxn];
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
vector<int> s[maxn];
void work(vector<int> &a){for(int i:a)if(!v[i]&&r[i]){v[i]=true;vector<int> tmp;for(int j:a)if(d[i][j])tmp.push_back(j),d[i][j]^=1,d[j][i]^=1,r[i]^=1,r[j]^=1;for(int x:tmp)for(int y:tmp)if(x!=y)d[x][y]^=1,r[x]^=1;work(a);int zero=0,one=0;for(int j:tmp)if(ans[j])one++;else zero++;if(zero&1)ans[i]=1;v[i]=false;break;}
}int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){int x,y;scanf("%d %d",&x,&y);d[x][y]^=1;d[y][x]^=1;r[x]^=1;r[y]^=1;fa[findfa(y)]=findfa(x);}for(int i=1;i<=n;i++)s[findfa(i)].push_back(i);for(int i=1;i<=n;i++)if(i==fa[i])work(s[i]);for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}

D

首先可以发现每个人的决策一定会想办法利用后面的人来使自己利益最大化，那么利用肯定利用到极致，比如最后选菜的人最喜欢的菜一定是没人选的，因为这样他就一定会选这个菜，前面的人就可以利用这一点。

所以实际上最后相当于反向贪心一下就行了。

代码是队友写的，就不贴了，也没啥实现难度。

E

要求 $y^2=x\times 10^k+c$ 即 $y=\sqrt{x\times 10^k+c}$，注意到 $c$ 其实影响很小，所以 $y=\lceil \sqrt{x\times 10^k}\rceil$。

枚举 $k$ 尝试求解即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;int main()
{cin.sync_with_stdio(false);int T;cin>>T;while(T--){long long n;cin>>n;int ans=0;long long c=1;for(int k=0;;k++){int p=sqrt(n)+1e-6;if(1ll*p*p/c==n/c)ans=p;p++;if(1ll*p*p/c==n/c)ans=p;if(ans)break;if(n>(long long)(1e17+0.5))break;n*=10;c*=10;}if(!ans)cout<<"-1\n";else cout<<ans<<'\n';}
}

F

注意到其实是个很经典的二分图模型。二分图博弈的结论是：假如起点无论如何都在最大匹配内，那么先手必胜。证明可以上网找，其实在最大匹配内就是要保证每次后手操作后先手一定可以操作。

把这个结论往这题上套，发现 $n$ 是偶数时一定每个点都在最大匹配上，先手一定必胜，$n$ 是奇数时二分图两侧点数是不一样的，$x+y+z$ 为奇数的点多一个，并且一定可以通过构造让任何一个 $x+y+z$ 为奇数的点不在最大匹配内，所以此时先手必败。如果 $x+y+z$ 为偶数那么还是先手必胜。

代码很简单就不贴了。

G

魔改一个马拉车即可。

最后贪心找子串来拼接，正确性可以这样考虑：

假设有一个串（方便看和理解这里使用传统意义的回文串）$abacaba$，那么贪心选可能会选出 $abacaba$ 这三段来覆盖，但如果存在更长一点的回文串可以覆盖这一段为什么不选呢？比如这里可以直接选整段，但这就意味着，前面的 $aba$ 在后面一定会对应另一个 $aba$，所以不考虑这个长段也无所谓。

代码是队友写的，就不贴了。

H

一开始想着对每种二进制数的长度分别在操作序列上建线段树来找下一个变成 $0$ 的位置，然后每次一个一个位置往后跳，应该是可以做的，但实现很麻烦。

后来想到直接不管长度限制，统一直接用一个 unsigned long long 来做，加一就正常加一，翻转后的加一变成减一，翻转就用 $2^{63}-1$ 来减去当前的数，最后需要多少位就截取多少位直接输出即可。注意到这样子不需要考虑进位溢出的情况了，所以把所有操作做一个前缀和每次就可以 $O(64)$ 回答了。

又是之前提到的先不考虑限制直接做，然后求出在限制下的答案的思想，非常经典。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010int n,m;
char s[maxn],ss[110];
int b[maxn],sum[maxn];int main()
{scanf("%d %d",&n,&m);scanf("%s",s+1);int now=1;for(int i=1;i<=n;i++){if(s[i]=='A')now*=-1,sum[i]=sum[i-1];else sum[i]=sum[i-1]+now;b[i]=now;}long long lastans=0;vector<int> ans;for(int i=1;i<=m;i++){int l,r,L,R,len;scanf("%d %d %s",&L,&R,ss+1);l=min((lastans^L)%n+1,(lastans^R)%n+1);r=max((lastans^L)%n+1,(lastans^R)%n+1);// printf("real : %d %d\n",l,r);len=strlen(ss+1);unsigned long long num=0;for(int j=1;j<=len;j++)num=(num<<1)+ss[j]-'0';int bl=s[l]=='A'?b[l]*(-1):b[l];num+=bl*(sum[r]-sum[l-1]);if(bl!=b[r])num=ULONG_LONG_MAX-num;lastans=0;for(int j=1;j<=len;j++)ans.push_back(num&1),num>>=1;while(ans.size()){lastans=(lastans<<1)+ans.back();putchar(ans.back()+'0'),ans.pop_back();}puts("");// printf("lastans : %lld\n\n",lastans);}
}

I

样例其实已经提示了构造方法了，就是每行（或每列）四个四个放，假如 $n,m$ 都是奇数那么特殊考虑一下最后一列和最后一行即可，具体可以看代码：

#include <bits/stdc++.h>
using namespace std;int main()
{int T;scanf("%d",&T);while(T--){int n,m;scanf("%d %d",&n,&m);if(n%2==0){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)putchar((i+(j-1)/4)%2?'x':'o');puts("");}}else if(m%2==0){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)putchar((j+(i-1)/4)%2?'x':'o');puts("");}}else{int d=(n+(m-2)/4)%2;for(int i=1;i<n;i++){for(int j=1;j<m;j++){putchar((i+(j-1)/4+d)%2?'x':'o');}putchar((i+(m-2)/4+d)%2?'o':'x');puts("");}for(int i=1;i<=m;i++)putchar((n+(m-2)/4-i+1+d)%2?'o':'x');puts("");}}
}

K

状态很少，dp一下即可，考虑每一个cover放在左中右哪个盒子上，注意不能和上一个cover交错放，要不然可能放在了上上个帽子上。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010int n,m,a[maxn],pos[maxn];
long long f[maxn][3];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(x)pos[++m]=i;}if(!m){printf("0");return 0;}for(int i=0;i<3;i++)f[1][i]=a[pos[1]+i-1];for(int i=2;i<=m;i++){for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(pos[i]+k-1>pos[i-1]+j-1)f[i][k]=max(f[i][k],f[i-1][j]+a[pos[i]+k-1]);}long long ans=max(f[m][0],max(f[m][1],f[m][2]));printf("%lld",ans);
}