A题 GRE

水题

#include<bits/stdc++.h>
using namespace std;
char a[11][10]={"zero","one","two","three","four","five","six","seven","eight","nine","ten"};
char b[11][10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu","shi"};
int main()
{int t;cin>>t;while(t--){char s[10];cin>>s;for(int i=0;i<11;i++){if(strcmp(s,a[i])==0){cout<<b[i]<<endl;break;}}}return 0;
}

B题 Words Game

统计母串26个小写字母每个字母的个数，然后对每个子串统计判断一遍，如果满足子串中所有字母每个字母的个数都不大于母串，那么这个子串一定是母串的一个子序列。

#include<iostream>
#include<cstring>
using namespace std;
int a[30],b[30];
int main()
{string s;while(cin>>s){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0;i<s.length();i++)a[s[i]-'a']++;int n,ans=0;cin>>n;while(n--){cin>>s;int blag=0,len=s.length();for(int i=0;i<len;i++)b[s[i]-'a']++;for(int i=0;i<26;i++){if(a[i]<b[i])blag=1;b[i]=0;}if(!blag)ans=max(ans,len);} cout<<ans<<endl;}return 0;
} 

C题 Arch0n’s interesting game

根据题意两重循环暴力走一遍即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=2505;
int a[maxn],b[9000005];
int cmp(int x,int y)
{return x>y;
}int main()
{int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];int p=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)b[p++]=min(a[i],a[j]);sort(b,b+p,cmp);cout<<b[k-1]<<endl;}return 0;
}

D题 另一个另一个简单游戏

实际上就是求平均值

#include<iostream>
using namespace std;
int main()
{int t,n;cin>>t;while(t--){cin>>n;int sum=0,x;for(int i=0;i<n;i++){cin>>x;sum+=x;}cout<<sum/n<<endl;}
}

E题 Xieldy And His Password

设每个二进制串s除以3有0,1,2三种转态（分别表示余数为0，余数为1，余数为2），那么根据推导有如下结论：

 状态0 + ‘0’   ==》 状态0状态1 + ‘0’   ==》 状态2状态2 + ‘0’   ==》 状态1状态0 + ‘1’   ==》 状态1状态1 + ‘1’   ==》 状态0状态2 + ‘1’   ==》 状态2

因此可以设dp[i][j] （1<=i<=n,j=0,1,2） 表示前i个串中余数为j的个数

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e6+10;
string s;
long long dp[maxn][4];
int main()
{while(cin>>s){memset(dp,0,sizeof(dp));dp[0][0]=dp[0][1]=dp[0][2]=0;int len=s.length();long long ans=0;for(int i=0;i<s.length();i++){if(s[i]=='0'){dp[i+1][0]=dp[i][0]+1;dp[i+1][2]=dp[i][1];dp[i+1][1]=dp[i][2];}else{dp[i+1][1]=dp[i][0]+1;dp[i+1][0]=dp[i][1];dp[i+1][2]=dp[i][2];}ans+=dp[i+1][0];}cout<<ans<<endl;}return 0;
}

F题 Operating System

理解题意之后实际上就是求不同数的个数，用set即可。

#include<iostream>
#include<set>
using namespace std;
set<int> s;
int main()
{int n,m,q,x;while(cin>>n>>m>>q){while(q--){cin>>x;s.insert(x);}cout<<s.size()<<endl;s.clear();}return 0;
}

G题 小国的复仇

题目大意：开始的时候a=1, b=1，有两种操作

（1）  a=a+b;
（2）  b=a , a=a*2;

问至少需要多少次操作，才能让a变成n?

解题思路：首先可以推断若n为素数，一定需要n-1次。那么就可以拓展到若n有素因子，即将n用唯一分解定理分解成若干个素因子相乘，因为每次变成一个素数需要-1次，因此n就需要若干个素因子-1次之和。

#include<iostream>
using namespace std;
int main()
{int t,n;cin>>t;while(t--){cin>>n;int ans=0;for(int i=2;i*i<=n;i++){while(n%i==0){ans+=i-1;n/=i;}}if(n>1)ans+=n-1;cout<<ans<<endl;}return 0;
}