来自FallDream的博客，未经允许，请勿转载，谢谢。
听学长说的就来玩一玩，随便乱打打 没想到一堆人被取消了成绩，莫名混了个Rank3
还有第一题数据肯定是有问题
------------------------------------------
T1 邦邦的大合唱站队／签到题
N个偶像排成一列，他们来自M个不同的乐队。每个团队至少有一个偶像。
现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。
请问最少让多少偶像出列？ n<=100000 m<=20
题解：这个应该很好想到状压dp吧 用f[i]表示选的乐队的状态是i的最小出列人数，那么枚举一个乐队转移一下就好了，至于算要出列多少人，可以差分一下。复杂度$m*2^{m}$
/*然后我来教你们怎么AC
首先，快速读入统统删掉，加了快速读入只有20分，其它全是T。
然后呢，虽然我们只需要差分数组，但是呢，必须把ai读入到数组里，不能读到变量。读到变量只有70，不信自己试试。大概是数据有问题，数组会溢出。
最后呢，写写代码，cin或者scanf随意。*/
数据已经修正了，没毛病。我貌似被这个从100坑到了60
#include<iostream> #include<cstdio> #include<cstring> #define MN 200000 #define MM 30 #define int long long using namespace std; int X; //inline int read() //{ // cin>>X;return X; /* 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,m,s[MN+5]; int f[MM+2][MN+5],size[MN+5],tot[(1<<21)+5],F[(1<<21)+5]; main() { // freopen("sb.in","r",stdin); cin>>n>>m; for(register int i=1;i<=n;i++) { cin>>s[i]; for(register int j=1;j<=m;j++) f[j][i]=f[j][i-1]; ++f[s[i]][i];++size[s[i]]; } for(register int i=0;i<1<<m;i++) for(register int j=0;j<m;j++) if((1<<j)&i) tot[i]+=size[j+1]; memset(F,42,sizeof(F));F[0]=0; for(register int i=1;i<1<<m;i++) for(register int j=1;j<=m;j++) if(i&(1<<(j-1))) F[i]=min(F[i],F[i^(1<<(j-1))]+size[j]-f[j][tot[i]]+f[j][tot[i]-size[j]]); printf("%lld ",F[(1<<m)-1]); return 0; }
B.开心派对小火车
Aqours铁路公司旗下有N个站，编号1,2,..,N。
有各停（各站停车）电车特急电车两种。特急车会在si..sm，一共M个车站停车。
相邻的两站(即编号为i的车站和编号为的车站，而不是特急电车停车的相邻的两站)之间，各停电车要运行A分钟，特急需要B分钟。我们认为列车一直匀速运行，不考虑停车和加减速。
现在要加一种快速电车，要求其停站覆盖所有的特急电车的停站，而相邻的两站要运行C分钟。为了要快，决定刚好停K个站(k>m，包括特急的所有车站）。如果一个站可以停多种电车，那么旅客可以在这一站换乘。不过只能向前坐车，不能往回坐。
你需要设计一种快速列车的设站方案，要求旅客在T分钟**乘车时间（等车和换乘时间不计）**内，可以从1号站到尽可能多数量的站。你只需要告知能有几站可以达到。
n,a,b,c<=10^9, m,k<=3000 ,T<=10^18
题解：答案肯定是你做B车到一个站，转C车，然后做A车，所以对于每一个段，你都右端点贪心，也就是每次选择目前能到的点建站。然后把这些塞到一个堆里，每次取出最大，重新算一下塞回去就行了。
复杂度只有klogm，不是很懂。
#include<iostream> #include<cstdio> #include<queue> #define pa pair<int,int> #define mp(x,y) make_pair(x,y) #define ll long long 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,m,k,a,b,c,s[3005],r[3005]; ll ans,T,t[3005]; priority_queue<pa>q; void push(int x) { if(r[x]==s[x+1]-1) return;++r[x]; ll time=(T-t[x]-1LL*(r[x]-s[x])*c); if(time<0)return; int R=(int)min(1LL*(s[x+1]-1),r[x]+time/a); q.push(mp(R-r[x]+1,x)); r[x]=R; } int main() { n=read();m=read();k=read();a=read();b=read();c=read(); scanf("%lld",&T); for(int i=1;i<=m;i++) s[i]=read();s[m+1]=n+1; for(int i=1;i<=m;i++) { t[i]=1LL*b*(s[i]-s[1]); if(t[i]>T) continue; r[i]=(int)min(1LL*s[i+1]-1,s[i]+(T-t[i])/a); ans+=r[i]-s[i]+1; } for(int i=1;i<m;i++) if(t[i]<=T)push(i);else break; for(int i=1;i<=k-m&&!q.empty();i++) { pa x=q.top();q.pop(); ans+=x.first;push(x.second); } printf("%lld ",ans-1); return 0; }
C.什么？这场比赛有C题？
D.Bushiroad的偶像派对
Bushiroad的派对有N个校园偶像团体，可能来自编号1-N的学校。每个学校可能有多个团体参加，也有可能没有团体参加。在所有的团体都演出完后，进行人气投票。
我们已经掌握分别了中场时和结束时的两张人气排行表。给出排行表从人气高到低排序，并给出每个组的学校编号（你却不知道具体是哪个团体）
可是，结束时的表是不太准确的。因为基于这样的一个事实：某个团体的结束时的人气不会低于中场的人气，而且每个团体的学校不会改变。结束的表产生一些矛盾。
负责统计的人为了不想背锅，希望尽可能少修改结束时的排行表的某些团体的学校（人气值不能改），使其不矛盾，请问至少要修改多少个呢？
题解：现场只会yy了一个费用流，只过了70%的点。
大概就是把每个结束时的人气拆成两个点，表示相同学校和不同学校，然后限制这两个点只能流1，两个点都向比他大的下一个点连边(第二个点往同颜色连边)。每个中场的点和第一个大等他的随意学校和相同学校(如果有)连边，和不同学校的点的连边设置费用1，跑一次费用流。这个能通过70%，也就是5000的数据
正解：贪心
从小到大拿结束时的人气去匹配。显然如果能匹配到相同学校的一定最优，那么只要能判断即可。这个可以通过线段树维护 每个点在他之前还有几个点可以被选 的最小值实现
费用流70%
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<vector> #include<algorithm> #define S 0 #define MAXN 200000 #define INF 200000000 #define getchar() (SS==TT&&(TT=(SS=B)+fread(B,1,1<<15,stdin),SS==TT)?0:(*SS++)) using namespace std; char B[1<<15],*SS=B,*TT=B; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x; } int ans=0,pi=0,T,d[MAXN*4+5],head[MAXN*4+5],n,m,cnt=1,t[MAXN+5],p[MAXN+5],t2[MAXN+5],p2[MAXN+5]; bool mark[MAXN*4+5]; struct edge{ int w,to,next,c; }e[4000000]; vector<int> v[MAXN+5]; deque<int> q; void insw(int f,int t,int w,int c) { e[++cnt].next=head[f];head[f]=cnt; e[cnt].to=t; e[cnt].w=w;e[cnt].c=c; } void ins(int f,int t,int w,int c){insw(f,t,w,c);insw(t,f,0,-c);} bool modlabel() { q.push_back(T); for(int i=0;i<=T;i++) d[i]=INF;d[T]=0; while(!q.empty()) { int u=q.front();q.pop_front(); for(int i=head[u];i;i=e[i].next) if(e[i^1].w&&d[u]+e[i^1].c<d[e[i].to]) { d[e[i].to]=d[u]+e[i^1].c; if(d[e[i].to]<=d[q.size()?q.front():0]) q.push_front(e[i].to); else q.push_back(e[i].to); } } for(int i=0;i<=T;i++) for(int j=head[i];j;j=e[j].next) e[j].c+=d[e[j].to]-d[i]; pi+=d[S]; return d[S]!=INF; } int dfs(int x,int f) { if(x==T) return ans+=pi*f,f; mark[x]=1; int used=0,nown; for(int i=head[x];i;i=e[i].next) if(!mark[e[i].to]&&!e[i].c&&e[i].w) { nown=dfs(e[i].to,min(f-used,e[i].w)); e[i].w-=nown;e[i^1].w+=nown; used+=nown;if(used==f) return f; } return used; } int get(int x) { int l=1,r=n,mid,ans; while(l<=r) { mid=l+r>>1; if(p2[mid]<x) r=mid-1; else ans=mid,l=mid+1; } return ans; } int get2(int x,int c) { int l=0,r=v[c].size()-1,mid,ans=-1; while(l<=r) { mid=l+r>>1; if(p2[v[c][mid]]<x) r=mid-1; else ans=v[c][mid],l=mid+1; } return ans; } int main() { n=read();T=n*4+1; for(register int i=1;i<=n;i++) t[i]=read(),p[i]=read(); for(register int i=1;i<=n;i++) { t2[i]=read();p2[i]=read(); v[t2[i]].push_back(i); } for(register int i=1;i<=n;i++) ins(S,i,1,0),ins(i+3*n,T,1,0); for(register int i=1;i<=n;i++) { int x=get(p[i]),y=get2(p[i],t[i]); ins(i,x+n,1,1);if(y!=-1)ins(i,y+2*n,1,0); if(i<n) ins(i+n+1,i+n,INF,0); ins(i+n,i+3*n,1,0);ins(i+2*n,i+3*n,1,0); } for(register int i=1;i<=n;i++) for(register int j=1;j<v[i].size();j++) ins(v[i][j]+2*n,v[i][j-1]+2*n,INF,0); while(modlabel()) do memset(mark,0,sizeof(bool)*(T+1)); while(dfs(S,INF)); printf("%d ",ans); return 0; }
贪心
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #define INF 200000000 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,ans,Last[400005]; vector<int> v[200005]; struct Node{int l,r,x,val;}T[1600005]; struct P{int kind,t,x,last; bool operator <(const P&y)const{return x==y.x?kind>y.kind:x<y.x;} }p[400005]; void pushdown(int x) { int ad=T[x].val,l=x<<1,r=x<<1|1; T[x].val=0; T[l].val+=ad;T[r].val+=ad; T[l].x+=ad;T[r].x+=ad; } void build(int x,int l,int r) { if((T[x].l=l)==(T[x].r=r)){ T[x].x=INF;return;} int mid=l+r>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); T[x].x=min(T[x<<1].x,T[x<<1|1].x); } void renew(int x,int l,int r,int ad) { if(T[x].l==l&&T[x].r==r){T[x].x+=ad;T[x].val+=ad;return;} if(T[x].val) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) renew(x<<1,l,r,ad); else if(l>mid) renew(x<<1|1,l,r,ad); else renew(x<<1,l,mid,ad),renew(x<<1|1,mid+1,r,ad); T[x].x=min(T[x<<1].x,T[x<<1|1].x); } bool check(int from) { renew(1,from+1,n,-1); if(T[1].x>=0) return true; renew(1,from+1,n,1); return false; } void change(int x,int k,int ad) { if(T[x].l==T[x].r){T[x].x=ad;return;} if(T[x].val) pushdown(x); int mid=T[x].l+T[x].r>>1; change(x<<1|(k>mid),k,ad); T[x].x=min(T[x<<1].x,T[x<<1|1].x); } int main() { ans=n=read(); for(int i=1;i<=n;i++) p[i].t=read(),p[i].x=read(),p[i].kind=1; for(int i=1;i<=n;i++) p[i+n].t=read(),p[i+n].x=read(); for(int i=n,j=n;i;--i) { while(j>1&&p[j+n].x<p[i].x) --j; p[i].last=n-j; } sort(p+1,p+n*2+1); build(1,1,n); for(int i=1,j=1;i<=n<<1;j+=(p[i++].kind)^1) if(p[i].kind) v[p[i].t].push_back(i); else { if(v[p[i].t].size()) { int u=v[p[i].t][v[p[i].t].size()-1]; if(p[u].last==n||check(p[u].last)) { v[p[i].t].pop_back();--ans; } else change(1,j,i-2*j); } else change(1,j,i-2*j); } printf("%d ",ans); return 0; }