比赛地址：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 == && g == ) printf( "NO\n" ) ;
else
if ( r - g > || g - r > ) printf( "NO\n" ) ;
else printf( "YES\n" ) ;
return ;
}
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 % == ) ans = ( * N + P + Q + ) / ;
else{
int d = P + Q ;
if ( P == ^ Q == ){
d-- ;
ans = ( * N + + ) / ;
ans += ( d + ) / ;
}
else ans = ( * N + P + Q + ) / ;
}
printf( "%d\n" , ans ) ;
return ;
}
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 * ;
int ans = temp / ;
int mod = temp % ;
if ( mod >= ) ans++ ;
return ans ;
}
int main(){
int N , K ;
scanf( "%d%d" , &N , &K ) ;
int ans = ;
int res = ;
int i ;
for( i = ; i <= N ; i++ ){
res += K ;
if ( res % > ){
ans += calc( res ) ;
res = ;
}
}
ans += calc( res ) ;
printf( "%d\n" , ans ) ;
return ;
}
D题 FIFA Online3
题意：
模拟题，给你11名球员的基础能力值，每名球员可能有5种能力加成，问你每名球员的综合能力值是多少。
分析：
模拟题没有什么特别的套路，关键就是要仔细读题，注意细节。
因为每种加成相互独立，所以你可以按照顺序一种一种进行加成。
注意队套加成里俱乐部加成和国家加成不能叠加的问题，就把两种加成分别算出来，再取一个大的作为他的加成。
特别注意，0卡的球员没有队套加成，但是他可以作为同一俱乐部或国家队队员给其他队员贡献队套加成。
这道题的读入有技巧，具体请看标程。
另外还有一个小坑，那就是俱乐部名称和国家队名称可能相同。
标程：
#include<stdio.h>
#include<string.h>
char name[][] , team[][] , nat[][] ;
int val[] , jing[] , qiang[] ;
int two , three , five , eight ;
int q[] = { , , , , , , , , , , } ;
int main(){
int x , y , z ;
scanf( "%d-%d-%d" , &x , &y , &z ) ;
int i ;
two = three = five = eight = ;
for( i = ; i <= ; i++ ){
scanf( "%s %d Lv.%d %d %s %s" , name[i] , &val[i] , &jing[i] , &qiang[i] , team[i] , nat[i] ) ;
if ( qiang[i] >= ) two++ ;
if ( qiang[i] >= ) three++ ;
if ( qiang[i] >= ) five++ ;
if ( qiang[i] >= ) eight++ ;
}
int a , b , c , d ;
scanf( "%d%d%d%d" , &a , &b , &c , &d ) ;
for( i = ; i <= ; i++ ){
val[i] += jing[i] - ;
val[i] += q[qiang[i]] ;
if ( qiang[i] >= && two >= ) val[i]++ ;
if ( qiang[i] >= && three >= ) val[i]++ ;
if ( qiang[i] >= && five >= ) val[i]++ ;
if ( qiang[i] >= && eight >= ) val[i]++ ;
int j ;
int t , n ;
t = n = ;
for( j = ; j <= ; j++ ){
if ( strcmp( team[i] , team[j] ) == ) t++ ;
if ( strcmp( nat[i] , nat[j] ) == ) n++ ;
}
t = t >= n ? t : n ;
if ( t >= && qiang[i] ) val[i] += ;
if ( t >= && qiang[i] ) val[i]++ ;
if ( i == ) val[i] += a ;
if ( i >= && i <= + x - ) val[i] += b ;
if ( i >= + x && i <= + x + y - ) val[i] += c ;
if ( i >= + x + y ) val[i] += d ;
printf( "%s %d\n" , name[i] , val[i] ) ;
}
return ;
}
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 <= ) return false ;
int i ;
for( i = ; i <= sqrt( N ) ; i++ )
if( N % i == ) return false ;
return true ;
}
int main(){
int N ;
scanf( "%d" , &N ) ;
if ( N % == ){
printf( "2 " ) ;
N -= ;
}
else{
printf( "3 " ) ;
N -= ;
}
int i ;
for( i = ; ; i++ )
if ( prime( i ) && prime( N - i ) ){
printf( "%d %d\n" , i , N - i ) ;
return ;
}
}