Petrozavodsk Summer-2017. Moscow IPT Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 84/133 | 4 | 4 | 11 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by 2sozx
题意¶
对于一个列表 \(b_i\)，定义 \(LP(b_i) = \max\limits_{i = 1}^{l - 1}({\mathop{\oplus}\limits_{x = 1}^{i}b_i + \mathop{\oplus}\limits_{x = i + 1}^{l}b_i})\) ，其中 \(l\) 是列表的大小，对于给定的输入列表每个前缀输出 \(LP\) 的值。$n\le 10^6, a_i\le10^6 $
题解¶
我们定义前缀异或和为 \(s_i\)，显然前 \(l\) 的 \(LP\) 值应该为 \(\max\limits_{i = 1}^{l - 1}(s_i + s_i\oplus s_l)\)。
对每个前缀 \(s_l\) 讨论，如果 \(s_l\) 在某一位是 \(1\)，显然前面的值取什么都不影响答案，否则贪心的选择 \(1\) 一定是最优的。因此我们记录 \(dp[S]\) 表示状态 \(S\) 出现的最早位置是哪里即可，其中 \(S\) 为 \(1\) 的位置表示这一位当前选择了 \(1\)，为 \(0\) 的位置表示任意状态。
C¶
solved by 2sozx Bazoka13
题意¶
给定 \(n\) 条直线，形式为 \(y=ax+b\) ，移动一条直线的代价是 \(|a'-a|+|b'-b|\)，询问将 \(n\) 条直线移到同一点的最小代价。
题解¶
假设同一点的坐标是 \((x_1,y_1)\) ，那么有 \(y_1=a'x_1+b'\) ，代入代价计算可得 \(cost = |a'-a|+|y_1-a'x_1-b|\) ，可以发现如果转化成 \(a\) 为横坐标，\(b\) 为纵坐标的坐标系，该距离为一个点到一条直线的最小曼哈顿距离，显然是在某个绝对值为 \(0\) 的时候取得最小值，然后转换一下可以得出 \(cost=\frac{|y_1-a'x_1-b'|}{max(1,|x_1|)}\)。
分情况考虑，假设 \(|x_1|<=1\) ，我们先固定 \(x_1\) ，那么显然 \(y_1\) 就是所有 \(a_i'x_1+b_i'\) 的中位数，假设 \(n\) 是奇数，那么 \(y_1\) 的值就是分段的一次函数，假设对于某一段而言 \(y_1=kx+b\)， 代入 \(cost\) 的计算公式，可以得到 \(cost=\Sigma a_i'x-\Sigma a_j'x+op(b_i')\)，其中 \(a_i\) 是对应 \(x\) 下纵坐标大于 \(y_1\) 的直线，\(a_j\) 是小于，\(op\) 代表一些加减运算，对 \(cost\) 求导发现 \(cost\) 的变化只与 \(a'\) 有关，那么考虑相邻两段的更替，一定是一个斜率较大的直线超过了斜率较小直线，枚举更替情况不难看出更替时 \(\Sigma a_i'-\Sigma a_j'\) 一定是增大的，那么就是个凹函数，直接三分求极小值即可，\(|x|>1\) 的情况同样成立。
一点吃shit的点：\(|x|>1\) 两边都要三分，并且范围要在不爆精度的情况下足够大，同时所有直线平行的情况要特判，以为一点微小抖动都能交于一点，精度什么的可能会炸掉。
D¶
upsolved by
题意¶
题解¶
E¶
upsolved by
题意¶
题解¶
F¶
upsolved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
\(n\times m\) 的矩阵，\(q\) 个小矩阵，被覆盖奇数次的位置为 \(+\)，其余位置为 \(-\)。每次操作分为如下两步：
- 记录当前所有为 \(+\) 的位置，如果没有 \(+\) 则结束。
- 对为 \(+\) 的位置都做一次变换。
对位置 \((x, y)\) 变换的定义为将与 \((x, y)\) 同行同列的所有位置均反转一次，问矩阵变为全 \(-\) 需要进行多少次变换。
\(n, m, q\le 10^5\)
题解（暂时）¶
第一次可以通过扫描线求出一共有多少个 \(+\)、\(+\) 出现奇数次的行总数 \(r_0\)，\(+\) 出现奇数次的列总数 \(c_0\)。
首先我们可以发现某个位置一次变换后为 \(+\) 当且仅当变换前这一行 \(+\) 的个数与这一列 \(+\) 的个数的和为奇数，无论这个位置在变换前是 \(+\) 还是 \(-\)，因此我们只需要知道每次变换后新的 \(r_i\) 与 \(c_i\) 即可。
对于初始状态，我们显然可以发现交换相邻行或者相邻列对于变换后的新 \(r_i\) 与 \(c_i\) 不会有任何影响，因此我们可以将每次变换变成如下的状态。
其中 \(r_1 = n - r_0, c_1 = m - c_0\) 即为行/列出现偶数次 \(+\)，显然下一次状态中，区域2，3均会变为 \(+\)，区域1，4均会变为 \(-\)，因此我们可以继续更新新的 \(r, c\) 值，且每次也可以很容易的知道 \(+\) 的数量，当重复出现相同的 \(r,c\) 状态时表示开始循环了，可以断定为无解。
我们容易发现后续的 \(r\) 状态只能为 \(0, r_0, r_1, n\) 四种状态， \(c\) 也是同理，因此模拟这个过程即可。
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
solved by 2sozx
题意¶
给定 \(n, m, k\) ，从 \(\{1, 2,\dots,n\}\) 中不改变顺序的选取所有 \(\binom{n}{k}\) 个大小为 \(k\) 的子集， 将其按照字典序排序后理解为一个矩阵，求
\(1 \le m \le k \le n \le 10^6\)
题解¶
考虑某一行数字 \(x\) 在第 \(m\) 位。
若下一行第 \(m\) 位数字大于 \(x\)：
我们显然可以知道下面的数字一定是 \(x + 1\)（证明摸了），那此时的贡献就是 \(1\)，考虑有多少个 \(x, x+1\) 会出现。
由于 \(x\) 前面的数均小于 \(x\) ，且有 \(m - 1\) 位要填，因此显然有 \(\binom{x - 1}{m - 1}\) 次贡献，并且我们要保证 \(x + 1\) 出现在下一行，显然 \(x + 1 \sim n\) 的个数大于 \(k - m\) 即可，即让 \(x + 1\) 在第 \(m\) 位时后面保证能填满剩余的 \(k - m\) 位。
若下一行第 \(m\) 位数字小于 \(x\)：
我们显然可以知道 \(x = n - (k - m)\) （证明摸了），因此我们需要知道下一位数字可以是多少，那我们可以枚举下一行第 \(x - 1\) 位 \(y\)，显然下一行第 \(x\) 位就是第 \(y + 1\)，那显然前 \(x - 1\) 位在确定最后一位的时候共有 \(\binom{y}{m - 1} - \binom{y - 1}{m - 1}\)。
两个贡献合起来即可。
（加强版之后再写一个题解）
记录¶
0h：开局看题，没看到太签到的，10min过J的人很多，ZYF扔了个题意，CSK给了个做法，感觉对就冲了。不会别的了，K好像有人过，G、B、I也有人过，可惜都不会，去打G的表了，试图找规律，失败了。CSK给了个H的题意和一个思路，MJX听了半天题意又理解错了。把题意都说了一遍，小挂机一会。
1h：MJX去想K了，ZYF说是zzh资料里的一道题，MJX感觉有点眼熟，搁哪开始推式子了。推了一会感觉要用到一个组合数的结论，搞出来了喂给了ZYF，貌似没喂好MJX就直接写去了。ZYF去开I，CSK再看C。MJX写着写着发现样例只问了一个位置的，那就属于是太好搞了，推了个寂寞。
2h：MJX把K过了，和ZYF想了想I的分块做法，不会，MJX润去看B了，ZYF再想I。CSK推了个C的东西，给MJX和ZYF讲，MJX和ZYF属于是听懂了其中的一小部分，可能是对的，CSK就去写了。ZYF看I感觉用分块+bitset暴力维护一下就行了，复杂度也对，CSK C写差不多在调的时候ZYF去写了I过了。
3h~4h：9成9时间在调精度，MJX期间给ZYF讲了H到现在的做法，ZYF题意也理解错了开始。期间一度想到了平行时无穷远交点的精度问题，但是调高inf后小数据没有问题了，但是没测大数据。4h时候MJX本地测了一下极限数据的平行状态，精度爆炸飞，特判掉就过了。（顺便一道题能测10min也是没谁了）。