容易发现 $(a_i-b_i)\bmod m$ 相同的一定可以同时变得一样，而不同的一定不行。
那么计算所有 $(a_i-b_i)\bmod m$，答案就是最大的出现次数。
时间复杂度与空间复杂度均为 $O(n+m)$。
难度约为 $700$ 到 $900$。
#include<bits/stdc++.h> using namespace std; const int maxn=100010; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,m,a[maxn],cnt[maxn],ans; int main(){ n=read();m=read(); FOR(i,1,n) a[i]=read(); FOR(i,1,n) cnt[(a[i]-read()+m)%m]++; FOR(i,0,m-1) ans=max(ans,cnt[i]); printf("%d\n",ans); } View Code瞎扯：想知道这题我的数据是怎么造的吗？上LOJ搜仙人掌，把其中一题的输入数据扣下来作为输入数据！（逃
可以发现如果一条边不在环上，那么是一定要选的。
对于长度为 $l$ 的一个环，生成树个数为 $l$，取决于哪条边不选。
在仙人掌上一条边不会影响多个环，所以环和环之间相互独立。
那么答案就是每个环的长度之积。
具体代码实现可以用栈等来判断，即令一个环只在反祖边处贡献答案。至少我是这么写的
时间复杂度与空间复杂度均为 $O(n+m)$。难度约为 $1400$ 到 $1500$。
#include<bits/stdc++.h> using namespace std; const int maxn=400040,mod=20190601; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,m,el,head[maxn],to[maxn],nxt[maxn],dep[maxn],ans=1; bool ins[maxn]; inline void add(int a,int b){ to[++el]=b;nxt[el]=head[a];head[a]=el; } void dfs(int u,int f){ ins[u]=true; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(v==f) continue; if(dep[v]){ if(ins[v]) ans=1ll*ans*(dep[u]-dep[v]+1)%mod; continue; } dep[v]=dep[u]+1; dfs(v,u); } ins[u]=false; } int main(){ n=read();m=read(); FOR(i,1,m){ int u=read(),v=read(); add(u,v);add(v,u); } dfs(1,0); printf("%d\n",ans); } View Code瞎扯：个人感觉一个比较有趣的题。（或许是迄今为止，甚至可能是整一辈子出过最好的题）
我们考虑把 $a_i$ 减 $1$ 后会发生什么：
根据第一条，$i$ 的怒气值会 $+1$；根据第二条，$i$ 的怒气值要么不变，要么 $+1$；（不变当且仅当 $i=1$ 或者 $a_{i-1}<a_i$）根据第二条，$i+1$（如果有）的怒气值要么不变，要么 $-1$。（$-1$ 当且仅当 $i\ne n$ 且 $a_{i+1}<a_i$）所以总怒气值不会变小。那么不进行减操作总怒气值一定最小。那么 $a_i=l_i$ 时总怒气值一定最小。
现在考虑如何让 $a$ 的和变小。那么就是进行减操作也可以让怒气值不变。
由上面的分析得，当且仅当 $i\ne n$ 且 $a_i>\max(a_{i-1},a_{i+1})$ 时 $a_i$ 可以减。（设 $a_0=0$）
发现相邻的两个数大小关系不会变（即，不会从小于变成大于，但可能变成等于）。那么 $a_i$ 最终一定会变成 $\max(a_{i-1},a_{i+1})$，且操作顺序无关。
注意开long long。时间复杂度与空间复杂度 $O(n)$。
难度约为 $1900$ 到 $2000$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=300030; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,a[maxn]; ll ans; int main(){ n=read(); FOR(i,1,n) a[i]=read(); FOR(i,1,n-1) if(a[i]>a[i+1]) ans+=a[i]-a[i+1]; FOR(i,1,n-1) a[i]=min(a[i],max(a[i-1],a[i+1])); printf("%lld\n",ans); FOR(i,1,n) printf("%d ",a[i]); } View Code本题可能有多种做法。这里讲其中两种。
考虑DP，首先可以想到 $f[i][j]$，前 $i$ 个数，目前用了 $j$ 个背包的最大值。
$f[i][j]=\max(f[k][j-1]+sum(k+1,i)\%p)$。$sum\%p$ 可以用前缀和做到 $O(1)$。
时间复杂度是 $O(n^2k)$，需要优化。
我们设前缀和模 $p$ 为 $s$，那么式子可以重写为 $f[i][j]=\max(f[k][j-1]+(s_i-s_k)\%p)$。
这启示我们把 $s_k$ 相同的分成一类。
具体的，令 $g[i][j]$ 表示对于所有满足 $s_k=j$ 的 $k$，$f[k][i]$ 的最大值。那么 $f[i][j]$ 可以用来更新 $g[j][s_i]$。
那么转移可以写成：$f[i][j]=\max(g[j-1][k]+(s_i-k)\%p)$。
时间复杂度 $O(nkp)$，空间复杂度 $O(nk+kp)$。
有个惊人的地方就是 $f$ 数组完全是多余的，空间复杂度可以做到 $O(kp)$。
发现对于一个背包，我们不关心它的开始在哪，只需要把物品塞到后面就行了。这样可以避免枚举新的背包的开始位置（上面的 $k$）。
那么就有 $f[i][j][k]$，前 $i$ 个数，目前正在装 $j$ 个背包，第 $j$ 个背包的体积是 $k$，前 $j-1$ 个背包的体积之和的最大值。
$f[i][j][k]=f[i-1][j][(k-v_i)\%p]$
$f[i][j][v_i]=\max(f[i-1][j][0],f[i-1][j-1][l]+l)$
答案为 $\max(f[n][j][k]+k)$。
时间复杂度与空间复杂度均为 $O(nkp)$。若使用滚动数组空间复杂度可以做到 $O(kp)$。
难度约为 $2000$ 到 $2100$。
#include<bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,K,p,v[22222],s[22222],g[55][111],ans; int main(){ n=read();K=read();p=read(); FOR(i,1,n) v[i]=read()%p,s[i]=(s[i-1]+v[i])%p; MEM(g,~0x3f);g[0][0]=0; FOR(i,1,n) ROF(j,K,1){ int x=-1e9; FOR(k,0,p-1) x=max(x,g[j-1][k]+(s[i]-k+p)%p); if(i==n) ans=max(ans,x); g[j][s[i]]=max(g[j][s[i]],x); } printf("%d\n",ans); } 第一种做法 #include<bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,K,p,v[22222],cur,f[2][55][111]; int main(){ n=read();K=read();p=read(); FOR(i,1,n) v[i]=read()%p; cur=1; MEM(f,~0x3f); f[0][0][0]=0; FOR(i,1,n){ MEM(f[cur],~0x3f); FOR(j,1,K) FOR(k,0,p-1){ f[cur][j][k]=f[cur^1][j][(k-v[i]+p)%p]; if(k==v[i]) FOR(l,0,p-1) f[cur][j][k]=max(f[cur][j][k],f[cur^1][j-1][l]+l); } cur^=1; } int ans=0; FOR(j,1,K) FOR(k,0,p-1) ans=max(ans,f[cur^1][j][k]+k); printf("%d\n",ans); } 第二种做法我们发现如果两个 $p_i$ 一开始相同，那么它们会一直相同；如果两个 $p_i$ 一开始不同，那么它们会一直不同。
而 troll 停止，当且仅当 $p>x$ 的宿舍全部 troll 过了，其中 $x$ 是出现过两次的数的最大值。
所以答案是：
如果区间中没有出现过两次或更多的数，那么是 $-1$；否则，设出现过两次或更多的数中最大的是 $x$，答案就是大于 $x$，且出现过的数的个数。这个可以用线段树维护。
由于 $0\le p_i\le 50$，可以考虑把区间中出现过至少一次和至少两次的数的集合压成二进制数 $s1,s2$。
pushup时，$s1$ 很简单，$s1=lson.s1|rson.s1$。
对于 $s2$，发现要么在左边有两次，右边有两次，或者左右各有一次。$s2=lson.s2|rson.s2|(lson.s1\&rson.s1)$。
pushdown就更简单了。注意区间的长度，看要不要改 $s2$ 即可。
时间复杂度 $O(n+m(P+\log n))$，空间复杂度 $O(n)$，其中 $P$ 是所有 $p_i$ 的最大值。
难度约为 $2100$ 到 $2300$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1111111; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } struct node{ ll s1,s2; node operator+(const node &nd)const{ node ans; ans.s1=s1|nd.s1; ans.s2=s2|nd.s2|(s1&nd.s1); return ans; } }seg[maxn]; int n,m,p[maxn],tag[maxn]; void pushdown(int o,int l,int r){ if(~tag[o]){ int mid=(l+r)>>1; tag[o<<1]=tag[o]; seg[o<<1].s1=1ll<<tag[o]; if(l!=mid) seg[o<<1].s2=1ll<<tag[o]; else seg[o<<1].s2=0; tag[o<<1|1]=tag[o]; seg[o<<1|1].s1=1ll<<tag[o]; if(mid+1!=r) seg[o<<1|1].s2=1ll<<tag[o]; else seg[o<<1|1].s2=0; tag[o]=-1; } } void build(int o,int l,int r){ tag[o]=-1; if(l==r) return void(seg[o]=(node){1ll<<p[l],0}); int mid=(l+r)>>1; build(lson);build(rson); seg[o]=seg[o<<1]+seg[o<<1|1]; } void update(int o,int l,int r,int ql,int qr,int v){ if(l>=ql && r<=qr){ tag[o]=v; seg[o].s1=1ll<<v; if(l!=r) seg[o].s2=1ll<<v; else seg[o].s2=0; return; } pushdown(o,l,r); int mid=(l+r)>>1; if(mid>=ql) update(lson,ql,qr,v); if(mid<qr) update(rson,ql,qr,v); seg[o]=seg[o<<1]+seg[o<<1|1]; } node query(int o,int l,int r,int ql,int qr){ if(l>=ql && r<=qr) return seg[o]; pushdown(o,l,r); int mid=(l+r)>>1; if(mid<ql) return query(rson,ql,qr); if(mid>=qr) return query(lson,ql,qr); return query(lson,ql,qr)+query(rson,ql,qr); } int main(){ n=read();m=read(); FOR(i,1,n) p[i]=read(); build(1,1,n); FOR(i,1,m){ int op=read(),x=read(),y=read(); if(op==1) update(1,1,n,x,y,read()); else{ node ans=query(1,1,n,x,y); int cnt=0;bool flag=false; ROF(i,50,0){ if((ans.s2>>i)&1){flag=true;break;} else if((ans.s1>>i)&1) cnt++; } printf("%d\n",flag?cnt:-1); } } } View Code转载于:https://www.cnblogs.com/1000Suns/p/10724007.html
