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

Codeforces Round #146 (Div. 2)

RXDoi posted @ 2014年7月17日 21:56 in Codeforces , 284 阅读

晚上没事干,就跟着SkyDec大神浪打一场Codeforces……

SkyDec选了一把,居然是丽洁姐出的题……真是有(sang)趣(xin)极(bing)了(kuang)……


A.Boy or Girl

这道题题意真是太逗了=。= 丽洁姐果然厉害……佩服佩服……算法方面没什么好讲的吧……

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

char c[100+19];
int n,cnt['z'+19];

int main()
{
	scanf("%s",c);
	for (int i=0;i<strlen(c);i++) cnt[c[i]]++;
	for (int i='a';i<='z';i++) if (cnt[i]) n++;
	printf("%s\n",n&1?"IGNORE HIM!":"CHAT WITH HER!");
}

B.Easy Number Challenge

这题的话,考虑到a,b,c的范围都<=100,就算乘起来100^3,开个根号求因子个数也不慢。

所以就暴力跑了……加个记忆化即可……

#include<cstdio>
using namespace std;

const int Mod=1073741824;
int a,b,c,F[100*100*100+19],Ans;

inline int calc(int x)
{
	if (F[x]) return F[x];
	int cnt=0;
	for (int i=1;i*i<=x;i++) 
	{
		if (i*i==x) cnt+=1;else
		if (x%i==0) cnt+=2;
	}
	return F[x]=cnt%Mod;
}

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	for (int i=1;i<=a;i++)
		for (int j=1;j<=b;j++)
			for (int k=1;k<=c;k++) Ans=(Ans+calc(i*j*k))%Mod;
	printf("%d\n",Ans);
}

C.LCM Challenge

这道题目的话,不要想太多233,我们可以在[n-100,n]这段区间内枚举a,b,c,求Lcm然后更新答案即可。

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

typedef long long LL;
int n;LL a,b,c,Ans;

LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}
LL Lcm(LL a,LL b) {return a/gcd(a,b)*b;}

int main()
{
	scanf("%d",&n);
	for (a=max(n-100,1);a<=n;a++)
		for (b=max(n-100,1);b<=n;b++)
			for (c=max(n-100,1);c<=n;c++)
			{
				LL tmp=Lcm(a,Lcm(b,c));
				if (tmp>Ans) Ans=tmp;
			}
	printf("%I64d\n",Ans);
}

D.Let's Play Osu!

这道题是求期望,这是我第一次做数学期望的题目……HHD大爷秒出D甚至比我做出B还要快……我在那里绝望地想了1个多小时才写出代码……

首先我们考虑:假如当前做到某一位,前面有连续的长为Len的一段o,那么对答案的贡献是什么?显然是pi*(Len+1)^2对吧。那么我们是不是求出到每一位时前面期望的连续o的长度就可以解决本题?

那么很显然的,一开始Len=0,每次处理完某一位后更新Len,有pi的几率Len+1,有(1-pi)的几率Len=0.那么新的Len就=pi*(Len+1)。

注意如果用这种方法计算的话,到每一位都累加一下答案,这样会有重复累加的情况,需要把前面算过的减掉,即(Len+1)^2-Len^2.如此即可。

#include<cstdio>
using namespace std;

int n;
double t,Ans,Len;

int main()
{
	scanf("%d",&n);
	while (n--)
	{
		scanf("%lf",&t);
		Ans+=t*(2*Len+1);
		Len=(Len+1)*t;
	}
	printf("%.10lf\n",Ans);
}

E.Cyclical Quest


登录 *


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