CF练习记
水了几场CF，由于自己傻逼还是个紫名狗
Codeforces Round #313 (Div. 2)
听几位主力爷说今天22:00有CF，我说我英语水平差，没有CF号，而且太晚了不想去，被几位主力爷训斥了一通。
但没想到第一次打CF竟然拿了全场RANK2，而且要不是HACK晚了就RANK1了。。先是在胡主力的帮助下弄了个CF号，报了div2，然后被黄主力弄进了一个CF交流群
然后听说div2有四道傻逼题，于是比赛前就先准备好板子，想马上交
但是几位主力爷早就征战div1了，蒟蒻只好一个人打div2了，比赛前来了一只酱油，感觉英语翻译有保障了
先看T1，一开始因为语言障碍没看懂，酱油翻译出来后马上秒了，但是第一发由于语言选错CE了，第二发A了
然后T2还是自己看懂了，不过一开始并没有想到什么好办法
然后T3群里已经给了中文解释，于是就弄出个乘对角和高度加两边的面积求法，第一遍WA了，因为把两边面积算成相等的了，改一下就A了。
看完T3又去看T4，然后觉得样例很奇怪，这两个串怎么会相等呢。。于是回去搞T2
想了想可以先把一个放在角上，枚举四个方向判断一下就可以了，因为代码能力捉急，写了将近20分钟。。
这时T4也已经被酱油翻译好了，然后想了想分治应该没问题，就把T4秒了
然后T5从群里找来翻译，发现好难啊，想了好久觉得没啥办法，去看了看所谓的原题，原来想抄，但发现好像也不太一样。于是先去HACK T1，找到了一个SB，结果自己更SB，HACK错了。回来又去原题那里看了看，发现可以枚举所有不能走的格子和两个端点做n^2DP，DP的值为所有路径-所有以前不能走的点的DP值*从该点走到所求点的方案数，于是拉了个卢卡斯模板，第一发卢卡斯预处理阶乘少打了1个0WA了，第二发就A了。
然后只有10多分钟了，又看了看那个SB的T1程序，造了个大数据，想应该能叉掉，但谁知ai不能重复，于是换了个ai不重复的数据，但那个人已经被别人叉掉了QAQ
然后看了看排名，大概是RANK4。。。要是叉掉那个人应该是RANK3
最后测完后变成了RANK2。。
#define N 222222
#include<cstdio>
#include<algorithm>
int n,i,a[N];
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
std::sort(a+1,a+n+1);
if(a[1]!=1)puts("1");else puts("-1");
}
#include<cstdio>
int n,i,x1,y1,x2,y2,x3,y3,now,nx,ny;
bool ok(int x1,int y1,int x2,int y2){
if(x1>y1)swap(x1,y1);if(x2>y2)swap(x2,y2);
if(x1>=x2&&y1>=y2)return 1;return 0;
}
int main(){
scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
if(x1>y1)swap(x1,y1);if(x2>y2)swap(x2,y2);if(x3>y3)swap(x3,y3);
if(x2>x1||y2>y1||x3>x1||y3>y1)return puts("NO"),0;
nx=x1-x2;ny=y1-y2;
if(ok(nx,y1,x3,y3)||ok(x1,ny,x3,y3))return puts("YES"),0;
nx=x1-y2;ny=y1-x2;
if(ny>=0)if(ok(nx,y1,x3,y3)||ok(x1,ny,x3,y3))return puts("YES"),0;
puts("NO");
}
#include<cstdio>
int n,i,a,b,c,d,e,f,s;
int main(){
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
s=(a+d)*(b+c)+b*c+e*f;
printf("%d",s);
}
#include<cstdio>
#include<cstring>
#define N 222222
int n,i;char s1[N],s2[N];
bool find(int l1,int r1,int l2,int r2){
bool ff=1;
for(int i=l1;i<=r1;i++)if(s1[i]!=s2[i+l2-l1]){ff=0;break;}
if(ff)return 1;
int len=r1-l1+1;
if(len%2==0){
int m1=(l1+r1)>>1,m2=(l2+r2)>>1;
if(find(l1,m1,l2,m2)&&find(m1+1,r1,m2+1,r2))return 1;
if(find(l1,m1,m2+1,r2)&&find(m1+1,r1,l2,m2))return 1;
}
return 0;
}
int main(){
scanf("%s%s",s1+1,s2+1);n=strlen(s1+1);
if(find(1,n,1,n))puts("YES");else puts("NO");
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2222
#define p 1000000007
using namespace std;
long long n,m,k,i,j,dp[N],fac[10000000];
struct EG{long long x,y;}eg[N];
bool cmp(EG a,EG b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
long long pow(long long a,long long b){
long long tmp=a%p,ans=1;
for(;b;b>>=1){
if(b&1)ans=ans*tmp%p;
tmp=tmp*tmp%p;
}
return ans;
}
long long C(long long n,long long m){
if(m>n)return 0;
return fac[n]*pow(fac[m]*fac[n-m],p-2)%p;
}
long long lucas(long long n,long long m){
if(!m)return 1;
else return(C(n%p,m%p)*lucas(n/p,m/p))%p;
}
long long path(long long i,long long j){
long long x1=eg[i].x,y1=eg[i].y;
long long x2=eg[j].x,y2=eg[j].y;
if(x2<x1||y2<y1)return 0;
long long y=y2-y1,x=x2-x1;
return lucas(x+y,x);
}
int main(){
fac[0]=1;for(i=1;i<=10000000;i++)fac[i]=fac[i-1]*i%p;
scanf("%I64d%I64d%I64d",&n,&m,&k);
for(i=1;i<=k;i++)scanf("%I64d%I64d",&eg[i].x,&eg[i].y);
k++;eg[k].x=1;eg[k].y=1;k++;eg[k].x=n;eg[k].y=m;
sort(eg+1,eg+k+1,cmp);
for(i=2;i<=k;i++){
dp[i]=path(1,i);
for(j=1;j<i;j++)
dp[i]=(dp[i]-(dp[j]*path(j,i))%p+p)%p;
}
printf("%I64d",dp[k]);
}
可以看到Div2的题难度还是极低的，两道题不到10行，出在小学生市赛还算简单题；两道20行，可以当普及组第一题第二题；一道40行，如果不像我这么逗用卢卡斯的话也是联赛难度。。
Codeforces Round #328 (Div. 2)
成就：FST div2的A题
A 作为div2 A实在太难了
B 比A不知道简单到哪里去了
C HACK好题
D 原题？原题！
E 卡精度，谁敢做？
Codeforces Round #337 (Div. 2)
还好只是随便水水。。ORZ毛主力，随便开个小号直接摞DE都把我摞翻了
A 作为A题还是很难哒
B 作为B题还是很难哒，找到最小值然后再单调扫一遍
C 分治构造即可
D 超裸线段树
E 傻逼了。。大概就是统计一下反顺序的然后线段树维护一下就好了
Educational Codeforces Round 6
傻逼模板题？不写辣来口胡~
A 傻逼
B 打表
C map直接上
D 大力讨论，对于换两组的情况，每一组内自交，排序后再单调扫一遍，时间复杂度O(n^2lgn)
E 线段树大力维护
F 莫队+字典树统计
Codeforces Round #340 (Div. 2)
时间不错，浪一发
A ...
B 傻逼写了DP
C 普及组原题
D 大力分类讨论，注意T字型
E 前缀和后莫队模板题
Educational Codeforces Round 7
k次方求前缀和。。好神啊
A 暴力
B 模拟
C 每个数找到右边第一个不同于它的数，O(1)回答
D 构造出来方案使得代价为0，方法是分成两半做
E 贪心，对每一颗子树找出所有的叶子节点，按照深度排序，然后先走深度大的即可
F 这东西3年前杜教在WC上讲过，然而根本看不懂。。于是拉了个模板，似乎不是很长。。
#include<bits/stdc++.h>
typedef long long LL;using namespace std;
const int M=1e9+7,N=1e6+10;LL res[N],pw[N],cc[N];int n,k,i;
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;}
int main(){
scanf("%d%d",&n,&k);
for(pw[0]=1,i=1;i<N;i++)pw[i]=pw[i-1]*i%M;
for(i=1;i<k+5;i++)res[i]=(res[i-1]+pow(i,k,M))%M;
if(n<=k+4)return printf("%I64d",res[n]),0;
for(i=1;i<k+5;i++){
cc[i]=pow(pw[i-1]*pw[k+4-i],M-2,M)*res[i]%M;
if((k+4-i)&1)cc[i]=(M-cc[i])%M;
}
LL an=0,p=1;
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;
printf("%I64d",an);
}
Damascus Collegiate Programming Contest
一场傻逼的普及组十合一，3☆的GYM原来这么**
A 傻逼状压DP
B 傻逼暴力
C 傻逼贪心
D 二分判断
E 直接上字典树
F 暴力找出所有字符串然后排序
G C(n+m,n)
H 扩欧判断边界情况
I 傻逼最短路
J 对一半字符暴力，剩下的因为回文一样填上去
8VC VENTURE CUP 2016 - ELIMINATION ROUND
寒假最后一场CF，全部是傻逼一眼题，由于手速慢而且FST还是没有上黄QAQ
开场自信开B，看不太懂，坑了快一分钟决定搞A，4分钟A了
然后继续B，觉得来个暴力就好了，赶紧写了一发，10分钟A
然后看C，觉得直接二分判就好了，16分钟A
然后看D，一开始觉得好难，好像要FFT？然后发现只要把差弄出来暴力卷积就可以了，28分钟A
然后看E，觉得可以枚举中位数然后二分搞啊，就写了发，还加了分类讨论，爆了两发OJ，然后发现前缀和算成排序前的了，改了就过了
然后看F，好难啊。。想了半个多小时，没有任何思路
于是去叉C，叉了几个人。。然后发现F题目读错了，把题目意思读懂后想了会，觉得可以DP搞
然后写了发，但是过不了样例，就推了好几遍方程，总算在快比完的时候推对了，压线交了一发
最后E题FST了。。二分应该是有点问题的，脑子简直进水了，为什么二分的东西和最优答案不符却不写个三分呢。。
然后就排到了一百开外滚粗了。。没有三场黄，以后更没有机会了
第二天看了下G题，不是傻逼题么。。直接线段树上摞就可以了。。早知道比赛的时候鏼G了，没准都RK10。。
解题报告在下面
A 暴力n^3判断即可
int T,n,m,x,y,i,j,k,ans,tot,a[N];char s[N];
int main(){
scanf("%d",&n);scanf("%s",s+1);
fr(i,n)for(j=i;j<=n;j++){
x=0;y=0;
for(k=i;k<=j;k++){
if(s[k]=='U')x++;
if(s[k]=='D')x--;
if(s[k]=='L')y--;
if(s[k]=='R')y++;
}
if(!x&&!y)ans++;
}
pi(ans);
}
B dp[i][j][k]表示i个B，j个G,k个R是否能到达，最后判断dp[1][0][0],dp[0][1][0]和dp[0][0][1]的值即可，时间复杂度O(n^3)
int T,n,m,x,y,i,j,tot,A,B,C,xa,xb,xc,a[N];bool v[222][222][222];char s[222];
void find(int A,int B,int C){
if(v[A][B][C])return;
v[A][B][C]=1;
if(A+B+C==1){
xa|=A;
xb|=B;
xc|=C;
return;
}
if(A&&B)find(A-1,B-1,C+1);
if(A&&C)find(A-1,B+1,C-1);
if(B&&C)find(A+1,B-1,C-1);
if(A>1)find(A-1,B,C);
if(B>1)find(A,B-1,C);
if(C>1)find(A,B,C-1);
}
int main(){
scanf("%d",&n);scanf("%s",s+1);
fr(i,n)if(s[i]=='R')A++;else if(s[i]=='B')B++;else C++;
printf("%d %d %d\n",A,B,C);
find(A,B,C);
if(xb)putchar('B');
if(xc)putchar('G');
if(xa)putchar('R');
}
C 二分答案，判断可行性就可以了，时间复杂度O(lg(n+m))
int T,n,m,x,y,o,w,u,A,B,l,r,mid,ans,i,j,tot,a[N];
bool ok(int x){
o=x/6;
w=o*2+((x%6)/2);
u=o+((x%6)/3);
A=n-w;B=m-u;
if(A<0)A=0;
if(B<0)B=0;
return A+B<=o;
}
int main(){
scanf("%d%d",&n,&m);
l=0;r=1e8;
ok(9);
for(;l<=r;)if(ok(mid=l+r>>1))r=mid-1,ans=mid;else l=mid+1;
pi(ans);
}
D 先算出每个差值赢的概率，然后做一遍卷积，再扫一遍就得到答案了，时间复杂度O(n^2)
int T,n,m,x,y,i,j,tot,a[N];double f[N],h[N],g[N],A,o;
int main(){
scanf("%d",&n);m=n*(n-1)/2;
fr(i,n)scanf("%d",&a[i]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i]>a[j])f[a[i]-a[j]]+=(double)1.0/m;else g[a[j]-a[i]]+=(double)1.0/m;
for(i=1;i<=5000;i++)
for(j=1;j<=5000;j++)
h[i+j]+=f[i]*f[j];
for(i=1;i<=5000;i++){
o=0;
for(j=1;j<i;j++)o+=h[j];
A+=o*g[i];
}
printf("%.10lf",A);
}
E 排序后枚举中位数，最优的答案一定是中位数前面取一段，然后右端点前再取一段，这个值先增后减，可以用三分法判断出来，时间复杂度O(nlgn)
int T,n,m,x,y,i,j,tot,ul,ur,wl,wr,l,r,mid,ans,a[N];LL s[N];double A=-1e18,B,C;
double G(int i,int j){return (double)(s[i]-s[i-j-1]+s[n]-s[n-j])/(2*j+1)-a[i];
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(i=1;i<=n;i++){
l=0;r=min(i-1,n-i);ans=0;
for(;l<r;){
mid=(l+r+1)>>1;
B=G(i,mid);C=G(i,mid-1);
if(B>C)l=mid;else r=mid-1;
//if(a[i]-a[i-mid]<=a[n-mid+1]-a[i]||!mid)ans=mid,l=mid+1;else r=mid-1;
}
B=G(i,l);
if(B>A)A=B,ul=i,ur=l;
//if(((double)(s[n]-s[n-ans]+s[i]-s[i-ans-1])/(ans*2+1)-a[i])>A)A=((double)(s[n]-s[n-ans]+s[i]-s[i-ans-1])/(ans*2+1)-a[i]),ul=i,ur=ans;
}
printf("%d\n",ur*2+1);
for(i=ul-ur;i<=ul;i++)printf("%d ",a[i]);
for(i=n-ur+1;i<=n;i++)printf("%d ",a[i]);
}
F 用f[i][j][k]表示取到第i个，有j组还正在组队，付出的代价是k，那么把a[i]排序后
f[i][j][k]-->f[i+1][j+1][k+(a[i+1]-a[i])*j]（一个人新建组）
f[i][j][k]*j-->f[i+1][j-1][k+(a[i+1]-a[i])*j]（一个人作为一个组的末尾）
f[i][j][k]*(j+1)-->f[i+1][j][k+(a[i+1]-a[i])*j]（一个人加到一个组中，注意可以自交）
时间复杂度O(n^2k)，加滚动数组就A了
int T,n,m,x,y,i,j,k,K,tot,a[N];LL f[202][1005],g[202][1005],ans;
LL up(LL &x,LL y){x=(x+y)%M;}
int main(){
scanf("%d%d",&n,&K);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
f[0][0]=1;
for(i=0;i<n;i++){
for(j=0;j<=n;j++)for(k=0;k<=K;k++)g[j][k]=f[j][k],f[j][k]=0;
for(j=0;j<=i;j++)
for(k=0;k<=K;k++){
if(k+(a[i+1]-a[i])*j<=K)up(f[j+1][k+(a[i+1]-a[i])*j],g[j][k]);
if((a[i+1]-a[i])*j+k<=K)up(f[j-1][k+(a[i+1]-a[i])*j],g[j][k]*j),up(f[j][k+(a[i+1]-a[i])*j],g[j][k]*(j+1));
}
}
for(k=0;k<=K;k++)ans=(ans+f[0][k])%M;
printf("%I64d",ans);
}
G 由于一种奖买得越多增加得会越少，于是可以考虑用数据结构维护，不妨使用线段树
先轻松维护出一开始的答案，对于修改操作，先把答案更新
然后算一算加一个的最大值和减一个的最小值，如果前者更大，那么就继续更新答案
时间复杂度O(nlgn)
#include<bits/stdc++.h>
#define N 200200
#define eps 1e-15
using namespace std;
int n,A,m,i,x,y,mid,a[N],mi[N<<2],mv[N<<2],v[N],p[N];double sum,f[N],g[N];
void G(int i){
f[i]=a[i]>=p[i]?0:(double)(v[i]*(a[i]+1))/(p[i]+a[i]+1)-(double)(v[i]*a[i])/(p[i]+a[i]);
if(a[i])g[i]=a[i]>p[i]?0:(double)(v[i]*a[i])/(p[i]+a[i])-(double)(v[i]*(a[i]-1))/(p[i]+a[i]-1);else g[i]=1e18;
}
void ps(int k){
mv[k]=(f[mv[k<<1]]>f[mv[k<<1|1]])?mv[k<<1]:mv[k<<1|1];
mi[k]=(g[mi[k<<1]]<g[mi[k<<1|1]])?mi[k<<1]:mi[k<<1|1];
}
void bt(int k,int l,int r){
if(l==r){mv[k]=mi[k]=l;return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
ps(k);
}
void ex(int k,int l,int r,int x){
if(l==r)return;int mid=l+r>>1;
if(x<=mid)ex(k<<1,l,mid,x);else ex(k<<1|1,mid+1,r,x);
ps(k);
}
int main(){
for(scanf("%d%d%d",&n,&A,&m),i=1;i<=n;i++)scanf("%d",&v[i]);
for(i=1;i<=n;i++)scanf("%d",&p[i]),G(i);
for(bt(1,1,n),i=1;i<=A;i++)x=mv[1],sum+=f[x],a[x]++,G(x),ex(1,1,n,x);
for(;m--;){
scanf("%d%d",&x,&y);
if(a[y])sum-=(double)v[y]*min((double)a[y]/(p[y]+a[y]),0.5);
if(x==1)p[y]++;else p[y]--;G(y);
if(a[y])sum+=(double)v[y]*min((double)a[y]/(p[y]+a[y]),0.5);
for(ex(1,1,n,y);1;){
x=mv[1];y=mi[1];
if(f[x]-g[y]>0){
sum+=f[x]-g[y];
a[x]++;G(x);a[y]--;G(y);
ex(1,1,n,x);ex(1,1,n,y);
}else break;
}
printf("%.10lf\n",sum);
}
}
感觉CF就是手速大战啊。。3道普及3道提高1道弱省省选，都没啥难度，手速还是不够QAQ
8VC Venture Cup 2016 - Final Round
为了抢衣服垫了发底，竟然还是涨RATING了。。
开场看A好难啊，B好长啊，就去看C了。。
感觉好水啊，似乎单调队列随便搞搞就好了，然后就发现过不了样例。。
搞了快30分钟啥也没搞出来。。好好想了想判断哪里买，50多分钟才过。。。
发现已经被碾飞了。。然后把A乱搞摞掉了，不知道对不对
然后发现B很SB，两个BIT就好了，就写了发，然后由于题意爆了3发。。
然后搞D，二分后就可以大力树DP了，可开始写的时候只有20min了。。没写出来
然后就垫底了。。红名爷都太强了，把我碾飞了。。
A 按位判就可以了，如果异或在该位为1那么有两种选择，但是它们的和-xor/2在该为不能为1
B 两个BIT，一个算前面的，一个算后面的就好了
C 单调队列，扫出每个点由哪个加油站控制就好了
D 二分后树DP，记录f表示子树答案，g表示子树最大，g2表示子树次大，up表示向上的答案，然后大力维护就可以了。不是很好写，注意分情况
#include<bits/stdc++.h>
#define N 400400
using namespace std;bool ff;
int n,k,i,x,y,l,r,mid,ans,tot,fir[N],ne[N],la[N],g[N],zs[N],g2[N],f[N],sum[N],up[N],a[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int w){
if(a[x]>=w)zs[x]=0;else zs[x]=1;g[x]=0;g2[x]=0;f[x]=0;
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa){
y=la[i];dfs(y,x,w);
if(!zs[y])f[x]+=f[y];else if(f[y]>g[x])g2[x]=g[x],g[x]=f[y];else if(f[y]>g2[x])g2[x]=f[y];
zs[x]+=zs[y];
}
sum[x]=f[x];if(a[x]<w)f[x]=0;else f[x]+=1+g[x];
}
void dfs2(int x,int fa,int w){
int v=0,mx=0,i,y;
if(a[x]>=w){
if(zs[1]-zs[x]==0)v+=up[x];else mx=max(mx,up[x]);
for(i=fir[x];i;i=ne[i])if(la[i]!=fa)if(zs[y=la[i]]==0)v+=f[y];else mx=max(mx,f[y]);
v+=mx+1;if(v>=k){ff=1;return;}
}
for(i=fir[x];i;i=ne[i])if(la[i]!=fa){
y=la[i];
if(a[x]<w)up[y]=0;else{
v=sum[x];mx=0;
if(zs[y]==0)v-=f[y];else if(g[x]==f[y])mx=max(mx,g2[x]);else mx=max(mx,g[x]);
if(zs[1]-zs[x]==0)v+=up[x];else mx=max(mx,up[x]);
up[y]=v+mx+1;
}
dfs2(y,x,w);
}
}
bool ok(int x){dfs(1,0,x);ff=0;dfs2(1,0,x);return ff;}
int main(){
for(scanf("%d%d",&n,&k),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(l=1,r=1000000;l<=r;)if(ok(mid=l+r>>1))l=(ans=mid)+1;else r=mid-1;
printf("%d",ans);
}
IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)
爆OJ+卡题+FST，滚大粗跌绿了。。
开场看A，好傻逼啊。写了发竟然WA了。。曰狗调不出来，先去看B了
B好神啊，感觉要写个大搜索啊，就开始写，发现还要去重啊，这TM也太难了吧。。
写了快20min过不了样例。发现题目看错了，原来是删除啊，而且ai还不同，那不是直接删就好了吗。。
写了发又WA了。。心情非常糟糕，看了5分钟发现一个小地方写错了。。然后把A改成n^3暴力就过了。。原来会有相同的啊
然后看C，这TM也太神了吧。。写了20min没过样例，弃疗去看D。
这不是傻逼题么。。赶紧写了发二分+网络流，爆了1发过了。。
然后继续C，觉得可以大力分类讨论啊，于是分了6种情况讨论，爆了2发卡时过了。
最后D就FST了。。这精度太TM难弄了。。以后二分还是不判精直接摞60次好了。。
一场跌绿，再这么玩就跌灰咯。。
2016年2月15日 17:48
小伙子我看好你
2016年2月15日 20:53
后排跪
2016年2月18日 20:31
大后排跪