【题解】2019年湘潭大学程序设计竞赛
A. Who’s better?
B. Number
直接模拟即可。
C. Math Problem
证明a % 192 = 1 
D. Stone
E. Watermelon
F. Black & White
G. Truthman& Fakeman
此问题即是把N个人分为两个集合，且满足以下条件。
H. Chat
可以转化为分组背包:
直接做即可
B. Number
直接模拟即可。
C. Math Problem
证明a % 192 = 1
后面就是等差数列和
D. Stone
贪心
题目乍一看像是NIM的模板题或者DP的模板题 但其实。。。
石子数累加和-最大一堆的石子数
因为每次合并代价都是小堆石子的数量，不妨设三堆石子a<= b <= c
最优方案，必然是a合并到c,再b合并到a+c;
如果先合并a和b，那么代价必然大于a+b
如果先合并a和b，那么代价必然大于a+b
推而广之，最优方案为每次都往最大的那个堆上合并。
时间复杂度O(n)
时间复杂度O(n)
E. Watermelon
两点
写法简单一点是O(m)，复杂一点是O(n)，两种都可以过 O(m)的方法:循环维护到每个人吃西瓜时的西瓜数量的区间[L,R]
初始L=R=m
对于非肚量最大的人L每次减一(至少吃一个)，R每次减去能a[i](至多吃a[i]个)
对于肚量最大的人L和R都减去a[i]
直到某个非肚量最大的人吃西瓜的时候如果L<0,得到答案为No
或者肚量最大的人吃西瓜时R<0，那么说明可以成功,得到答案为Yes
O(n)方法类似，求出肚量最大的人之前和之后的人的肚量之和即可优化。
F. Black & White
二分+ 前缀和
首先预处理出前缀和，pre0[i]表示[1..i]这个区间有多少0； 然后二分答案，再对答案进行O(n)的验证；
只需判断区间内0或1的个数加上m是否不小于当前二分的答案便可；
时间复杂度：O(nlogn)
G. Truthman& Fakeman
此问题即是把N个人分为两个集合，且满足以下条件。
i认为j是一个Truthman，那么i和j属于一个集合(一真都真一假都假)
i认为j是一个Fakeman，那么i和j属于不同集合(你真我假你假我真)
要求出符合条件的Truthman最多的一种合理解。
dfs即可，任意找一个没有被分配身份的人开始dfs，假设他的身份为任意一 种，由此可以推出一些人的身份(或者矛盾)，因为要使Truthman最多，所以选择人数多的集合作为Truthman(1)即可。
注意预设一个人的身份可能无法推出所有人的身份(图不连通)，循环做上面 的步骤即可。
复杂度O(n+m)
H. Chat
可以转化为分组背包:
每一天可以选择造成1.2.3...m点生气度，在造成生气度的同时可以省去一些 上线时间。对于每一天m*m即可算出造成i点生气度时最多能省去多少时间。
预处理每一天，复杂度O(n*m*m)
把每一天的每一种生气度当做一个物品，那么生气度就是这个物品的空间， 省去的时间就是这个物品的价值，n个组，每个组m个物品，而背包的大小 就是可以造成生气度的最大值k
做分组背包即可求得最多能省去多少时间，用原来所需要的总时间减去最大省去的时间即是答案，背包复杂度O(n*m*k)，总复杂度O(n*m*m+n*m*k)
std
