比赛地址：http://acm.uestc.edu.cn/#/contest/show/191
A题 小羽涂色
题意：
在x轴的正半轴上，问你是否存在一段区间[L,R]其中包含r个奇数和g个偶数。
分析：
对于区间的起点与终点，我们可以分4种情况进行讨论。
1.起点为奇数，终点为奇数，这种情况下r=g+1.
2.起点为奇数，终点为偶数，这种情况下r=g.
3.起点为偶数，终点为奇数，这种情况下r=g.
4.起点为偶数，终点为偶数，这种情况下r+1=g.
综上所述，只要满足|r - g| ≤ 1 就可以符合条件。
但是，这里有一个坑点，那就是区间不能为空，所以说r=g=0的时候答案应该是“NO”.
标程：
#include<stdio.h> int main(){ int r , g ; scanf( "%d%d" , &r , &g ) ; if ( r == 0 && g == 0 ) printf( "NO " ) ; else if ( r - g > 1 || g - r > 1 ) printf( "NO " ) ; else printf( "YES " ) ; return 0 ; }
B题 座位分配
题意：
有N对异性情侣，P名单身男性，Q名单身女性需要到食堂就餐，你需要给他们安排四人桌。其中，情侣有一个限制条件，就是必须在同一张桌上就餐，且自己对面和旁边的座位不能出现其他异性（斜对角的位置没有限制），问最少需要多少张四人桌才能满足所有人的就餐要求。
分析：
假设没有限制条件，一共有M人需要就餐，问需要多少张四人桌，这个问题就很简单，答案就是M/4+(M % 4 ? 1 : 0 )，也可以写成(M + 3) /4.
但是情侣有特别的限制条件，我们就得想办法把这种条件转换或者消除。
首先我们来考虑一对情侣该怎么坐，一共有三种做法：面对面坐，同时坐桌子的一边，坐桌子的两个角。
首先，如果情侣坐桌子两角的话，剩下两个位置无论是安排男性还是女性都无法符合题意，只能空着，很浪费空间。
而情侣面对面坐或者坐桌子的一边实际上是等价的，把桌子旋转90度就能从一种情况转移到另一种情况，且不会改变安排方式的合法性。
所以我们就把这两种情况统一看成面对面坐，而面对面坐的话，男生旁边可以坐男生，女生旁边可以坐女生，空间还有利用的余地。
所以，给一对情侣安排座位肯定面对面坐最优。
现在考虑多对情侣安排位置的问题。显然，你可以把两对情侣安排在同一桌，男生坐一边，女生坐一边，这样的话他们两对情侣占满了一张桌子，这样安排肯定最优。
所以说如果有偶数对情侣，他们恰好能占据N/2张桌子，剩下的人再按照无限制条件的方式计算。
如果有奇数对情侣，先把N-1对情侣安排占据(N-1)/2张桌子，然后剩下那对情侣面对面坐，旁边还有两个空位，
如果有单身男性还可以安排一位单身男性坐情侣那桌，如果有单身女性还可以安排一位单身女性坐情侣那桌，剩下的人再按照无限制条件的方式计算。
总的思路很简单，优先给情侣安排好位置，再考虑单身狗的位置，这个问题就迎刃而解了~
标程：
#include<stdio.h> int main(){ int N , P , Q , ans ; scanf( "%d%d%d" , &N , &P , &Q ) ; if ( N % 2 == 0 ) ans = ( 2 * N + P + Q + 3 ) / 4 ; else{ int d = P + Q ; if ( P == 0 ^ Q == 0){ d-- ; ans = ( 2 * N + 1 + 3 ) / 4 ; ans += ( d + 3 ) / 4 ; } else ans = ( 2 * N + P + Q + 3 ) / 4 ; } printf( "%d " , ans ) ; return 0 ; }
C题 马里奥饼店
题意：
你需要到马里奥饼店买N个价值为K元的面包。9折卡可以使你的消费优惠10%，但是有一个四舍五入的原则，精确到元。
你可以多次购买你所需要的N个面包，使总花费最小，问这个最小的总花费是多少？
分析：
首先，因为有四舍五入的原则，我们就应该尽可能地使总价格打完9折后能够舍，不要入；也就是说打完折后小数点是0.1,0.2,0.3,0.4都是我们所希望的。
所以，原来的总价格个位数是6,7,8,9是比较好的。因此，我们可以采用贪心的思想，不断积累面包，当面包的价钱个位数6,7,8,9结尾时我们就把它买下，
便可以实现舍的目标，也就可以转换为第一次使得面包价钱个位数为6,7,8,9结尾时的面包数量为m，每买m个面包就能多便宜1块钱。因此就证明了贪心思想的正确性。
注意在计算打9折算四舍五入价格时建议采用整数运算，可以先乘9再除10，对余数判断大于等于5就加1，用浮点型运算可能会有精度问题。
标程：
#include<stdio.h> int calc( int x ){ int temp = x * 9 ; int ans = temp / 10 ; int mod = temp % 10 ; if ( mod >= 5 ) ans++ ; return ans ; } int main(){ int N , K ; scanf( "%d%d" , &N , &K ) ; int ans = 0 ; int res = 0 ; int i ; for( i = 1 ; i <= N ; i++ ){ res += K ; if ( res % 10 > 5 ){ ans += calc( res ) ; res = 0 ; } } ans += calc( res ) ; printf( "%d " , ans ) ; return 0 ; }
D题 FIFA Online3
题意：
模拟题，给你11名球员的基础能力值，每名球员可能有5种能力加成，问你每名球员的综合能力值是多少。
分析：
模拟题没有什么特别的套路，关键就是要仔细读题，注意细节。
因为每种加成相互独立，所以你可以按照顺序一种一种进行加成。
注意队套加成里俱乐部加成和国家加成不能叠加的问题，就把两种加成分别算出来，再取一个大的作为他的加成。
特别注意，0卡的球员没有队套加成，但是他可以作为同一俱乐部或国家队队员给其他队员贡献队套加成。
这道题的读入有技巧，具体请看标程。
另外还有一个小坑，那就是俱乐部名称和国家队名称可能相同。
标程：
#include<stdio.h> #include<string.h> char name[15][25] , team[15][25] , nat[15][25] ; int val[15] , jing[15] , qiang[15] ; int two , three , five , eight ; int q[11] = { 0 , 5 , 6 , 7 , 8 , 10 , 12 , 14 , 17 , 20 , 24 } ; int main(){ int x , y , z ; scanf( "%d-%d-%d" , &x , &y , &z ) ; int i ; two = three = five = eight = 0 ; for( i = 1 ; i <= 11 ; i++ ){ scanf( "%s %d Lv.%d %d %s %s" , name[i] , &val[i] , &jing[i] , &qiang[i] , team[i] , nat[i] ) ; if ( qiang[i] >= 2 ) two++ ; if ( qiang[i] >= 3 ) three++ ; if ( qiang[i] >= 5 ) five++ ; if ( qiang[i] >= 8 ) eight++ ; } int a , b , c , d ; scanf( "%d%d%d%d" , &a , &b , &c , &d ) ; for( i = 1 ; i <= 11 ; i++ ){ val[i] += jing[i] - 1 ; val[i] += q[qiang[i]] ; if ( qiang[i] >= 2 && two >= 6 ) val[i]++ ; if ( qiang[i] >= 3 && three >= 6 ) val[i]++ ; if ( qiang[i] >= 5 && five >= 6 ) val[i]++ ; if ( qiang[i] >= 8 && eight >= 6 ) val[i]++ ; int j ; int t , n ; t = n = 0 ; for( j = 1 ; j <= 11 ; j++ ){ if ( strcmp( team[i] , team[j] ) == 0 ) t++ ; if ( strcmp( nat[i] , nat[j] ) == 0 ) n++ ; } t = t >= n ? t : n ; if ( t >= 6 && qiang[i] ) val[i] += 2 ; if ( t >= 9 && qiang[i] ) val[i]++ ; if ( i == 1 ) val[i] += a ; if ( i >= 2 && i <= 2 + x - 1 ) val[i] += b ; if ( i >= 2 + x && i <= 2 + x + y - 1 ) val[i] += c ; if ( i >= 2 + x + y ) val[i] += d ; printf( "%s %d " , name[i] , val[i] ) ; } return 0 ; }
E题 秦队长猜想
题意：
给你一个大于等于6且不超过10^9的整数N，请你把它拆成三个质数的和。
分析：
我们知道，判一个数是否为质数的最基本方法是O(sqrt(N))的。
你可以轻而易举地相出一种算法复杂度为O((Nsqrt(N))^3)的做法，但是这道题肯定不能这么做。
我们发现一个特别奇妙的性质，那就是2和3都是质数。
如果N是偶数，你就选其中一个质数为2；如果N是奇数，你就选其中一个质数为3。这样剩下两个质数的和均为偶数了。
然后，题目就转换成了任何一个大于等于4的偶数都能写成两个质数的和。咦，这不是哥德巴赫猜想吗？
要怎么做呢，O((Nsqrt(N))^2)？似乎还是不行的哟。
其实，你可以优化到O(Nsqrt(N))，但是这样看上去复杂度还是爆炸。
但是，你要胆子大一点嘛，因为它的复杂度不是严格的O(Nsqrt(N))，而是你找到了答案就能往外跳。
经过试验发现，你可以很快的就找到答案，也就是说就算一个偶数N大到1e9，基本上都可以在2e2之内找到一个数p，使得p和N-p均为质数。
这是为什么呢?其实这可以用生日悖论来解释。
1e9内大约有5e7个质数，也就是质数的概率大约为5%，合数的概率大约为95%。
你可以从小到大枚举质数2,3,5,7...那么N-2为合数，N-3为合数，N-5为合数，N-7为合数同时成立你才会接着往下找，不然的话你就找到了一组合法的解，可以直接跳出。
因此，进行K次操作后，你依然找不到解的概率约为(0.95)^K；当K=200时，概率仅为0.004%，所以说你可以很快的找出一组解然后输出跳出就可以了。
标程：
#include<stdio.h> #include<math.h> #define bool int #define false 0 #define true 1 bool prime( int N ){ if ( N <= 1 ) return false ; int i ; for( i = 2 ; i <= sqrt( N ) ; i++ ) if( N % i == 0 ) return false ; return true ; } int main(){ int N ; scanf( "%d" , &N ) ; if ( N % 2 == 0 ){ printf( "2 " ) ; N -= 2 ; } else{ printf( "3 " ) ; N -= 3 ; } int i ; for( i = 2 ; ; i++ ) if ( prime( i ) && prime( N - i ) ){ printf( "%d %d " , i , N - i ) ; return 0 ; } }