NWERC 2018
赛后总结
BUPT校赛训练，clone了NWERC 2018。上大学以来首次没有队友的比赛（队友心态爆炸暂时弃疗了），于是这次就是单开一挑三。本来就处于复健过程，雪上加霜的是ACM队友又没了，只能自己单搞了。
开场花了一点时间读题，最开始有点懵，没太搞明白题意，读了半天终于明白题目说的某几个词是啥意思，于是一发过了I。之后跟着榜去看H，发现H也是挺简单，稍微讨论一下情况就可以轻松通过。此时虽然我两道题都是一发就过，但速度上相比其他队伍都慢了太多。回过头来去看跟榜去看k，发现也不难，可以稍微推一下等价关系就好（终于意识到自己其实一直有一些很笨的代码习惯）。此时逯克婷小姐姐来找我讲scanf/printf和c语言数据类型，于是果断咕了比赛去给小姐姐讲题（doge。回来的时候已经三个多小时了。发现B是一个n多年没写的拓扑排序，于是尝试了一段时间慢慢把代码写出来，之后有一些想法，但也没啥时间，于是就弃疗了咕咕咕。没有队友真的好惨啊啊啊！
题解
I: Inflation
题意：给定n个正整数a_1,a_2,...,a_n，寻找\{ a_n \}的一种排列p_1,p_2,…,p_n，使得对于第i个数，总有p_i与i的比值0 \leq \frac{p_i}{i} \leq 1。求一种排列，使得所有\frac{p_i}{i}中的最小值最大，输出这个最小值。如果所有的排列均存在至少一个比值大于1，则输出-1。
思路：观察发现将给定数列从小到大排列是最优排列，如果在这种排列下有比值大于1，则直接输出-1。
证明这种正确性用反证法，不妨考虑交换从小到大排列的任何一对数。发现有两种情况，一种是数列不变，不用考虑；另一种是数列改变，则靠后的那个位置交换后的\frac{p_i}{i}一定会变小且一定小于较前那个位置交换前的\frac{p_i}{i}，则最小值必然变小。
#include <bits/stdc++.h>
#define eps 0.000001
using namespace std;
const int maxn = 200000 + 10;
int n;
int c[maxn];
double ans = 1.1;
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> c[i];
}
sort(c + 1, c + 1 + n);
bool explode = false;
for (int i = 1; i <= n; ++i)
{
if (c[i] > i)
{
explode = true;
break;
}
ans = min(ans, ((double)(c[i])) / ((double)(i)));
}
printf("%g", (explode ? -1 : ans));
}H: Hard Drive
题意：给定一个正整数n(1 \leq n \leq 5 \times 10^5)，求一个长度为n的二进制数串，满足以下条件：
- 给定b个位置，对应位置必须为0且保证最后一位必须为0
- 每两个相邻位的逻辑异或等于1则称之为一个“bit change”，要求“bit change”总数恰好等于正整数c
思路：既然要求某些位必须是0，那么我们可以考虑从长度为n的全零二进制串开始讨论。我们发现，每当我们将一位数从0修改为1，“bit change”就增加2，除非这个位置是第一位（最后一位不能改）。那么先判断奇偶性，若为奇数就先将第一位改成1。之后我们发现，…010…与…0110…的贡献是一样的，那么完全没有必要将连续位修改为1。因而我们遍历二进制串，若该位置之前不是1且可以修改，则将之改为1并将c减去2，直到c=0。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 10;
bitset<maxn> s, broke;
int n, c, b;
int main()
{
cin >> n >> c >> b;
for (int i = 1; i <= b; ++i)
{
int pos;
cin >> pos;
broke[pos] = 1;
}
if (c % 2)
{
s[1] = 1;
--c;
}
for (int i = n - 1; i >= 1 && c > 0; --i)
{
if (broke[i]) continue;
if (s[i + 1] == 0) s[i] = 1, c -= 2;
}
for (int i = 1; i <= n; ++i)
{
printf("%d", (s[i] == 1 ? 1 : 0));
}
}K: Kleptography
题意：对于纯小写字母字符串用0~25一一对应表示。存在一种加密算法加密字符串a_1 a_2 ... a_m。给出加密后的密文b_1 b_2 ... b_m和明文的最后n位a_{m-n+1} ... a_m，请你求出明文。
加密算法如下：
k_i=\left\{
\begin{array}{rcl}
\text{某种保密随机字符串} & & {1 \leq i \leq n}\\
a_{i-1} & & {n < i < m}\\
\end{array} \right..
\\
b_i = (a_i + k_i) \mod 26.