来自FallDreaｍ的博客，未经允许，请勿转载，谢谢。
————————————————————————
A.n个数，m个询问，每次给出区间[li,ri]和xi，yi，求这个区间中膜x=y的数的个数。n,m,x,y<=40000
我的sb做法：确定一个k，大概根号n，我定的是400。大于k的操作主席树，小于k的操作分块。复杂度n^1.5+n^2logn/k，还是挺科学的。但是因为主席树常数太大，T了一个点（全部是大于k的询问）
#include<iostream> #include<cstdio> #include<cmath> #define MAXN 40000 #define MN 2000000 #define DITOLY 400 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } struct TREE{ int l,r,x; }T[MN+5]; int n,cnt=0,L,R,X,Y,q; int rt[MAXN+5],block[MAXN+5],size,ans; int num[205][DITOLY+5][DITOLY+5],s[MAXN+5]; int query(int x,int k) { int l=1,r=MAXN+1,mid; while(l<r) { mid=l+r>>1; if(k<=mid)x=T[x].l,r=mid; else x=T[x].r,l=mid+1; } return T[x].x; } void ins(int x,int nx,int k) { int l=1,r=MAXN+1,mid; while(l<r) { mid=l+r>>1;T[nx].x=T[x].x+1; if(k<=mid) { T[nx].r=T[x].r;T[nx].l=++cnt; x=T[x].l;nx=T[nx].l;r=mid; } else { T[nx].l=T[x].l;T[nx].r=++cnt; x=T[x].r;nx=T[nx].r;l=mid+1; } } T[nx].x=T[x].x+1; } int solve() { register int i; if(block[L]+1>=block[R]){ for(i=L;i<=R;i++) ans+=(s[i]%X==Y); return ans; } for(i=block[L]+1;i<block[R];i++) ans+=num[i][X][Y]; for(i=L;block[i]==block[L];i++) ans+=(s[i]%X==Y); for(i=R;block[i]==block[R];i--) ans+=(s[i]%X==Y); return ans; } int main() { // freopen("datastructure.in","r",stdin); // freopen("datastructure.out","w",stdout); n=read();q=read();size=sqrt(n); for(int i=1;i<=n;i++)block[i]=(i-1)/size+1; for(int i=1;i<=n;++i) { s[i]=read(); for(int j=1;j<=DITOLY;j++) ++num[block[i]][j][s[i]%j]; ins(rt[i-1],rt[i]=++cnt,s[i]+1); } for(register int i=1;i<=q;++i) { L=read();R=read();X=read();Y=read();ans=0; if(X>=DITOLY) { for(register int j=Y;j<=MAXN;j+=X) ans+=query(rt[R],j+1)-query(rt[L-1],j+1); printf("%d ",ans); } else printf("%d ",solve()); } return 0; }
靠谱做法：题目不要求在线，所以把询问拆成两个，然后排序，只要往前推，差分一下就好啦。 复杂度qlogq+qn^0.5
#include<iostream> #include<cstdio> #include<algorithm> #define MN 40000 #define MM 200 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } struct ques{ int x,num,ad,X,Y; }q[MN*2+5]; int tot=0,n,m; int ans[MN+5],s[MN+5]; bool cmp(ques x,ques y){return x.x<y.x;} int f[MM+5][MM+5],f2[MN+5]; int calc(int X,int Y) { if(X<=MM) return f[X][Y]; int sum=0; for(int i=Y;i<=MN;i+=X) sum+=f2[i]; return sum; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) s[i]=read(); for(int i=1;i<=m;i++) { int l=read(),r=read(),x=read(),y=read(); if(l!=1) q[++tot]=(ques){l-1,i,-1,x,y}; q[++tot]=(ques){r,i,1,x,y}; } sort(q+1,q+tot+1,cmp); for(int i=1,j=1;i<=n;i++) { for(int k=1;k<=MM;k++) f[k][s[i]%k]++; f2[s[i]]++; for(;j<=tot&&q[j].x==i;j++) ans[q[j].num]+=q[j].ad*calc(q[j].X,q[j].Y); } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }
Ｂ．给定ｎ道题，每道题有出现时间ｘ和难度增加量ｗ，如果没有在ｘ时完成，每一秒他的难度就会提高ｗ，你可以在任意时间写其中的一段作业，但是只能写ｋ次。你要求出最小的总难度。
n,k<=5000 改编自ｂｚｏｊ１０９６仓库建设。
题解：看到题目很容易想到斜率优化，做法和仓库建设一样。
#include<iostream> #include<cstdio> #define ll long long #define INF (double)2000000000000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,K; ll f[5005][5005]; ll W[5005],P[5005],G[5005]; int x[5005],q[5005],top,tail; double get(int x,int y) { if(W[x]==W[y]) return G[x]>=G[y]?INF:-INF; return (double)(G[x]-G[y])/(W[x]-W[y]); } void ins(int num) { while(top>tail&&get(num,q[top])<get(q[top],q[top-1])) top--; q[++top]=num; } ll Solve(int x) { while(top>tail&&get(q[tail+1],q[tail])<x) tail++; return q[tail]; } int main() { n=read();K=read(); for(int i=1;i<=n;i++) { x[i]=read();W[i]=read(); P[i]=P[i-1]+x[i]*W[i]; W[i]+=W[i-1]; } for(int i=1;i<=n;i++) f[1][i]=x[i]*W[i]-P[i]; for(int k=2;k<=K;k++) { top=-1;tail=0; for(int i=1;i<=n;i++) { G[i-1]=f[k-1][i-1]+P[i-1]; ins(i-1); int from=Solve(x[i]); f[k][i]=f[k-1][from]-P[i]+P[from]+1LL*x[i]*(W[i]-W[from]); //cout<<k<<" "<<i<<" "<<"Find"<<from<<" "<<f[k][i]<<endl; } } cout<<f[K][n]<<endl; return 0; }
C.你的三角形已如风中残烛
给定n个点，有部分点之间有连边，你要选一些点，使得形成的三角形数量比去选的点的数量的值最大。n<=50
题解：我们把三角形全部找出来，和T连流量为1边，然后三角形从对应的三个点连INF的边，每个点都从S向它连边.
然后我们二分一个答案，并且把S向每个点的连边的流量改成它。当到T的边全部满流时候，存在答案。
这样以后我们从S出发dfs，只走还剩余流量的边，走到的点显然都不是最优解，我们输出剩下的点就可以啦。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #define eps 1e-10 #define INF 2000000000 #define T 9851 #define S 0 #define ld long double using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int head[T+5],d[T+5],q[T+5],cnt=1,n,tot,top,c[T+5]; struct edge{ int to,next;ld w; }e[1200000]; bool b[55][55]; void ins(int f,int t,ld w) { e[++cnt]=(edge){t,head[f],w};head[f]=cnt; e[++cnt]=(edge){f,head[t],0};head[t]=cnt; } ld dfs(int x,ld f) { if(x==T)return f; ld used=0; // cout<<"dfs"<<x<<" "<<f<<endl; for(int&i=c[x];i;i=e[i].next) if(e[i].w>0&&d[e[i].to]==d[x]+1) { ld w=dfs(e[i].to,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(fabs(f-used)<eps) return f; } return used; } bool bfs() { memset(d,0,sizeof(d));int i,j; for(d[q[top=i=0]=S]=1;i<=top;i++) for(int j=c[q[i]]=head[q[i]];j;j=e[j].next) if(e[j].w>0&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[T]>0; } void solve(int x) { // cout<<"solve"<<x<<endl; if(!d[x]) { d[x]=1; for(int&i=head[x];i;i=e[i].next) if(e[i].w>1e-6) solve(e[i].to); } } int main() { // freopen("triangle.in","r",stdin); // freopen("triangle.out","w",stdout); tot=n=read(); for(int i=1;i<=n;i++) ins(S,i,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=read(); for(int i=1;i<n;i++) for(int j=i+1;j<n;j++) for(int k=j+1;k<=n;k++) if(b[i][j]&&b[i][k]&&b[j][k]) { ++tot;ins(i,tot,INF);ins(j,tot,INF); ins(k,tot,INF);ins(tot,T,1); } ld l=0,r=393,mid,sum=0; int i,j;tot-=n; while(l+eps<r) { mid=(l+r)/2;sum=0; for(i=2,j=1;j<=n;j++,i+=2) e[i].w=mid,e[i^1].w=0; for(;i<=cnt;i+=2) e[i].w=1,e[i^1].w=0; while(bfs()) sum+=dfs(S,INF); if((ld)tot<=sum)r=mid; else l=mid; } // cout<<mid<<endl; top=0;memset(d,0,sizeof(d)); solve(S); for(int i=1;i<=n;i++)if(!d[i])q[++top]=i; cout<<top<<endl; for(int i=1;i<=top;i++) printf("%d ",q[i]); return 0; }