这次比赛有好几个题目都不会做，好好学习吧！虽然有很多想法，但是自己一一否定了 0.0
C、 True Love
看懂题目意思就是一个多重背包，题目只要求染色方案数，使用 bool型多重背包可以方便解决这个问题。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200],b[200];
int dp[100100],cnt[100100];
int main(){
int cases,n,m;
scanf("%d",&cases);
for (int cas=1;cas<=cases;cas++){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
memset(dp,false,sizeof(dp));
int ans=0;dp[0]=true;
for (int i=1;i<=n;i++){
memset(cnt,0,sizeof(cnt));
for (int j=a[i];j<=m;j++){
if (dp[j-a[i]]&&!dp[j]&&cnt[j-a[i]]<b[i]){
ans++;
dp[j]=true;
cnt[j]=cnt[j-a[i]]+1;
}
}
}
printf("Case %d: %d\n",cas,ans);
}
return 0;
}
D、 LSS
题目求 连续的最多的相同的字母 的个数。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char st[200];
int main(){
int cases;
scanf("%d",&cases);gets(st);
while (cases--){
gets(st);
int len=strlen(st);
int sum=1,ans=1;
for (int i=1;i<len;i++){
if (st[i-1]==st[i]) sum++;
else sum=1;
if (ans<sum) ans=sum;
}
printf("%d\n",ans);
}
return 0;
}
H、 Salmon and Cat
（a+2）（b+2）=c+2 、 把a+2 、b+2、c+2 看成一个整体，于是题目就变成 求n+2是否被3和5除尽。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
int n;
while (~scanf("%d",&n)){
n+=2;
while (n%3==0) n/=3;
while (n%5==0) n/=5;
if (n==1) printf("Yes\n");
else printf("No\n");
}
return 0;
}
F、The Arrow
题目大意：
掷骰子，1-6、给定一个n。我们把我们k次掷骰子的和记为sum，当前掷骰子点数为t。若 sum+t>n ，sum 不变，
若sum+t==n 游戏结束
若sum+t<n 继续游戏，sum+=t。
问，期望多少次 能结束游戏。
这应该叫 期望dp？
我们设dp[x]表示x还期望走多少步能到达n。显然 dp[n]=0 、dp[0]就是我们要求解的期望。
方程是 dp[x]=(dp[x+1]+dp[x+2]+...+dp[x+6])/6+1 可以这样理解，x到x+1 期望走1步，1/6的概率、
和n相邻的6个点n-1到n-6要注意。以n-2为例 dp[n-2]=dp[n-1]/6+dp[n]/6+dp[n-2]*4/6+1..为何要加入dp[n-2]呢？因为n-2自己可以掷出3-6的话可以得到自己。然后我们解方程就可以得到dp[n-2]...
这便是所谓的期望dp 要倒着来做了吧、在这样算出来之后，可以考虑正向打表，但是这对于初学者不好理解啊= =、
#include <iostream>
#include <cstring>
#include <cstdio>
#define Maxn 100100
using namespace std;
double dp[Maxn];
int main (){
int cases,n,cnt;
scanf("%d",&cases);
while (cases--){
scanf("%d",&n);
dp[n]=0;
for (int i=n-1;i>=0;i--){
dp[i]=0;cnt=0;
for (int j=1;j<=6;j++){
if (i+j>n) cnt++;
else dp[i]+=dp[i+j];
}
dp[i]=(dp[i]+6)/(6-cnt);
}
printf("%.2f\n",dp[0]);
}
return 0;
}
G、Number Theory
题目大意：所有的数<=222222、给出一个n，和n个数，问有多少对互质的数、
莫比乌斯反演，我还没怎么弄明白，以后再来总结。
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define Maxn 222222
using namespace std;
bool isPri[Maxn+30];
int mu[Maxn+10],pri[Maxn+10],a[Maxn+10],cnt[Maxn+10],num[Maxn+10];
int pnum;
int mobius(int n){
memset(isPri,true,sizeof(isPri));
pnum=0;isPri[1]=false;mu[1]=1;
for (int i=2;i<=n;i++){
if (isPri[i]){
pri[++pnum]=i;
mu[i]=-1;
}
for (int j=1;j<=pnum;j++){
if (i*pri[j]>n) break;
isPri[i*pri[j]]=false;
if (i%pri[j]==0){
mu[i*pri[j]]==0;
break;
}
mu[i*pri[j]]=-mu[i];
}
}
}
LL cal(LL x){
return x*(x-1)/2;
}
int main(){
mobius(222222);
int n;
while (~scanf("%d",&n)){
int Max=0;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
Max=max(Max,a[i]);
}
memset(cnt,0,sizeof(cnt));
memset(num,0,sizeof(num));
for (int i=1;i<=n;i++){
num[a[i]]++;
}
for (int i=1;i<=Max;i++){
for (int j=i;j<=Max;j+=i){
cnt[i]+=num[j];
}
}
LL ans=0;
for (int i=1;i<=Max;i++){
ans+=mu[i]*cal(cnt[i]);
}
printf("%lld\n",ans);
}
return 0;
}
其他还有很多好题目！以后记得一定要补齐。