Codeforces Round #146 (Div. 2)
Codeforces 30题 II (Aug.12~?,2014)

Codeforces 30题 (July.16~Aug.12,2014)

RXDoi posted @ 2014年7月18日 17:26 in Codeforces , 412 阅读

据说刷CF可以锻炼代码能力……

机房大爷们都开始刷CF了,我一代蒟蒻怎能不跟随大爷们的脚步?

先预订个30题,希望能坚持完成。这里只有>=Div.1 A的题目才算吧~~以题解数量为证~~

ps:我干脆把< Div.1 A的题解也写到这里吧,就算Unofficial……>=Div.1 A的会在左边表明Prob.XX~~


Prob.01——CF 448D Multiplication Table

这题其实非常水=。=我们可以二分答案x,然后O(n)统计<=x的有多少个。显然对于第i行,<=x的数有x/i个。不要忘了对于每一行要和m取一个min!

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

typedef long long LL;
LL L,R,k,n,m;

int main()
{
	scanf("%I64d%I64d%I64d",&n,&m,&k);
	L=0;R=1LL*n*m;
	while (L<R)
	{
		LL Mid=(L+R)>>1,cnt=0;
		for (int i=1;i<=n;i++) cnt+=min(m,Mid/i);
		if (cnt<k) L=Mid+1;else R=Mid;
	}
	printf("%I64d\n",R);
}

Prob.02——CF 332C Students' Revenge


Prob.03——CF 449A Jzzhu and Chocolate


Prob.04——CF 449B Jzzhu and Cities


Prob.05——CF 449D Jzzhu and Numbers


Unofficial.01——CF 342B Xenia and Spies


Prob.06——CF 342C Cupboard and Balloons


Prob.07——CF 342D Xenia and Dominoes

这是一道值得推荐的题目。

题目的意思是用多米诺骨牌去填充,要保证填完的结果可以移动至少一次多米诺骨牌('O'的位置要空出来,让一块多米诺骨牌移动到'O'的位置),求方案数。

考虑到行数只有3,这么小的常数,所以为何不状压?然后求方案数,那么递推啊,于是就很好想了:Dp[x][now][Flag]表示当前处理到从左往右第x列,当前这一列的障碍情况是now (0<=now<=7),Flag=1表示已经满足“可以移动至少一次”的条件,=0则尚未满足。用记忆化搜索实现。

显然我们可以枚举这一列放置的情况。可以放第1、2列,也可以放2、3列,也可以和第(x+1)列合起来放横过来的。注意细节问题即可。

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

const int Maxn=1e4+19,Mod=1e9+7;
char Map[3][Maxn];
int Dp[Maxn][8][2],tmp[Maxn];
int n;

inline int is_0(int x,int Dis) {return ((x>>Dis)&1)==0;}
inline int Get_Dp(int x,int now,int Flag)
{
	int &A=Dp[x][now][Flag];
	if (A^-1) return A;A=0;
	if (x==n) return A=(!now&&Flag);
	now|=tmp[x];
	if (now==7) return A=Get_Dp(x+1,0,Flag);
	if (is_0(now,0)&&is_0(now,1)) A=(A+Get_Dp(x,now|3,Flag||Map[2][x]=='O'))%Mod;
	if (is_0(now,1)&&is_0(now,2)) A=(A+Get_Dp(x,now|6,Flag||Map[0][x]=='O'))%Mod;
	int can=1,nxt_Flag=0,nxt_now=0;
	for (int i=0;i<3;i++)
	{
		if (is_0(now,i)&&!is_0(tmp[x+1],i)) {can=0;break;}
		if (x&&Map[i][x-1]=='O'||Map[i][x+2]=='O') nxt_Flag=1;
		if (is_0(now,i)) nxt_now|=(1<<i);
	}
	if (can) A=(A+Get_Dp(x+1,nxt_now,Flag||nxt_Flag))%Mod;
	return A;
}

int main()
{
	scanf("%d",&n);
	for (int i=0;i<3;i++) scanf("%s",Map[i]);
	for (int i=0;i<n;i++)
	{
		tmp[i]=7;
		for (int j=0;j<3;j++)
			if (Map[j][i]=='.') tmp[i]-=(1<<j);
	}
	memset(Dp,-1,sizeof(Dp));
	printf("%d\n",Get_Dp(0,0,0));
}

Prob.08——CF 342E Xenia and Tree


Prob.09——CF 449C Jzzhu and Apples


Prob.10——CF 359C Prime Number


Prob.11——CF 448C Painting Fence


Prob.12——CF 448E Divisors


Unofficial.02——CF 361B Levko and Permutation


Prob.13——CF 361C Levko and Array Recovery


Prob.14——CF 361D Levko and Array


Prob.15——CF 354A Vasya and Robot


Prob.16——CF 354C Vasya and Beautiful Arrays


Prob.17——CF 406A Unusual Product

跪烂6分钟切掉这题的SkyDec大爷!

这是一道非常好的题目,下面是蒟蒻的题解~~~

考虑两个点(x,y)和(y,x)。它们相乘对答案的贡献有两次,分别是行向量x点乘列向量x的时候,行向量y点乘列向量y的时候。这两次的结果是一样的。那么他们对答案的贡献显然是0.

所以无论矩阵是怎么样的,对答案有贡献的只有对角线。那么只要统计对角线即可,不管行取反还是列取反,Ans都取反即可。

#include<cstdio>
using namespace std;

int n,m,x,c,Ans;

int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
		{
			scanf("%d",&x);
			if (i==j) Ans^=x;
		}
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d",&c);
		if (c<=2) scanf("%d",&x),Ans^=1;else printf("%d",Ans);
	}
	printf("\n");
}

Prob.18——CF 406B Toy Sum

这道题也是SkyDec大爷告诉我方法的……

我刚看题目,背包~~~ 仔细一看范围,算了下效率,10^12~~~你背包个**……

然后我们可以这么想:对于一个x,它对答案的贡献是x-1。与之对应的y是多少?显然是1e6+1-x对吧,因为1e6-(1e6+1-x)=x-1。

那么我们理所当然地会想到对于每个x找出对应的y。可是有些x和对应的y都被选中了,即都∈X,那怎么办呢?这样的话这对x和y对答案的共同贡献是x-1+(1e6+1-x-1)=1e6-1。这怎么处理呢?我们需要找一对x'和y',使得1e6-x'+1e6-y'==1e6-1。那么显然的,x'+y'=1e6+1。这样就和刚才的条件一样了~~~

最终的算法就是:对于所有数分类,把x和1e6+1-x分到一组,如果一组中一个被选中了,一个没被选中,那么没被选中的那个作为y输出。如果两个都被选中了,就另外找一个两个数都没选中的组,把这两个数输出。

#include<cstdio>
using namespace std;

const int Max=1e6+19,tot=1e6+1;
int use[Max],n,x,sol[Max],Ans,now=1;

int main()
{
	scanf("%d",&n);
	while (n--) scanf("%d",&x),use[x]=1;
	for (int i=1;i<tot;i++)
		if (use[i]==1)
			if (!use[tot-i]) 
			{
				use[tot-i]=-1;
				sol[Ans++]=tot-i;
			} else
			{
				while (use[now]||use[tot-now]) now++;
				use[now]=use[tot-now]=-1;
				sol[Ans++]=now;sol[Ans++]=tot-now;
				use[tot-i]=0;
			}
	printf("%d\n",Ans);
	while (--Ans>=0) printf("%d ",sol[Ans]);
}

Prob.19——CF 444A DZY Loves Physics

这里先给出结论:枚举每一条边。答案一定是某一条边。

CF官方有严密证明。不过显然的,就像平均数,a和b的平均值肯定在a与b之间,如果给出很多数要求其中若干数的平均值的最大值,那么答案肯定在某一个数中。因为再加任何一个数都会拉低平均值。这题也是一样的道理。

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

int A[500+19];
int n,m,x,y,z;
double Ans=0.;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&A[i]);
	while (m--)
	{
		scanf("%d%d%d",&x,&y,&z);
		Ans=max(Ans,(A[x]+A[y])/(1.0*z));
	}
	printf("%.15lf\n",Ans);
}

Prob.20——CF 444B DZY Loves FFT


Prob.21——CF 392A Blocked Points


Prob.22——CF 392B Tower of Hanoi


Prob.23——CF 383A Milking cows


Prob.24——CF 383C Propagating tree


Prob.25——CF 383D Antimatter


Prob.26——CF 364A Matrix


Prob.27——CF 364B Free Market


Prob.28——CF 256A Almost Arithmetical Progression


Prob.29——CF 256B Mr. Bender and Square


Prob.30——CF 213A Game


登录 *


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