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