牛客练习赛68题解
A:牛牛的mex
题目要求一个区间的mex，可以离线，我们可以莫队维护。
需要注意的是，因为我们要的是根号算法，不能带log，因此我们搞两个分块，一个是莫队的，一个是值域的。
可以做到插入是O(1)的，单次查询是O(sqrt(n))的，就可以通过，总时间复杂度O(nsqrt(n))
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5,B=355;
struct node{int l,r,id;}b[N];
int n,q,cntB,a[N],s[N],cnt[N],bl[N],L[N],R[N],ans[N];
void ins(int x){
if(!x){cnt[0]++;return;}
cnt[x]++;if(cnt[x]==1)s[bl[x]]++;
}
void del(int x){
if(!x){cnt[0]--;return;}
cnt[x]--;if(!cnt[x])s[bl[x]]--;
}
int mex(){
if(!cnt[0])return 0;
for(int i=1;i<=cntB;i++)if(s[i]!=R[i]-L[i]+1){
for(int j=L[i];j<=R[i];j++)if(!cnt[j])return j;
}
return -1;
}
bool cmp(node a,node b){return bl[a.l]!=bl[b.l]?bl[a.l]<bl[b.l]:a.r<b.r;}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<N;i++)bl[i]=(i-1)/B+1;
cntB=bl[n];for(int i=1;i<=cntB;i++)L[i]=(i-1)*B+1,R[i]=min(i*B,N-1);
for(int i=1;i<=q;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
sort(b+1,b+q+1,cmp);
for(int i=1,L=1,R=0;i<=q;i++){
while(L>b[i].l)ins(a[--L]);
while(R<b[i].r)ins(a[++R]);
while(L<b[i].l)del(a[L++]);
while(R>b[i].r)del(a[R--]);
ans[b[i].id]=mex();
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
return 0;
}
B:牛牛的算术
这题的模数很小，我们发现大于等于模数的情况都是0，那么我们只需要考虑剩余的情况。
发现这是一个可以递推两次求出来的，
我们先求一个1..i的和，然后再相加，接着相乘就可以。
然后这题我们就可以分部，特判一下较大的情况，剩余递推。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5,P=199999;
int n,f[N],ans[N];char str[N];
int sum(int x){return (LL)x*(x+1)/2LL%P;}
int main(){
for(int i=1;i<N;i++)f[i]=(f[i-1]+(LL)i*sum(i)%P)%P;
ans[0]=1;for(int i=1;i<N;i++)ans[i]=(LL)ans[i-1]*f[i]%P*i%P;
int T;scanf("%d",&T);
while(T--){
scanf("%s",str+1);
int l=strlen(str+1),res=0;bool fl=false;
for(int i=1;i<=l;i++){
res=res*10+str[i]-'0';
if(res>=P){fl=true;res%=P;}
}
if(fl)puts("0");else printf("%d\n",ans[res]);
}
return 0;
}C:牛牛的无向图
这个套路好像经常考，特别是codeforces上的。
我们考虑路径上的最大值，我们可以考虑转化为我们按照边权排序，然后用并查集维护连通性。
这样我们可以利用并查集的size求出点对的个数。
这题我们直接把边权和查询放在一起，排个序，然后并查集维护就可以，我们注意边权相同的情况，我们要先处理加边再查询。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
struct node{int u,v,w;}e[N];
int tot,fa[N],sz[N];
unsigned int SA, SB, SC; int n, m, q, LIM;
unsigned int rng61(){
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM);
for(int i = 1; i <= m; i++){
e[i].u = rng61() % n + 1;
e[i].v = rng61() % n + 1;
e[i].w = rng61() % LIM;
}
tot=m;
for(int i = 1; i <= q; i++){
e[++tot].w = rng61() % LIM;
e[tot].u=e[tot].v=-i;
}
}
bool cmp(node a,node b){return a.w!=b.w?a.w<b.w:a.u>b.u;}
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
int main(){
gen();for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
sort(e+1,e+tot+1,cmp);
LL res=0,ans=0;
for(int i=1,u,v,ru,rv;i<=tot;i++)if(e[i].u>0){
u=e[i].u;v=e[i].v;ru=find(u);rv=find(v);
if(ru!=rv)res+=(LL)sz[ru]*sz[rv],fa[rv]=ru,sz[ru]+=sz[rv];
}else ans^=res;//printf("%d %lld\n",-e[i].u,res);
printf("%lld\n",ans);
return 0;
}D:牛牛的粉丝
首先我们考虑暴力dp，是O(nk)的，
紧接着我们发现n还不是特别大，我们可以对于这个n下手，然后想办法用倍增或者矩乘等类似方法把这个k降下来，降到大概log的复杂度，通常这种数据范围是这种套路。
这是我们已经有了一种暴力矩乘的方法，但是因为n至少是三方的，所以这题n=500不能接受。
于是我们观察，发现如果从i移到了j和从i+1移到了j+1是等价的，这样我们发现其实只和他们的移动的距离有关系（这里注意方向，是不等价的，也就是说向左和向右是不同的），那么由于这个距离是O(n)级别的，因此我们把这个矩乘优化到了平方的级别，可以通过。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=505,P=998244353;
int n,a,b,c,s,inv,pa,pb,pc,v[N],cv[N],mat[75][N][N],r[N<<1];LL k;bool usd[N<<1];
LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=(LL)x*x%P)if(y&1)res=(LL)res*x%P;return res;}
int main(){
scanf("%d%lld",&n,&k);scanf("%d%d%d",&a,&b,&c);
s=a+b+c;inv=qpow(s,P-2);
pa=(LL)a*inv%P;pb=(LL)b*inv%P;pc=(LL)c*inv%P;
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
//assert((k<=1e8&&(double)n*k<=4e8)||(double)n*n*n*log(k)<=8e8);
for(int i=1,pk,sk;i<=n;i++)
pk=i==1?n:i-1,sk=i==n?1:i+1,mat[0][pk][i]=pa,mat[0][i][i]=pc,mat[0][sk][i]=pb;
int lg=(int)log2(k)+1;assert((1LL<<lg)>=k);
for(int t=1;t<=lg;t++){
memset(usd,false,sizeof(usd));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!usd[j-i+n]){
usd[j-i+n]=true;
for(int k=1;k<=n;k++)mat[t][i][j]=(mat[t][i][j]+(LL)mat[t-1][i][k]*mat[t-1][k][j]%P)%P;
r[j-i+n]=mat[t][i][j];
}else mat[t][i][j]=r[j-i+n];
//printf("jz:%d\n",t);
//for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)printf("%d%c",mat[t][i][j]," \n"[j==n]);
}
for(LL t=0;t<=lg;t++)if(k&(1LL<<t)){
memset(cv,0,sizeof(cv));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cv[i]=(cv[i]+(LL)v[j]*mat[t][j][i]%P)%P;
for(int i=1;i<=n;i++)v[i]=cv[i];
}
for(int i=1;i<=n;i++)printf("%d%c",v[i]," \n"[i==n]);
return 0;
}E:牛牛的字符串
考试的时候发现这题稍微不太劣的暴力能过，也就是我们写一个暴力dp，然后发现这题的性质是我们i的转移是j
存在以j结尾的划分方案，并且这个j最大。
于是我们可以暴力dp，然后字符串hash判断是否回文，这个也可以用manacher来实现。
先给出暴力代码：
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
const ULL base=1e9+7;
int n,dp[N],pre[N];char str[N];
ULL phs[N],shs[N],pw[N];
vector<pii>v;
bool check(int l,int r){
return phs[r]-phs[l-1]*pw[r-l+1]==shs[l]-shs[r+1]*pw[r-l+1];
}
int main(){
scanf("%s",str+1);n=strlen(str+1);
for(int i=1;i<=n;i++)phs[i]=phs[i-1]*base+str[i];
for(int i=n;i;i--)shs[i]=shs[i+1]*base+str[i];
pw[0]=1;for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base;
memset(dp,-0x3f,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++)for(int j=i;j>=1;j--)if(dp[j-1]>=0&&!check(j,i)){
if(dp[i]<dp[j-1]+1){dp[i]=dp[j-1]+1;pre[i]=j-1;break;}
}
if(dp[n]<0){puts("-1");return 0;}
int now=n;
while(now)v.pb(pii(pre[now]+1,now)),now=pre[now];
reverse(v.begin(),v.end());
printf("%d\n",(int)v.size());
for(auto x:v){
for(int i=x.first;i<=x.second;i++)printf("%c",str[i]);puts("");
}
return 0;
}比赛结束以后，思索为什么这个暴力为什么能过呢？
首先我们显然是找到合法的过程很快，所以暴力能过。
但是这个合法具体是什么呢？
我们举个例子
比如串是aabbccdd，我们显然如果转移过来的到当前只有一种字符显然是不行的，因为只有一种字符肯定是回文。
然后我们发现存在两种字符交替，比如是bbcc这样的一定不是回文，而且我们只会bbcc怎么转移，不会aabbcc，因为我们发现aabbcc肯定没有bbcc优。
有人可能会问？
aabbaa呢？
那这也是有两种字符，但是它是回文，不能转移欸。
我们发现bbaa肯定比aabbaa优，我们可以无视那种情况。
因此我们bbaa只会在bbaa和baa里面选，也就是a前面的字符的那个长度的里面的任意一个转移点。
然后这个就很好处理了，我们直接有线段树维护即可。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5,Inf=1e9;
int n,dp[N],trs[N],id[N<<2],pre[N];char str[N];
int Cmp(int x,int y){return dp[x]>dp[y]?x:y;}
void build(int rt,int l,int r){
if(l==r){id[rt]=l;return;}
int mid=(l+r)>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
id[rt]=Cmp(id[rt<<1],id[rt<<1|1]);
}
void change(int rt,int l,int r,int x){
if(l==r)return;
int mid=(l+r)>>1;
(x<=mid)?change(rt<<1,l,mid,x):change(rt<<1|1,mid+1,r,x);
id[rt]=Cmp(id[rt<<1],id[rt<<1|1]);
}
int ask(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return id[rt];
int mid=(l+r)>>1;
if(R<=mid)return ask(rt<<1,l,mid,L,R);
if(L>mid)return ask(rt<<1|1,mid+1,r,L,R);
return Cmp(ask(rt<<1,l,mid,L,R),ask(rt<<1|1,mid+1,r,L,R));
}
void print(int x){
if(trs[x])print(trs[x]);
for(int i=trs[x]+1;i<=x;i++)printf("%c",str[i]);
puts("");
}
int main(){
scanf("%s",str+1);n=strlen(str+1);
for(int i=1;i<=n;i++)dp[i]=-Inf;
build(1,0,n);
for(int i=1;i<=n;i++)if(str[i]!=str[i-1])pre[i]=i;else pre[i]=pre[i-1];
for(int i=1,x;i<=n;i++)if(pre[i]!=1)
x=pre[i]-1,trs[i]=ask(1,0,n,pre[x]-1,x-1),dp[i]=dp[trs[i]]+1,change(1,0,n,i);
if(dp[n]<=0)puts("-1");else printf("%d\n",dp[n]),print(n);
return 0;
}F待补，作者还不太会...见谅
查看9道真题和解析