题解

语无伦次系列

A. Domino Disaster

原题链接

给定一个 $2 \times n$ 的网格, 向其中填入多米诺骨牌, 给出其中一行, 求另一行

直接根据另一行输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>

char buf[101];

int main(){
int T, n, i;
scanf("%d", &T);
while (T--){
scanf("%d %s", &n, buf);
for (i = 0; i < n; i++){
switch(buf[i]){
case 'U': putchar('D'); break;
case 'D': putchar('U'); break;
case 'L': putchar('L'); break;
case 'R': putchar('R'); break;
}
}
putchar('\n');
}
return 0;
}

B. MEXor Mixup

原题链接

求一个满足以下条件最短序列的大小:
① 不在序列中的最小非负数为 $a$
② 序列中所有数异或的结果为 $b$

众所周知, 异或的两个性质:

  • $a \oplus b \oplus b = a$

  • 若$a \oplus b = c$, 则 $a = b\oplus c$

由①, $0 \sim a-1$ 的数在序列中必须存在, 先把它们与 $b$ 异或, 就可以得到序列中其他元素的异或值$v$

异或的结果有三种情况:

  • $v=0$

    不用再加元素了, $0 \sim a-1$ 就可以让它们的异或为$b$.

  • $v=a$

    最坏的情况, 只加一个元素的话只能加$a$, 但是加了$a$就不满足条件①了. 所以尝试加两个元素.

    设$x=$0xFFFF0000, 可以加上$x$和$v \oplus x$, 这样两个元素均不是$a$而且异或的值等于$a$.

  • 其他

    简单加上$v$即可.

可以先将$0 \sim 300000$内异或运算的值缓存到变量tab中.

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
#include <stdio.h>
#include <stdlib.h>

unsigned tab[300001];

void init(){
unsigned prev = 0, i;
for (i = 0; i <= 300000; i++){
prev = tab[i] = prev ^ i;
}
}

int main(){
unsigned T, m, n;
init();
scanf("%u", &T);
while (T--){
scanf("%u %u", &m, &n);
unsigned v = tab[m - 1] ^ n, r;
if (v == 0) r = m;
else if (v == m) r = m + 2;
else r = m + 1;
printf("%u\n", r);
}
return 0;
}

C. Carrying Conundrum

原题链接

Alice 进行加法计算时, 进位没有算到下一位, 而是下两位, 像这样
正确的加法 Alice的加法
现给出$n$, 求有序正整数对的数量, 使得数对中的两个数按照 Alice 的方法可以得出结果$n$.

我的想法是, 枚举能出现的数字, 然后递归枚举所有情况
比如已知$n=12345$, 假设$M=\overline{abcde}$, $N=\overline{vwxyz}$.
现在知道最后一位数字是5, 那么$(e,z)$可以是$(0,5),(1,4),(2,3),(3,2),(4,1),(5,0),(6,9),(7,8),(8,7),(9,6)$. 后面四种是需要进位的情况, 在代码中用adv保存进位
根据进位与否把这些有序对分为两类, 递归求解在进位与不进位的情况下各有多少种情况(对应代码18~21行), 再把它们相乘相加.
递归终止条件为数的第一位已算出, 但是还有进位标记
真正的结果还要减二, 因为0不是正整数, 而我们枚举出的结果是包含$(0,n)$和$(n,0)$的.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char num[11], adv[12];
int N;

void arr(const char *p){
int i;
N = strlen(p);
for (i = 0; i < N; i++) num[i] = p[N - i - 1] - '0';
}

unsigned proc(int d){
int i, j; unsigned total = 0;
if (d >= N) return (adv[d] == 1 || adv[d + 1] == 1) ? 0 : 1;
i = num[d] - adv[d];
adv[d + 2] = 1;
total += proc(d + 1) * (9 - i);
adv[d + 2] = 0;
total += proc(d + 1) * (i + 1);
return total;
}

unsigned calc(){
memset(adv, 0, 12);
return proc(0) - 2;
}

int main(){
unsigned T; char p[11];
scanf("%u", &T);
while (T--){
scanf("%s", p);
arr(p);
printf("%u\n", calc());
}
return 0;
}

打cf的时候, 我用的第一种方法, 当时递归出bug了, 调试用了很长时间, 因为递归的bug是真的难找.
下面是来自@wyh的方法:

因为每次进位都加到下两位, 所以每一位对于相邻的位没有任何影响, 把$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
#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

int main(){
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int a = 0, b = 0;
for(int i = 0; i < s.size(); ++ i){
if(i&1){
a = a*10 + s[i]-'0';
}
else{
b = b*10 + s[i]-'0';
}
}
printf("%lld\n", (a+1)*(b+1)-2);
}
return 0;
}

然后突然感觉我的方法好复杂, 当时时间全花在这个题了. 然后, 就没有然后了
所以, 人生苦短, 别用递归(误)

D. Expression Evaluation Error

原题链接

给出整数$s$和$n$, 把$s$拆分成$n$个正整数, 求一种拆分方式, 使这$n$个数被当做11进制相加时, 得到的数最大.

结论: 当有最大为$t$的数可以分配给某个元素时, 分配$10^{[log_{10}{t}]}$是最好的方法之一.
11进制下两数和的字面值总是不大于十进制的和, 因为11进制满11才能进位. 所以我们应该尽可能的多保留高位数.
然后总是贪心地按这种方法取值就行了.
程序流程:
假设$s=1000, n=15$.
对于第1个元素, 最多有$986$可以分配(因为后面的元素至少需要$1$), 按照前面提到的结论, 分配$100$, 剩下$886$.
对于第2个元素, 有$886+1$可以分配, 分配$100$, 剩下$787$.
对于第3个元素, 有$787+1$可以分配, 分配$100$, 剩下$688$.

对于第9个元素, 有$193+1$可以分配, 分配$100$, 剩下$94$.
对于第10个元素, 有$94+1$可以分配, 分配$10$, 剩下$85$.

对于第15个元素, 有$49+1$可以分配, 这是最后一个元素, 把$50$全部分配给它.
至此, 分配方式为$100,100,100,100,100,100,100,100,100,10,10,10,10,10,50$, 程序结束.

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
#include <stdio.h>

int buf[101];

int min10(int n){
int t = 0;
while (n >= 10){n /= 10; t++;}
if (n > 1) n = 1;
while (t--) n *= 10;
return n;
}

void calc(int t, int c, int o){
if (c == 0) return;
t++;
int r = min10(t);
buf[o] = c == 1 ? t : r;
calc(t - r, c - 1, o + 1);
}

int main(){
int T;
scanf("%d", &T);
while (T--){
int m, n, i;
scanf("%d %d", &m, &n);
calc(m - n, n, 0);
for (i = 0; i < n; i++){
printf("%d%c", buf[i], (i + 1 == n) ? '\n' : ' ');
}
}
return 0;
}

E. Non-Decreasing Dilemma

原题链接

给出长度为$n$的数组, 进行$q$次操作, 操作有3个数$t,x,y$:

  • $t=1$时, 将数组第$x$个元素设置为$y$
  • $t=2$时, 输出子数组$[x,y]$中递增子数组的个数

之前尝试了维护递增数组的方法, 最坏复杂度$qn$, 总之就是非常慢, 直接TLE.
然后参考了maxplus的方法写了个线段树的代码, 复杂度$q \log{n}$.

1
2
3
typedef struct Node{
int l, r, lt, rt; long long sum;
}Node, &NodeRef;

Node维护二叉树的每一个结点, 其中l是子数组左边界, r是右边界, lt是在子数组中从左往右看的递增序列的长度, rt是从右往左看单调递减序列的长度, sum是子数组$[l,r]$中递增子数组的个数.

对于两个非空子树a, b, 合并到父结点的方法:

  • 左边界为a.l, 右边界为b.r
  • 检查buf[a.r]是否比buf[b.l]大, 即连接两个区间时是否在连接处发生递增的中断(以下简称递增中断)
  • 如果递增中断或者a.lt本来就小于子数组长度, lt = a.lt, 否则递增在两个区间是连续的, lt = a.lt + b.lt, 对于rt同理.
  • 合并后区间递增子数组的个数, 除了原先左右子区间各自的个数外, 如果没有递增中断, 应该还包括跨越区间边界的部分, 如下图所示, 最下方的结点递增子数组的个数除包括左右两边子区间各自的个数外, 还有$[A4,A5]$和$[A4,A6]$两个.
graph TD B1(n=1) --> |A1|C1 B2(n=2) --> |A2|C1 B3(n=4) --> |A3|C2 B4(n=3) --> |A4|C2 B5(n=8) --> |A5|C3 B6(n=9) --> |A6|C3 B7(n=5) --> |A7|C4 B8(n=3) --> |A8|C4 C1(s=1+1+1*1) --> |B1|D1 C2(s=1+1) --> |B2|D1 C3(s=1+1+1*1) --> |B3|D2 C4(s=1+1) --> |B4|D2 D1(s=3+2+2*1) --> |C1|E D2(s=3+2) --> |C2|E E(s=7+5+1*2)

初始化和t = 1时, 更新叶子结点和对应父节点即可.

t = 2时, 利用线段树中已计算出的结果得到答案:

  • 对于左边界, 如果是一个右节点, 就先合并结果, 并转到父结点的下一个结点, 左节点则直接转到父结点等待合并.
  • 对于右边界, 如果是左节点, 合并结果并转到父节点的前一个结点, 右节点转到父节点等待合并.
  • 一直向树根走直到a > b, 此时l, r已连续, 合并它们并且返回合并结果.

例如要求$[A2,A8]$递增子数组的个数, 令a = A2, b = A8, lr为空:

  • a指向一个右结点(A2), 将它与l合并, 并且让它指向父节点的下一个结点B2.
  • b指向一个右节点(A8), 让它直接指向父节点B4.
  • a指向一个右节点(B2), 将它与l合并, 并且让它指向父节点的下一个结点C2.
  • b指向一个右节点(B4), 让它直接指向父节点C2.
  • a指向一个右节点(C2), 将它与l合并, 并且让它指向父节点的下一个结点C1(本来是在D1(未标出)的下一个结点, 越界跑到上一层了属于是, 不过问题不大, 因为l已经把$[A5,A8]$合并, 而且后面b在算的时候由于是右结点不合并, 不会导致重复).
  • b指向一个右结点(C2), 让它直接指向父节点D1.
  • 此时a > b, 循环结束, 此时l包含了$[A2,A8]$, r为空.
  • l, r合并, 得到在$[A2,A8]$上的结果.
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
40
41
42
43
44
45
46
47
48
49
50
51
// Referred to the code on https://codeforces.com/contest/1567/submission/128027587

#include <stdio.h>

typedef struct Node{
int l, r, lt, rt; long long sum;
}Node, &NodeRef;

const int P = 1 << 18;
Node node[P << 1] = {0};
int buf[200000];

void combine(NodeRef a, NodeRef b, NodeRef p){
if (!a.sum || !b.sum){p = a.sum ? a : b; return;}
p.l = a.l, p.r = b.r;
int cont = buf[a.r] <= buf[b.l];
p.lt = (cont && a.lt + a.l == a.r + 1) ? a.lt + b.lt : a.lt;
p.rt = (cont && b.rt + b.l == b.r + 1) ? a.rt + b.rt : b.rt;
p.sum = a.sum + b.sum + (cont ? ((long long)a.rt) * b.lt : 0);
}

long long calc(int a, int b){
Node l = {0}, r = {0}, t;
while (a <= b){
if (a & 1){combine(l, node[a], t); l = t; a++;}
if (!(b & 1)){combine(node[b], r, t); r = t; b--;}
a >>= 1, b >>= 1;
}
combine(l, r, t);
return t.sum;
}

int main(){
int T, N, i, a, b, type;
scanf("%d %d", &N, &T);
for (i = 0; i < N; i++){
scanf("%d", buf + i);
node[P + i] = {i, i, 1, 1, 1};
}
for (i = P - 1; i > 0; i--) combine(node[i << 1], node[(i << 1) + 1], node[i]);
while (T--){
scanf("%d %d %d", &type, &a, &b);
if (type == 1){
a--; buf[a] = b;
node[P + a] = {a, a, 1, 1, 1};
b = P + a;
while (b > 1){b &= -2; combine(node[b], node[b + 1], node[b >> 1]); b >>= 1;}
}else printf("%lld\n", calc(a + P - 1, b + P - 1));
}
return 0;
}