Contest Info

date: 2018.11.13 17:21-22:21

practice link

Solutions

A. Maximum sum with swaps

题目大意：

给出一个数列\(\{A_n\}\)，\(|A_i|\le10^9\)，\(1\le n\le10^5\).

可以进行不超过\(0\le k\le10\)次std::swap(A[i], A[j])这样的交换操作。

问最大的最大子段和是多少，并输出方案。

题解：

有效的交换一定是将选中的区间内的数与区间外的数交换。

具体是哪些对位置发生了交换并不重要，重要的是哪些位置换出去了，哪些位置换进来了。

令\(dp[i][0/1/2][a][b]\)为考虑前缀\(i\)，\(i\)在选定区间的前(0)中(1)后(2)三种情况下，换进来了\(a\)个数，换出去了\(b\)个数的最优解。

最终答案就是\(\max dp[n+1][2][a][a]\)，状态数\(O(nk^2)\)，转移\(O(1)\)。

输出方案如果完整记录每个dp状态的前驱将会mle。

但是有这样一个贪心的策略，如果我们选到的区间为\([L,R]\)且交换了\(m\)次，最优解一定是将区间内的\(m\)个最小的换出去，区间外的\(m\)个最大的换进来。

因此，我们可以使用滚动数组，在每个dp状态顺便记录一下区间端点即可。

时间复杂度\(O(n(k^2+\log{n}))\).

B. Inspection

签到题。

C. Karmon go

签到题。

E. Autocomplete

题目大意：定义两个串相似，当且仅当他们在大小写不敏感的时候相同，大小写敏感的时候相差不超过 \(K\) 个位置。给出字典和若干次询问，每次询问字典中有多少个串与询问相似。

题解：大小写不敏感建trie，然后bitset求大小写敏感的不同位数。

F. Amazing Divisibility

签到题。

G.Group tournament

题目大意：

有\(n\le100\)只队伍参加比赛，每两只不同的队伍之间有且只有一场对决。

每场对决，两队总共积3分，根据比赛情况，其中一只队伍会获得0到3分不等。

给出其中若干场对决的结果，以及每只队伍至少要得到多少分（或者是恰好？），构造一种可能的方案（保证有解）。

题解：

先计算已经得到的分数，建图，s到每个队伍连流量等于不足的分数的边，每支队伍向对应的未确定结果的对决连流量等于3的边，每个未确定结果的对决向t连流量等于3的边，这个图的最大流就是方案。

如果一场对决总积分不满3分，将剩下的随意分给一个队伍。

流量是\(O(n^2)\)，总的时间复杂度是\(O(n^4)\).

H. Multiplier

题目大意：让你用加法、减法、移位搭建一个电路，使得输入为 \(1\) 的时候输出为 \(N(N\leq 1000)\)。求最少用多少个器件，注意移位只能作用于 \(1\) 上，产生 \(2^t\)。

题解：爆搜，可以给出一个答案的上界是 \(\log N\)。假设 \(N\) 的二进制表示中有 \(x\) 个 \(1\) 和 \(y\) 个 \(0\)，如果 \(x<y\)，那么我们用移位寄存器产生这些 \(1\)，然后加起来。如果 \(x>y\)，那么我们减掉这些 \(0\) 所在的位置。

I. Guess the modulo

题目大意：交互题。给你 \(n-1\) 个在 \([0,10^{9}]\) 的数，排成一个队列。每次操作你可以问一个数，然后将它加到队尾，再把队列中的所有数的和对 \(M\in[2,10^{9}]\) 取模，告诉你是什么并将它加到队尾。之后删去队首的两个数。现在要求你在 \(1000\) 次询问之内把 \(M\) 猜出来。

题解：考虑每次随机问一个数，将不符合的模数全部删掉。第一次需要用根号分解来筛，之后直接暴力 check 即可。感受一下询问的次数不会太多。

J. Carts

题目大意：给出平面上的 \(n\) 个箱子，让他们移动到在同一行的连续一段，或者同一列的连续一段，求最小代价。移动的时候同一个位置只能有一个箱子。

题解：横纵坐标无关，考虑同一行的情况。我们对 \(y\) 排序，取中位数。然后对 \(x\) 排序，再对 \(x-i\) 排序，取中位数即可。

K. School informatics

题目大意：求 \(\min_{1\le k\le L}\lceil\frac{L}{k}\rceil\lceil k\log_{2}n\rceil\)。

题解：根号分解。

L. Give the Parabellum away

题目大意：点 \(O\) 相对于地面做匀速直线运动，点 \(P\) 相对于点 \(O\) 做圆周运动，且它相对于地面的速度大小为定值。给出点 \(O,P\) 的初始位置，点 \(O\) 的速度，点 \(P\) 相对于地面的速度大小，有 \(N\le10^{5}\) 个询问，问第 \(t\) 秒时点 \(P\) 的位置。

题解： 以 \(O\) 为参考系，列出角度和时间的微分方程，这个方程很容易求解。但是解出的积分不可积，需要使用 gauss-legendre 求积公式来进行数值积分。感觉上来说积分区间越小精确度越高，因此我们可以把被积区间划分为若干很小的区间分别计算。注意到角度以 \(2\pi\) 为周期，因此我们可以预处理 \(2\pi\) 内每个小区间的积分值。查询时只需计算最后一个区间即可。