XIX Open Cup named after E.V. Pankratiev. Grand Prix of SPb, Division 1.¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 46/278 | 7 | 8 | 12 |
A¶
solved by Bazoka13
题意¶
根据样例和一段shit代码算出一个变量
题解¶
训练时狗运流暴力遍历
（but zzh说可以加速，正在搞）
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
solved by 2sozx JJLeo
题意¶
将二维平面划分为数个十字，问从一点到另一点最少要经过多少个十字的边界。
题解¶
斜着看图可以发现将每个十字的中心重新赋一个坐标，对应的方程为： $$ \begin{cases} i+2j=x \newline 2i+j=y \end{cases} $$ 最终答案即为两点在新坐标下的曼哈顿距离。
E¶
solved by 2sozx
题意¶
给定 \(n\) 维空间两条直线，每条直线给两个点，求两条直线的距离。 \(n\le10^5\)
题解¶
正解：二次型
考虑把两条线上的点看成 \(S_i + t_i * (T_i - S_i)\) ，这样可以表示任意两点间的距离的平方为 \(a_1 t_1^2 + a_2t_1t_2 + a_3 t_2^2 +a_4 t_1 + a_5 t_2 +a_6\) ，对 \(t_1\) 求偏导让其为零可得 \(t_2 = \frac{-2a_1t_1 - a_4}{a_2}\) ，这里就需要讨论 \(a_2\) 是否为零，为零继续讨论即可。不为零可以带入得 \(k_1t_1^2 +k_2t_1 + k_3\) ，讨论 \(k_1\) 易得最大值。
此题爆 \(\_\_int128\) 要写\(python\)
F¶
solved by 2sozx JJLeo
题意¶
给定长度为 \(n\) 的序列，找到任意一个长度为 \(k\) 的子串 \(a_i\)，使得对于任意子串 \(b_i\)，均有 \(a_i \ge b_i\)，或判断无解。
题解¶
如果 \(n=k\) 显然本身就符合条件。
对于 \(n \ne k\) 的情况，设序列的最大值为 \(A\)，那么如果 \(a_i\) 不是开头或结尾的子串，必有 \(a_i = A\)，否则将 \(a_i\) 整体移动就可以得到一个更大的序列；如果 \(a_i\) 是开头的子串，那么 \(a_i\) 必然单调递减，且 \(a_k \ge \max \limits _{i=k+1}^n a_i\)；如果 \(a_i\) 是结尾的子串，那么 \(a_i\) 必然单调递增，且 \(a_{n-k+1} \ge \max \limits _{i=1}^{n-k} a_i\)。
G¶
solved by Bazoka13
题意¶
给定一个数字 \(n\) (\(1\leq n\leq 10^6\))和数字 \(d\) (\(0\leq d\leq 9\))，求最小数不出现 \(d\) 且各位之和为 \(n\)。
题解¶
从低位开始，先尽可能塞最大的，然后根据剩下的数字决定是调整上一位大小还是拆成两位。
(细节恶心的签到题)
(但是我把情况考虑完却因为自己的 \(bullshit\) 代码给dirt做了贡献草)
H¶
upsolved by 2sozx
题意¶
\(K\) 维空间，\(n\) 个立方体，问空间中是否存在一个点没被立方体覆盖，如果有多个点输出按维度排序后字典序最小的一种。\(n\le18, k\le10\)
题解¶
由于要求了字典序，因此从低维到高维扫，每个维度可以二分他的边界，判断小于等于这个边界的立方体体积是否能铺满整个维度，计算体积时容斥一下即可。
与很久之前的一道题神似。
I¶
solved by JJLeo
题意¶
交互题，需要猜一个 \([0, 2^{31}-1]\) 的奇数 \(x\)，你可以输出 \(n\) (\(4 \le n \le 10^5\)，\(n\) 是偶数) 个 \([0, 2^{31}-1]\) 的整数，评测机随机选择 \(\dfrac{n}{2}\) 个数，乱序返回它们和 \(x\) 的乘积模 \(2^{31}\) 的结果。
题解¶
随意输出 \(n\) 个奇数，这样它们和 \(2^{31}\) 互质，存在逆元，再随机挑出约 \(25\) 个数将它们的逆元和返回的 \(\dfrac{n}{2}\) 个数分别相乘，将得到的数放入 map，出现次数最多的数就是答案。
J¶
solved by JJLeo
题意¶
交互题，有两个长度为 \(100\) 的二进制串，你可以询问至多 \(100\) 次，每次系统会等概率挑选一个串，随机选择 \(15\) 个位置将数字反转（并不修改原串），并返回这个串，你需要猜出这两个串。
题解¶
如果存在某一位出现 \(1\) 的次数与出现 \(0\) 的次数比较接近（不超过 \(20\) 次），就可以认为这一位两个串不同，按照这一位将所有串分类，如果每一组每一位出现 \(1\) 的次数与出现 \(0\) 的次数差异较大（超过 \(7\) 次），就可以认为该串这一位是出现次数多的那一个。
如果遍历所有位后均不满足条件，则认为两串相同，且每一位直接取出现次数多的那一个。
K¶
upsolved by 2sozx
题意¶
给定 \(n\times m\) 的矩阵，每个位置为数字或 \(?\) ，\(?\) 表示此位置数字未知，每个位置如果左右或上下存在则此处的值应为左右或上下值的平均数，问是否有唯一、不唯一或者不存在解。\(n,m\le10\)
题解¶
直接列方程消元即可，复杂度 \(O(n^3m^3)\)
还有一种思路，需满足的条件可以表示为每行或每列是一个等差数列，构造即可，还未实现，复杂度应为 \(O(nm)\)
L¶
upsolved by