晚上没事干，就跟着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