再次补打。
由于Bonus的解答没有测试方法，因此可能有一定问题。若有发现，欢迎在下方评论区提出。
Problem A. Left-handers, Right-handers and Ambidexters
题目大意
有$l$个左撇子，用$r$个右撇子，有$a$个左右手都能熟练使用的人，将他们分配到一个组，使得能熟练使用左手和熟练使用右手的人数相同，求最大人数。
题目分析
3秒钟水题。
代码
1 |
|
Bonus!
BONUS (easy): 在$O(1)$时间内解决该问题
That’s what I’ve actually done.
BONUS (easy): 读不懂
跳掉吧
Problem B. Intercepted Message
题目大意
给出两个和相同的序列$A,B$，按照序列先后顺序将$A,B$分别分成若干子序列，使得$A,B$的子序列和对应相等，试最大化分出的子序列数量。
题目分析
从左往右双指针扫一遍，遇到相等就剖分。
代码
1 |
|
Bonus!
BONUS (easy): 若第二个序列丢失了一块，你可以在任意位置插入该块，询问不变
维护三个指针，第三个指针指向最靠左的差量大于等于该块和的位置。
若第一、二个指针相等了，将第三个指针移动到第二个指针。
若第一个指针与第三个指针刚好相差该块和了，在此处插入块，移除第三个指针。
由于两个序列加入块后和相等，因此块一定能找到地方插入。
Problem C. Zebras
题目大意
定义$0,1$交替且开始结束均为$0$的串是斑马串，如$0,010,01010$是斑马串，而$1,0110,0101$均不是。
将给定的串分为若干个序列（可以不连续），使得每个序列都是一个斑马串。
若有多解，输出任意一个。若无解，输出$-1$。
题目分析
存储末尾为$0$与末尾为$1$的斑马串。
若当前位置是$0$，在末尾为$1$的斑马串中找一个接上去，或新开一个斑马串。
若当前位置是$1$，此时若没有末尾为$0$的斑马串就无解，否则选出一个末尾为$0$的斑马串接上去。
代码
1 |
|
Bonus!
BONUS (easy): 使输出方案最长的斑马串最短
每次在挑选串的时候选一个最短的斑马串即可，可以用堆什么的维护。
BONUS (hard): 使输出方案斑马串个数最少
这在搞笑，因为所有方案的斑马串个数均相同，等于$0$的个数$-1$的个数。
Problem D. A Leapfrog in the Array
题目大意
有$n$个数，每两个数间隔一个放在长度为$2n-1$的格子中。
每次移动最后一个数到其前面最靠近它的空位，最后铺满前$n$个格子。
给出$n$，询问$q$次结束序列第$x$位的数。
题目分析
先敲个暴力压压惊。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int a[105];
int main() {
int n=Get_Int();
for(int i=1; i<=n; i++)a[2*i-1]=i;
for(int i=2*n-1; i>n; i--)
for(int j=i-1; j>=1; j--)
if(!a[j]) {a[j]=a[i];break;}
for(int i=1; i<=n; i++)cout<<a[i]<<" ";
return 0;
}
然后找找规律。
| $n=1$ | $\color{red}1$ | ||||||
|---|---|---|---|---|---|---|---|
| $n=2$ | $\color{red}1$ | $2$ | |||||
| $n=3$ | $\color{red}1$ | $3$ | $\color{red}2$ | ||||
| $n=4$ | $\color{red}1$ | $3$ | $\color{red}2$ | $4$ | |||
| $n=5$ | $\color{red}1$ | $5$ | $\color{red}2$ | $4$ | $\color{red}3$ | ||
| $n=6$ | $\color{red}1$ | $4$ | $\color{red}2$ | $6$ | $\color{red}3$ | $5$ | |
| $n=7$ | $\color{red}1$ | $6$ | $\color{red}2$ | $5$ | $\color{red}3$ | $7$ | $4$ |
注意红色的项，也就是奇数项，始终不变，等于$\frac {x+1}2$。
现在考虑偶数项。
| $n=1$ | $1$ | ||||||
|---|---|---|---|---|---|---|---|
| $n=2$ | $\color{red}1$ | $\color{red}2$ | |||||
| $n=3$ | $\color{yellow}1$ | $\color{yellow}3$ | $\color{yellow}2$ | ||||
| $n=4$ | $1$ | $\color{red}3$ | $2$ | $\color{red}4$ | |||
| $n=5$ | $1$ | $5$ | $2$ | $4$ | $3$ | ||
| $n=6$ | $1$ | $\color{yellow}4$ | $2$ | $\color{yellow}6$ | $3$ | $\color{yellow}5$ | |
| $n=7$ | $e1$ | $6$ | $2$ | $5$ | $3$ | $7$ | $4$ |
$n$是偶数时，偶数项具有规律：如图，相同颜色的数对应大小关系相同。
即与$n=\frac n2$的对应项大小关系相同。
现在考虑$n$是奇数的情况：
| $n=1$ | $1$ | ||||||
|---|---|---|---|---|---|---|---|
| $n=2$ | $1$ | $2$ | |||||
| $n=3$ | $1$ | $\color{red}3$ | $\color{red}2$ | ||||
| $n=4$ | $1$ | $\color{yellow}3$ | $\color{yellow}2$ | $\color{yellow}4$ | |||
| $n=5$ | $1$ | $\color{red}5$ | $2$ | $\color{red}4$ | $3$ | ||
| $n=6$ | $1$ | $4$ | $2$ | $6$ | $3$ | $5$ | |
| $n=7$ | $e1$ | $\color{yellow}6$ | $2$ | $\color{yellow}5$ | $3$ | $\color{yellow}7$ | $4$ |
$n$是奇数时，偶数项具有规律：如图，相同颜色的数对应大小关系相同。
即与$n=\frac {n+1}2$的靠右对齐对应项大小关系相同。
至此，就可以敲代码了。
代码
1 |
|
Problem E. Data Center Maintenance
题目大意
有$n$个数据库，有$m$种数据，一天有$h$小时。
为了方便下载，每种数据$i$被存放在两个数据库（$c_{i,1},c_{i,2}$）中。
每个数据库$i$都有一个维护时间$u_i$，每天维护一小时。
要求选出一个非空子集，使得这个子集中的数据库维护时间向后推迟一小时（$u_i\leftarrow (u_i+1)\bmod h$）。同时需要满足推迟后任意一种数据在任意时刻都可以被下载，你可以认为给出的初始维护时间满足这一性质。
保证有解。若有多种方案，选择任意一个方案满足这个非空子集的元素数量最少。
题目分析
很呵呵的一道题。
开始的时候想的是2-sat，但是似乎不能最小化答案。
又因为题目有这个坑爹的限制：你可以认为给出的初始维护时间满足这一性质。说实话我读了3遍题都没有看出来这是哪句话说的。
这样我们可以重新建图：
若$(u_{c_{i,1}}+1)\bmod k=u_{c_{i,2}}$，连一条边$c_{i,1}\rightarrow c_{i,2}$。
若$(u_{c_{i,2}}+1)\bmod k=u_{c_{i,1}}$，连一条边$c_{i,1}\rightarrow c_{i,2}$。
边$x\rightarrow y$表示的意义是$x$一结束维护，$y$立刻开始维护。
在这个图中若选择一个点推迟维护，其能够到达的所有点都需要推迟维护。
这样我们对原图进行强连通分量缩点，即可得到一个DAG。
显然，在这个DAG中选择出度为$0$的连通分量是最优的，故在出度为$0$的强连通分量中选择一个最小的即可。
由于题目的坑爹限制，正确性是有保证的。
代码
1 |
|
Bonus!
BONUS (medium): 若原来不满足坑爹的限制，但不要求最小化答案，你能解决吗？
当然，这就是刚刚说的2-sat的方法。
关于2-sat怎么选择非空子集？因为保证有解，因此可以随便选一个点，让其选择不推迟，检查是否有合法方案。
若有合法方案，直接输出，否则让其选择推迟，再寻找合法方案。
BONUS ((NP?)-hard): 若原来不满足坑爹的限制，要求最小化答案，你能解决吗？
好像确实是NP问题。
Problem F. Curfew
题目大意
学校有个$n$个寝室排列成一条直线，每个寝室住有$b$个学生，查寝前学生在任意寝室玩，若第$i$个寝室有$a_i$个学生，满足$\sum_{i=1}^na_i=nb$。
现在有$2$个宿管老师来查寝，在检查寝室$i$的时候，若$a_i\neq b$，宿管老师就会记录一个寝室违规，但不会驱逐学生，若$a_i=b$时，老师也不会点名而认为该寝室没有违规。检查完毕后，宿管老师会关灯锁门。另外，学生可以藏在床底下，你可以认为床底下可以藏任意多个学生，而不会被宿管老师发现。
第一个宿管老师从$1$寝室检查到$\frac {n+1}2$寝室，第二个则从$n$寝室检查到$\frac {n+1}2+1$。
查寝的流程是这样的：
- 当宣布查寝时，第$i$个寝室有$a_i$个学生。
- 学生可以跑到另外一个寝室，但是不能移动超过$d$个寝室。然后学生可以藏在床底下。
- 宿管老师进入$1$寝室和$n$寝室，清点人数然后关灯锁门（之后没人能够进入或出去）。
- 在$2\sim n-1$号寝室的学生可以跑到另一个寝室，但是不能移动超过$d$个寝室，也不能进入一个锁着的寝室。然后学生可以藏在床底下。
- 宿管老师进入$2$寝室和$n-1$寝室，清点人数然后关灯锁门（之后没人能够进入或出去）。
- 按照以上流程重复进行。
若第一个宿管老师发现有$x_1$个寝室违规，第二个宿管老师发现有$x_2$个寝室违规时，他们会将$\max(x_1,x_2)$报给校长。故你需要找到一种最优的方案，使得$\max(x_1,x_2)$最小。
题目分析
题面超长。
我们先考虑只有一个宿管老师，他从$1$寝室检查到$n$寝室。
有一种贪心的方案：
- 从左往右考虑每一个房间。
- 若这个房间有太多学生，将多余的学生移动到后一个房间。
- 若这个房间的学生不够，但从右边的房间可以移动学生到当前房间（$\sum_{j=i}^{\min(n,i+i\times d)}a_j\ge b$），那就这么做。
- 若这个房间不可能凑够人数，将所有人移动到后一个房间。
- 如果这是最后一个房间，所有多余的学生藏在床底。
正确性是显然的，可以在$O(n)$的时间内完成。
可以发现一个性质，学生的移动路径一定不会相交。也就是说，若$i$寝室的学生移动到$a$寝室，$j$寝室的学生移动到$b$寝室，若$i\le j$，则$a\le b$，因为若不满足，可以交换两个学生。
现在重新考虑两个宿管老师的情况。
因为满足学生的移动路径一定不会相交，因此一定存在一个边界$x(0\le x\le nb)$，其中$x$个学生去前$\frac {n+1}2$个寝室，其余的去后$\frac n2$个寝室，同时也存在一个边界位置$pos(1\le pos\le n)$，其中$1\sim pos$的学生去前$\frac {n+1}2$个寝室，$pos\sim n$的学生去后$\frac n2$个寝室。
若$m$是边界，令$f(m)$是第一个宿管老师的记录值，$g(m)$是第二个宿管老师的记录值。
当$m$确定时，可以将原问题分割称两个子问题，分别使用只有一个宿管老师时的方法计算，即可求出$f(m)$与$g(m)$。
不难发现，当$f(m)$减少时，$g(m)$增加，而我们要找到$ans(m)=\max(f(m),g(m))$的最小值，令$z(m)=g(m)-f(m)$，$z(m)$不严格单增。
要寻找$z(m)$最接近$0$的位置，可以使用二分，时间复杂度$O(n\log nb)$。
代码
因为有更优的方法（见Bonus 1），故没写。
Bonus!
Bonus (medium): 在$O(n)$时间内解决该问题
由于我们说了一定存在一个边界，将原问题剖分成两个子问题。
但由于人数超过边界后不会对答案造成影响，因此没有必要为了找出边界而进行二分。
直接从左往右，从右往左来两次一个宿管老师的情况即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
LL n;
int d,b,a[100005];
int main() {
n=Get_Int();
d=Get_Int();
b=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
LL sum=0;
int cnt=0,mid=(n+1)>>1;
for(int i=1,j=1; i<=mid; i++) {
for(; j<=min(n,i+1ll*i*d); j++)sum+=a[j];
if(sum>=b)sum-=b;
else cnt++;
}
int ans=cnt;
cnt=sum=0;
for(int i=n,j=n; i>mid; i--) {
for(; j>=max(0ll,i-1ll*(n-i+1)*d); j--)sum+=a[j];
if(sum>=b)sum-=b;
else cnt++;
}
printf("%d\n",max(ans,cnt));
return 0;
}
Bonus (medium): 若学生们都是Achen（很胖）而不能藏在床下，你能解决吗？
这就意味着贪心时不能将所有学生都怼到最后一个房间了。
修改贪心方案：
- 从左往右考虑每一个房间。
- 若这个房间有太多学生，将多余的学生移动到后一个房间。
- 若这个房间的学生不够，但从右边的房间可以移动学生到当前房间（$\sum_{j=i}^{\min(n,i+i\times d)}a_j\ge b$），那就这么做。
- 若这个房间不可能凑够人数，将一定的学生$x=\max(0,(n-i)b-\sum_{j=i+1}^na_j)$移动到后一个房间，其余的藏在床底。
- 如果这是最后一个房间，所有多余的学生藏在床底。
