ACM第二次考核（部分）题解

写在最前面，计算机题目，大多数考察的都是思维能力，首先要完整的将题目多读两遍，明确题目的目的，然后再结合样例输入输出检测自己的想法是否是正确的；

A题：

考察点：快速幂的运用；

 分析：

初始速度为1，每次脚踩脚会让速度翻倍，即乘以二，踩了n次，那么最后的速度就是2^n米每秒，如果用传统的方法那么时间复杂度为O（n），由于时间限制是400ms，当n过大时，运行就会超时，所以正确做法是使用快速幂，就可以将时间复杂度降低，代码如下：

#include
using namespace std;
#define p 299792458
int main()
{
	int n;
	scanf("%d",&n);
	long long base=2;
	long long  result=1;
	while(n>0){
		if(n&1){
			result=(result%p*base%p)%p;
		}
		n>>=1;
		base=(base*base)%p;
	}
	printf("%lldn",result);
}

B题：

考察点：递归思维；

分析：

 这种考察思维的题，看完题目后去看样例输入输出对思维启发会有很大帮助，我们可以看到：

1只时：一定会被吃点，然后变成，没有别的，他一定不会被吃掉，所以最开始那只羊一定会被吃掉；

2只时：假如有一只狼把羊吃了，他自己变成了羊，那他就一定会被另一只狼吃掉，所以他不敢吃羊；所以两只狼都不敢吃羊；

3只狼时：假入有一只狼把羊吃掉了，那他自己就变成了羊，然后现在的状态就是两只狼一只羊，回到了上一种状态，另外两只狼不敢吃羊，吃掉羊的那只狼就不用担心自己是否会被吃，所以羊一定会被吃掉；

4只狼时：就假设一只狼吃掉了羊，回到第三只狼的状态……

由上述规律可得，有奇数只狼时，羊一定会被吃掉，偶数只狼时，不会被吃掉；

#include
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if(n%2==0){
		printf("NO");
	}else {
		printf("YES");
	}
}

之所以这题没做出来，一个是因为自己着急了，二一个是觉得这种思维题估计会很难想到，于是猜测了只有当n=1时会被吃掉其他不会被吃的情况，提交后错了，于是就没有思考这题了，也算是很可惜吧，要是把思考最后一题的时间拿来思考这题，应该还是能过的。

C题

考察点：思维；

分析：

    首先要将输入的数的回文数构建出来，然后再来判断是不是素数，我们可以分析出，最大的回文数为999999999，将近10亿！这么大的数，构建素数表再来做判断显然不可能，编译都要实际二十多秒（当时我还以为是软件的问题），所以大概率这题也就是用最常规的方法做判断是不是素数， 难点在于构建回文数，emmm，好吧其实也不算是难点，写多了就会了，

#include
using namespace std;
const int N=1e6+5;
int main()
{
	string s;
	getline(cin,s);
	int i;
	int l1=s.length();
	long long ans=0;
	for(i=0;i<=2*l1-1;i++){
		if(l1==1){
			ans=s[i]-'0';
			break;
		}
		if(i=l1){
			ans=ans*10+s[2*l1-i-1]-'0';
		}
	}
	for(i=1;i<=8&&ans<=8;i++){
		if(ans==2||ans==3||ans==7||ans==5){
			printf("isprimen");
			break;
		}else {
			printf("noprimen");
			break;
		}
	}
	for(i=3;i<=sqrt(double(ans));i++){
		if(ans%i==0){
			//printf("%dn",i);
			printf("noprimen");
			break;
		}
		if(i>sqrt(double(ans))-1){
			printf("isprimen");
			break;
		}
	} 
}

E题：

考察知识点：快速幂，前缀和一点gcd的结合运用 

分析：

        在m轮循环中，每一个数都或多或少的乘以了2或3，我们的目的是求最大公约数，按常理来说，直接每一轮分别乘就是了，但是！注意这题的时间限制是500ms，也就是这题大概率是要在运行时间卡我们，那么常规的方法大概率就是不行的，根据本周所学知识，其实就是考察快速幂的使用，也就是每个位置上的数成了多少个2，乘了多少个3，然后用快速幂求出来，所以我们就要分别记录下来每个位置乘了多少2和3，可以用两个数组来实现；但如果我们就是每个位置去挨个加一，那就和直接乘2，乘三没有区别了，还是多了一个for循环，造成超时，所以我们要用前缀和的方法来记录，这样就能少一层循环；

        记录好后，我们就要来找最小公约数，每个位置上的数都是1乘以了多少个2，乘以多少个3，也就是说多乘以了一个2的那个数一定是少乘一个2的那个数的倍数，那我们就只需要找乘2次数最少的，3也一样，所以我们找到乘2的最小次数，乘3的最小次数，然后再利用快速幂求出最大公约数即可；

//分别记录下每个位置的数乘了多少次2，3， 可以利用前缀和； 
#include
using namespace std;
const int N=1e5+5;
#define p 999999998
#define ll long long
ll quick(ll base,ll n)
{
	ll result=1;
	while(n>0){
		if(n&1){
			result=result*base%p;
		}
		n>>=1;
		base=base*base%p;
	}
	return result;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		int a2[N],a3[N];//前缀和记录2和3的个数； 
		int x[N],y[N];
		//都初始化为0； 
		memset(a2,0,sizeof(a2));
		memset(a3,0,sizeof(a3));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		while(m--){
			int l,r,x;
			scanf("%d%d%d",&l,&r,&x);
			if(x==2){
				a2[l]++;
				a2[r+1]--;
			}
			if(x==3){
				a3[l]++;
				a3[r+1]--;
			}
		}
		//找到所有元素中乘的次数最少次的那个； 
		int min2=a2[1],min3=a3[1];
		for(int i=1;i<=n;i++){
			x[i]=x[i-1]+a2[i];
			y[i]=y[i-1]+a3[i];
			min2=min(min2,x[i]);
			min3=min(min3,y[i]);
		}
		ll ans=(quick(2,min2)%p*quick(3,min3)%p)%p;
		printf("%lldn",ans);
	}
}

G题

考察点：排序、前缀和、思维能力，

 分析：

在读完题目后，我们要明确目的“使所有人的平均等待时间最短”，平均等待时间其实就是所有人的等待时间之和除以总人数，所以我们要使找所有人的等待时间之和最小化；

那么当前面一个人在洗澡的时候，后面所有人也就在等待，对于第一个人，她直接就进去洗澡了，她的等待时间为0，她在洗澡的时候，后面的人也就在等待，第二个人进去的时候，后面的人也就在等待，也就是说，后面的人的等待时间也就是前面洗澡的人的洗澡时间之和，所以这里可以想到要用到前缀和，那如何让总的等待时间最短呢？也就是让洗澡时间最长的人最后洗，这样其他人的等待时间就大幅缩减了，也就是说，最好的排序方式是按照洗澡时间从短到长排序，那么最后一个人洗澡时就没人需要等待了，所以这里要用到排序的知识，那么平均等待时间也就是所有人等待时间之和除以总人数；

我的：

想法是：建立结构体数组，一个值表达洗澡时间，一个值表达最开始输入这个洗澡时间时它的位置，然后按照思路做。而我一直被卡着的原因是：没想通怎么记录下最开始的位置，其实不用结构体，用另一个数组也能做，但可能太紧张，太着急了，所以一直没想出来；

#include
using namespace std;
const int N=1e6+5;
int b[N];
struct piont {
	int x;
	int y;
}a[N];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i].x);
		a[i].y=i;
		int t=i;
		for(j=i-1;j>0;j--){
			if(a[t].x

最优解（出题人的解）：

其实也是使用了结构体；

#include
using namespace std;
struct st{
	int x;
	int y;
};
st a[1005];
bool rule(st i,st j){
	if(i.y