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待补,作者还不太会...见谅