###
Codeforces1142B
循环位移相关问题，我们记录一下值的链接关系
然后对于每一个$l$，求出包含循环位移的最小右端点$r$，然后就可以$O(1)$回答询问了
我们从后往前扫，把当前值看成匹配循环位移的第一个，倍增找答案，然后与上一个取min就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 200010 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; int n,m,Q,a[MAXN],p[MAXN],Pos[MAXN],Next[MAXN],Ans[MAXN],f[MAXN][25]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } int main(){ n=read(); m=read(); Q=read(); Ans[m+1]=m+1; for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=m;++i) p[i]=read(); for(int i=1;i<=n;++i) Next[a[i-1]]=a[i];Next[a[n]]=a[1]; for(int i=1;i<=n;++i) Pos[i]=m+1; for(int i=m;i>=1;--i){ f[i][0]=Pos[Next[p[i]]]; Pos[p[i]]=i; for(int k=0;k<=20;++k) f[m+1][k]=m+1; for(int k=1;k<=20;++k) f[i][k]=f[f[i][k-1]][k-1]; int Step=n-1; Ans[i]=i; for(int k=20;k>=0;--k)if(Step>=(1<<k)) Step-=(1<<k),Ans[i]=f[Ans[i]][k]; cmin(Ans[i],Ans[i+1]); } for(int i=1;i<=Q;++i){ int l=read(),r=read(); printf(Ans[l]<=r?"1":"0"); } return 0; }
|
Codeforces1139D
有趣的概率问题，比赛时脑残了一直WA
正常做的话思路还是比较简单的，Tutorial评论区给出了奇妙的Mobius做法
我们知道答案是$$E(gcd(a_i)>1)+1$$但是这个期望不太好算的样子
我们尝试计算$E_k(k|a_i)$，那么$$E(gcd(a_i)>1)=\sum_{k=1}^{m}-\mu(k)E_k(k|a_i)$$
为什么这个式子成立？其实就是一个容斥，贡献系数与Mobius函数有关
那么接下来就是计算$E_k(k|a_i)$的问题了，设$P_k=P(k|rand())=\frac{\left\lfloor m/k \right\rfloor}{m}$，那么$$E_k(k|a_i)=\sum_{n=1}^{+\infty}nP_{k}^{n}(1-P_k)=\frac{P_k}{1-P_k}$$
注：$$\sum_{n=1}^{+\infty}nx^n(1-x)=x\sum_{n=1}^{+\infty}{(x^{n})}’-x^2\sum_{n=1}^{+\infty}{(x^{n})}’=(x-x^2){(\sum_{n=1}^{+\infty}x^n)}’=x(1-x){(\frac{x}{1-x})}’=\frac{x}{1-x}$$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 100010 #define cadd(a,b) a=add(a,b) #define csub(a,b) a=sub(a,b) #define cmul(a,b) a=mul(a,b) using namespace std; const int mod=1e9+7; int m,cnt,Ans,mu[MAXN],check[MAXN],prime[MAXN/10]; inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;} inline int sub(int a,int b){return (a-=b)<0?a+mod:a;} inline int mul(int a,int b){return 1LL*a*b%mod;} inline int Pow(int a,int b){ int ret=1; while(b){ if(b&1) cmul(ret,a); cmul(a,a); b>>=1; }return ret; } inline int inv(int a){return Pow(a,mod-2);} void Init(){ int N=m; Ans=1; for(int i=2;i<=N;++i){ if(!check[i]) prime[++cnt]=i,mu[i]=sub(0,1); for(int j=1;j<=cnt&&prime[j]*i<=N;++j){ check[prime[j]*i]=1; if(i%prime[j]==0) break; mu[prime[j]*i]=sub(0,mu[i]); } }mu[1]=1; } int main(){ scanf("%d",&m); Init(); for(int i=1;i<=m;++i){ int P=mul(m/i,inv(m)); csub(Ans,mul(mu[i],mul(P,inv(sub(1,P))))); } printf("%d\n",Ans); return 0; }
|
Codeforces1139E
倒着做删除就变成了添加，每个$p_i$向$c_i$连边，问题就变成了一个匹配问题
由于是求最大的$mex$，我们从0开始匹配，直到匹配不上为止就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 5010 using namespace std; int n,m,d,p[MAXN],c[MAXN],del[MAXN],vis[MAXN],Mat[MAXN],Ans[MAXN]; vector<int>G[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } inline bool Match(int x){ if(vis[x]) return 0; vis[x]=1; for(int i=0;i<G[x].size();++i){ int y=G[x][i]; if(Mat[y]==-1||Match(Mat[y])){ Mat[y]=x; return 1; } } return 0; } int main(){ n=read(); m=read(); int cur=0; for(int i=1;i<=n;++i) p[i]=read(); for(int i=1;i<=n;++i) c[i]=read(); d=read(); for(int i=1;i<=d;++i){ del[i]=read(); vis[del[i]]=1; } for(int i=1;i<=n;++i) if(!vis[i]) G[p[i]].push_back(c[i]); memset(Mat,-1,sizeof(Mat)); for(int i=d;i>=1;--i){ while(1){ memset(vis,0,sizeof(vis)); if(Match(cur)) ++cur; else break; } G[p[del[i]]].push_back(c[del[i]]); Ans[i]=cur; } for(int i=1;i<=d;++i) printf("%d\n",Ans[i]); return 0; }
|
Codeforces1136E
题目中的判断条件可以搞一搞
$$a_{i+1}<a_{i}+k_{i}\Leftrightarrow a_{i+1}-a_{i}<k_{i}$$
我们想办法把右边化成和左边一样的形式，很容易想到前缀和之差
$$a_{i+1}-a_{i}<Sumk_{i+1}-Sumk_{i}$$
我们用线段树维护$b_{i}=a_{i}+Sumk_{i-1}$
那么修改就相当于在该点右端找到第一个大于$b_{i}$的数，然后区间覆盖
这份代码在CF上跑了第一（我的线段树什么时候这么优秀了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 100010 using namespace std; typedef long long ll; const ll INF=1e18; struct Segment_Tree{ ll sum,maxx,tag; Segment_Tree(){tag=-INF;} }tr[MAXN<<2]; ll n,Q,a[MAXN],b[MAXN],c[MAXN],S[MAXN],K[MAXN]; inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } inline void relord(int p){ tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum; tr[p].maxx=max(tr[p<<1].maxx,tr[p<<1|1].maxx); } inline void pushdown(int p,int l,int r){ int mid=(l+r)>>1; if(tr[p].tag!=-INF){ tr[p<<1].tag=tr[p<<1|1].tag=tr[p].tag; tr[p<<1].maxx=tr[p<<1|1].maxx=tr[p].tag; tr[p<<1].sum=tr[p].tag*(mid-l+1); tr[p<<1|1].sum=tr[p].tag*(r-mid); } tr[p].tag=-INF; } inline void build(int p,int l,int r){ if(l==r){ tr[p].sum=tr[p].maxx=b[l]; return; }int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); relord(p); } inline int find(int p,int l,int r,int x,int y,ll v){ if(l==r) return l; int mid=(l+r)>>1; pushdown(p,l,r); if(x<=mid&&tr[p<<1].maxx>=v) return find(p<<1,l,mid,x,y,v); else if(y>mid&&tr[p<<1|1].maxx>=v) return find(p<<1|1,mid+1,r,x,y,v); else return n+1; } inline void modify(int p,int l,int r,int x,int y,ll v){ if(x<=l&&y>=r){ tr[p].tag=tr[p].maxx=v; tr[p].sum=v*(r-l+1); return; }int mid=(l+r)>>1; pushdown(p,l,r); if(x<=mid) modify(p<<1,l,mid,x,y,v); if(y>mid) modify(p<<1|1,mid+1,r,x,y,v); relord(p); } inline ll query(int p,int l,int r,int x,int y){ if(x<=l&&y>=r) return tr[p].sum; int mid=(l+r)>>1;ll Ans=0; pushdown(p,l,r); if(x<=mid) Ans+=query(p<<1,l,mid,x,y); if(y>mid) Ans+=query(p<<1|1,mid+1,r,x,y); return Ans; } inline void Add(int x,ll v){ ll Value=query(1,1,n,x,x)+v; int r=find(1,1,n,x+1,n,Value)-1; modify(1,1,n,x,r,Value); } inline void Sum(int x,int y){ printf("%I64d\n",query(1,1,n,x,y)+S[y-1]-S[x-2]); } int main(){ n=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<n;++i) K[i]=read(); for(int i=1;i<=n;++i) c[i]=c[i-1]+K[i]; for(int i=1;i<=n;++i) b[i]=a[i]-c[i-1]; for(int i=1;i<=n;++i) S[i]=S[i-1]+c[i]; build(1,1,n); Q=read(); for(int i=1;i<=Q;++i){ char ch[3]; scanf("%s",ch); int x=read(),y=read(); if(ch[0]=='+') Add(x,y); else if(ch[0]=='s') Sum(x,y); else puts("出题人SB"); } return 0; }
|
Codeforces2B
末尾0的数量分开考虑乘积中2和5的贡献，取较小的就是答案
矩阵中有0的情况得单独考虑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 1010 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; const int INF=1e9; int n,sx,sy,a[MAXN][MAXN],b[MAXN][MAXN],f[MAXN][MAXN][2]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } void solve(int x,int y){ puts("1"); for(int i=1;i<x;++i) putchar('D'); for(int i=1;i<y;++i) putchar('R'); for(int i=x;i<n;++i) putchar('D'); for(int i=y;i<n;++i) putchar('R'); } void solve(int x,int y,int id){ if(x==1&&y==1) return; else if(x==1) solve(x,y-1,id),putchar('R'); else if(y==1) solve(x-1,y,id),putchar('D'); else if(f[x-1][y][id]<f[x][y-1][id]) solve(x-1,y,id),putchar('D'); else solve(x,y-1,id),putchar('R'); } int main(){ n=read(); int Flag=0; memset(f,10,sizeof(f)); for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){ int x=read(); if(!x){ a[i][j]=b[i][j]=INF; Flag=1; sx=i; sy=j; continue; } while(x%2==0) ++a[i][j],x/=2; while(x%5==0) ++b[i][j],x/=5; } f[1][1][0]=a[1][1]; f[1][1][1]=b[1][1]; for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){ cmin(f[i+1][j][0],f[i][j][0]+a[i+1][j]); cmin(f[i][j+1][0],f[i][j][0]+a[i][j+1]); cmin(f[i+1][j][1],f[i][j][1]+b[i+1][j]); cmin(f[i][j+1][1],f[i][j][1]+b[i][j+1]); } if(Flag&&min(f[n][n][0],f[n][n][1])) solve(sx,sy); else if(f[n][n][0]<f[n][n][1]){ printf("%d\n",f[n][n][0]); solve(n,n,0); } else{ printf("%d\n",f[n][n][1]); solve(n,n,1); } return 0; }
|
Codeforces607B
这种删除游戏还是挺有意思的
设$f[l][r]$表示删除区间$[l,r]$的答案，那么分情况讨论
左端点单独删除$f[l][r]=f[l+1][r]+1$
左端点与相邻位置颜色相同可以一起删除$f[l][r]=f[l+2][r]+1$
找到一个与左端点颜色相同的位置$k$，左端点与位置$k$随区间$[l+1,k-1]$一起删除，$f[l][r]=f[l+1][k-1]+f[k+1][r]$
记忆化搜索无脑实现即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<bits/stdc++.h> #define FILE "read" #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; int n,S[505],f[505][505]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } int solve(int l,int r){ if(l>r) return 0; if(l==r) return 1; if(f[l][r]!=-1) return f[l][r]; f[l][r]=solve(l+1,r)+1; if(S[l]==S[l+1]) cmin(f[l][r],solve(l+2,r)+1); for(int k=l+2;k<=r;++k)if(S[l]==S[k]) cmin(f[l][r],solve(l+1,k-1)+solve(k+1,r)); return f[l][r]; } int main(){ n=read(); memset(f,-1,sizeof(f)); for(int i=1;i<=n;++i) S[i]=read(); printf("%d\n",solve(1,n)); return 0; }
|
Codeforces1137C
我们把每个点建成$(x,k)$，表示第$k$天的第$x$个城市，连边的话就是$(x,k)\rightarrow(y,k+1)$
我们发现一个强连通分量中所有的状态都能到达，并且对于同一个城市$x$，若$(x,i),(x,j)$有边相连，则他们必然在同一个SCC中
这样的话求一下SCC，然后统计SCC中能到达的不同博物馆个数
然后在缩点后的图上按拓扑序统计答案就行了
刚开始写的vector存图一直MLE，后来发现边数有玄机
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 5001000 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; int n,m,D,len,bcnt,dfs_clock,dfn[MAXN],low[MAXN],rk[MAXN],bl[MAXN],val[MAXN],Ans[MAXN],In[MAXN],vis[MAXN];char ch[55]; struct Edge{int y,next;}e[MAXN<<1]; struct Graph{ int Link[MAXN]; void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;} }G,SCC; stack<int>S;queue<int>q; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } inline int Id(int x,int k){return x*D+k;} void Tarjan(int x){ dfn[x]=low[x]=++dfs_clock; vis[x]=1; S.push(x); for(int i=G.Link[x];i;i=e[i].next){ int y=e[i].y; if(!dfn[y]){ Tarjan(y); cmin(low[x],low[y]); } else if(vis[y]) cmin(low[x],dfn[y]); } if(dfn[x]==low[x]){ ++bcnt; int ret; do{ ret=S.top(); S.pop(); vis[ret]=0; bl[ret]=bcnt; }while(ret!=x); } } void Topsort(){ for(int i=1;i<=bcnt;++i)if(!In[i])q.push(i); while(!q.empty()){ int x=q.front(); q.pop(); rk[++rk[0]]=x; for(int i=SCC.Link[x];i;i=e[i].next) if(--In[e[i].y]==0) q.push(e[i].y); } for(int k=bcnt;k;--k){ int x=rk[k]; for(int i=SCC.Link[x];i;i=e[i].next) cmax(Ans[x],Ans[e[i].y]); Ans[x]+=val[x]; } } int main(){ n=read(); m=read(); D=read(); for(int i=1;i<=m;++i){ int x=read(),y=read(); for(int k=0;k<D;++k) G.insert(Id(x,k),Id(y,(k+1)%D)); } for(int i=1;i<=n*D;++i)if(!dfn[i])Tarjan(i); for(int i=1;i<=n;++i){ scanf("%s",ch); for(int k=0;k<D;++k){ int x=Id(i,k); if(ch[k]=='1'&&!vis[bl[x]])++val[bl[x]],vis[bl[x]]=1; for(int j=G.Link[x];j;j=e[j].next){ int y=e[j].y; if(bl[x]!=bl[y]){ SCC.insert(bl[x],bl[y]); ++In[bl[y]]; } } } for(int k=0;k<D;++k)vis[bl[Id(i,k)]]=0; } Topsort(); printf("%d\n",Ans[bl[Id(1,0)]]); return 0; }
|
Codeforces1100D
我们先把国王移到棋盘的正中央$(500,500)$，然后棋盘被划分为了四个象限
我们发现除去车的数量最少的那个象限，其余三个象限中车的数量大于等于$666\times\frac{3}{4}=499.5$
那么国王朝着最少象限反方向沿对角线移动499步，必然存在一个车来不及逃跑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<bits/stdc++.h> using namespace std; struct Point{int x,y;}S,a[705]; int K,D,cnt[5],vis[1010][1010]; void move(int dx,int dy){ S.x+=dx; S.y+=dy; if(vis[S.x][S.y]) S.x-=dx; printf("%d %d\n",S.x,S.y); fflush(stdout); int k,x,y; scanf("%d%d%d",&k,&x,&y); if(k==-1) exit(0); vis[a[k].x][a[k].y]=0; a[k]=(Point){x,y}; vis[a[k].x][a[k].y]=1; } int main(){ scanf("%d%d",&S.x,&S.y); K=666; for(int i=1;i<=K;++i){ scanf("%d%d",&a[i].x,&a[i].y); vis[a[i].x][a[i].y]=1; } while(S.x<500) move(1,0); while(S.x>500) move(-1,0); while(S.y<500) move(0,1); while(S.y>500) move(0,-1); for(int i=1;i<=K;++i) ++cnt[((a[i].x<500)<<1)+(a[i].y<500)]; for(int i=0;i<=3;++i) if(cnt[i]<cnt[D]) D=i; while(1) move(D/2?1:-1,D%2?1:-1); return 0; }
|
Codeforces1132G
先用单调栈算出每个位置右边第一个比它大的数字的位置，然后连单向边
连完之后出现了一棵森林，我们把每棵树的根连向一个超级根构成一棵树
这样的话，每次相当于给一段连续的点染色，求最长的全部染过色的链
由题目的性质我们发现如果$v$是$u$的父亲且$v,u$都被染上色了，那么它们路径上的点一定也是被染过色的
这样的话我们可以如下操作：
每给一个点染色，就把以它为根的子树权值全部加一
取消染色，就把以它为根的子树权值全部减一
那么询问的答案就是所有点中点权的最大值
这样的操作显然可以用线段树维护DFS序实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 1000010 using namespace std; int n,K,dfs_clock,top,root,a[MAXN],st[MAXN],Tin[MAXN],Tout[MAXN],tr[MAXN<<2],tag[MAXN<<2]; vector<int>e[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } void Euler_Tour(int x){ Tin[x]=++dfs_clock; for(int i=0;i<e[x].size();++i) Euler_Tour(e[x][i]); Tout[x]=dfs_clock; } void pushdown(int p){ if(tag[p]){ tr[p<<1]+=tag[p]; tr[p<<1|1]+=tag[p]; tag[p<<1]+=tag[p]; tag[p<<1|1]+=tag[p]; }tag[p]=0; } void modify(int p,int l,int r,int x,int y,int v){ if(x<=l&&y>=r){ tr[p]+=v; tag[p]+=v; return; }int mid=(l+r)>>1; pushdown(p); if(x<=mid) modify(p<<1,l,mid,x,y,v); if(y>mid) modify(p<<1|1,mid+1,r,x,y,v); tr[p]=max(tr[p<<1],tr[p<<1|1]); } int main(){ n=read(); K=read(); root=n+1; for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=n;++i){ while(top&&a[st[top]]<a[i]) e[i].push_back(st[top--]); st[++top]=i; } while(top) e[root].push_back(st[top--]); Euler_Tour(root); for(int i=1;i<K;++i) modify(1,1,root,Tin[i],Tout[i],1); for(int i=K;i<=n;++i){ modify(1,1,root,Tin[i],Tout[i],1); printf("%d ",tr[1]); modify(1,1,root,Tin[i-K+1],Tout[i-K+1],-1); } return 0; }
|
Codeforces1132F
简单的区间dp问题，设$f[l][r]$表示区间$[l,r]$的答案，那么有两种转移
单独删除左端点字符，$f[l][r]=f[l+1][r]+1$
左端点字符和区间中另外一个相同字符一起删除，$f[l][r]= min(f[l+1][k-1],f[k][r])(s[l]==s[k])$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 555 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) const int INF=1e9; using namespace std; int n,f[MAXN][MAXN]; char S[MAXN]; inline int solve(int l,int r){ if(l>r) return 0; if(l==r) return 1; if(f[l][r]!=INF) return f[l][r]; f[l][r]=solve(l+1,r)+1; for(int k=l+1;k<=r;++k)if(S[k]==S[l]) cmin(f[l][r],solve(l+1,k-1)+solve(k,r)); return f[l][r]; } int main(){ scanf("%d%s",&n,S+1); for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=INF; printf("%d\n",solve(1,n)); return 0; }
|
Codeforces1132E
很妙的一道题，设$L=lcm(1,2,3,4,5,6,7,8)=840$
假设权值为$i$的选了$c_i$个，那么我们可以用$p_i$个$L$和$q_i$个$i$来代替这$ic_i$的贡献，即$$ic_i=p_iL+iq_i$$
这样的话我们就可以把$L$的贡献单独考虑，状态数大大减少
设$dp[i][j]$表示考虑前$i$个权值为$j$，额外选出$L$的贡献的个数的最大值
转移完成后统计$L$的贡献即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<bits/stdc++.h> #define FILE "read" #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; typedef long long ll; const ll L=840; ll W,Ans,cnt[9],dp[9][6725]; inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } int main(){ memset(dp,-1,sizeof(dp)); W=read(); dp[0][0]=0; for(int i=1;i<=8;++i) cnt[i]=read(); for(int i=0;i<8;++i)for(int j=0;j<L*8;++j){ if(dp[i][j]<0) continue; for(int k=0;k<=min(L/(i+1)-1,cnt[i+1]);++k) cmax(dp[i+1][j+(i+1)*k],dp[i][j]+(cnt[i+1]-k)/(L/(i+1))); } for(int i=0;i<L*8;++i)if(dp[8][i]>=0&&i<=W) cmax(Ans,i+L*min(dp[8][i],(W-i)/L)); printf("%I64d\n",Ans); return 0; }
|
Codeforces1132D
二分一下然后判断是否能够完成比赛
对于每个选手计算出需要充电的时刻统计出该时刻需要充电次数的前缀和就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 200010 using namespace std; typedef long long ll; const ll INF=1e18; ll n,K,a[MAXN],b[MAXN],cnt[MAXN]; inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } bool check(ll mid){ for(int i=1;i<=K;++i)cnt[i]=0; for(int i=1;i<=n;++i){ ll sum=a[i],Pos=sum/b[i]+1; if(!b[i]) continue; while(Pos<K){ ++cnt[Pos]; sum+=mid; if(cnt[Pos]>Pos) return 0; Pos=sum/b[i]+1; } } for(int i=1;i<=K;++i)cnt[i]+=cnt[i-1]; for(int i=1;i<=K;++i)if(cnt[i]>i)return 0; return 1; } int main(){ n=read(); K=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<=n;++i)b[i]=read(); ll l=0,r=INF; while(l+1<r){ ll mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid; } if(check(l)) printf("%I64d\n",l); else if(check(r)) printf("%I64d\n",r); else puts("-1"); return 0; }
|
Codeforces1117D
打Round时脑残了，一直在推组合数求和GG
其实就是个脑残dp，$g[n]=g[n-1]+g[n-m]$，矩阵乘法优化一下即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include<bits/stdc++.h> #define FILE "read" #define cadd(a,b) a=add(a,b) #define csub(a,b) a=sub(a,b) #define cmul(a,b) a=mul(a,b) using namespace std; typedef long long ll; const int mod=1e9+7; inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;} inline int sub(int a,int b){return (a-=b)<0?a+mod:a;} inline int mul(int a,int b){return 1LL*a*b%mod;} struct Matrix{ int L,R,a[105][105]; Matrix(){memset(a,0,sizeof(a));} inline Matrix operator*(const Matrix &b){ Matrix ret; ret.L=L; ret.R=b.R; for(int i=1;i<=L;++i)for(int j=1;j<=b.R;++j) for(int k=1;k<=R;++k) cadd(ret.a[i][j],mul(a[i][k],b.a[k][j])); return ret; } }Trans,First,Ans; int main(){ ll n; int m; scanf("%I64d%d",&n,&m); for(int i=1;i<m;++i) Trans.a[i][i+1]=1; for(int i=1;i<=m;++i) First.a[i][1]=1; for(int i=1;i<=m;++i) Ans.a[i][i]=1; Trans.a[m][1]=1;Trans.L=m;First.L=m;Ans.L=m; Trans.a[m][m]=1;Trans.R=m;First.R=1;Ans.R=m; while(n){ if(n&1) Ans=Ans*Trans; n>>=1; Trans=Trans*Trans; } Ans=Ans*First; printf("%d\n",Ans.a[1][1]); return 0; }
|
Codeforces1100F
区间子序列最大异或和问题，这个数据范围线段树是跪了
考虑离线处理，询问按右端点排序，在线性基中插数的时候保留位置
显然这个位置越靠后越优，遇到这种情况就交换基中的数
回答询问时，基中数的位置大于询问左端点时对答案有贡献
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 500010 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; struct Query{ int l,r,id; inline bool operator<(const Query &b)const{return r<b.r;} }Q[MAXN]; int n,m,L,b[55],pos[55],a[MAXN],Ans[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int P){ for(int i=L;i>=0;--i)if(x>>i&1){ if(b[i]){ if(P>pos[i]) swap(b[i],x),swap(pos[i],P); x^=b[i]; } else{ b[i]=x; pos[i]=P; break; } } } int query(int x){ int ret=0; for(int i=L;i>=0;--i)if(pos[i]>=x)cmax(ret,ret^b[i]); return ret; } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); L=20; for(int i=1;i<=n;++i) a[i]=read(); m=read(); for(int i=1;i<=m;++i){ int l=read(),r=read(); Q[i]=(Query){l,r,i}; } sort(Q+1,Q+m+1); int now=1; for(int i=1;i<=m;++i){ while(now<=Q[i].r&&now<=n) insert(a[now],now),++now; Ans[Q[i].id]=query(Q[i].l); } for(int i=1;i<=m;++i) printf("%d\n",Ans[i]); return 0; }
|
Codeforces1110E
考虑差分序列$d_i$，每做一次题中的操作：
$d_{i}’=c_{i+1}-c_{i}’=c_{i+1}-(c_{i+1}+c_{i-1}-c_{i})=c_{i}-c_{i-1}=d_{i-1}$
$d_{i-1}’=c_{i}’-c_{i-1}=(c_{i+1}+c_{i-1}-c_{i})-c_{i-1}=c_{i+1}-c_{i}=d_{i}$
所以题中操作等价于交换差分序列中的相邻两项，判断一下就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #include<bits/stdc++.h> #define MAXN 100010 using namespace std; int n,a[MAXN],b[MAXN]; bool Check(){ if(a[1]!=b[1]) return 0; for(int i=1;i<n;++i) a[i]=a[i+1]-a[i]; for(int i=1;i<n;++i) b[i]=b[i+1]-b[i]; sort(a+1,a+n); sort(b+1,b+n); for(int i=1;i<n;++i) if(a[i]!=b[i]) return 0; return 1; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) scanf("%d",&b[i]); puts(Check()?"Yes":"No"); return 0; }
|
Codeforces1110D
注意到如果有3个三元组$[i,i+1,i+2]$，那么可以用$[i,i,i],[i+1,i+1,i+1],[i+2,i+2,i+2]$代替答案
考虑到数$i$只可能被包含在$[i-2,i-1,i],[i-1,i,i+1],[i,i+1,i+2]$三类三元组中
所以我们需要设置其中两个的状态进行转移
设$f[i][A][B]$表示前$i$个数中有A组$[i-1,i,i+1]$,B组$[i,i+1,i+2]$的答案
考虑转移过程，$f[i-1][C][A]$表示前$i-1$个数中有C组$[i-2,i-1,i]$，A组$[i-1,i,i+1]$的答案
所以数$i$一共被用去了$A+B+C$次，所以转移如下：
$$f[i][A][B]=f[i-1][C][A]+B+(cnt[i]-A-B-C)/3$$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 1000010 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; int n,m,cnt[MAXN],f[MAXN][3][3]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ int x; scanf("%d",&x); cnt[x]++; } for(int i=1;i<=m;++i)for(int A=0;A<3;++A) for(int B=0;B<3;++B)for(int C=0;C<3;++C)if(A+B+C<=cnt[i]) cmax(f[i][A][B],f[i-1][C][A]+B+(cnt[i]-A-B-C)/3); printf("%d\n",f[m][0][0]); return 0; }
|