这场cf时间特别好，周六下午，于是就打了打（谁叫我永远1800上不去div1）
比以前div2的题目更均衡了，没有太简单和太难的...好像B题难度高了很多，然后卡了很多人。
然后我最后做了四题，E题感觉不会太难就是切不下来，还好前面几题A的快居然混了个RANK6，然后＋204，终于上到紫名了......
－－－－－－－－－我是分割线君
A.Snacktower
有一个1到n的全排列，按顺序每一秒会到达一个数，你要把它们从n到1叠起来，如果能叠，你就马上叠。
比如n＝3到达顺序312 ，那么你第一秒就叠3，第三秒叠21。
没什么好说的，直接模拟。n<=10^5
看到题目直接就写了个堆，根本没必要，好傻。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} priority_queue<int> q;
int n,nown; void check()
{
while(!q.empty()&&q.top()==nown)
{
printf("%d ",q.top());
q.pop();nown--;
}
} int main()
{
n=read();nown=n;
for(int i=;i<=n;i++)
{
int x=read();
if(x==nown)
printf("%d ",x),nown--;
else
q.push(x);
check();
printf("\n");
}
return ;
}
B.The Queue
有一个只从ts开到tt的地方，很多人来，每个人要呆t分钟做事情。一个人来的时候如果有人在做事情，他就排队。你是一个谦让的人，会让同时到的人排前面或者先做事情，问你从什么时候来等候时间最小。
这道题卡了很多人.....
很显然，直接枚举在那一个人的前一秒来，或者所有人之后来就可以了。
对于开门之前的时候，设你在第i个人之前1s到，等候时间为(i-1)*t+(ts-你到的时间)；
对于开门之后的时候，维护队伍，以及从什么时候开始排队，设有tot个人排队，开始排队的时间为begin，等候时间为t*tot+begin-s[i]
这样就没了，考的就是细节。
还好写一次就过了，这题拉了挺多分......
复杂度On
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} ll s[];
int n;
ll tf,tt,t;
ll beg,tot;
ll ans=200000000000000LL,times=; int main()
{
tf=read();tt=read();t=read();n=(int)read();tt-=t;
for(int i=;i<=n;i++) s[i]=read();
int i=;
s[]=-;
for(;s[i]<tf&&i<=n;i++)
{
if(s[i]==s[i-]) continue;
if(ans>tf-(s[i]-)+t*(i-))
{
ans=tf-(s[i]-)+t*(i-);times=s[i]-;
}
}
beg=tf;tot=i-;
for(;i<=n&&s[i]<=tt;i++)
{
if(s[i]!=s[i-])
{
if(beg+tot*t<=s[i]-)
{
printf("%I64d\n",s[i]-);
return ;
}
else
{
if(beg+tot*t-(s[i]-)<ans)
{
ans=beg+tot*t-(s[i]-);
times=s[i]-;
}
}
}
if(beg+tot*t<=s[i])
{
beg=s[i];tot=;
}
else
tot++;
}
if(beg+tot*t<=tt)
{
printf("%I64d\n",beg+tot*t);
}
else
printf("%I64d\n",times);
return ;
}
C.Garland
有一棵给定根的树，有点权，要求剪掉两条边使得三个联通块权值和相等。n<=1000000
很水的题目，直接dfs，用S[i]表示点i和它的子树的权值和，能分就分了。
最后判断一下即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,rt,cnt=;
struct edge{
int to,next;
}e[];
int head[];
int tot=,has=;
int s[]; int ans1=-,ans2=-; inline void ins(int f,int t)
{
e[++cnt].next=head[f];
head[f]=cnt;
e[cnt].to=t;
} inline void insw(int f,int t){ins(f,t);ins(t,f);} void findans(int x)
{
if(has>) return;
else has++;
if(ans1==-) ans1=x;
else if(ans2==-) ans2=x;
} void dfs(int x,int fa)
{
for(int i=head[x];i>;i=e[i].next)
{
int v=e[i].to;
if(v!=fa)
{
dfs(v,x);
if(s[v]==tot) findans(v);
else s[x]+=s[v];
}
}
} int main()
{
n=read();
for(int i=;i<=n;i++)
{
int u=read();s[i]=read();
if(u==) rt=i;
else insw(i,u);
tot+=s[i];
}
if(tot%!=) return *puts("-1");
else tot/=;
dfs(rt,);
if(has>=)
printf("%d %d\n",ans1,ans2);
else puts("-1");
return ;
}
D.Cartons of milk
冰箱有n瓶牛奶，商店有m瓶牛奶。
每瓶牛奶一个保质期Ai，然后必须在保质期前喝完它，每天只能喝k瓶牛奶。求最多可以从商店买几瓶。n,m<=10^6,Ai<=10^7
Ai范围很小，从后往前，让每一瓶牛奶尽可能晚喝掉，看看能否喝完冰箱里的。
如果能喝完，就把商店的牛奶排序一下，从后往前对每一个还能喝的天，都尽可能的买，即可。复杂度(mlogm+Ai)
应该有更简单的做法，我这个做法是现场想的，能做就直接做了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,m,maxn,k;
int f[];
struct gg{
int num,x;
}s[];
int ans[];
int sum=; bool cmp(gg x,gg y)
{
return x.x<y.x;
} int main()
{
n=read();m=read();k=read();
for(int i=;i<=n;i++)
{
int x=read();++f[x];
maxn=max(maxn,x);
}
for(int i=;i<=m;i++)
{
s[i].x=read();s[i].num=i;
}
sort(s+,s+m+,cmp);
for(int i=maxn;i;i--)
{
if(f[i]>k)
{
f[i-]+=f[i]-k;f[i]=;
}
else
f[i]=k-f[i];
}
if(f[]>k) return *puts("-1");
else f[]=k-f[];
int j=m;
for(int i=maxn+;i<=;i++) f[i]=k;
for(int i=;i>=;--i)
{
while(j>=&&s[j].x>=i&&f[i]--)
{
ans[++sum]=s[j].num;j--;
}
}
printf("%d\n",sum);
for(;sum;--sum)printf("%d ",ans[sum]);
return ;
}
E. Change-Free
一个人无限的纸币（100快）和有限的硬币（1块），他要在n天内每天买不同价格的产品Si，每天服务员都有一个不满意因数Wi,每次交易服务员会有一个不满意度
为Wi*(找回的纸币的数量＋找回的硬币的数量)。求一个付钱方案让总不满意度最小。n<=100000
很显然每天要考虑怎么付钱的部分只有 Si％100，并且要不然就全部硬币付，要不然就一张纸币甩出来。
其实这道题真的不难，但我就是没发现一个性质，就是每一天付硬币和不付硬币，硬币的差值是100......
知道了这个就很简单了。
我们从第一天到最后一天，每天都先购买它，然后把不购买会产生的不满意度存到堆里面。
如果发现钱不够了，就去堆里找一个最小值，并且在那一天用纸币付钱，换取100个硬币。最后输出就行了。复杂度nlogn
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,m;
int s[];
bool flag[];
int w[];
ll ans=; struct node{
ll f,num;
friend bool operator < (node x,node y)
{
return x.f>y.f;
}
}newx;
priority_queue<node> q; int main()
{
n=read();m=read();
for(int i=;i<=n;i++)
s[i]=read();
for(int i=;i<=n;i++) w[i]=read();
for(int i=;i<=n;i++)
{
if(s[i]%==) continue;
m-=s[i]%;
ll x=(ll)(-(s[i]%))*w[i];
q.push((node){x,i});
while(m<)
{
newx=q.top();q.pop();
flag[newx.num]=;
m+=;
ans+=newx.f;
}
}
printf("%I64d\n",ans);
for(int i=;i<=n;i++)
{
if(s[i]%==) printf("%d 0\n",s[i]/);
else if(flag[i]) printf("%d 0\n",s[i]/+);
else printf("%d %d\n",s[i]/,s[i]%);
}
return ;
}
最后附上成绩图。