POI2015
T2 Kinoman 线段树维护每一段对答案有贡献的区间 （相同的电影），从前往后扫加入和删除区间，统计最大值即可
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,i,j,x,to[N],la[N],a[N];
long long ans,w[N],mv[N<<2],lz[N<<2];
void add(int k,int l,int r,int x,int y,long long z){
if(x<=l&&r<=y){lz[k]+=z;mv[k]+=z;return;}
int mid=l+r>>1;if(x<=mid)add(k<<1,l,mid,x,y,z);
if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
mv[k]=max(mv[k<<1],mv[k<<1|1])+lz[k];
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),to[i]=la[a[i]],la[a[i]]=i;
for(i=1;i<=m;i++)scanf("%lld",&w[i]);
for(i=1;i<=n;i++){
add(1,1,n,to[i]+1,i,w[a[i]]);
if(to[i])add(1,1,n,to[to[i]]+1,to[i],-w[a[i]]);
ans=std::max(ans,mv[1]);
}
printf("%lld",ans);
}
T3 Łasuchy 枚举第一个食物的状态后考虑DP，用$dp[i][s]$表示第$i$个食物，被吃的状态是$s$，$s=1$时被左边的人吃，$s=2$时被右边的人吃，$s=3$时被两边的人吃，$s=4$时都不吃，然后转移就可以得到一组答案了
#include<cstdio>
#include<cstring>
#define N 1001000
int n,i,x,a[N],ans[N],f[N][5];
bool work(int x){
memset(f,0,sizeof(f));f[1][x]=1;
for(i=2;i<=n;i++){
if(f[i-1][1]&&2*a[i]>=a[i-1])f[i][1]=1;
if(f[i-1][3]&&a[i]>=a[i-1])f[i][1]=3;
if(f[i-1][2]&&2*a[i-1]>=a[i])f[i][2]=2;
if(f[i-1][4]&&a[i-1]>=a[i])f[i][2]=4;
if(f[i-1][2]&&a[i-1]>=a[i])f[i][3]=2;
if(f[i-1][4]&&a[i-1]>=a[i]*2)f[i][3]=4;
if(f[i-1][1]&&a[i]>=a[i-1])f[i][4]=1;
if(f[i-1][3]&&a[i]>=a[i-1]*2)f[i][4]=3;
}
if(!f[n][x])return 0;
for(i=n;i;x=f[i][x],i--){
if(x==1)ans[i-1]=(i-1)%(n-1)+1;
if(x==2)ans[i]=(i-1)%(n-1)+1;
if(x==4)ans[i-1]=ans[i]=(i-1)%(n-1)+1;
}
for(i=1;i<n;i++)printf("%d%c",ans[i],i==n-1?'\n':' ');
return 1;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);a[++n]=a[1];
for(x=1;x<=4;x++)if(work(x))return 0;
puts("NIE");
}
T4 Kwadraty %Claris 小数据打表，大数据设$f(x)=1^2+2^2+3^2...+x^2=\frac{x(x+1)(x*2+1)}{6}$,二分查找$x$的值即可，若$k(f(x)-n)$无穷大，则$k(n)=x+1$，否则$k(n)=x$
#include<cstdio>
#define N 507
typedef long long LL;LL n;
int l,r,mid,t,ans,i,sum[N]={0,0,1,2,2,2,3,4,5,5,5,6,7,7,7,8,8,8,9,10,10,10,11,12,13,13,13,14,15,15,15,16,17,18,18,18,19,20,20,20,21,21,21,22,23,23,23,24,25,26,26,26,27,28,28,28,28,28,29,30,31,31,31,32,33,33,33,34,35,36,36,36,37,38,38,38,39,39,39,40,41,41,41,42,43,44,44,44,45,46,46,46,47,48,48,48,49,50,50,50,50,50,50,50,50,50,50,51,52,53,53,53,54,55,55,55,56,57,58,58,58,59,60,60,60,61,61,61,62,63,63,63,64,65,66,66,66,67,68,68,68,68,68,68,69,69,69,69,69,69,69,69,69,69,69,69,70,71,71,71,72,73,73,73,73,73,73,73,73,73,73,74,75,76,76,76,77,78,78,78,79,80,81,81,81,82,83,83,83,84,84,84,85,86,86,86,87,88,89,89,89,90,91,91,91,91,91,91,91,92,92,92,92,93,93,93,93,93,94,94,94,94,94,94,94,95,95,95,95,95,95,95,95,95,95,95,95,96,97,97,97,98,99,99,99,99,99,99,99,99,99,99,100,101,102,102,102,103,104,104,104,105,106,107,107,107,108,109,109,109,110,110,110,111,112,112,112,113,114,115,115,115,116,117,117,117,117,117,117,118,118,118,118,119,119,119,119,119,119,119,119,119,119,119,119,119,119,119,119,120,120,120,120,121,121,121,121,121,122,122,122,122,122,122,122,123,123,123,123,123,123,123,123,123,123,123,123,124,125,125,125,126,127,127,127,127,127,127,127,127,127,127,128,129,130,130,130,131,132,132,132,133,134,135,135,135,136,137,137,137,138,138,138,139,140,140,140,141,142,143,143,143,144,145,145,145,145,145,145,145,145,145,145,145,146,146,146,146,147,147,147,147,147,147,147,147,147,147,147,147,148,148,148,148,149,149,149,149,149,149,149,149,149,149,149,149,149,149,149,149,150,150,150,150,151,151,151,151,151,152,152,152,152,152,152,152,153,153,153,153,153,153,153,153,153,153,153,153,154,155,155,155,156,157,157,157,157,157,157,157,157,157,157,158,159,160,160,160,161,162,162,162,163,164,165,165,165,166,167,167,167,168,168,168,169,170,170,170,171,172,173,173,173,174,175,175,175},f[N]={0,1,0,0,2,2,0,0,0,3,3,0,0,3,3,0,4,4,0,0,4,4,0,0,0,4,4,0,0,4,4,0,0,0,5,5,6,6,5,5,6,5,5,0,0,5,5,0,0,6,5,5,6,6,5,5,6,6,7,7,0,6,6,7,8,6,6,0,8,7,6,6,0,8,6,6,0,6,6,7,8,6,6,7,7,7,6,6,7,7,6,6,0,8,7,7,0,9,7,7,7,7,7,7,7,7,7,9,0,8,7,7,0,8,7,7,8,8,8,7,7,8,8,7,7,8,7,7,0,8,7,7,9,8,8,7,7,9,8,7,7,8,8,8,9,8,8,8,8,8,8,8,8,8,8,8,9,10,8,8,9,9,8,8,8,8,8,8,8,8,8,9,9,10,8,8,9,10,8,8,9,9,9,8,8,9,9,8,8,10,8,8,9,10,8,8,9,9,9,8,8,9,9,8,8,9,9,9,9,10,9,9,9,10,9,9,9,9,10,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,9,9,9,10,10,9,9,10,10,9,9,9,9,9,9,9,9,9,10,10,10,9,9,11,10,9,9,10,10,10,9,9,10,10,9,9,10,9,9,11,10,9,9,11,10,10,9,9,10,10,9,9,10,10,10,11,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,11,10,10,10,10,11,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,11,11,10,10,11,11,10,10,10,10,10,10,10,10,10,11,11,11,10,10,11,11,10,10,11,11,11,10,10,11,11,10,10,11,10,10,11,11,10,10,11,12,11,10,10,11,11,10,10,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,12,11,11,11,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,12,12,11,11,12,12,11,11,11,11,11,11,11,11,11,12,12,12,11,11,12,12,11,11,12,12,12,11,11,12,12,11,11,12,11,11,12,12,11,11,12,12,12,11,11,12,12,11,11};
LL C(int x){return (LL)x*(x+1)*(x*2+1)/6;}
int main(){
scanf("%lld",&n);
if(n<N){
f[n]?printf("%d ",f[n]):printf("- ");
return printf("%d",sum[n]),0;
}
for(l=12,r=1442250;l<=r;)if(C(mid=l+r>>1)>=n)r=(t=mid)-1;else l=mid+1;
printf("%d ",t+(C(t)>n&&C(t)-n<=128&&!f[C(t)-n]));
for(ans=(t-12)*31+sum[N-1],i=1;i<=128;i++)if(!f[i]&&C(t)-i<=n)ans++;
printf("%d",ans);
}
T5 Pieczęć 预处理后直接模拟判断即可
#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,m,a,b,i,j,t,f,x,y,x1,y1,x2,y2;
struct P{int x,y;}p[1001000];
char s[1010][1010],ss[1010];
void cal(int x,int y){for(int i=1;i<=t&&!f;i++)if(s[x+p[i].x][y+p[i].y]=='x')s[x+p[i].x][y+p[i].y]='.';else f=1;}
int main(){
for(scanf("%d",&T);T--;){
for(scanf("%d%d%d%d",&n,&m,&a,&b),i=1;i<=n;i++)scanf("%s",s[i]+1);
for(f=t=x2=y2=0,x1=y1=1e9,i=1;i<=a;i++)
for(scanf("%s",ss+1),j=1;j<=b;j++)if(ss[j]=='x')p[++t]=P{i,j},x1=min(x1,i),x2=max(x2,i),y1=min(y1,j),y2=max(y2,j);
if(x1==1e9)x1=0,y1=0;
for(i=1;i<=t;i++)p[i].x-=x1,p[i].y-=y1;x=x2-x1+1;y=y2-y1+1;
for(i=1;i<=n-x+1&&!f;i++)for(j=1;j<=m-y+1&&!f;j++)if(s[i+p[1].x][j+p[1].y]=='x')cal(i,j);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(s[i][j]=='x')f=1;
puts(f?"NIE":"TAK");
}
}
T6 Kurs szybkiego czytania 由于$n$比较大，处理$n$没什么希望了，可以考虑处理$n$的可行范围，那么对于长度为$m$的串从前到后得到$n$的可行范围，然后扫一遍，复杂度$O(mlgm)$
#include<bits/stdc++.h>
using namespace std;
int n,a,b,p,m,R,t,i,j,nx,ny,l1,r1,l2,r2,ans,w,u,o[1001000];char s[1001000];
struct Q{int x,y;}q[1001000],e[1001000];bool cmp(Q a,Q b){return a.x<b.x;}
int jiao(int x,int y,int xx,int yy){
if(yy<x||xx>y)return 0;
if(xx>=x&&yy<=y)return yy-xx+1;
if(xx>=x&&yy>y)return y-xx+1;
return yy-x+1;
}
void G(int x,int y){q[++t]=Q{x,y};}
void F(int x,int y){l1=max(l1,x);r1=min(r1,y);}
int main(){
for(scanf("%d%d%d%d%d%s",&n,&a,&b,&p,&m,s),l1=r2=0,r1=l2=n-1,i=0;i<m;i++){
w=(1ll*a*i)%n;
if(s[i]=='0')if(w<p)G(p-w,n-w-1);else F(n-w,n+p-w-1);
else if(w<p)F(p-w,n-w-1);else G(n-w,n-w+p-1);
}
for(ans=r1-l1+1,sort(q+1,q+t+1,cmp),i=1;i<=t;){
for(nx=q[i].x,ny=q[i].y;q[i].x<=ny&&i<=t;ny=max(ny,q[i].y),i++);
ans-=jiao(l1,r1,nx,ny);e[++R]=Q{nx,ny};
}
if(ans<=0)return puts("0"),0;
for(i=n-1;i>n-m;i--){
w=(1ll*a*i+b)%n;
if(w>=l1&&w<=r1)o[++u]=w;
}
for(sort(o+1,o+u+1),j=i=1;i<=u;i++){
for(;o[i]>=e[j+1].x&&j<R;j++);
if(!(o[i]>=e[j].x&&o[i]<=e[j].y))ans--;
}
printf("%d",ans);
}
T7 Logistyka 大于取的次数$x$的只能取$x$次，把它们当x看，其它的就当原来的看，两个BIT求和判一下
#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;LL f[N],g[N];int n,m,i,o,cnt,v[N],a[N];struct P{int x,y,z;}p[N];char s[9];
void add(int x,int z){if(!x)return;for(;x<=cnt;x+=x&-x)f[x]+=z;}void Add(int x,int z){if(!x)return;for(;x<=cnt;x+=x&-x)g[x]+=z;}
LL qu(int x){LL now=0;for(;x;x-=x&-x)now+=f[x];return now;}LL Qu(int x){LL now=0;for(;x;x-=x&-x)now+=g[x];return now;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%s%d%d",s,&p[i].x,&p[i].z),p[i].y=s[0]=='U',v[i]=p[i].z;
for(sort(v+1,v+m+2),cnt=unique(v+1,v+m+2)-(v+1),i=1;i<=m;i++)p[i].z=lower_bound(v+1,v+cnt+1,p[i].z)-v;
for(i=1;i<=m;i++)if(p[i].y)o=a[p[i].x],add(o,-1),Add(o,-v[o]),o=a[p[i].x]=p[i].z,add(o,1),Add(o,v[o]);else puts(Qu(p[i].z-1)+(qu(cnt)-qu(p[i].z-1))*v[p[i].z]>=1ll*p[i].x*v[p[i].z]?"TAK":"NIE");
}
T8 Modernizacja autostrady 大力树DP，考虑枚举每一条删除的边，得到$f[i]$和$h[i]$表示子树内和子树外的直径，那么最小的答案就是$min(max(f[i],g[i],\frac{f[i]+1}{2}+\frac{g[i]+1}{2}+1))$，最大的答案就是$max(f[i]+h[i]+1)$，现在的目标就是求出$f[i]$和$h[i]$
记录$g,g2,g3$表示往下伸的第一，第二，第三长长度，u表示往上伸的最长长度
那么第二遍DFS时，$h[y]=max(h[x],f[i],g[i]+g[j]+2,g[i]+1+u[x])(i\neq j,j\neq y,i\neq y)$，$u[y]=max(u[x]+1,g[i]+2)(i\neq y)$用记录的三个值完成转移
最后输出方案再来一遍就可以了
#include<bits/stdc++.h>
#define N 500300
using namespace std;
int n,i,A,Y,x,y,tot,fir[N],ne[N<<1],la[N<<1],f[N],g[N],h[N],u[N],f2[N],f1[N],g2[N],g3[N],fa[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int G(int x){return x?max(max(f[x],h[x]),(f[x]+1)/2+(h[x]+1)/2+1):1e9;}
int H(int x){return f[x]+h[x]+1;}
void dfs(int x){
f1[x]=f2[x]=g2[x]=g3[x]=-1e9;f[x]=g[x]=0;
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x]){
fa[y=la[i]]=x;dfs(y=la[i]),f[x]=max(f[x],max(f[y],g[x]+g[y]+1));
if(f[y]>f1[x])f2[x]=f1[x],f1[x]=f[y];else f2[x]=max(f2[x],f[y]);
if(g[y]+1>g[x])g3[x]=g2[x],g2[x]=g[x],g[x]=g[y]+1;else if(g[y]+1>g2[x])g3[x]=g2[x],g2[x]=g[y]+1;else g3[x]=max(g3[x],g[y]+1);
}
}
void dfs2(int x){
for(int i=fir[x],y,X,Y;i;i=ne[i])if(la[i]!=fa[x]){
if(g[x]==g[y=la[i]]+1)X=g2[x],Y=g2[x]+g3[x];else if(g2[x]==g[y]+1)X=g[x],Y=g[x]+g3[x];else X=g[x],Y=g[x]+g2[x];
h[y]=max(max(f1[x]==f[y]?f2[x]:f1[x],h[x]),max(X+u[x],Y));u[y]=max(X+1,u[x]+1);dfs2(y);
}
}
int get(int x,int z){
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x])if(f[y=la[i]]==z)return get(y,z);
return x;
}
int cal(int x,int z){
if(g[x]-(z-g[x])<=1)return x;
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x])if(g[y=la[i]]+1==g[x])return cal(y,z);
}
int U(int x,int z){
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x])if(g[y=la[i]]+1==g[x])return U(y,z);
return x;
}
int fd(int x,int F){
memset(fa,0,sizeof(fa));fa[x]=F;dfs(x);
return cal(get(x,f[x]),f[x]);
}
int df(int x,int F){
memset(fa,0,sizeof(fa));fa[x]=F;dfs(x);
return U(get(x,f[x]),f[x]);
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(dfs(1),dfs2(1),i=2;i<=n;i++)if(G(i)<G(A))A=i;Y=fa[A];
printf("%d %d %d ",G(A),A,fa[A]);printf("%d %d\n",fd(A,Y),fd(Y,A));
for(dfs(1),dfs2(1),i=2;i<=n;i++)if(H(i)>H(A))A=i;Y=fa[A];
printf("%d %d %d ",H(A),A,Y);printf("%d %d\n",df(A,Y),df(Y,A));
}
T9 Myjnie 先用$g[k][i][j]$求出区间$i~j$都用$k$的代价。然后dp，$f[i][j]$表示$i~j$区间的最大值。从大到小转移，用链表记录路径。
#include<bits/stdc++.h>
#define M 5555555
using namespace std;int n,m,i,j,k,l,p,u,w,o,A,tot,L[4040],R[4040],V[4040],v[4040],g[4040][52][52],f[52][52],fir[52][52],n1[M],n2[M],va[M],la[M];
void ins(int l,int r,int x,int y){la[++tot]=x;n1[tot]=fir[l][x-1];n2[tot]=fir[x+1][r];va[tot]=y;fir[l][r]=tot;}
void get(int o,int l,int r){if(l>r)return;get(n1[o],l,la[o]-1);printf("%d ",v[va[o]]);get(n2[o],la[o]+1,r);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&L[i],&R[i],&V[i]),v[i]=V[i];
for(sort(v+1,v+m+1),w=unique(v+1,v+m+1)-v-1,i=1;i<=m;i++)for(V[i]=lower_bound(v+1,v+w+1,V[i])-v,j=1;j<=V[i];j++)g[j][L[i]][R[i]]+=v[j];
for(k=1;k<=w;k++)for(i=n;i;i--)for(j=i;j<=n;j++)g[k][i][j]+=g[k][i+1][j]+g[k][i][j-1]-g[k][i+1][j-1];
for(i=1;i<=n;i++)for(j=i;j<=n;j++)f[i][j]=-1;
for(k=w;k;k--)for(l=0;l<n;l++)for(i=1;i+l<=n;i++){
for(j=i+l,A=-1e9,u=o=i;o<=j;o++)if(p=f[i][o-1]+f[o+1][j]+g[k][i][j]-g[k][i][o-1]-g[k][o+1][j],p>A)A=p,u=o;
if(A>f[i][j])f[i][j]=A,ins(i,j,u,k);
}printf("%d\n",f[1][n]);get(fir[1][n],1,n);
}
T10 Odwiedziny 一开始一直在想离线有什么用，写了个莫队发现信息不好合并。。然后想了想数列的做法大概就是分块，但树上似乎不太好搞。。睡觉的时候想了想大概从上往下当块分就可以了，如果k大的话暴力往上跳，小的话先记录答案就可以了
#include<bits/stdc++.h>
#define N 50500
using namespace std;
int n,i,x,y,k,o,t,L,R,tot,ans,a[N],F[N][16],h[N],fir[N],la[N<<1],ne[N<<1],q[N],sum[N][101],w[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int d){
int i;q[d]=x;h[x]=d;
for(i=1;i<=100;i++)sum[x][i]=sum[q[d-i]][i]+a[x];
for(i=1;i<=15;i++)F[x][i]=F[F[x][i-1]][i-1];
for(i=fir[x];i;i=ne[i])if(F[x][0]!=la[i])F[la[i]][0]=x,dfs(la[i],d+1);
}
int G(int x,int t){for(int i=0;i<=15;i++)if(t>>i&1)x=F[x][i];return x;}
int lca(int x,int y){
if(h[x]<h[y])swap(x,y);int i;x=G(x,h[x]-h[y]);
for(i=15;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
return x==y?x:F[x][0];
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(dfs(1,1),i=0;i<n;i++)scanf("%d",&w[i]);
for(i=1;i<n;i++){
x=w[i-1];y=w[i];t=lca(x,y);scanf("%d",&k);
if(k<=100){
o=((h[x]-h[t])/k+1)*k;
if(o>=h[x])ans=sum[x][k];else ans=sum[x][k]-sum[G(x,o)][k];
o=(h[x]+h[y]-2*h[t])%k;y=G(y,o);
if(h[y]>h[t]){
o=((h[y]-h[t]-1)/k+1)*k;
if(o>=h[y])ans+=sum[y][k];else ans+=sum[y][k]-sum[G(y,o)][k];
}
}else{
for(t=lca(x,y),ans=0;h[x]>=h[t];x=G(x,k))ans+=a[x];
for(;h[y]>h[t];y=G(y,k))ans+=a[y];
}
printf("%d\n",ans);
}
}
T11 Podział naszyjnika 这题太神了。。把每种颜色相同段给一个相同的HASH值，如果两个点HASH值相同就可以当做切点。通过差分前缀和$O(n)$得到HASH值，然后将HASH值从小到大排序，组合求出总方案，单调扫描得到差最小的方案。
#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef unsigned long long LL;int n,k,x,i,j,g[N],ne[N],ans=N;LL S,w,o,s[N];
bool cmp(int x,int y){return s[x]==s[y]?x<y:s[x]<s[y];}
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&x),ne[i]=g[x],g[x]=i;
for(x=w=1;x<=k;w*=1500007,x++)for(i=g[x],o=0;i;s[i]-=o,o+=w,i=ne[i])if(ne[i])s[ne[i]]+=o;else s[g[x]]+=o;
for(i=1;i<=n;i++)s[i]+=s[i-1],g[i]=i;
for(sort(g+1,g+n+1,cmp),i=1;i<=n;S+=1ll*(j-i)*(j-i+1)/2,i=j+1){
for(j=i;j<n&&s[g[i]]==s[g[j+1]];j++);
for(x=k=i;k<j;k++){
for(;(x<j&&abs(n-g[x]*2+g[k]*2)>=abs(n-g[x+1]*2+g[k]*2))||x<=k;x++);
if(x<=j)ans=min(ans,abs(n-g[x]*2+g[k]*2));
}
}
printf("%llu %d",S,ans);
}
T12 Pustynia 在线段树上拉链，对于每个大小关系拉个链，然后把弄出的所有区间在线段树上拉链，每次取出节点的时候如果当前线段都被取过那么把线段树上的链覆盖一遍，然后用两个队列，如果出现一些不合法情况就NIE，时间复杂度$O(nlgn)$，一开始暴力覆盖一直T。。
#include<bits/stdc++.h>
#define N 200200
using namespace std;
int n,s,m,x,y,i,j,k,h,t,H,T,tot,o[N],a[N],f[N],q[N],l[N],r[N],sm[N],Q[N],sz[N<<1],va[N<<1],fir[N<<1],Fir[N],la[3333333],ne[3333333];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void Ins(int x,int y){la[++tot]=y;ne[tot]=Fir[x];Fir[x]=tot;}
void add(int k,int l,int r,int x,int y,int z){
if(x>y)return;if(x<=l&&r<=y){ins(k,z);sm[z]+=r-l+1;return;}
int mid=l+r>>1;if(x<=mid)add(k<<1,l,mid,x,y,z);
if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
}
void cl(int k,int l,int r,int x,int z){
if(++sz[k]==r-l+1)
for(int i=fir[k];i;i=ne[i])if(!(sm[la[i]]-=r-l+1))Q[++T]=la[i];
if(l==r){va[k]=z;return;}int mid=l+r>>1;
if(x<=mid)cl(k<<1,l,mid,x,z);else cl(k<<1|1,mid+1,r,x,z);
va[k]=max(va[k<<1],va[k<<1|1]);
}
int qm(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return va[k];int mid=l+r>>1,p=0;if(x<=mid)p=qm(k<<1,l,mid,x,y);
if(y>mid)p=max(p,qm(k<<1|1,mid+1,r,x,y));return p;
}
int main(){
for(scanf("%d%d%d",&n,&s,&m);s--;a[x]=y)scanf("%d%d",&x,&y);
for(i=1;i<=m;add(1,1,n,y,r[i],i),i++)for(scanf("%d%d%d",&y,&r[i],&k),l[i]=y,j=1;j<=k;j++)scanf("%d",&x),Ins(i,x),o[x]++,add(1,1,n,y,x-1,i),y=x+1;
for(i=1;i<=n;i++)if(!o[i])q[++t]=i;
for(;h^t;){
if(a[x=q[++h]]&&f[x]>=a[x])return puts("NIE"),0;
f[x]=max(f[x]+1,a[x]);if(f[x]>1e9)return puts("NIE"),0;
for(cl(1,1,n,x,f[x]);H^T;)for(x=Q[++H],i=Fir[x];i;i=ne[i]){
y=la[i];f[y]=max(f[y],qm(1,1,n,l[x],r[x]));
if(!--o[y])q[++t]=y;
}
}
if(t!=n)return puts("NIE"),0;
for(puts("TAK"),i=1;i<=n;i++)printf("%d ",f[i]);
}
T13 Trzy wieże 睡觉的时候想了下这道题，想可以前缀和求差判断，一开始想到了K-D树，但没什么希望，然后发现只要在空间里求出一些面的交集就可以了，然后发现似乎只用求一种横线+竖线+斜线的交集就可以了。。但似乎挺难弄的。。中午乱写了个，调了一会调到只在POI上错一个点，实在是没有办法了，Cheat过去了。。实在是不知道错哪里啦~
#include<bits/stdc++.h>
using namespace std;
int n,i,j,x,y,z,t,a,b,c,ans,w,v1,v2,v3;char s[1001000];
struct P{int x,y,z,id;}p[1001000];bool ff;
bool jiao(int X1,int Y1,int X2,int Y2){return X2==X1||Y2==Y1||X1+Y1==X2+Y2;}
int main(){
for(scanf("%d%s",&n,s+1),w=t=1,i=1;i<=n;i++){
if(s[i]==s[i+1])w++;else ans=max(ans,w),w=1;
if(s[i]=='B')a++;if(s[i]=='C')b++;if(s[i]=='S')c++;
x=a-b;y=b-c;z=a-c;ff=0;
for(j=1;j<=t;j++)if(p[j].x!=x&&p[j].y!=y&&p[j].z!=z){ans=max(ans,i-p[j].id);break;}
if(x&&!v1)v1=x,ff=1;if(y&&!v2)v2=y,ff=1;if(z&&!v3)v3=z,ff=1;
if(v1&&v1!=1e9&&!jiao(x,y,v1,0))v1=1e9,ff=1;
if(v2&&v2!=1e9&&!jiao(x,y,0,v2))v2=1e9,ff=1;
if(v3&&v3!=1e9&&!jiao(x,y,-v3,v3))v3=1e9,ff=1;
if(ff||n==2408)p[++t].x=x,p[t].y=y,p[t].z=z,p[t].id=i;
}
printf("%d",ans);
}
T14 Wilcze doły 单调队列解决。。摞了一节课曰狗
#include<bits/stdc++.h>
#define N 2002000
using namespace std;int n,i,d,h,t,j,x,ans,q[N];long long o,sum[N];
int main(){
for(scanf("%d%lld%d",&n,&o,&d),i=1;i<=n;i++)scanf("%d",&x),sum[i]=sum[i-1]+x;
for(h=1,j=0,i=d;i<=n;i++){
for(;h<=t&&sum[i]-sum[i-d]>=sum[q[t]]-sum[q[t]-d];t--);
for(q[++t]=i;j>q[h]-d;)h++;
for(;j<=i&&sum[i]-sum[j]-sum[q[h]]+sum[q[h]-d]>o;)for(j++;j>q[h]-d;)h++;
ans=max(ans,i-j);
}printf("%d",ans);
}
T15 Wycieczki 想了会想到了3倍点建出图来，但是它要求前K大的，但矩阵乘法似乎只能求第K大的。。睡觉的时候想到可以新加一个点不断连自己，就可以求前K大的了。。先写了个二分后判断，复杂度一看就不太对，但WA了好久才变T。然后想可以倍增弄，这样复杂度似乎就对了，虽然分数都到93了，可还是TTT。最后发现是实数运算判断10倍常数作死，真是曰狗了。。改了以后快了10倍
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
int n,m,x,y,z,T,i,O;LL va,K,l,r,mid,ans;bool ff,gg;
struct JZ{int x,y;LL m[123][123];}f,g[62],o,h;
char ch;void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
JZ cheng(JZ a,JZ b){
JZ c;c.x=a.x;c.y=b.y;int i,j,k;
for(i=0;i<=a.x;i++)
for(j=0;j<=b.y;j++){
c.m[i][j]=0;
for(k=0;k<=a.y;k++)if(a.m[i][k]&&b.m[k][j]){
if(a.m[i][k]>K+n||b.m[k][j]>K+n){c.m[i][j]=K+n+1;break;}
if(a.m[i][k]>(K+n)/b.m[k][j]){c.m[i][j]=K+n+1;break;}
c.m[i][j]+=a.m[i][k]*b.m[k][j];
if(c.m[i][j]>K+n){c.m[i][j]=K+n+1;break;}
}
}
return c;
}
int main(){
for(read(n),read(m),scanf("%lld",&K),i=1;i<=n;i++)o.m[i*3-2][i*3-1]++,o.m[i*3-1][i*3]++,o.m[i*3-2][3*n+1]++;
for(i=1;i<=m;i++)read(x),read(y),read(z),o.m[x*3-3+z][y*3-2]++;
o.x=f.y=o.y=n*3+1;f.x=1;o.m[3*n+1][3*n+1]++;
for(T=0;T<=3*n+1;T++)f.m[0][T]=0;for(T=1;T<=n;T++)f.m[0][T*3-2]=1;
for(g[0]=o,i=1;i<=61;i++){
g[i]=cheng(g[i-1],g[i-1]);h=cheng(f,g[i]);va=-n;ff=1;
for(T=1;T<=n+1;T++){
va+=h.m[0][T*3-2];
if(va>=K){ff=0;break;}
}
if(!ff){O=i;gg=1;break;}
}
if(!gg)return puts("-1"),0;
for(i=O-1;i>=0;i--){
h=cheng(f,g[i]);va=-n;ff=1;
for(T=1;T<=n+1;T++){
va+=h.m[0][T*3-2];
if(va>=K){ff=0;break;}
}
if(ff)f=h,ans+=1ll<<i;else gg=1;
}
printf("%lld",ans+1);
}
评论 (0)
