NOIP普及组模拟赛I

蒟蒻第一次举办比赛，如有不足之处请多多谅解。题目难度大致相当于noip普及组，可能会略难于noip普及组。欢迎神犇前来AK！ 题意问题请私信我也就是Created_equal1。由于某些原因，我只能到九点以后才能集中回答，给您带来的不便敬请谅解！ 邀请码：615f

====================我是华丽的分割线==================== T1 全选奇数即可。因为奇数+奇数=偶数，所以当x和y属于B时x+y必定不属于B。 标程核心部分仅两行：输入n、输出n。

T2 从前往后扫一遍即可。先设一个计数器变量z。遇到字母z则变量z增加1，遇到字母y则答案加上z*(z-1)/2。

T3 算法1： 首先考虑最暴力的做法，枚举每个物品是选还是不选。得到一个物品的集合后，枚举其全排列。在所有方案中找到最大值。时间复杂度O(2^nn!)，可以通过20%的数据。 算法2： 考虑对题目进行一个等价的变换：即选择某个物品后，选择该物品前所有选择的物品的收益减少Ri。 然后我们可以贪心地对Ri从大到小排个序，然后搜索的时候只需要枚举每个物品是选还是不选，无需枚举全排列了。时间复杂度是O(2^n)，可以通过50%的数据。 算法3： 受算法2的启发，我们可以设计一个动态规划算法。首先仍然是要按照Ri从大到小排个序。然后设F[i][j]表示前i个物品中选j个可以获得的收益最大值。 状态转移方程：F[i][j]=max{F[i-1][j],F[i-1][j-1]+W[i]-R[i](j-1)} 边界条件：F[1][1]=W[1] 最后的答案=max{F[n][i]} 算法2和算法3的贪心的正确性不难证明。

T4 首先添加一个超级源，然后从超级源开始跑一遍SPFA求最长路并且判正权环即可。 实际上这题数据特别水，暴力地从每个点出发都跑一遍SPFA也可以通过所有测试点。