GDUT初赛题解
这次比赛，看到了自己跟大家的差距，所谓的大神是从一点一滴练起的。不是说钻研得多高深，就多牛；而是所有的题干细节处理到位，所有能做的题1A，向bin神学习吧，同志们！一起加油！
说明：这个题解，有我自己的代码，也有bin神的，axp巨巨的，Tonny巨巨，还有好多帮助过我的人，希望群巨多多参与题解的建设，方便自己做总结，也方便群巨学习。
话不多说。从每一题开始（题意全部略去）
第一天
A.模拟。对3种情况，分别进行处理。容易出现的错误有：注意当队伍中已经没人的时候请忽略第2种事件，每组数据新开始的时候队伍中人数都为0！另外，我一开始实现的代码是用queue写的，不知道为什么超时了。。。估计是迭代器比较慢。AC代码如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971
typedef long long LL;
const int maxn=10000050;
int head,tail;
int num[maxn];
int main(){
//freopen("input.txt","r",stdin);
int t,n,a,b,k;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(num,0,sizeof(num));
head=0,tail=0;
while(n--){
scanf("%d",&a);
if (a==1){
scanf("%d",&b);
num[tail]=b;
tail++;
}
else if (a==2){
if (head<tail) head++;
}
else{
scanf("%d",&k);
if (head+k<=tail) printf("%d\n",num[head+k-1]);
else puts("na li you zhe me duo ren");
}
}
}
return 0;
}细节：注意head<tail这句，是处理重点语句的。我当时写了等号，意味着没有处理一开始就是选项2的情况，题意中说明了是有这种可能的。
B.按照题意，对输入的数字进行转换。我的代码很挫，改了又改最后对的。对于n=1000的这种小数据，告诉大家一个1A的方法，用freopen形成一个1到1000的测试数据，看看答案是不是有规律连续的即可。
我的代码：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971
void Print(int n){
int i,j,k;
if (n<=26){
printf("%c\n",n+'A'-1);
return;
}
if (n>=27&&n<=26*27){
for(j=1;j<=26;j++)
for(k=1;k<=26;k++){
if (j*26+k==n){
printf("%c",j+'A'-1);
printf("%c",k+'A'-1);
puts("");
return;
}
}
}
printf("A");
for(j=1;j<=26;j++)
for(k=1;k<=26;k++){
if (j*26+k==n-26*26){
printf("%c",j+'A'-1);
printf("%c",k+'A'-1);
puts("");
return;
}
}
}
int main(){
int t;
int n;
int ans[500];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
Print(n);
}
return 0;
}上上bin神的代码，每道题都可以学学不同的思路，有时候有了题解，不要懒，自己实现实现
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
if(n <= 26){
printf("%c\n",(char)('A'+n-1));
}
else if(n <= 26+26*26){
n -= 27;
printf("%c%c\n",(char)('A'+n/26),(char)('A'+n%26));
}
else {
n -= 26+26*26+1;
printf("%c%c%c\n",(char)('A'+n/26/26),(char)('A'+(n/26)%26),(char)('A'+n%26));
}
}
return 0;
}
又有一个巨巨提供的代码，觉得挺好的，供大家学习string的细节处理：
#include <cstdio>
#include <cstring>
int main()
{
int N;scanf("%d",&N);
while(N--)
{
int n,cnt=0;
char s[16];
scanf("%d",&n);
while(n)
{
int m=n%26;
if(!m)m=26;
s[cnt++]=m+64;
n=(n-m)/26;
}
for(int i=cnt;i;--i)
putchar(s[i-1]);
puts("");
}
return 0;
}C.这道题不需要题解的吧。。给大家提供个bin神快的诀窍。
sort(a,a+n)代表对a数组中的a[0]到a[n]从小到大排序
reverse(a,a+n)代表对a数组中所有元素反序存储。之后的。大家懂
D.这个题是比较好的一道题。有多种做法。
先说说思路。
1.bin神思路。dp[i][0]代表共i位数字，最后1位为0的不含有11的数目，dp[i][1]代表共i位数字，最后1位为1的不含有11的数目，这样，答案就是2^n-dp[i][0]-dp[i][1]。递推过程很好想。代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MOD = 1e9+7;
int dp[1000010][2];
void Add(int &a,int b){
a += b;
if(a >= MOD)
a -= MOD;
}
int two[1000010];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
memset(dp,0,sizeof(dp));
dp[1][0] = dp[1][1] = 1;
two[1] = 2;
for(int i = 2;i <= 1000000;i++){
dp[i][0] = dp[i-1][1]+dp[i-1][0];
if(dp[i][0] >= MOD)
dp[i][0] -= MOD;
dp[i][1] = dp[i-1][0];
two[i] = 2LL*two[i-1]%MOD;
}
int T;
int n;
cin>>T;
while(T--){
scanf("%d",&n);
int ans = two[n]-(dp[n][0]+dp[n][1])%MOD;
ans = (ans%MOD+MOD)%MOD;
printf("%d\n",ans);
}
return 0;
}
2.dfs处理所有小数据（或者手算打表）。发现ans[n]=2*ans[n-1]-f[n-1]，其中f代表斐波那契数列，其中f[1]=f[2]=1。打表不贴代码，大家自己实现吧。
3.axp巨巨提供：光棍是递推，长度为n的有两种情况，110+长度为n-3不符合情况的，0或1加上长度为n-1符合要求的
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int maxn = 1000100;
const int mod = 1000000007;
int arr[maxn];
int two[maxn];
int T,n;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
two[0]=1;
for(int i=1;i<maxn;i++)
two[i]=(two[i-1]*2)%mod;
arr[2]=1;
for(int i=3;i<maxn;i++)
{
arr[i]=( (2*arr[i-1])%mod + two[i-3]-arr[i-3] )%mod;
while(arr[i]<0)
arr[i]+=mod;
}
cin>>T;
while(T--)
{
scanf("%d",&n);
printf("%d\n",arr[n]);
}
return 0;
}
5.物理题。。大家注意，题中条件少，意味着需要自己找。判断要求为：炮弹45度出发打不中的话就肯定打不中了（高中物理）。就是求以v斜向上45度发射，求最大距离x与d的关系。x=v^2/g。分解成水平速度v0和垂直速度vy。大家都会的。细心就好
6.我大概懂了，axp巨巨教的。每次循环都改动字符串，就是第i位和第len-k+i相同所以就统计所有相隔len-k的字符，选出出现次数最多的，把这些字符都修改为这个字符，统计要修改的次数就是答案了。代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int ans;
const int maxn = 1100;
char ch[maxn];
int T,k;
int arr[26];
int be;
int l;
int f(int x)
{
memset(arr,0,sizeof(arr));
int re=0;
int r=0;
while(x<l)
{
r++;
arr[ch[x]-'A']++;
x=be+x;
}
for(int i=0;i<26;i++)
re=max(re,arr[i]);
return r-re;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>T;
while(T--)
{
scanf("%s%d",ch,&k);
l=strlen(ch);
be=l-k;
ans=0;
for(int i=0;i<k && i<l-k;i++)
{
ans+=f(i);
}
printf("%d\n",ans);
}
return 0;
}
上面这题我一直没过是因为我用贪心思考的，判断的时候没有管到连续的修改值的问题。axp巨巨Hack我的数据是aaabbbccc 8。我的贪心代码比较渣，只关注了第i位和第i位匹配位和第len-i位的匹配位。没有想到链接的关系。Hack数据len=9，k=8，意思是连续的都相同，即为所有字符都一样。所以，贪心策略不知道实行多少次，没有贪心的正确性保证，只能用类似搜索的方法实现。
7.既然是颗树，既然是n=1000，dfs和bfs是不会有问题的。我的思路，用ans[i]记录，若等于0说明未访问过，若等于j说明走到i之前必须过j（由于是颗树），dfs时数目肯定不会大，因为每次扩展的节点是有限的。代码如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971
const int maxn=2000;
int t,n,s;
int mp[maxn][maxn];
int ans[maxn];
void dfs(int start){
int i,j;
for(i=1;i<=n;i++)
if (!ans[i]&&mp[start][i]){
ans[i]=start;
dfs(i);
}
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&t);
int a,b;
int i,j,k;
while(t--){
memset(mp,0,sizeof(mp));
memset(ans,0,sizeof(ans));
scanf("%d%d",&n,&s);
ans[s]=-1;
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
mp[a][b]=mp[b][a]=1;
}
dfs(s);
for(i=1;i<=n;i++)
printf("%d%c",ans[i],i==n?'\n':' ');
}
return 0;
}
8.大大的水题。给个式子就好了。
num[1]=1;
num[2]=2;
for(i=3;i<=1000;i++)
num[i]=num[i-1]+i-1;小数据打表就好。
初赛的题解就到这里。谢谢bin神，axp巨巨，Tonny巨巨和群巨的帮助和支持。希望大家也能分享自己的AC和各种错误，一起提高。
Hint：比赛就是这样，还记得我初中数学老师说的，打不了满分就不要说题目简单。放到ACM也一样，这道题你不是1A就没有资格说它简单，这场比赛没有AK，有错误就不够完美，赛后题解只是补充学习，更多的是大家平时的细节注意，大家为着梦想加油！
网易公司福利 166人发布
