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
大后排跪