2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 23/834 | 7 | 9 | 10 |
A¶
solved by 2sozx
题意¶
每天可以投入 \(x_i\) 元使得 \(a_{i+1}=a_i+x_i+\min(a_i+x_i,\lfloor\frac{n-a_i-x_i}{2}\rfloor),\sum x_i \le k\) 问最少几天可以使得 \(a_{las}=n(n\le10^{18})\)
题解¶
显然是只在第一天和最后一天花钱是最优解（具体是怎么个显然法有待思考。。），然后枚举第一天花多少钱然后模拟即可。
B¶
solved by Bazoka13 JJLeo
题意¶
摸了
题解¶
也摸了
C¶
solved by 2sozx
题意¶
给一棵树，节点数为 \(n(n\le10^5)\) ，现将这个树每个点放入一个 \(1000000\times20\) 的矩阵中，树种节点对应矩阵中的一个点，如果两个点在树上有一条边相连，那么在矩阵中也会连一条边，问是否能构造出一种对应方式使得矩阵中的边两两不相交。
题解¶
对于原树进行重链剖分，每个点和重儿子在同一列 \(y\) 上，非重儿子则放入 \(y+1\) 列，这样保证了不使用超过 \(\log{n}\) 列，并且在每一列中按顺序摆放即可满足条件。
D¶
solved by JJLeo
题意¶
给出一种奇怪的编码方式，让你解码。
题解¶
模拟即可。运算过程中需要开ull，提示很明显但是还是忘记开了，wa了一发。
E¶
upsolved by
题意¶
题解¶
F¶
solved by JJLeo
题意¶
按照acm比赛规则，比赛时长五个小时，四个小时后封榜，给出封榜前的完整榜单，和终榜的连续一部分榜单，问是否合法。题目保证，如果不合法，那么一定是题目给出的终榜上面的人不可能在终榜上连续。另外，排名先看过题数，再看罚时，再看过最后一题的时间，最后按队伍名称的字典序。题数\(n \le 26\)，人数\(m \le 1000\)。
题解¶
只需要验证不在给出终榜上的人要么比终榜上最好的人还好，或比终榜上最差的人还差即可。最好的话就是封榜后立刻AK，最差的话就是封榜后挂机，一个个判断即可。（因为英语太差没看到罚时相同比较过最后一题的时间而WA了好几次，还好mjx成功救场）
G¶
solved by 2sozx JJLeo
题意¶
给出一个\(n \times m(n, m \le 500)\)循环的网格（左右边界相连，上下边界相连），每个格子可以在它的四条边处形成任意整数大小的顺时针风或逆时针风，给定每条边期望的风力和方向，问是否有解。
题解¶
数据太弱只判断是否某一整行和某一整列的和为0卡过的。正解为，如果有解，那么就有无数个解，因为只要在某一个解的基础上让所有方格增加相同的整数仍然有解。依据这个性质，只需给任意一个格子赋任意值，然后一个个验证是否矛盾即可。
H¶
solved by Bazoka13
题意¶
构造一个数列，满足\(m\)个特定位置为给定值，并且满足相邻元素差的绝对值不大于\(1\)，同时数列和为\(T\)，询问是否存在
题解¶
显然数列和的最小值和最大值可以求出来，求出区间判断即可，如果中途有相邻的约束条件不能同时满足直接判否。
I¶
solved by Bazoka13
题意¶
给定\(n\)个\(k\)维向量，对于任意向量\(a\)，和\(a+vi\)连边，判断是否构成二分图
题解¶
找奇环就可以了，对每个向量模\(2\)后构造出\(k\)个\(n\)元异或方程，且异或和为\(0\)，并且\(X_1xorX_2xor\cdots xorX_n=1\)，高斯消元\(+bitset\)（猜的做法，正在证明\(ing\)）
J¶
upsolved by 2sozx
题意¶
给定一个矩形 \(w\times h(w,h\le 10^4)\) ，其中包含了 \(n(n\le 10^5)\) 个三角形，保证三角形面积和小于矩形面积，找到包含于矩形但不包含于所有三角形的一个点。
题解¶
由于三角形面积和小于矩形面积，因此我们可以二分出一个分界线，将矩形分成两部分。如果分界线上面存在一点不属于任何一个三角形，那么即为答案。如果不存在，至少有一部分使得其中的三角形面积和小于这部分矩形的面积，因此我们可以向这一部分进行二分，操作同上，最终能得到答案。
注¶
计算几何精度就nm离谱。
记录¶
10min：MJX写
14min：MJX过A，ZYF写D
18min：ZYF WA
23min：ZYF过D，CSK写H
46min：CSK WA，MJX写C
58min：MJX过C，ZYF感觉G是高斯消元，找板子去了
65min：CSK过H
78min：决定乱搞G
82min：乱搞成功
90+min：ZYF写F
154min：ZYF WA 两发
？min：讨论I，貌似是高斯消元，决定搞一发
182min：CSK WA
189min：MJX发现ZYF少读了一行题，ZYF过F
201min：CSK过I
till end：MJX搞J，CSK，ZYF搞B
after end；CSK,ZYF秒B，J题卡精度，MJX 15发AC
总结¶
CSK要保持状态，后期接近失去思考能力
ZYF要学会细心读题，大胆猜想，不用求证。
MJX要好好学习计算几何精度问题。