由Codeforces #268的惨跪引发的感想
Codeforces 练习计划 #1

[坑] Codeforces Div.2 刷场计划

RXDoi posted @ 2014年10月05日 20:29 in Codeforces , 186 阅读

鉴于人太弱,零零散散地做题我总会自动跳过比较难的题,加上看着CF上一个个蓝框很不爽,综合Div.1刷不动等原因,本紫名狗决定刷一发Div.2。

进度:4/10

[10.4][10.7][10.14][10.18]

  +1    +1    +1    +1


Codeforces Round #137 (Div. 2)

[A] 可以发现如果有终止,肯定是在2*n次以内就终止了。所以把序列模拟n次,然后判断是否终止。如果已经终止再去往前找最早的时间。

[B] 这题PJ的时候做过了。我们只要维护H[i],表示第i行的数现在被换到了第H[i]行,列同理。交换的时候只交换这个数就行了。

[C] 坑题。

[D] 名次的最小值肯定是1。最大值的话,我们就要组合一下两个数组,使得和>=x的尽量多。那么分别排序然后两个指针扫一遍即可。

[E] 我的第一道矩阵乘法题。设 \(f[i][j]\)表示前i个填完,最后一个是j。那么显然 \(f[i][j]=\sum{f[i-1][k]*can[k][j]}\)。可以发现这成了矩阵乘法的形式。那么我们用一个行向量来表示\(f[i]\)的值,矩阵乘法即可。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int Maxn=(1e5+19)*24,PP=1e7+19;
int cntA[PP],cntB[PP],p[PP],A[Maxn],B[Maxn];
int n,m,x,ca,cb,cca,ccb;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=2;i<=1e7;i++)
		if (!p[i])
			for (int j=i+i;j<=1e7;j+=i) p[j]=1;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&x);A[i]=x;
		for (int j=2;j<=sqrt(x)&&p[x];j++) while (x%j==0) cntA[j]++,x/=j;
		if (x!=1) cntA[x]++;
	}	
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&x);B[i]=x;
		for (int j=2;j<=sqrt(x)&&p[x];j++) while (x%j==0) cntB[j]++,x/=j;
		if (x!=1) cntB[x]++;
	}
	for (int i=1;i<=PP;i++)
	{
		int x=min(cntA[i],cntB[i]);
		cntA[i]-=x;cntB[i]-=x;
	}
	printf("%d %d\n",n,m);
	for (int i=1;i<=n;i++)
	{
		int x=A[i],t=1;
		for (int j=2;j<=sqrt(x)&&p[x];j++) while (x%j==0) {x/=j;if (cntA[j]) cntA[j]--,t*=j;}
		if (cntA[x]) cntA[x]--,t*=x;
		printf("%d ",t);
	}
	puts("");
	for (int i=1;i<=m;i++)
	{
		int x=B[i],t=1;
		for (int j=2;j<=sqrt(x)&&p[x];j++) while (x%j==0) {x/=j;if (cntB[j]) cntB[j]--,t*=j;}
		if (cntB[x]) cntB[x]--,t*=x;
		printf("%d ",t);
	}
	puts("");
}
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

const int Maxn=1e5+19;
int A[Maxn],B[Maxn];
int n,x,a,t=1;

int main()
{
	scanf("%d%d",&n,&x);
	for (int i=1;i<=n;i++) scanf("%d",&A[i]);
	for (int i=1;i<=n;i++) scanf("%d",&B[i]);
	sort(A+1,A+n+1);
	sort(B+1,B+n+1,greater<int>());
	for (int i=1;i<=n;i++)
		if (A[i]+B[t]>=x) t++;
	printf("1 %d\n",t-1);
}
#include<cstdio>
#include<cstring>
using namespace std;

const int Maxn=52+19,Mod=1e9+7;
typedef long long LL;
struct Matrix
{
	LL n,m;
	LL s[Maxn][Maxn];	
	Matrix() {n=m=0;memset(s,0,sizeof(s));}
} can,F;
LL n,m,k,Ans;
char s[10];

Matrix operator * (Matrix A,Matrix B)
{
	Matrix C;
	C.n=A.n;C.m=B.m;
	for (int i=1;i<=A.n;i++)
		for (int j=1;j<=B.m;j++)
			for (int k=1;k<=A.m;k++) (C.s[i][j]+=1LL*A.s[i][k]*B.s[k][j]%Mod)%=Mod;
	return C;
}
Matrix Power(Matrix A,LL b)
{
	Matrix Res,tmp=A;
	Res.n=Res.m=m;
	for (int i=1;i<=m;i++) Res.s[i][i]=1;
	while (b)
	{
		if (b&1) Res=Res*tmp;
		tmp=tmp*tmp;
		b>>=1;
	}
	return Res;
}

int main()
{
	scanf("%I64d%I64d%I64d",&n,&m,&k);n--;
	can.n=can.m=m;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=m;j++) can.s[i][j]=1;
	while (k--)
	{
		scanf("%s",s);
		int x=(s[0]>='a'?s[0]-'a'+1:s[0]-'A'+1+26);
		int y=(s[1]>='a'?s[1]-'a'+1:s[1]-'A'+1+26);
		can.s[x][y]=0;
	}
	F.n=1,F.m=m;
	for (int i=1;i<=m;i++) F.s[1][i]=1;
	Matrix tmp=F*Power(can,n);
	for (int i=1;i<=m;i++) (Ans+=tmp.s[1][i])%=Mod;
	printf("%I64d\n",Ans);
}

Codeforces Round #271 (Div. 2)

[C] 暴力枚举每个点的旋转次数,根据三角形搞搞来得出旋转后的点。然后用各种方法判断正方形。需要注意的是虽然点的范围只有绝对值\(1e4\),但是旋转后会达到\(3e4\),\((3e4+3e4)^2=3.4*10^9\),稳稳地爆了int。

[D] 简单递推。维护前缀和。\(f[i]=f[i-1]+f[i-k]\)。分别表示填R,填W。

[E] 类似于NOIp2013TG第5题。用两个BIT分别维护高度\(>=x\),\(<=x\)的\(f[]\)最大值。然后在原数组里二分出\(A[i]\)的排名,以及\(A[i]+d,A[i]-d\)的排名。然后更新BIT即可。注意的是由于要记录方案,BIT返回的值最好是一个pair<int,int>。

[F] 考虑区间最小值。如果它==区间gcd的值,那么显然这个最小值满足条件。否则由于\(gcd(a,b)<=min(a,b)\),区间内一定不可能有任何数满足条件了。那么线段树或者ST表维护区间最小、区间gcd,然后在pair<int,int>里面二分等于这个最小值的数个数即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
struct Point
{
	int x,y;
} A[6],B[6],tmp[6];
int c[6],n;
LL cc[6][6];

inline LL sqr(LL x) {return x*x;}
inline Point turn(Point A,Point B,int c)
{
	int x=A.x-B.x,y=A.y-B.y;
	if (c==0) return A;
	if (c==1) return (Point){B.x-y,B.y+x};
	if (c==2) return (Point){B.x-x,B.y-y};
	if (c==3) return (Point){B.x+y,B.y-x};
}
inline int check()
{
	if (tmp[1].x==tmp[2].x&&tmp[1].y==tmp[2].y) return 0;
	for (int i=1;i<=4;i++)
	{
		for (int j=1;j<=4;j++)
			if (i!=j) cc[i][j]=sqr(tmp[i].x-tmp[j].x)+sqr(tmp[i].y-tmp[j].y);
				else cc[i][j]=0;
		sort(cc[i]+1,cc[i]+5);
		if (cc[i][2]!=cc[i][3]) return 0;
		if (cc[i][4]<=cc[i][2]) return 0;
	}
	if (cc[1][2]!=cc[2][2]||cc[2][2]!=cc[3][2]||cc[3][2]!=cc[4][2]) return 0;
	if (cc[1][4]!=cc[2][4]||cc[2][4]!=cc[3][4]||cc[3][4]!=cc[4][4]) return 0; 
	return 1;
}

int main()
{
	scanf("%d",&n);
	while (n--)
	{
		int Ans=(1<<30)-1;
		for (int i=1;i<=4;i++) scanf("%d%d%d%d",&A[i].x,&A[i].y,&B[i].x,&B[i].y);
		memset(c,0,sizeof(c));
		while (c[0]==0)
		{
			int x=4,num=0;
			for (int i=1;i<=4;i++) tmp[i]=turn(A[i],B[i],c[i]);
			if (check())
			{
				for (int i=1;i<=4;i++) num+=c[i];
				Ans=min(Ans,num);
			}
			while (c[x]==3) x--;
			c[x]++;
			for (int i=x+1;i<=4;i++) c[i]=0;
		}
		printf("%d\n",(Ans==(1<<30)-1)?-1:Ans);
	}
}
#include<cstdio>
#include<algorithm>
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
const int Maxn=1e5+19;
int pre[Maxn],out[Maxn],cnt,n,d;
LL A[Maxn],B[Maxn];
PII F[Maxn],G[Maxn],Ans;

inline void F_Update(int x,PII v) {while (x<=n) F[x]=max(F[x],v),x+=x&-x;}
inline void G_Update(int x,PII v) {while (x<=n) G[x]=max(G[x],v),x+=x&-x;}
inline PII F_Query(int x) 
{
	PII Ans=mp(0,0);while (x) Ans=max(Ans,F[x]),x-=x&-x;return Ans;
}
inline PII G_Query(int x) 
{
	PII Ans=mp(0,0);while (x) Ans=max(Ans,G[x]),x-=x&-x;return Ans;
}

int main()
{
	scanf("%d%d",&n,&d);
	for (int i=1;i<=n;i++) scanf("%I64d",&A[i]),B[i]=A[i];
	sort(B+1,B+n+1);
	Ans=mp(0,0);
	for (int i=1;i<=n;i++)
	{
		int sm=lower_bound(B+1,B+n+1,A[i]-d+1)-B-1;
		int bg=lower_bound(B+1,B+n+1,A[i]+d)-B;
		PII _F=(sm==0?mp(0,0):F_Query(sm));
		PII _G=(bg==n+1?mp(0,0):G_Query(n-bg+1));
		PII tmp;
		if (_F>_G) tmp=_F,pre[i]=_F.second;else tmp=_G,pre[i]=_G.second;
		tmp.first++;tmp.second=i;
		int x=lower_bound(B+1,B+n+1,A[i])-B;
		F_Update(x,tmp);
		G_Update(n-x+1,tmp);
		if (tmp>Ans) Ans=tmp;
	}
	printf("%d\n",Ans.first);
	for (int i=Ans.second;i!=0;i=pre[i]) out[cnt++]=i;
	for (int i=cnt-1;i>=0;i--) printf("%d ",out[i]);puts("");
}
#include<cstdio>
#include<algorithm>
#define mp make_pair
using namespace std;

const int Maxn=1e5+19;
pair<int,int> A[Maxn];
int Min[21][Maxn],Gcd[21][Maxn];
int n,Q,L,R,x;

inline int _min(int a,int b) {return a<b?a:b;}
inline int _gcd(int a,int b) {return !b?a:_gcd(b,a%b);}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&x),Gcd[0][i]=Min[0][i]=x,A[i]=make_pair(x,i);
	sort(A+1,A+n+1);
	for (int i=1;i<=20;i++)
		for (int j=1;j+(1<<i)-1<=n;j++)
		{
			Gcd[i][j]=_gcd(Gcd[i-1][j],Gcd[i-1][j+(1<<i-1)]);
			Min[i][j]=_min(Min[i-1][j],Min[i-1][j+(1<<i-1)]);
		}
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%d%d",&L,&R);
		int k=0;
		for (;1<<(k+1)<=R-L+1;k++);
		int GCD=_gcd(Gcd[k][L],Gcd[k][R-(1<<k)+1]);
		int MIN=_min(Min[k][L],Min[k][R-(1<<k)+1]);
		int cnt=upper_bound(A+1,A+n+1,mp(GCD,R))-lower_bound(A+1,A+n+1,mp(GCD,L));
		printf("%d\n",R-L+1-(GCD==MIN?cnt:0));
	}
}

Codeforces Round #169 (Div. 2)

[A]

[B]

[C]

[D]

[E] 显然给出的那棵树形如一条条链。我们要在这个结构上维护。可以发现,如果这条链上的某个节点要影响到别的链上的结点,肯定是从上往下影响,也就是说,是连续的。第一想法是对于每条链维护一颗BIT,但是如果形成菊花树每次就可能要更新n棵BIT。所以我们在全局开一棵BIT,记录所有链上深度<=x的结点共同增加了多少。然后再对于每条链维护一棵BIT。这个就很容易了。需要注意的是,为了防止TLE,我们必须把所有BIT压缩到一起。这样就需要离散什么的,比较好的方法是记录每条链链首的下标以及每个点的深度。细心点调试即可。

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

const int Maxn=1e5+19;
struct Edge {int y,nxt;} E[Maxn*2];
int n,Q,x,y,v,d,Ecnt,now,type,cnt,Ans1;
int C[Maxn],Cr[Maxn];
int Fir[Maxn],Last[Maxn],D[Maxn],B[Maxn];

inline void Add_r(int x,int v) {while (x<=n) Cr[x]+=v,x+=x&-x;}
inline int Sum_r(int x) {int Ans=0;while (x) Ans+=Cr[x],x-=x&-x;return Ans;}
inline void Add(int x,int v) {while (x<=n) C[x]+=v,x+=x&-x;}
inline int Sum(int x) {int Ans=0;while (x) Ans+=C[x],x-=x&-x;return Ans;}

inline void Link(int x,int y)
{
	E[Ecnt]=(Edge){y,Last[x]};Last[x]=Ecnt++;
	E[Ecnt]=(Edge){x,Last[y]};Last[y]=Ecnt++;
}
inline void DFS(int x,int Fa,int Deep,int Bel)
{
	++now;
	D[x]=Deep;B[x]=Bel;
	for (int i=Last[x];i!=-1;i=E[i].nxt)
		if (E[i].y!=Fa) DFS(E[i].y,x,Deep+1,Bel);
}

int main()
{
	memset(Last,-1,sizeof(Last));
	scanf("%d%d",&n,&Q);
	for (int i=1;i<n;i++) scanf("%d%d",&x,&y),Link(x,y);
	for (int i=Last[1];i!=-1;i=E[i].nxt)
	{
		Fir[++cnt]=++now;
		DFS(E[i].y,1,1,cnt);now--;
	}
	Fir[cnt+1]=n;
	while (Q--)
	{
		scanf("%d",&type);
		if (type==0)
		{
			scanf("%d%d%d",&x,&v,&d);
			int now=B[x],L=D[x]-d,R=D[x]+d;
			if (x==1) 
			{
				Add_r(1,v);Add_r(d+1,-v);
				Ans1+=v;continue;
			}
			if (L<=0) Ans1+=v;
			if (L>0) Add(Fir[now]+max(L-1,0),v),Add(min(Fir[now]+R,Fir[now+1]),-v);
			if (L<=0) 
			{
				L=-L;
				Add_r(1,v);Add_r(L+1,-v);
				if (Fir[now]+L<Fir[now+1])
					Add(Fir[now]+L,v),Add(min(Fir[now]+R,Fir[now+1]),-v);
			}
		} else
		{
			scanf("%d",&x);
			if (x==1) printf("%d\n",Ans1);
				else 
				{
					printf("%d\n",Sum_r(D[x])+Sum(Fir[B[x]]+D[x]-1));
				}
		}
	}
}

Codeforces Round #252 (Div. 2)

[B]

[C] 模拟一下即可。在奇数行左移,偶数行右移。

[D] 有点凶。我们用置换群的知识来解决这个问题。首先,我们考虑到一个状态可以表示成一个置换,进一步表示成若干循环的乘积。要达到初始状态的次数就是n-(循环个数)。然后可以发现,如果我们把两个循环合并到一起,答案就会+1,如果把一个循环拆开,答案-1。接下来我们要考虑怎样构造出字典序最小的合法方案。我们先考虑当前答案>m的情况,即我们要拆开若干个循环。经过观察可以发现这个性质:一个循环内任意两个数交换都会使循环分裂成两个循环。比如:3 4 2 1,这个对应的图是\((3->2),(2->4),(4->1),(1->3)\)。我们交换x,y的话,原来连向y的就会连向x,原来连向x的就会连向y。这样就成功地完成了拆分任务。\(swap(A[i],A[j])\)以后重新找一遍循环即可。至于当前答案<m的情况,也就是要合并若干循环,道理也是一样的。不再赘述。

[E]

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Maxn=3000+19;
int A[Maxn],f[Maxn],vis[Maxn];
int cnt,n,m,t;

inline int get_cir()
{
	int tmp=0;
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)
		if (!vis[i]) {tmp++;for (int j=i;!vis[j];j=A[j]) vis[j]=1,f[j]=tmp;}
	return tmp;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&A[i]);
	scanf("%d",&m);
	cnt=get_cir();
	printf("%d\n",t=abs(m-(n-cnt)));
	if (n-cnt<m) 
	{
		for (int i=1;i<=n&&t;i++)
			for (int j=i+1;j<=n&&t;j++)
				if (f[i]!=f[j])
				{
					printf("%d %d ",i,j);
					swap(A[i],A[j]);
					get_cir();t--;
				}
	} else
	{
		for (int i=1;i<=n&&t;i++)
			for (int j=i+1;j<=n&&t;j++)
				if (f[i]==f[j])
				{
					printf("%d %d ",i,j);
					swap(A[i],A[j]);
					get_cir();t--;
				}
	}
	puts("");
}

Codeforces Round #216 (Div. 2)

[C] 树形DP,先处理儿子,如果子树中没有一个被选中,且这个点到父亲结点的路需要修复,就加入这个点。

[D] 比较好的题。一开始没想到。我们注意每个人的目标,题目里写的是“除了自己以外编号最小”的那人。仔细想想,这一轮可能被打到的只有最小的、次小的这两个人。然后以这两个值作为状态\((x,y)\),BFS即可。分为三种转移:x活y死,x死y活,x死y死。

[E] 比较好的题。有点像301D。这类题目终于有了些感觉。首先答案是:n-(处于cnt个点中相邻两点之间的线段条数)。那么我们先把相邻两点构成的线段都搞出来,离线做,由于搞出的线段肯定是没有交集的,问题就变成了:已知两个线段集X和Y,求X中有多少线段被包含在Y中某线段里。由于“包含”要满足\(L_y<=L_x \& R_x<=R_y\),BIT比较适合处理一维,那么我们把所有线段按照L从大到小排序,从前往后扫描,这样可以保证\(\forall i<j\),都能满足\(L_j<=L_i\)。那么剩下只要满足\(R_i<=R_j\)。这个用BIT维护即可。

#include<cstdio>
#include<cstring>
using namespace std;

const int Maxn=3000+19;
struct state {int x,y;} Q[Maxn*Maxn];
int f,w,n,k,L0,L1,Ans;
int A[Maxn],Dis[Maxn][Maxn];

inline void Update(int x,int y,int D)
{
	if (x>n) x=0;
	if (y>n) y=0;
	if (D<Dis[x][y]) Dis[x][y]=D,Q[++f]=(state){x,y};
}

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&A[i]);
	if (n==1) {puts("1");return 0;}
	for (L0=n;L0&&A[L0]==0;L0--);
	for (L1=n;L1&&A[L1]!=100;L1--);
	memset(Dis,60,sizeof(Dis));
	Q[++f]=(state){1,2};Dis[1][2]=0;
	while (w<f)
	{
		w++;
		int x=Q[w].x,y=Q[w].y;
		if (!x||!y||Dis[x][y]>=k) continue;
		if (A[x]!=0&&L1<=x) Update(x,y+1,Dis[x][y]+1);
		if (y<=L0&&A[x]!=100) Update(y,y+1,Dis[x][y]+1);
		if (A[x]!=0&&y<=L0) Update(y+1,y+2,Dis[x][y]+1);
	}
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++) Ans+=(Dis[i][j]<=k);
	for (int i=1;i<=n;i++) Ans+=(Dis[i][0]<=k);
	Ans+=(Dis[0][0]<=k);
	printf("%d\n",Ans);
}
#include<cstdio>
#include<algorithm>
using namespace std;

const int Maxn=3e5+19,Len=1e6+19;
struct Seg {int L,R,ID;} A[Maxn*3];
int n,m,l,r,cnt,t;
int s[Maxn],Ans[Maxn],c[Len];

inline int cmp(Seg A,Seg B) {return A.L>B.L||A.L==B.L&&A.ID<B.ID;}
inline void Add(int x) {while (x<=1e6) c[x]++,x+=x&-x;}
inline int Query(int x) {int Ans=0;while (x) Ans+=c[x],x-=x&-x;return Ans;}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d",&A[i].L,&A[i].R),A[i].ID=0;
	cnt=n;
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&t);
		for (int j=1;j<=t;j++) scanf("%d",&s[j]);
		s[0]=0;s[t+1]=1e6+1;
		for (int j=0;j<=t;j++)
			if (s[j]+1<=s[j+1]-1) A[++cnt]=(Seg){s[j]+1,s[j+1]-1,i};
	}
	sort(A+1,A+cnt+1,cmp);
	for (int i=1;i<=cnt;i++)
		if (A[i].ID==0) Add(A[i].R);else Ans[A[i].ID]+=Query(A[i].R);
	for (int i=1;i<=m;i++) printf("%d\n",n-Ans[i]);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter