国家集训队命题答辩
BZOJ炸了，只好来Tsinsen做题咯。。现在做了几道
50
采矿 傻逼树剖，线段树维护背包后的答案，$m^2$背包一次更新操作，并支持链上查最大操作即可，时间复杂度$O(nm^2+qm^2lgn+qmlg^2n)$
#include<bits/stdc++.h>
#define N 20020
using namespace std;const int X=65536,Y=2147483647;int n,m,A,B,Q,x,y,i,j,C,o,id,tot,ans,b[N*4][52],a[N][52],e[N*4][52],c[52],d[52],fir[N],ne[N],la[N],sz[N],fa[N],hs[N],st[N],ed[N],bl[N],h[N],to[N];
int gi(){A=((A^B)+(B/X)+(B*X))&Y;B=((A^B)+(A/X)+(A*X))&Y;return (A^B)%Q;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
sz[x]=1;int i,y;for(i=fir[x];i;i=ne[i]){
fa[y=la[i]]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];
if(sz[y]>sz[hs[x]])hs[x]=y;
}
}
void dfs2(int x,int f){
st[x]=++id;to[id]=x;bl[x]=f;if(hs[x])dfs2(hs[x],f);
for(int i=fir[x];i;i=ne[i])if(la[i]!=hs[x])dfs2(la[i],la[i]);ed[x]=id;
}
void ps(int k){
memset(b[k],0,sizeof b[k]);int i,j;
for(i=0;i<=m;i++)for(j=0;i+j<=m;j++)b[k][i+j]=max(b[k][i+j],b[k<<1][i]+b[k<<1|1][j]);
for(i=1;i<=m;i++)e[k][i]=max(e[k<<1][i],e[k<<1|1][i]);
}
void bt(int k,int l,int r){
int i=1,mid=l+r>>1;if(l==r){for(;i<=m;i++)b[k][i]=e[k][i]=a[to[l]][i];return;}
bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);ps(k);
}
void cha(int k,int l,int r,int x){
int i=1,mid=l+r>>1;if(l==r){for(;i<=m;i++)b[k][i]=gi();sort(b[k]+1,b[k]+m+1);for(i=1;i<=m;i++)e[k][i]=b[k][i];return;}
if(x<=mid)cha(k<<1,l,mid,x);else cha(k<<1|1,mid+1,r,x);ps(k);
}
void get(int k,int l,int r,int x,int y){
int i=m,j,mid=l+r>>1;
if(x<=l&&r<=y){for(i=m;i;i--)for(j=i;j;j--)c[i]=max(c[i],b[k][j]+c[i-j]);return;}
if(x<=mid)get(k<<1,l,mid,x,y);if(y>mid)get(k<<1|1,mid+1,r,x,y);
}
void qu(int k,int l,int r,int x,int y){
int i=1,mid=l+r>>1;if(x<=l&&r<=y){for(;i<=m;i++)d[i]=max(d[i],e[k][i]);return;}
if(x<=mid)qu(k<<1,l,mid,x,y);if(y>mid)qu(k<<1|1,mid+1,r,x,y);
}
int main(){
for(scanf("%d%d%d%d%d",&n,&m,&A,&B,&Q),i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
for(i=1;i<=n;sort(a[i]+1,a[i]+m+1),i++)for(j=1;j<=m;j++)a[i][j]=gi();
for(dfs(1),dfs2(1,1),bt(1,1,n),scanf("%d",&C);C--;)
if(scanf("%d",&o),o){
scanf("%d%d",&x,&y);memset(c,0,sizeof c);memset(d,0,sizeof d);get(1,1,n,st[x],ed[x]);
if(x!=y){
for(x=fa[x];bl[x]!=bl[y];x=fa[bl[x]])qu(1,1,n,st[bl[x]],st[x]);
qu(1,1,n,st[y],st[x]);
}
for(ans=i=0;i<=m;i++)ans=max(ans,c[i]+d[m-i]);printf("%d\n",ans);
}else scanf("%d",&x),cha(1,1,n,st[x]);
}
复杂的大门 建出分层图跑网络流，答案就是最小割。但是理论上会T的，应该要写Dijkstra，但是我懒得写直接网络流水过了，其实网络流和最短路在分层图上速度差距也不是特别大
#include<bits/stdc++.h>
#define N 20020
#define M 300300
using namespace std;
int n,m,i,x,y,z,s,t,u,w,V,fl,tot,fir[N],cur[N],pre[N],d[N],nb[N],ne[M],la[M],va[M];
void ins(int x,int y,int z){
la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;
}
int main(){
for(scanf("%d%d",&n,&m),s=2*n+1,t=s+1,tot=i=1;i<=n;i++)scanf("%d",&x),ins(s,i,x),ins(i+n,t,x),fl+=x;
for(;m--;ins(x,y+n,z))scanf("%d%d%d",&x,&y,&z);
for(i=1;i<=t;i++)cur[i]=fir[i];
for(u=s,nb[0]=t;d[s]<t;){
if(u==t){
for(V=1e9,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<V)V=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=V,va[cur[i]^1]+=V;
fl-=V;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],w=t;i;i=ne[i])if(d[la[i]]<w&&va[i])w=d[la[i]];
++nb[d[u]=w+1];if(u!=s)u=pre[u];
}
}
printf("%d",fl);
}
大楼
连边☆ $f[i][j]$表示选了$i$条边，有$j$个点的度数为奇数的方案数
先不考虑有重复的边，那么$f[i][j]=f[i-1][j-2]*c(j,2)+f[i-1][j]*j*(n-j)+f[i-1][j+2]*c(n-j,2)$
但题目要求不能有重复的边，考虑第$i$条边和前面的某一条边重复，那么奇偶性不变，前面有$i-1$条边可选，每条边又有$c(n,2)-i+2$种方案，所以$f[i][j]$减去$f[i-2][j]*(i-1)*(c(n,2)-i+2)$
#include<bits/stdc++.h>
#define M 10007
#define N 1010
int n,m,i,j,k,x,y,w,o,v,f[N][N],a[N];
int G(int x){return (x*(x-1)/2)%M;}
int pow(int a,int b,int p){for(o=1,a%=p;b;a=a*a%p,b>>=1)if(b&1)o=o*a%p;return o;}
int main(){
for(scanf("%d%d%d",&n,&m,&k);m--;a[x]^=1,a[y]^=1)scanf("%d%d",&x,&y);for(i=1;i<=n;w+=a[i++]);
for(f[0][0]=1,i=1;i<=k;i++)for(j=0;j<=n;j++)f[i][j]=(f[i-1][j]*(n-j)%M*j%M+f[i-1][j-2]*G(j)%M+f[i-1][j+2]*G(n-j)%M-f[i-2][j]*(i-1)%M*(G(n)-i+2+M)%M+M)%M;
for(v=i=1;i<=k;i++)v=v*pow(i,M-2,M)%M;
printf("%d",f[k][w]*v%M);
}
画圈圈☆ 很明显是插头DP，今天学习了下，基本方法差不多，判断是否在多边形内可以用射线法。下面写一下推插头DP转移方程的基本方法
用括号序列表示联通状态，共$m+1$个插头，$0$表示无插头，$1$表示左括号，$2$表示右括号
逐格递推，将上插头和左插头变成下插头和右插头，考虑转移
如果左插头为$1$，上插头为$2$，那么形成一个回路，在这道题目中可以看成转移到$(0,0)$。但如果到终点累加到答案中。
如果左插头为$2$，上插头为$1$，那么连起来发现转移到$(0,0)$
如果左插头和上插头同时为$0$，那么可以转移到$(0,0)$和$(1,2)$，由于这题要求每个点都要经过，所以只能转移到$(1,2)$
如果左插头和上插头有一个为$0$，那么可以转移到$(0,x)$和$(x,0)$，$x$为不为$0$的那个插头状态
如果左插头和上插头相等，转移到$(0,0)$。那么如果都是插头$1$，并将右边第一个状态为$2$的不匹配插头改为$1$。如果都是插头$2$，那么往左找第一个状态为$1$的不匹配插头改为$2$。
#include<bits/stdc++.h>
#define M 123456791
using namespace std;char s[15];struct Q{int x,y;}q[8888888];int n,m,i,j,h,t,W,S,x,y,z,p,en,ans,a[15],u[15][22],f[2][4444444],v[2][4444444];
int G(int x,int q1,int q2){int k=0,i=m+1;for(;i;i--)k=k*3+(i==x?q1:(i==x+1?q2:a[i]));return k;}
void up(int x,int S,int z){
x++;int o=x&1;
if(v[o][S]!=x)v[o][S]=x,f[o][S]=0,q[++t]=Q{x,S};
f[o][S]=(f[o][S]+z)%M;
}
int main(){
for(memset(u,1,sizeof(u)),scanf("%d%d",&n,&m),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=m;j++)if(s[j]=='#')u[j][i]=1;else if(s[j]=='*')u[j][i]=2;else u[j][i]=0;
for(en=n*m-1;u[en%m+1][en/m+1];en--);
for(q[f[0][0]=v[0][0]=t=1]=Q{0,0};h<t;){
W=q[++h].x;S=q[h].y;z=f[W&1][S];x=W%m+1;y=W/m+1;
if(W%m==0)S*=3;for(i=1,j=S;i<=m+1;i++,j/=3)a[i]=j%3;
if(u[x][y]){
for(p=0,i=1;i<x;i++)if(a[i])p^=1;
if(u[x][y]==1&&!p||u[x][y]==2&&p)up(W,G(x,0,0),z);
}else if(a[x]==1&&a[x+1]==2&&W==en){ans=(ans+z)%M;}else
if(a[x]==1&&a[x+1]==2||a[x]==2&&a[x+1]==1)up(W,G(x,0,0),z);else
if(!a[x]&&!a[x+1]){
if(!u[x][y+1]&&!u[x+1][y])up(W,G(x,1,2),z);
}else if(!a[x]){
if(!u[x+1][y])up(W,G(x,0,a[x+1]),z);
if(!u[x][y+1])up(W,G(x,a[x+1],0),z);
}else if(!a[x+1]){
if(!u[x+1][y])up(W,G(x,0,a[x]),z);
if(!u[x][y+1])up(W,G(x,a[x],0),z);
}else if(a[x]==a[x+1]){
if(a[x]==1)for(j=0,i=x+2;i<=m+1;i++){
if(a[i]==1)j--;if(a[i]==2)j++;
if(j>0){a[i]=1;break;}
}else for(j=0,i=x-1;i;i--){
if(a[i]==1)j++;if(a[i]==2)j--;
if(j>0){a[i]=2;break;}
}
up(W,G(x,0,0),z);
}
}
printf("%d",ans);
}
单选错位
刷题计划 如果$m$比较小，直接堆就可以了；现在$m$比较大，可以先粗略地把$m$插进去，剩下大约$n$个再用堆得到更加精确的答案。
#include<bits/stdc++.h>
#define N 50100
#define sqr(x)((x)*(x))
using namespace std;int n,m,i,rt,x,b[N],l[N],r[N];double L,sum,ans,a[N];
double G(int i){return sqr(a[i]/(b[i]+2)-L)*(b[i]+2)-sqr(a[i]/(b[i]+1)-L)*(b[i]+1);}
int mg(int x,int y){
if(!x||!y)return x+y;if(G(x)>G(y))swap(x,y);
r[x]=mg(r[x],y);swap(l[x],r[x]);return x;
}
int main(){
for(scanf("%d%d%lf",&n,&m,&L),i=1;i<=n;i++)scanf("%lf",&a[i]);
for(i=1;i<n;i++)a[i]=a[i+1]-a[i],sum+=fabs(a[i]);
for(i=1;i<n;i++)b[i]=max(min((int)(m/sum*fabs(a[i]))-1,(int)fabs(a[i]/L)-1),0);
for(i=1;i<n;i++)rt=mg(rt,i),m-=b[i];
for(;m--&&G(rt)<0;rt=mg(rt,x))b[rt]++,x=rt,rt=mg(l[x],r[x]),l[x]=r[x]=0;
for(i=1;i<n;i++)ans+=sqr(a[i]/(b[i]+1)-L)*(b[i]+1);
printf("%.3lf",ans);
}
飞飞侠 傻逼最短路，加一个状态z表示还能飞几次，不用连边，否则MLE
跳跳棋☆ 好神啊。考虑三个棋子间距相等的话，那么只能中间这个棋子向两边动。否则还可以两边棋子向中间动
这很像一颗树，三个棋子间距相等就是树根，两边向中间跳就是向父亲走一步，中间向两边跳就是向儿子走一步
这样就把问题转化为①两种情况是否同根②如果同根，两点在树上距离
直接暴力也是不可以的，但可以考虑一次跳很多很多步，这样走到s1==s2的情况的步数是log级的
然后要求LCA，可以先把两个点移动到相同深度，然后可以二分答案x，判断一下两个点向上走x步是不是一个点
于是总的复杂度变成$O(log^2ans)$，好题！
#include<bits/stdc++.h>
using namespace std;struct P{int x,y,z;}a,b,A,B;int d1,d2,l,r,mid,w,v,o,p,q;
bool xd(P a,P b){return a.x==b.x&&a.y==b.y&&a.z==b.z;}
void G(P&a){if(a.x>a.y)swap(a.x,a.y);if(a.x>a.z)swap(a.x,a.z);if(a.y>a.z)swap(a.y,a.z);}
int rt(P a,P&b){
for(v=0,b=a;b.y*2!=b.x+b.z;v+=o,G(b)){
p=b.y-b.x;q=b.z-b.y;
if(p<q)o=(q-1)/p,b.x+=p*o,b.y+=p*o;else o=(p-1)/q,b.z-=q*o,b.y-=q*o;
}
return v;
}
P up(P a,int x){
for(;x;x-=o,G(a)){
p=a.y-a.x;q=a.z-a.y;
if(p<q)o=min((q-1)/p,x),a.x+=p*o,a.y+=p*o;else o=min((p-1)/q,x),a.z-=q*o,a.y-=q*o;
}
return a;
}
bool ok(int x){return xd(up(a,x),up(b,x));}
int main(){
scanf("%d%d%d%d%d%d",&a.x,&a.y,&a.z,&b.x,&b.y,&b.z);G(a);G(b);
d1=rt(a,A);d2=rt(b,B);if(!xd(A,B))return puts("NO"),0;
puts("YES");if(d1>d2)w=d1-d2,a=up(a,w);else w=d2-d1,b=up(b,w);
for(l=0,r=min(d1,d2);mid=(l+r)/2,l<r;ok(mid)?r=mid:l=mid+1);
printf("%d",w+2*l);
}
悄悄话 OTZ出题人
Crash的数字表格
Crash的文明世界 $x^k=\sum Sterling2(k,i)*i!*C(x,i)$，递推出斯特林数和阶乘，然后用树形DP递推组合数
#include<bits/stdc++.h>
#define M 10007
#define N 50050
using namespace std;int n,k,L,W,A,B,Q,p,i,j,x,y,v,tot,fir[N],ne[N<<1],pw[155],la[N<<1],S[N][155],f[N][155],g[N][155];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
f[x][0]=1;
for(int i=fir[x],j,y;i;i=ne[i])if(la[i]!=fa)for(dfs(y=la[i],x),f[x][0]+=f[y][0],j=1;j<=k;j++)f[x][j]=(f[x][j]+f[y][j]+f[y][j-1])%M;
}
void dp(int x,int fa){
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa){
for(g[y=la[i]][0]=n-f[y][0],j=1;j<=k;j++)g[y][j]=((g[x][j-1]+g[x][j]+f[x][j-1]+f[x][j]-2*f[y][j-1]-f[y][j]-f[y][j-2])%M+M)%M;
dp(y,x);
}
}
int main(){
for(scanf("%d%d%d%d%d%d%d",&n,&k,&L,&W,&A,&B,&Q),pw[0]=S[0][0]=i=1;i<=k;pw[i]=pw[i-1]*i%M,i++)for(S[i][i]=j=1;j<i;j++)S[i][j]=(j*S[i-1][j]+S[i-1][j-1])%M;
for(i=1;i<n;i++)W=(W*A+B)%Q,p=i<L?i:L,x=i-W%p,y=i+1,ins(x,y),ins(y,x);
for(dfs(1,0),dp(1,0),i=1;i<=n;printf("%d\n",v),i++)for(v=0,j=1;j<=k;j++)v=(v+(int)(1ll*S[k][j]*pw[j]*(f[i][j]+g[i][j])%M))%M;
}
Construct 第一问求出最大和最小的就行了，第二问可以维护一个单调栈，得到单调上升和下降的曼哈顿凸包，就可以统计出面积了
#include<bits/stdc++.h>
#define N 100100
using namespace std;typedef long long LL;int n,i,t;LL ans,yv=-1e9,yi=1e9;
struct P{LL x,y;}p[N],q[N];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%lld%lld",&p[i].x,&p[i].y);
yi=min(yi,p[i].y);yv=max(yv,p[i].y);
}
for(sort(p+1,p+n+1,cmp),i=1;i<=n;i++){
if(!t||p[i].y>q[t].y)q[++t]=p[i];
if(p[i].y==yv)break;
}
for(i++;i<=n;q[++t]=p[i++])for(;p[i].y>q[t].y;t--);
for(i=2;i<=t;i++)ans+=min(q[i-1].y,q[i].y)*(q[i].x-q[i-1].x);
for(t=0,i=1;i<=n;i++){
if(!t||p[i].y<=q[t].y)q[++t]=p[i];
if(p[i].y==yi)break;
}
for(i++;i<=n;q[++t]=p[i++])for(;p[i].y<q[t].y;t--);
for(i=2;i<=t;i++)ans+=max(q[i-1].y,q[i].y)*(q[i-1].x-q[i].x);
printf("%lld\n%lld",(p[n].x-p[1].x+yv-yi)*2,ans);
}
免费的馅饼 $f[i]=max(f[j])(2t[i]+p[i]\geq2t[j]+p[j],2t[i]-p[i]\geq2t[j]-p[j])$，树状数组优化一下就可以了
#include<bits/stdc++.h>
#define N 100100
using namespace std;int n,w,i,x,y,z,cnt,ans,v[N],c[N];
struct P{int x,y,z;}p[N];bool cmp(P a,P b){return a.x<b.x;}
void add(int x,int z){for(;x<cnt;x+=x&-x)c[x]=max(c[x],z);}
int qu(int x){for(w=0;x;x-=x&-x)w=max(w,c[x]);return w;}
int main(){
for(scanf("%d%d",&w,&n),i=1;i<=n;i++)scanf("%d%d%d",&x,&y,&p[i].z),x*=2,p[i].x=x+y,p[i].y=v[i]=x-y;
for(sort(p+1,p+n+1,cmp),sort(v+1,v+n+1),cnt=unique(v+1,v+n+1)-v,i=1;i<=n;i++)
x=lower_bound(v+1,v+cnt,p[i].y)-v,z=qu(x)+p[i].z,add(x,z),ans=max(ans,z);
printf("%d",ans);
}
圈地计划 黑白染色，黑点源流量商业，汇流量工业；白点源流量工业，汇流量商业；相邻两点间流量$c1+c2$。跑最大流。
切割 树形DP，$f[i][j][k]$表示以$i$为根，需要联通块大小为$j$，当前联通块大小为$k$的最小值，$g[i]$为$min(f[i][j][j])(k1\leq j\leq k2)$，暴力$n^4$转移
#include<bits/stdc++.h>
using namespace std;int n,k1,k2,i,j,k,x,y,tot,fir[52],la[101],ne[101];double sm,v[52],g[52],f[52][52][52];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
int i,j,k,l,y;g[x]=1e18;
for(i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x);
for(j=k1;j<=k2;g[x]=min(g[x],f[x][j][j]),j++)for(f[x][j][1]=v[x]/j,i=fir[x];i;i=ne[i])if(la[i]!=fa)for(k=j;k;k--)for(f[x][j][k]+=g[y=la[i]],l=1;l<k;l++)f[x][j][k]=min(f[x][j][k],f[x][j][k-l]+f[y][j][l]);
}
int main(){
for(scanf("%d%d%d",&n,&k1,&k2),i=1;i<=n;i++)scanf("%lf",&v[i]),sm+=v[i];
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=0;i<=n;i++)for(j=1;j<=k2;j++)for(k=0;k<=k2;k++)f[i][j][k]=1e18;
dfs(1,0);if(g[1]==1e18)g[1]=sm*2;printf("%.2lf",g[1]);
}
Submultiple 可以发现答案就是\prod(\sum_{j\leq a[i]+1}j^k)，对于不同的数据采取不同的方法
对于$k=3$的情况，对每个数用三次方求和公式求解统计贡献
对$P_i\leq100000$的情况，暴力统计$k$次方前缀和
对于$k较$小的情况，用矩阵乘法来做$k$次方前缀和，当然这个$k$完全可以做到$200000$，CF上出过，拉下来就好了
#include<bits/stdc++.h>
#define M 1000000007
using namespace std;typedef long long LL;int n,i;LL x,y,v,k,ans,a[77777],F[111111],pw[44],cc[44],R[44];
LL pow(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
LL get(LL n,LL k){
int i,j;LL an=0,p=1;if(n<=k+4)return R[n];
for(i=1;i<k+5;i++)p=p*(n-i)%M;
for(i=1;i<k+5;i++)an=(an+p*pow(n-i,M-2,M)%M*cc[i])%M;
return an;
}
int main(){
for(scanf("%d%lld",&n,&k),ans=i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]++,v=max(v,a[i]);
if(k==3){
for(i=1;i<=n;i++)x=a[i]%M,y=(a[i]+1)%M,x=(x*y/2)%M,ans=ans*x%M*x%M;
return printf("%lld",ans),0;
}
if(v<=100001){
for(i=1;i<=100001;i++)F[i]=(F[i-1]+pow(i,k,M))%M;
for(i=1;i<=n;i++)ans=ans*F[a[i]]%M;
return printf("%lld",ans),0;
}
for(pw[0]=1,i=1;i<k+5;i++)pw[i]=pw[i-1]*i%M;
for(i=1;i<k+5;i++)R[i]=(R[i-1]+pow(i,k,M))%M;
for(i=1;i<k+5;i++){
cc[i]=pow(pw[i-1]*pw[k+4-i],M-2,M)*R[i]%M;
if((k+4-i)&1)cc[i]=(M-cc[i])%M;
}
for(i=1;i<=n;i++)ans=ans*get(a[i],k)%M;
printf("%lld",ans);
}
Road☆ 首先贪心地按A和B的顺序先分配边，这样构成了很多个环，目标是把这些环连到一起，可以转化为最小生成树模型，树上的边就是相邻环的代价
#include<bits/stdc++.h>
#define sqr(x)((x)*(x))
#define N 1001000
using namespace std;int n,i,x,y,z,ans,F[N];
struct P{int y,z;}a[N],b[N],c[N];bool cmp(P a,P b){return a.z>b.z;}
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
int main(){
for(scanf("%d%d%d%d%d%d",&n,&a[1].z,&a[2].z,&x,&y,&z),i=3;i<=n;i++)a[i].z=(a[i-1].z*x+a[i-2].z*y+z)%32767;
for(scanf("%d%d%d%d%d",&b[1].z,&b[2].z,&x,&y,&z),i=3;i<=n;i++)b[i].z=(b[i-1].z*x+b[i-2].z*y+z)%32767;
for(i=1;i<=n;i++)F[i]=a[i].y=b[i].y=i;sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
for(i=1;i<=n;i++)F[gf(b[i].y)]=gf(a[i].y),ans=max(ans,sqr(a[i].z)-sqr(b[i].z));
for(i=1;i<n;i++)c[i].z=sqr(a[i].z)-sqr(b[i+1].z),c[i].y=i;
for(sort(c+1,c+n,cmp),i=n-1;i;i--){
z=c[i].y;x=gf(a[z].y);y=gf(b[z+1].y);
if(x!=y)ans=max(ans,c[i].z),F[x]=y;
}
printf("%d",ans);
}
Mario填格子
整数的lqp拆分
拆迁队☆ 设$d[i]=a[i]-i$，则$f[i]=max(f[j]+1)(d[i]\geq d[j])$
$dp[i]=min(a[i]+b[i]+dp[j]+(i-j+1)*a[j]+(i-j+1)*(i-j)/2)$
设$c[i]=i(i+1)/2+dp[i]-a[i]*i-a[i]$
则$dp[i]=min(c[j]+i*d[j])+b[i]+a[i]+i(i-1)/2$
满足①$j<i$②$f[j]+1=f[i]$③$d[j]\leq d[i]$
按照$f[i]$分组，用$f[i]=x$的组去更新$f[i]=x+1$的答案，并按照序号排序，解决①②两个限制
考虑$j$比$k$更优时，当且仅当$c[j]+i*d[j]<c[k]+i*d[k]$
$\frac{c[j]-c[k]}{d[j]-d[k]}<-i（假设$d[j]\geq d[k]$）
和上题一样利用CDQ分治解决，分治的时候按d排序解决限制③
维护凸壳，查询时在凸壳上二分，时间复杂度$O(nlg^2n)$
Tsinsen上不知为何挂了5分。。
信号塔 把每个菱形先转45°变成正方形，从后往前求出当前正方形的交并记录答案，再从前往后把答案推出来即可
#include<bits/stdc++.h>
using namespace std;struct P{int lx,ly,rx,ry;}w,A[100100];vector<P>v[100100];int n,m,i,j,z,x,y,px,py,d[100100];
void get(P b){w.lx=max(w.lx,b.lx);w.ly=max(w.ly,b.ly);w.rx=min(w.rx,b.rx);w.ry=min(w.ry,b.ry);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&d[i]);
for(i=1;i<=m;i++)scanf("%d%d%d",&z,&x,&y),v[z].push_back(P{x-y-d[z],x+y-d[z],x-y+d[z],x+y+d[z]});
for(w.lx=w.ly=-1e8,w.rx=w.ry=1e8,i=n;i;i--){
w.lx+=d[i];w.ly+=d[i];w.rx-=d[i];w.ry-=d[i];
for(j=0;j<v[i].size();j++)get(v[i][j]);A[i]=w;
w.lx-=d[i];w.ly-=d[i];w.rx+=d[i];w.ry+=d[i];
}
for(w.lx=w.ly=-1e8,w.rx=w.ry=1e8,i=1;i<=n;i++){
get(A[i]);px=w.lx;py=w.ly;
if((px+py)&1)if(w.lx==w.ly)py++;else px++;
printf("%d %d\n",(px+py)/2,(py-px)/2);
w.lx=px+d[i]-d[i+1];w.ly=py+d[i]-d[i+1];w.rx=px-d[i]+d[i+1];w.ry=py-d[i]+d[i+1];
}
}
部落战争
种树
聪聪可可
设计铁路 裸斜率优化
#include<bits/stdc++.h>
#define N 40040
using namespace std;typedef long long LL;
int n,m,i,j,h,t,q[N];LL f[N],g[N],s[N];
struct P{int d,r;}p[N];bool cmp(P a,P b){return a.d>b.d;}
LL gx(LL j,LL k){return f[j]+s[j]-f[k]-s[k];}
LL gy(LL j,LL k){return g[j]-g[k];}
LL gd(LL i,LL j){return f[j]+s[j]-s[i]+(g[i]-g[j])*p[i].d+m;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&p[i].d,&p[i].r);
for(sort(p+1,p+n+1,cmp),i=n-1;i>=0;i--)s[i]=s[i+1]+p[i+1].d*p[i+1].r,g[i]=g[i+1]+p[i+1].r;
for(i=1;i<=n+1;q[++t]=i++){
for(;h<t&&gx(q[h+1],q[h])<gy(q[h+1],q[h])*p[i].d;h++);
for(f[i]=gd(i,q[h]);h<t&&gx(i,q[t])*gy(q[t],q[t-1])>gx(q[t],q[t-1])*gy(i,q[t]);t--);
}
printf("%lld",f[n+1]-m);
}
星际探险 BZOJ上是傻逼最短路
旅游
拉拉队排练 Manacher扫一遍，然后按半径从大到小贪心快速幂就可以了
#include<bits/stdc++.h>
#define N 2000003
#define M 19930726
using namespace std;typedef long long LL;int l,n,i,p,mx,r[N],sum[N];char a[N],s[N];LL k,ans,v;
LL pow(LL a,LL b,LL p){for(v=1;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
int main(){
for(scanf("%d%lld%s",&n,&k,a),s[l++]='&',s[l++]='#',i=0;i<n;i++)s[l++]=a[i],s[l++]='#';
for(i=0;i<l;i++){
for(r[i]=mx>i?min(r[2*p-i],mx-i):1;s[i+r[i]]==s[i-r[i]];r[i]++);
if(i+r[i]>mx)mx=i+r[i],p=i;
if(i%2==0)sum[r[i]/2]++;
}
for(ans=1,i=n;i;i--)sum[i]+=sum[i+1];
for(i=n;i&&k;i--)if(sum[i]<=k)k-=sum[i],ans=ans*pow(2*i-1,sum[i],M)%M;else ans=ans*pow(2*i-1,k,M)%M,k=0;
printf("%lld",ans);
}
男生女生☆ 好题！首先解决第一问，找一个最大的全连边的二分图，不妨建出反图，那么反图的最小割即为答案。
可是还要让男生尽量多，不妨把男生的权值设为$100$，女生的权值设为$99$，跑最小割就可以得到男生更多的答案
这样就解决了第一问，假设答案为$x$个男生，$y$个女生，用DP解决第二问
$f[x][y]$表示选择$x$个男生，$y$个女生的方案数，不妨看成一个$x*y$的方格上取数
那么容斥一下，得到$f[x][y]=c[x*y][k]-\sum_{x\neq x'\ or\ y\neq y'}f[x'][y']*c[x][x']*c[y][y']$
这样时间复杂度是$O(Maxflow+n^4)$
#include<bits/stdc++.h>
#define N 2525
#define P 19921228
using namespace std;bool v[52][52];long long f[52][52],c[N][N];
int n,k,m,x,y,s,t,i,j,I,J,u,tot,V,w,fl,fir[N],d[N],pre[N],cur[N],nb[N],ne[N*3],la[N*3],va[N*3];
void ins(int x,int y,int fl){
la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;
}
int main(){
for(scanf("%d%d%d",&n,&k,&m);m--;)scanf("%d%d",&x,&y),v[x][y]=1;
for(s=2*n+1,t=s+1,tot=i=1;i<=n;i++)for(j=1;j<=n;j++)if(!v[i][j])ins(i,j+n,1e9);
for(i=1;i<=n;i++)ins(s,i,100),ins(i+n,t,99);
for(i=1;i<=t;i++)cur[i]=fir[i];
for(u=s,nb[0]=t;d[s]<t;){
if(u==t){
for(V=1e9,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<V)V=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=V,va[cur[i]^1]+=V;
fl+=V;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],w=t;i;i=ne[i])if(d[la[i]]<w&&va[i])w=d[la[i]];
++nb[d[u]=w+1];if(u!=s)u=pre[u];
}
}
x=fl-fl/99*99;y=fl/99-x;x=n-x;y=n-y;
for(i=0;i<=x*y;i++)for(c[i][0]=1,j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
for(i=1;i<=x;i++)for(j=1;j<=y;j++)for(f[i][j]=c[i*j][k],I=1;I<=i;I++)for(J=1;J<=j;J++)if(I!=i||J!=j)f[i][j]=(f[i][j]-f[I][J]*c[i][I]%P*c[j][J]%P+P)%P;
printf("%d %d\n%lld",x,y,f[x][y]);
}
稳定婚姻☆ 暴力二分图是没什么希望的，发现每次不合法的情况一定是在二分图上构成了一个“环”
由此想到可以把每对婚外情当做一条有向边，然后用tarjan判断每一个点所在的联通分量是否大于$1$，就可以$O(n+m)$出解了
#include<bits/stdc++.h>
#define N 32001
using namespace std;char s[9];int n,m,i,j,w,u,o,tot,id,cnt,di,t,c[N][52],fir[N],ne[N],la[N],low[N],dfn[N],st[N],sz[N],bl[N],is[N],to[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int C(char x){return x>='a'&&x<='z'?x-'a':x-'A'+26;}
void G(){for(scanf("%s",s),u=j=0;s[j];u=c[u][o],j++)if(!c[u][o=C(s[j])])c[u][o]=++id;}
void tj(int x){
low[x]=dfn[x]=++di;is[x]=1;st[++t]=x;int y,i;
for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])for(cnt++,u=0;u!=x;u=st[t--],bl[u]=cnt,sz[cnt]++,is[u]=0);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)G(),to[u]=i,G(),to[u]=i;
for(scanf("%d",&m);m--;)G(),w=to[u],G(),ins(w,to[u]);
for(i=1;i<=n;i++)if(!dfn[i])tj(i);
for(i=1;i<=n;i++)puts(sz[bl[i]]>1?"Unsafe":"Safe");
}
排队 分块在线统计逆序对
礼物 扩展lucas
happiness 神奇的最小割
cheat 分块，记录$s[i][j][k]$表示$1~i,1~j$，在块$1~k$的答案，每$m$分一块，总复杂度$O(n^2m+qm)$
#include<bits/stdc++.h>
using namespace std;
int i,j,k,pa,pb,pc,n,m,O,Q,X1,Y1,X2,Y2,l,r,t,ans,v[255][255],s[255][255][255];long long a[3333],b[3333],c[3333];
int get(int i,int j,int O){return (a[i%pa+1]+b[i%pb+1]+c[i%pc+1]+a[j%pa+1]+b[j%pb+1]+c[j%pc+1])%O+1;}
struct P{int z,x,y;}p[66666];bool cmp(P a,P b){return a.z<b.z;}
int G(int z){
int u,i,V=0,o;
for(u=0;u<m;u++)if(p[u*n+1].z>z)break;
if(p[u*n+1].z>z)u--;if(u==m)u--;
if(u>=0){
V=s[X2][Y2][u]+s[X1-1][Y1-1][u]-s[X2][Y1-1][u]-s[X1-1][Y2][u];o=u*n;
for(i=2;i<=n;i++)if(p[o+i].z<=z&&p[o+i].z!=p[o+1].z)if(X1<=p[o+i].x&&p[o+i].x<=X2&&Y1<=p[o+i].y&&p[o+i].y<=Y2)V++;
}return V;
}
int main(){
for(scanf("%d",&pa),i=1;i<=pa;i++)scanf("%lld",&a[i]);
for(scanf("%d",&pb),i=1;i<=pb;i++)scanf("%lld",&b[i]);
for(scanf("%d",&pc),i=1;i<=pc;i++)scanf("%lld",&c[i]);
for(scanf("%d%d%d%d",&n,&m,&O,&Q),i=1;i<=n;i++)for(j=1;j<=m;j++)v[i][j]=get(i,j,O),p[++t]=P{v[i][j],i,j};
for(sort(p+1,p+t+1,cmp),i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<m;k++)if(v[i][j]>p[k*n+1].z)s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]-s[i-1][j-1][k];else s[i][j][k]=s[i][j-1][k]+s[i-1][j][k]-s[i-1][j-1][k]+1;
for(i=1;i<=Q;i++){
X1=get(i,1,n);Y1=get(i,2,m);X2=get(i,3,n);Y2=get(i,4,m);l=get(i,5,O);r=get(i,6,O);
if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);if(l>r)swap(l,r);ans^=(G(r)-G(l-1));
}
printf("%d",ans);
}
candy 记录多个前缀和，加一加减一减，对于每个询问$O(1)$回答
#include<bits/stdc++.h>
using namespace std;int pa,pb,pc,n,m,i,j,p,q,x,y,z,a[3030],b[3030],c[3030];
long long ans,v[620][620],s2[620][620],s3[620][620],s4[620][620],s5[620][620];
int G(int i,int j){return a[i%pa+1]+b[i%pb+1]+c[i%pc+1]+a[j%pa+1]+b[j%pb+1]+c[j%pc+1];}
int main(){
for(scanf("%d",&pa),i=1;i<=pa;i++)scanf("%d",&a[i]);
for(scanf("%d",&pb),i=1;i<=pb;i++)scanf("%d",&b[i]);
for(scanf("%d",&pc),i=1;i<=pc;i++)scanf("%d",&c[i]);
for(scanf("%d%d%d%d",&n,&m,&p,&q),n+=10,m+=10,i=6;i<=n-5;i++)for(j=6;j<=m-5;j++)v[i][j]=G(i-5,j-5)%p+1;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)v[i][j]=v[i][j-1]+v[i][j],s2[i][j]=s2[i][j-1]+v[i][j],s3[i][j]=s3[i-1][j]+s2[i][j],s4[i][j]=s4[i-1][j-1]+s2[i][j],s5[i][j]=s5[i-1][j+1]+s2[i][j];
for(i=1;i<=q;i++){
x=G(i,1)%(n-10)+6;y=G(i,2)%(m-10)+6;z=G(i,3)%min(min(x-5,y-5),min(n-5-x+1,m-5-y+1))+1;
ans^=(s4[x][y+z-1]-s4[x-z][y-1]+s4[x+z-1][y-2]-s4[x-1][y-z-2]+s5[x-1][y-z]-s5[x-z][y-1]+s5[x+z-1][y]-s5[x][y+z-1]-2*(s3[x+z-1][y-1]-s3[x-z][y-1]));
}
printf("%lld",ans);
}
等差子序列 正解应该是HASH，我用了一个分治+Cheat的方法。取出一个最大的，然后两边看看能不能找到小的和大的构成等差数列。分治下去。取出一个最小的做同样的事。数据实在太弱特判1组水过了。
最短路☆ 静态仙人掌（杨天树），学习了一下。这个图是分层的，所以可以先最短路求出1号点到每个点的距离，然后处理处每个环，环上其他点向环头连边建立出新树，在新树上求LCA，进行以下讨论：
①两个点在一条链上，直接输出两个点在最短路上的距离差
②LCA后两个点在一个环上，先加上两个点到环上点的距离，再加上环上较短的一段
③LCA后两个点不在一个环上，直接按正常LCA返回距离
#include<bits/stdc++.h>
#define N 10020
using namespace std;bool us[N*4],v[N];int n,m,Q,i,h,t,x,y,z,tot,cnt,id,d[N],H[N],q[N],rd[N],rl[N],bl[N],dfn[N],fir[N],pre[N],F[N][14],ne[N*4],la[N*4],va[N*4];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void gr(int x,int y,int z){
us[z]=us[z^1]=1;rl[++cnt]+=va[z];
for(int i=y;i!=x;i=la[pre[i]^1])bl[i]=cnt,us[pre[i]]=us[pre[i]^1]=1,ins(x,i,0),rl[cnt]+=va[pre[i]];
}
void dfs(int x){
dfn[x]=++id;
for(int i=fir[x],y;i;i=ne[i])if(i!=(pre[x]^1)&&i<=m*2+1)if(!dfn[y=la[i]])pre[y]=i,rd[y]=rd[x]+va[i],dfs(y);else if(dfn[y]<dfn[x])gr(y,x,i);
}
void dfs2(int x){
v[x]=1;int i,y;for(i=1;i<=13;i++)F[x][i]=F[F[x][i-1]][i-1];
for(i=fir[x];i;i=ne[i])if(!us[i]&&la[i]!=F[x][0])F[y=la[i]][0]=x,H[y]=H[x]+1,dfs2(y);
}
int qu(int x,int y){
if(H[x]<H[y])swap(x,y);int t=H[x]-H[y],i,o=d[x]+d[y],w=d[x]-d[y];
for(i=0;i<=13;i++)if(t&(1<<i))x=F[x][i];if(x==y)return w;
for(i=13;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];t=F[x][0];
return bl[x]&&bl[x]==bl[y]?o-d[x]-d[y]+min(rl[bl[x]]-abs(rd[x]-rd[y]),abs(rd[x]-rd[y])):o-2*d[t];
}
int main(){
for(scanf("%d%d%d",&n,&m,&Q),i=tot=1;i<=m;ins(x,y,z),ins(y,x,z),i++)scanf("%d%d%d",&x,&y,&z);
for(memset(d,63,sizeof(d)),d[q[t=1]=1]=0,v[1]=1;h^t;)for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[++t]=y]=1;
for(dfs(1),memset(v,0,sizeof(v)),dfs2(1);Q--;printf("%d\n",qu(x,y)))scanf("%d%d",&x,&y);
}
排斥反应☆ 把问题转化为在$p*q$矩阵上取若干个元素，任意两个不相邻的方案个数
如果直接$2^p$是$1024$，不能接受，把不合法状态去掉后变成$123$，复杂度$O(123^3lgq)$
#include<bits/stdc++.h>
#define M 19921107
int p,T,t,i,j,A,B,C,q[124];long long ans,f[124][124],h[124][124],g[124][124];
void dfs(int x,int y){
if(x==p-1){
if(!((1<<(x-1))&y)&&y%2==0)q[++t]=y+(1<<x);
q[++t]=y;
}else if(!x)dfs(x+1,0),dfs(x+1,1);else{
if(!((1<<(x-1))&y))dfs(x+1,y+(1<<x));
dfs(x+1,y);
}
}
int main(){
for(scanf("%d%d",&p,&T),dfs(0,0),i=1;i<=t;f[i][i]=1,i++)for(j=1;j<=t;j++)if(!(q[i]&q[j]))g[i][j]++;
for(T--,i=0;i<=30;i++){
if(T>>i&1){
for(memset(h,0,sizeof(h)),A=1;A<=t;A++)for(B=1;B<=t;B++)for(C=1;C<=t;C++)h[A][B]=h[A][B]+f[A][C]*g[C][B];
for(A=1;A<=t;A++)for(B=1;B<=t;B++)f[A][B]=h[A][B]%M;
}
for(memset(h,0,sizeof(h)),A=1;A<=t;A++)for(B=1;B<=t;B++)for(C=1;C<=t;C++)h[A][B]=h[A][B]+g[A][C]*g[C][B];
for(A=1;A<=t;A++)for(B=1;B<=t;B++)g[A][B]=h[A][B]%M;
}
for(i=1;i<=t;i++)for(j=1;j<=t;j++)if(!(q[i]&q[j])||!T)ans=(ans+f[i][j])%M;
printf("%lld",ans);
}
字符串游戏 $f[i][j][k][p]$表示$i$到$j$是否可以表示第$k$个字符串的前$p$个字符，$c[i][j]$表示$i$到$j$是否可以全部删去。
转移$f[i][j][k][p]|=(f[j-1][k][p-1]&S[k][p]==s[j])\ or\ (f[d][k][p]&c[d+1][j])$
#include<bits/stdc++.h>
using namespace std;char s[155],S[33][22];bool f[155][33][22],c[155][155];int l,m,i,j,k,p,u,L[33],g[155];
int main(){
for(scanf("%s%d",s+1,&m),l=strlen(s+1),i=1;i<=m;i++)scanf("%s",S[i]+1),L[i]=strlen(S[i]+1);
for(i=l;i;i--){
for(memset(f,0,sizeof(f)),j=1;j<=m;j++)f[i-1][j][0]=1;
for(j=i;j<=l;j++){
for(k=1;k<=m;k++)for(p=1;p<=L[k];p++)f[j][k][p]|=(f[j-1][k][p-1]&S[k][p]==s[j]);
for(u=i;u<=j;u++)if(c[u+1][j])for(k=1;k<=m;k++)for(p=1;p<=L[k];p++)f[j][k][p]|=f[u][k][p];
}
for(j=i;j<=l;j++)for(k=1;k<=m;k++)c[i][j]|=f[j][k][L[k]];
}
for(i=1;i<=l;i++)for(g[i]=g[i-1]+1,j=1;j<=i;j++)if(c[j][i])g[i]=min(g[i],g[j-1]);
printf("%d",g[l]);
}
股市的预测 HASH大法好！差分后枚举A串长度，用HASH求出前面一段和后面一段最多弄多少，时间复杂度是调和级数*二分HASH的复杂度，即$nlg^2n$，BZOJ上卡了好几发才过。
#include<bits/stdc++.h>
#define M 1000000007
#define N 111111
using namespace std;typedef long long LL;int n,m,i,j,o,la,a[N];LL ans,O,I[N],sm[N];
inline LL C(const int&l,const int&r){return (sm[r]-sm[l-1]+M)*I[l-1]%M;}
inline bool G(const int&x,const int&y,const int&z){return C(x,x+z-1)==C(y,y+z-1);}
inline int get(const int&x,const int&y){
int l=1,r=min(n*2+1-y+1,n),mid,A=0;
for(;l<=r;)if(G(x,y,mid=l+r>>1))l=(A=mid)+1;else r=mid-1;
return A;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(n--,i=1;i<=n;i++)a[i]=a[i+1]-a[i],a[n+n+2-i]=a[i];a[n+1]=23333333;
for(I[0]=O=i=1;i<=2*n+1;i++)O=O*999983%M,sm[i]=(sm[i-1]+1ll*(a[i]+M)*O)%M,I[i]=I[i-1]*496501444%M;
for(j=1;j+j+m<=n;j++)for(la=0,i=1;i+j+m<=n;i+=j){
o=min(get(i,i+j+m),j);if(o+la>=j)ans+=o+la-j+1;
la=min(get(n+n-i-j+3,n*2-i-j-j-m+3),j-1);
}printf("%lld",ans);
}
数颜色
墨墨的等式 任选一个$a_i$，那么如果$x+ka_i$可以凑出来，那么$x+(k+w)a_i$也可以凑出来。于是对于每个$x$找到最小的满足条件的$k$就好了，使用最短路即可。
JZPFAR 直接上K-D树（口胡）
tree 直接LCT（口胡）
Crisis(GG) 建出矩阵，然后主席树往下传。。然后矩阵TM不能换，一定要按顺序，爆炸了
黑白染色 不同颜色连1边否则连0边，每个点为起点跑最短路，找到一个点使距离最远的黑点最小。不知为何挂了5分。。
#include<bits/stdc++.h>
using namespace std;char s[44][44];
int n,m,i,j,p,h,t,S,x,y,ans=1e9,tot,fir[1666],d[1666],ne[8888],la[8888],va[8888],c[1666],q[23333333],v[1666];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void I(int x,int y,int z){ins(x,y,z);ins(y,x,z);}
int G(int x,int y){return x*m-m+y;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)for(scanf("%s",s[i]+1),j=1;j<=m;j++){
c[G(i,j)]=s[i][j]=='B'?1:0;
if(i>1)I(G(i,j),G(i-1,j),s[i][j]!=s[i-1][j]);
if(j>1)I(G(i,j),G(i,j-1),s[i][j]!=s[i][j-1]);
}
for(S=1;S<=n*m;S++){
for(memset(d,63,sizeof(d)),h=d[q[t=1]=S]=0,v[S]=1;h^t;)for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],v[y]!=S)v[q[++t]=y]=S;
for(p=0,i=1;i<=n*m;i++)if(c[i])p=max(p,d[i]+1);ans=min(ans,p);
}
printf("%d",ans);
}
矩形计算☆ 离线好题啊。。可是没讲
对于出现次数比较多的点，预处理出答案
对于出现次数比较少的点，枚举点对做矩形，这样每次询问相当于询问一个矩形里有多少个矩形
把一维排序后变成三维数点，树状数组解决
设这个出现次数的分界线为p，则时间复杂度为$O(n^2m^2/p+Q(nm/p+lg^3n)+(nm/p)lg^3n))$
#include<bits/stdc++.h>
#define N 40040
#define M 100100
using namespace std;long long ans[M];
int n,m,i,j,k,w,o,t,x,O,Q,cnt,X1,X2,Y1,Y2,a[202][202],b[N],s[202][202][802],c[202][202][202];
struct U{int x,y;};vector<U>v[N];
struct P{int x1,y1,x2,y2,id;}q[M],p[M*9];bool cmp(P a,P b){return a.x1>b.x1;}
void add(int x,int y,int z){int i,j;for(;x;x-=x&-x)for(i=y;i<201;i+=i&-i)for(j=z;j<201;j+=j&-j)c[x][i][j]++;}
int qu(int x,int y,int z){int i,j,v=0;for(;x<201;x+=x&-x)for(i=y;i;i-=i&-i)for(j=z;j;j-=j&-j)v+=c[x][i][j];return v;}
int main(){
for(scanf("%d%d",&n,&m),O=40,i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]),b[++w]=a[i][j];
sort(b+1,b+w+1);cnt=unique(b+1,b+w+1)-b-1;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)v[a[i][j]=lower_bound(b+1,b+cnt+1,a[i][j])-b].push_back(U{i,j});
for(k=1;k<=cnt;k++)if(v[k].size()>O)
for(o++,i=1;i<=n;i++)for(j=1;j<=m;j++)s[i][j][o]=s[i-1][j][o]+s[i][j-1][o]-s[i-1][j-1][o]+(a[i][j]==k);
else{
for(i=0;i<v[k].size();i++)for(j=0;j<v[k].size();j++){
X1=v[k][i].x;Y1=v[k][i].y;X2=v[k][j].x;Y2=v[k][j].y;
p[++t]=P{min(X1,X2),min(Y1,Y2),max(X1,X2),max(Y1,Y2)};
}
}
for(scanf("%d",&Q),i=1;i<=Q;i++){
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);q[i]=P{X1,Y1,X2,Y2,i};
for(j=1;j<=o;j++)x=s[X2][Y2][j]+s[X1-1][Y1-1][j]-s[X1-1][Y2][j]-s[X2][Y1-1][j],ans[i]+=1ll*x*x;
}
sort(p+1,p+t+1,cmp);sort(q+1,q+Q+1,cmp);
for(i=j=1;i<=Q;i++){
for(;p[j].x1>=q[i].x1;j++)add(p[j].y1,p[j].x2,p[j].y2);
ans[q[i].id]+=qu(q[i].y1,q[i].x2,q[i].y2);
}
for(i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}
城市改建☆ 大力树DP，$f[i]$表示子树直径，$h[i]$表示子树外直径，那么答案为$min(max(f[i],h[i],(f[i]+1)/2+(h[i]+1)/2+1))$
但是还要记录方案，那么记录g,g2,g3表示往下伸的第一，第二，第三长长度，u表示往上伸的最长长度
那么第二遍DFS时，$h[y]=max(h[x],f[i],g[i]+g[j]+2,g[i]+1+u[x])(i\geq j,j\geq y,i\geq y)$，$u[y]=max(u[x]+1,g[i]+2)(i\geq y)$用记录的三个值完成转移
#include<bits/stdc++.h>
#define N 300300
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;}
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 fd(int x,int F){
memset(fa,0,sizeof(fa));fa[x]=F;dfs(x);
return cal(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\n%d %d\n",G(A),A,fa[A]);
printf("%d %d\n",fd(A,Y),fd(Y,A));
}
Calc d=gcd(i,j),i=ad,j=bd,gcd(a,b)=1,(a+b)|abd,gcd(a,b)=1-->gcd(a+b,b)=1,gcd(a+b,a)=1,-->(a+b)|d,d=(a+b)t
只需求a<b gcd(a,b)=1 b(a+b)t<=n，打表也可以找到这个规律。然后枚举b，乱搞。。
Attack K-D树套权值线段树，时间复杂度$O(nlgn+m\sqrt{n}lgn)$。
#include<bits/stdc++.h>
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define N 60600
#define M 23333333
using namespace std;char s[9];
int n,m,i,l,r,O,k,x,y,z,V,id,md,rt,W,X,Y,X1,Y1,X2,Y2,t1,t2,Z[N],T[N],to[N],q1[N],q2[N],L[M],R[M],sz[M];
struct P{int l,r,z,fa,id,d[2],mi[2],mx[2];}p[N];
bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
void ins(int&k,int l,int r,int x,int z){
if(!k)k=++id;sz[k]+=z;if(l==r)return;int md=l+r>>1;
if(x<=md)ins(L[k],l,md,x,z);else ins(R[k],md+1,r,x,z);
}
void tou(int k,int rt){
ins(T[rt],1,W,p[k].z,1);
if(p[k].l)tou(p[k].l,rt);if(p[k].r)tou(p[k].r,rt);
}
int bt(int l,int r,int o,int fa){
O=o;int k=l+r>>1,i;nth_element(p+l,p+k,p+r+1,cmp);
for(i=0;i<2;i++)p[k].mi[i]=p[k].mx[i]=p[k].d[i];to[p[k].id]=k;p[k].fa=fa;
if(l<k)for(p[k].l=bt(l,k-1,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].l].mi[i]),Mx(p[k].mx[i],p[p[k].l].mx[i]);
if(k<r)for(p[k].r=bt(k+1,r,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].r].mi[i]),Mx(p[k].mx[i],p[p[k].r].mx[i]);
return tou(k,k),k;
}
void qu(int k){
if(X1>p[k].mx[0]||X2<p[k].mi[0]||Y1>p[k].mx[1]||Y2<p[k].mi[1])return;
if(X1<=p[k].mi[0]&&p[k].mx[0]<=X2&&Y1<=p[k].mi[1]&&p[k].mx[1]<=Y2){q1[++t1]=T[k];return;}
if(X1<=p[k].d[0]&&p[k].d[0]<=X2&&Y1<=p[k].d[1]&&p[k].d[1]<=Y2)q2[++t2]=k;
if(p[k].l)qu(p[k].l);if(p[k].r)qu(p[k].r);
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d%d",&p[i].d[0],&p[i].d[1],&p[i].z),p[i].id=i,Z[i]=p[i].z;
for(sort(Z+1,Z+n+1),W=unique(Z+1,Z+n+1)-Z-1,i=1;i<=n;i++)p[i].z=lower_bound(Z+1,Z+W+1,p[i].z)-Z;
for(rt=bt(1,n,0,0);m--;)
if(scanf("%s",s),s[0]=='S'){
scanf("%d%d",&x,&y);x++;y++;
for(X=to[x],z=p[X].z;X;X=p[X].fa)ins(T[X],1,W,z,-1);
for(Y=to[y];Y;Y=p[Y].fa)ins(T[Y],1,W,z,1);
for(Y=to[y],z=p[Y].z;Y;Y=p[Y].fa)ins(T[Y],1,W,z,-1);
for(X=to[x];X;X=p[X].fa)ins(T[X],1,W,z,1);
swap(p[to[x]].z,p[to[y]].z);
}else{
scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&k);t1=t2=0;
if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);qu(rt);
for(V=0,i=1;i<=t1;i++)V+=sz[q1[i]];if(V+t2<k){puts("It doesn't exist.");continue;}
for(l=1,r=W;l<r;){
md=l+r>>1;V=0;
for(i=1;i<=t1;i++)V+=sz[L[q1[i]]];
for(i=1;i<=t2;i++)if(p[q2[i]].z<=md&&p[q2[i]].z>=l)V++;
if(k<=V)for(r=md,i=1;i<=t1;i++)q1[i]=L[q1[i]];
else for(l=md+1,k-=V,i=1;i<=t1;i++)q1[i]=R[q1[i]];
}
printf("%d\n",Z[l]);
}
}
飞行计划 每个点拉链，把所有和他入边和出边有关的权值作为一个点。上行边有费用，下行边无费用，两点间再连边。但这样横向边有点多。发现太离谱的话还不如先上后下而不走横向边，优化一下可以大大缩小边数，就能通过了。
航班计划 直观的费用流建图可以按时间建分层图，可这样点数NT不能接受。可以把所有$M$个条件建分层图，把$M$个条件拆点，两点间连费用的边，如果两个条件间可以互达或者起点可以到左部或者右部可以到终点就连。点数$O(m)$，边数$O(m^2)$
特技飞行 普及水题。
世博会 坐标转化后两个坐标独立，然后建一颗主席树求出区间和和权值和并在上面二分即可，懒写了个暴力。
JZPLCM☆ 离线好题啊。。可是没讲
对每个数，拆分成$p_i^{a_i}$的形式，对质数的每个幂记录一个状态表示，贡献为$p_i$
每个询问就是询问一段区间有多少种不同的状态，把贡献乘起来，离线后BIT维护
#include<bits/stdc++.h>
#define M 1000000007
using namespace std;typedef long long LL;map<int,int>mp;
int Q,n,i,j,k,t,o,w,x,id,v[2333333],p[33333];bool f[33333];
struct P{int x,y,z,l;}u[2333333],q[111111];LL c[111111],ans[111111];
bool cmp(P a,P b){return a.y<b.y;}
LL pow(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
void add(int x,int z){if(!x)return;for(;x<=n;x+=x&-x)c[x]=c[x]*z%M;}
LL qu(int x){LL v=1;for(;x;x-=x&-x)v=v*c[x]%M;return v;}
int main(){
for(scanf("%d%d",&n,&Q),i=2;i<33333;i++){
if(!f[i]){
p[++t]=i;
for(j=1;1ll*j*i<=1e9;)j*=i,mp[j]=++id;
}
for(j=1;j<=t&&i*p[j]<33333;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(i=1;i<=n;i++){
scanf("%d",&x);c[i]=1;
for(j=1;p[j]*p[j]<=x;j++)for(w=1;x%p[j]==0;x/=p[j])w*=p[j],u[++o]=P{i,mp[w],p[j],0};
if(x>1){
if(!mp[x])mp[x]=++id;
u[++o]=P{i,mp[x],x,0};
}
}
for(i=1;i<=o;i++)u[i].l=v[u[i].y],v[u[i].y]=u[i].x;
for(i=1;i<=Q;i++)scanf("%d%d",&q[i].x,&q[i].y),q[i].z=i;
for(sort(q+1,q+Q+1,cmp),i=j=k=1;i<=n;i++){
for(;u[j].x==i&&j<=o;j++)add(u[j].x,u[j].z),add(u[j].l,pow(u[j].z,M-2,M));
for(;q[k].y==i&&k<=Q;k++)ans[q[k].z]=qu(i)*pow(qu(q[k].x-1),M-2,M)%M;
}
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
}
2016年2月21日 11:02
贵贵贵贵
2016年11月01日 20:17
信号塔:
6 1
999995 999996 999997 999998 999999 1000000
6 -1000000 -1000000
您的答案好像越界了