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，有错误就不够完美，赛后题解只是补充学习，更多的是大家平时的细节注意，大家为着梦想加油！