2015 NEERC 回顾
校队欢乐赛其三。现在还是觉得欢乐赛的氛围还是属实比较欢乐的，但是很快就要随着三月的结束而结束了。接下来就是正式结成队伍训练了。
按照惯例，先码官方网站：https://neerc.ifmo.ru/archive/2015.html
可以下载到问题集、测试数据和标程，但是不知道是什么原因，没有能找到题解的PPT…… 最后在谷歌上找到的题解PPT，链接在下面：
按照LinkedIn账号登陆就可以下载，也可以在线观看。等博客图书馆功能施工完成后也会提供站内链接
补题地址：http://codeforces.com/gym/100851
在开始之前应当特别注意：本次比赛中的绝大多数题目的输入输出都不是标准输出/输入文件，需要重定向输入流到特定文件。C++选手需要使用freopen("fileName","r",stdin)和freopen("fileName","w",stdout)；Java选手需要使用System.setIn(new BufferedInputStream(new FileInputStream("fileName")))和System.setOut(new PrintStream(new FileOutputStream("fileName")))；Python选手需要使用sys.stdin=open("fileName","r")和sys.stdout=open("fileName","w")。
根据官方提供的提交数据，可以对本次题目做出以下的难度划分：
- 简单题：E、A、G、F —— 通过数量均为100+
- 中档题：L、J、K ——通过数量在24~60之间
- 困难题：C、B、D、H、I ——通过数量不超过20，甚至还有0
欢乐赛过程中，所有队伍一共做了A、B、E、F、G、J、K、L八道题，最高通过七道题。
废话不多说，开始补题了：
Problem A. Adjustment Office
给一个N*N的矩阵A，A[i,j] = i+j；一共Q次操作，操作有两种类型：R r 取出第r行还未被取的所有数，并输出和；C c取出第c列还未被取出的所有数并输出和；要求输出每次操作之后需要输出的和。n的范围是1e6，q的范围是1e5.
分析
Problem B. Binary vs Decimal
首先，我们先定义专有名词bindecimal数字：
一个数字是bindecimal，当且仅当它的十进制表示是它的二进制表示的后缀。
输入一个n，要求你求出第n个bindecimal的十进制表示。n的规模是10000.
Problem C. Cactus Jubilee
首先先定义仙人掌树：仙人掌树是一般树的一些拓展——允许在树上出现一些环，但是要求每条边最多只能在一个环中。该无向图中不会出现重边和自环；现在给定一个仙人掌树，允许移动一条边（不可以放在原处），求移动之后还是仙人掌树的方案数。
输入n和m——顶点数和不同的路径数；接下来的m行每行包含一个路径：第一个整数k表示该行数字数量；保证输入的是仙人掌，并且每条边只遍历了一次。n和m的数据规模是5e4.
Problem D. Distance on Triangulation
给一个n个顶点的凸多边形，和对它的一种三角剖分（n-3条对角线）；接下来进行q次查询：每次查询有两个顶点索引组成，要求查找两个顶点间在多边形的边和给定的对角线上移动的最短距离——每个边和对角线的长度记为1.
输入顶点数量 n，接下来 n-3 行包含所有对角线；输入查询数 q，接下来 q 行包含了查询的两个定点序号。
Problem E. Easy Problemset
一共有n个考官，每个人有pi个难度介于049的简单问题和无限个复杂问题；每次从1n顺序选当前考官的问题，如果这个问题的难度≥之前所有问题难度系数和，则将这个问题加入问题集；否则，舍弃这个问题。
比赛一共需要k个问题。当一个考官拿不出简单的问题时，它会拿出难度系数为50的困难问题。求最终比赛的问题集的难度总和是多少。
Problem F. Froggy Ford
有一条宽度为w的河流，河的两岸位于 x = 0 和 x = w 两条直线上；在 x ∈ (0,w) 的河流中有 n 块石头，每块石头的坐标是 (xi,yi)；小青蛙现在想要过河，但是它只能从石头上跳着走；现在你可以在河流中任意一处放置一块石头来帮助小青蛙，使得它在过河的最短路中单次跳跃的最大距离尽可能最小化。
题目给出w和n，以及石头的坐标，求为了达成目的，新石头应当放置的坐标。
Problem G. Generators
线性同余生成器：可以由 x₀ a b c 四个整数定义，可以根据递归定义 x' = (ax + b) mod c 产生无穷序列。
一共有n个序列，每个序列包含 x a b c 四个值，描述了一个LCG；求从每一个LCG生成的序列中取出一个数，求和之后不是k的倍数的最大值。如果求出，输出最大值和一种具体选取方案，否则输出-1。n k 给出，n规模1e4，k规模1e9.
Problem H. Hypercube
Problem I. Iceberg Orders
Problem J. Jump
我们基于游戏 OneMax （猜字串中猜中的位数）定义游戏 Jump ：
Jump游戏的交互方法：
- 你知道一个整数n，有一个长度为n的01字符串S，你不知道它的具体内容。
- 你可以猜一个01字符串并且发起询问，根据你给出的字符串Q：
- 当Q和S完全相同时，系统返回 n 并退出
- 当Q和S恰好有一半的位置相同时，系统返回 n/2 并等待下次询问
- 其他情况时，系统返回 0 并等待下次询问
- 您被允许最多发起 n+500 次询问，要求在这些询问次数之内使得 Q=S
系统退出后尝试输出，或者超过指定的询问次数将会导致WA；如果询问包含了非法字符或长度≠n，会导致PE和系统退出；完成要求会AC，并且在超过时间限制的情况下会TLE。
给一个长度 n，按照Jump游戏规则进行猜测；要求在 n+500 次猜测之内猜出字符串 S。
Problem K. King’s Inspection
给定一个有n个节点和m条边的有向图，问是否存在一条路从1号节点出发，访问每个其他节点一次后回到1号节点（哈密顿环）；如果存在，输出以1作为首尾的哈密顿环；否则输出指定字符串。
Problem L. Landscape Improved
给定一个宽度为N的网格，第i列上有高度为hi的方块；现在给w个方块，要求使得加上这些方块后，得到的网格的最高列的高度尽可能高；放置方块需要放置的位置的下方、左下方、右下方都有方块——也就是说最左和最右两列不能放置方块。
后记
