简介：

入坑acm也有一年多了，确实本人的第一篇微博，那么就从xdoj的acm校赛开始吧。

 

赛题介绍：

本次校赛，题目难度为2 + 3 + 4，即两道签到题，三道过关题和四道登峰题。

 

两道签到题基本毫无难度，三道过关题还是有点坑点的，至于登峰题基本属于挑战，既然最终将五题定为了省赛选拔门槛，那就让我们来回忆一下这前五题吧。

 

题目：

 

Problem A Keal’s Skill IV - PlasticSpirit

 

 

思路：这一题纯水题，根据输入的数值所在范围输出相应字符串，不说了，直接上代码

 

 

/* Author：Owen_Q */ #include <bits/stdc++.h> using namespace std; int main() { int n; while(scanf("%d",&n)!=EOF) { if(n>0&&n<=1000) { printf("XiaoZhen\n"); } else if(n>1000&&n<10000) { printf("Zh0ngshen\n"); } else if(n>=10000) { printf("DaNuo\n"); } } return 0; }

 

Problem B The Gym - EXCITING

 

 

思路：又是一道水题，根据读入的字符串，匹配输出对应的字符串，因为明确规定不会有非法输入，所以可以直接用字符数组秒过

 

/* Author：Owen_Q */ #include <bits/stdc++.h> using namespace std; int main() { char s[10]; while(scanf("%s",s)!=EOF) { if(strcmp(s,"v8")==0) { printf("SingleDog&YangRouHuoGuo\n"); } else if(strcmp(s,"qsqx")==0) { printf("Couple&Program\n"); } else if(strcmp(s,"lbz007")==0) { printf("SingleDog&GoodGoodStud\n"); } } return 0; }

 

Problem C Counting Stars - RiseAbove

 

 

思路：这是一道典型的数学题，圆分平面，根据样例，甚至再算一位都满足2的n次方，于是很容易让人产生2^n的联想，于是WA到生无可恋，再加上18位的模数M，使选手心存恐惧，查错过程起了很大误导。

 

其实，还是需要耐心去推一下公式，不要想走捷径，这题就没什么了，至于那个可怕的M，由于太大了，其实没有任何作用，忽略掉就好了。

 

至于圆分平面问题，其实和线段分平面有点类似，就是个递推找规律，其实只要推到第四项就会发现问题了，答案是14而不是2^4=16。下面来推导一下公式

 

问题抽象：n个圆最多可以把平面划分成多少个区域通项公式：B(n)=n(n-1)+2证明如下：1) n个圆最多可以把一个圆划分成多少段.通项公式记为A(n)2) n个圆最多可以把一个平面划分多成个区域.通项公式记为B(n)第一个问题,因为两个圆相交最多2个交点,所以n个圆最多在指定的圆上留下2n个交点,把这个圆分成2n段,即A(n)=2n第二个问题,假设平面上已有n个圆,它们把平面划分成最多的区域,那么第n+1个圆下去的时候,为了保证获得最多的区域,要求这个圆和之前的n个圆都相交,并且新产生的交点不和之前的交点重合.根据第一个问题,之前的n个圆把第n+1个圆划分成A(n)段,每一段都将原来的区域一分为二,于是B(n+1)=B(n)+A(n),将B(1)=2,A(n)=2n带入很容易求得B(n)=n(n-1)+2提示：利用以下求和公式：1+2+...+n=n(n+1)/2

 

最后，再注意两点，一时数值较大，最终结果可能会超int，所以直接存long long避免数据超出；二是对于0不满足情况，需要单独考虑，其他就没什么了

 

/* Author：Owen_Q */ #include <bits/stdc++.h> using namespace std; int main() { long long n,sum=0; while(scanf("%lld",&n)!=EOF) { if(n==0) { sum = 1; } else { sum = n * (n - 1) + 2; } printf("%lld\n",sum); } return 0; }

 

 

Problem D Lnever and Pikachu

 

 

思路：这是一道典型的排列组合问题，从n个数中任选m个排成一个环，即A（m；n）/m=n*(n-1)*(n-2)*……*(n-m+1)/m;

 

由于m大小可以接受，所以可以直接用循环完成，但需要随时取模防溢出，而最后一个除法就会很尴尬。于是考虑将除数分解，按最大公约数分配到被除数上，先约分后进行乘法，完美解决，最后，记得防溢出用long long

 

/* Author：Owen_Q */ #include <bits/stdc++.h> using namespace std; long long gcd(long long a,long long b) { if(a<0) { a = a * (-1); } if(b<0) { b = b * (-1); } while(b) { long long t = a % b; a = b; b = t; } return a; } int main() { long long m,n,p; while(scanf("%lld%lld%lld",&n,&m,&p)!=EOF) { long long sum = 1; long long m0 = m; for(long long i=n;i>n-m;i--) { long long i0 = i; long long temp = gcd(i0,m0); if(temp!=1) { m0 /= temp; i0 /= temp; } sum = (sum * i0) % p; } //sum = sum * (p + 1) / m0 % p; printf("%lld\n",sum); } return 0; }

 

Problem E Hanoi Tower - SetariaViridis

 

 

思路：经典汉诺塔问题，双倍塔结尾乘二即可。

 

这本是一道递归问题，但由于输入数据给的是10的18次方，递归直接TLE。

 

于是考虑到推算公式，根据递归过程不难推出a【n+1】 = a【n】^2 + 2， a【1】 = 2 ， 取对数可得 a【n】= 2^（n+1） - 2; 

于是快速幂一波成功搞定，就是注意一个小小的坑点，由于快速幂内部取模，先取模后做减法运算可能会做出负数，最后处理一下这种情况就好了

 

其实如果想到打表，惊奇的发现每21个数一循环，瞬间豁然开朗，也可以成功ac

 

/* Author：Owen_Q */ #include <bits/stdc++.h> using namespace std; const int mode = 2097151; /* long long quickmi(long long a) { if(a==0) { return 1; } else if(a==1) { return 2; } else { long long temp; if(a%2==0) { temp = quickmi(a/2); return ( temp * temp ) % mode; } else { temp = quickmi(a-1); return (temp * 2) % mode; } } } */ int hnt[30]; int main() { long long n; hnt[1] = 2; hnt[2] = 6; for(int i=3;i<=24;i++) { hnt[i] = (2*hnt[i-1] + 2) % mode; //cout << hnt[i] << endl; } while(scanf("%lld",&n)!=EOF) { int id = n % 21; printf("%d\n",hnt[id]); } return 0; }

总结：

 

相对来说，这次比赛的难度还是可以的，数学题居多，主要考验思维和细节，A、B两题水题，C题纯数学计算，D题排列组合考虑大数除法最大公约数分解问题，E题从递归到推公式最后打表，一步步深入，关键还是比赛过程中的心态，稳定内心才能获得最终胜利，没到最后时刻，一切皆有可能！