第 31 届国际信息学奥林匹克竞赛（IOI 2019）将于 2019 年 8 月 4 日 - 11 日在阿塞拜疆举行。由中国计算机学会（CCF）主办的国际信息学奥林匹克中国队选拔（CTS 2019）于 5 月 12 日 - 16 日在首都师范大学附属中学成功举行。经过为期五天的层层选拔，IOI 2019 中国国家队正式产生：     本次中国代表队领队是 NOI 科学***会***、清华大学王宏博士，副领队是 NOI 科学***会***副***、北京航空航天大学赵启阳博士。NOI 科学***会顾问、北京航空航天大学尹宝林教授和 NOI 科学***会***、清华大学韩文弢博士...

A 坐飞机   按第i航班降落时间和第i+1航班起飞时间的差值排序，贪心即可。    B 饱和式救援   对于同一个发电机救援成功的概率= 1 –不成功的概率   然后考虑动态规划DP i j代表第i个发动机，已经救援j个发动机的概率，递推即可.    C 晾衣服        排序之后贪心，或者直接二分答案进行check都可以。    D 温暖的签到题   区间修改和查询，考虑线段树维护。   将l~r改为1~r-l+1，发现修改后的值递增1，而被修改的元素下标也递增1。那么就可以在线段树中不用真的修改成1~r-l+1，而是全部修改成l-1，然后区间查询的时候用元素下标之和（等差数列或者前缀...

1.深度学习   最优的B显然等于n   2.异或求和      3.异或计数   考虑比较两个数的大小，肯定是在二进制下从高往低，找到第一个不同的位然后比较   枚举i表示b中所有数，二进制下高于i的那些二进制位的都与k对应位的二进制位相同   那么k的第i位肯定为1   b里一些数的第i位为1，且至少有一个数第i位为0   首先第i位为1的数必须有偶数个，这样才能满足第i位异或值为0   之后就是0...i-1的异或值要求为0，假设bx满足第i位为0，那么bx的0...i-1位可以随便选都不会违背bx小于等于k的条件      4.最小生成树   考虑作为一个生成树，每个点肯定往其他点连了...

1.Birthday    思路：考虑费用流时把每个 part 拆成 n 个点，选择第 i 个点的代表为放置 i 块蛋糕和(i - 1)块蛋糕的时间差，这个时间差是递增的，因此在费用流的过程中必定会从小到***择。   具体建图：左边 n 个点代表 n 个蛋糕，右边 m * n 个点代表 m 个 part,每个 part拆成 n 个点。源点向每个左边的点连一条流量 1 费用 0 的边，每个右边的点向汇点连一条流量 1 费用 0 的编。   每个蛋糕向可以放的两个 part 的所有点连边，连向第 i 个点的费用为 i^2 - (i - 1)^2，流量为 1。这样求最小费用流既为答案。   2.B...

1.璀璨光华    首先固定一号点标 0，那么与一号点相邻的标 2^i，对于一个标号x，如果已经确定了 x-2^a,x-2^b，那么这个点可以被唯一确定。   接下来就相当与这些位可以随便调换，每个位关于这 2^n 个数字是个 01序列，然后排个序即可。   2.电音之王   黑科技 wiki Montgomery modular multiplication/ 现在在 32 位机上跑不过暴力，所以用 long double 试除就能过。   3.萌新拆塔   状压 dp+简单计算。注意有模仿怪所以不要无脑吃宝石即可。    4.奇迹暖婊   对偶费用流，努力卡了很久之比 LP 快了一点点，只...

1.矩阵乘法   注意到，矩阵 B 是一个二进制矩阵。考虑红色的部分，它将和 B 的若干列向量点乘。   若我们将红色部分的长度切块，例如分成 8 个 bit 一组，B 的列向量就只有 256 种情况。   将这些值预处理，就可以用取值代替乘法操作了。   2.字符串的幂   枚举确定了 a 之后，依次删去 S 前缀的 a 和后缀的 a此时有两种情况：   剩下的串与 a 或空串的编辑距离为2   剩下的串最前面 |a|± 1 的串，后面 |a|± 1 的串与 a 的编辑距离为 1   暴力枚举上面的所有情况，用哈希判断字符串相等即可。   3.生命游戏   考虑将生命游戏的坐标转45度，变成...

1.Knight   不妨假设 x>=y>=0。   当 x<=2y 时，定义每一步的冗余值 wi=3-dx-dy，那么∑wi=∑(2-dx)=3* 步数-x-y，显然我们只需要最小化冗余值。我们先只用(+2,+1)(若 x 为奇数则加一步(+1,+2))走到(x,y’)，然后通过将(+2,+1)替换为 2 个(+1,+2)使得0<=y-y’<3。   若 y-y’=0，则冗余值为 0，显然最小。   若 y-y’=1，则将(+1,+2)替换为(+2,+1)和(-1,+2)或将 2 个(+2,+1)替换为(+1,+2),(+1,+2),(+2,-1)，冗余值为 2...

A. Chino with Geometry签到题+喜闻乐见的乱搞题。。。因为都是整点，所以答案都是整数。。。算法一联立直线和圆的方程，得到D,E的坐标，然后根据距离公式强算。窝也没有写过，布吉岛会不会爆精度。不过比较难写就对了。算法二过圆心作AH⊥BC，则答案就是(√(AB^2-AH^2 )-√(r^2-AH^2 ))×(√(AB^2-AH^2 )+√(r^2-AH^2 )).似乎精度爆炸……算法三化简上述式子可以得到答案等于AB^2-r^2，于是我们得到了：割线长的乘积等于切线长的平方。看似很有道理，你也恍然大悟，然而这是初中平面几何里我们都学过的“切割线定理”。 B. Chino wit...

A 骆驼拼写法  嘟噜噜，这个题目很简单啊 用getchar()一个一个的读入字符 第一个单词都小写后面的单词都首字母大写  空格过滤掉输出答案就可以啦      B 流浪地球    这个题目要看图片   图片里一个v速度的小星体绕一个u速度的星体速度变成了2u+v   题目中 一个超级大球向右运动 有n个小球向左运动 其中每个小球的质量都远小于其左边的球   问的是 需要进行图片中的加速多少次  会产生一个达到光速百分之一的小星体   答案就是 进行图片里那个式子的过程  记录一下加速了多少次就可以啦      C Retina    很简单的模拟题   主要注意好最后 山的一横 后面没有空...

大家心心念的手办揭晓啦~   活动详情可见：https://ac.nowcoder.com/discuss/153063 and https://ac.nowcoder.com/discuss/153121   将从前20名牛客战神，以及，练习区刷题人数超过80的选手中，   随机抽取2人赠送手办一个~~~      欢迎大家前来投票挑选你最心水的手办（关乎下次活动的奖品哦~）

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 游戏   其实只需要看左上角就行了,因为题目描述写的很清楚,三个人的操作都是为了BLUESKY007能赢,所以游戏一定会结束,那么当横纵坐标最大的非B颜色方格变为B颜色时,可操作的方格范围显然是趋向收敛的,又因为操作规则的要求,左上角的方格在每次操作中都会按规则进行变换,当可操作范围收敛到左上角且左上角变为B颜色时,游戏结束,所以无论中间的操作是怎样进行的,最终左上角的方格一定会变为B颜色,而且进行操作的人数和操作变换长度相同,所以我们只需要判断左上角方格的颜色即可。      T2 水果蛋糕   不妨设n为长,m...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）   T1 K小生成树（kmst）   1.1 算法1   对于每次询问，进行一次暴力搜索，枚举所有情况，然后检验是否为生成树及权值和是否符合要求。   时间复杂度，期望得分分。   1.2 算法2   在算法1 的基础上，加入以下优化：   优化一：显然，对于任意一个n个节点的图，生成树的变数总是n-1条，若当前点数没有到n个但边数超过了n-1条。则剪枝。   优化二：在搜索的过程中，对该图的每一个生成树，使用前缀和数组来维护答案，将查询的复杂度降为。    1.3 算法3   对于val（u，v）两两相等，L=R的10%的...

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题） T1 又是一年推gal季    T2 可爱 星空   T3 数学题     其他疑问可加以下交流群（加入一个即可啦~） 牛客多校算法训练营1：453799454 牛客全国算法训练营2：330766563 牛客多校算法训练营3：934889305

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）T1 地斗主  T2 1408  T3 爆瓶子  其他疑问可加以下交流群（加入一个即可啦~）牛客多校算法训练营1：453799454牛客全国算法训练营2：330766563牛客多校算法训练营3：934889305