【题解】[ARC066]C/D/E Sol

主要是正好做到了这一场的F,就顺便把前三个题给做了。

嗯,感觉思维能力还是很重要的。所以不能再这么沉沦了啊。

C

有编号为 $1\sim N$ 号的 $N$ 个人,给你第 $i$ 个人的「自己的左排列的人数和自己的右排列的人数的差的绝对值」$A_i$。 请根据他们的报告,求出原来的排列方法有几种。对 $10^9+7$ 取模 。

$A_i\leq 10^9,N\leq 10^5$

或许可以根据样例猜出来,大概是一点性质吧,比如什么数值必须对称分布。那么想到这一点,再深入想一下就可以发现对于每个 $n$ 而言,他们的 $A_i$ 是固定的。所以直接生成这个标准答案序列,然后把给出的 $A$ 排一遍序,比较是否相同即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
sort(base + 1, base + n + 1) ;
if (n & 1){
yes[1] = 0 ; int cnt = 0 ;
for (int i = 2 ; i <= n ; i += 2)
yes[i] = yes[i + 1] = 2 * (++ cnt) ;
for (int i = 1 ; i <= n ; ++ i)
if (base[i] != yes[i]) return printf("0\n"), 0 ;
}
else{
int cnt = 0 ;
yes[1] = yes[2] = ++ cnt ;
for (int i = 3 ; i <= n ; i += 2)
yes[i] = yes[i + 1] = (cnt += 2) ;
for (int i = 1 ; i <= n ; ++ i)
if (base[i] != yes[i]) return printf("0\n"), 0 ;
}
return printf("%d\n", expow(2, n / 2)), 0 ;
}

D

求出整数对 $u$ 和 $v$ $(0≤u,v≤N)$ 的数目,使得存在两个非负整数 $a$ 和 $b$ 满足 $a xor b = u$ 和 $a + b= v$.

要求对答案取模 $10^9 + 7$ 。$N\leq 10^{18}$。

这个题好像有一堆十分有趣的做法…但是碍于智商并不是很想去学qaq,就放个链接吧

然后自己就对着一个神奇的做法编了一下原理。发现自己果然是马后炮选手

考虑

这个式子的意义在于,后半部分是因为异或运算是二进制下不进位的加法,前半部分则是在描述二进制下的进位。反正无论怎么样,我们可以轻松得到 $a+b\geq a~\mathrm{xor}~b$ 这样的结论。

那么如果由于 $u\leq v$,所以如果 $v$ 不越界那么 $u$ 一定不越界。于是考虑按 $v$ 进行 $dp$。具体的,考虑状态 $f_{i,j}$ 表示考虑了 $a$ 和 $b$ 二进制下的前 $i$ 位,当前 $v=a+b=j$ 的方案数。

考虑如何转移。对于 $a$ 和 $b$ 而言,第 $i$ 位有三种情况,$(0,0),(0,1),(1,1)$ 。那么也就是假设原来的和为 $j’$,和当前的和 $j$ 可能有以下关系:

1、$2\cdot (j’+1)=j$,对应着都补一位 $1$。

2、$2\cdot j’=j$,对应着都补一位 $0$ 。

3、$j’+ (j’ + 1)=j$,对应着一个补 $1$ 一个补 $0$ 。

那么也就是

发现本质上,第一维状态随着第二维递减,且都是 $\Delta(\log)$ 级别,并且每次计算,必定存在三项中有两项是相等的,所以可知最后状态数一定介于 $\Omega(2\log N)\sim O(\log N)$ 之间,可以通过本题。

然后第一维就可以直接压掉了。

不过话说回来,关于这个状态数,我还是不知道该怎么算,最终还是打表打出来的这么一个界,大概是在 $2^k-1$ 时达到下界,$2^k$ 时达到上界。想了想这么分布似乎很合理,但是还是不知道为啥。

1
2
3
4
5
6
7
8
9
LL f(int p, LL x){
if (m.count(x)) return m[x] ; if (x == 0) return m[x] = 1 ; if (x == 1) return m[x] = 2 ;
return m[x] = ((f(p - 1, x / 2) + f(p - 1, (x - 1) / 2)) % P + f(p - 1, (x - 2) / 2)) % P ;
}
int main(){
cin >> n ;
cout << f(log2(n) + 1, n) << endl ;
return 0 ;
}

E

给你一个只包含 $’+’$ 、$’-‘$、正整数的式子,你需要在式子中添加一些括号,使运算结果最大,输出最大的结果。

$n\leq 10^5,a_i\leq 10^9$ 。

大概是个观察性质题。首先可以知道,加号后面不会右括号,或者说可以被忽略掉;其次,最多有两层括号嵌套,多了没有意义,因为比如 $-((a-b)-(a-(a-b)-b))$ 这个就可以写成 $-((a-b)-(a-a)-(b-b))$ 的形式。

考虑 $dp$ 实现,状态大概设计为 $f_{i,j}$ 表示考虑了前 $i$ 个数,一共有 $j$ 个左括号没有闭合的最大结果。可以知道第二维只会是 $0,1,2$ 。思考如何转移,大概就是分类讨论左括号数量。一开始带符号地读入 $x$ ,那么可知可以先赋初值: $f_{i,0}=x,f_{i,1}=-x,f_{i,2}=x$ 这样。然后考虑转移。发现我们可以通过加一个右括号使得未匹配的左括号数量减少,那么也就是 $f_{i,0}$ 可以加上 $\max\{f_{i-1,0},f_{i-1,1},f_{i-1,2}\}$ ,$f_{i,1}$ 可以加上 $\max\{f_{i-1,1},f_{i-1,2}\}$ , $f_{i,2}$ 就只能原地转移。然后就是考虑,如果当前的 $x <0$ ,也就是读进来一个符号,那么可以考虑放一个左括号,所以需要 chkmax 一下 (f[i][2],f[i][1]),(f[i][1],f[i][0])

注意最后要输出 $\max\{f_{i-1,0},f_{i-1,1},f_{i-1,2}\}$ ,原因是根据状态的定义,我们没有考虑在第 $n$ 个数最后添上右括号的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
cin >> n ; LL x ;
f[0][1] = f[0][2] = -(1ll << 52) ;
for (int i = 1 ; i <= n ; ++ i){
x = qr() ;
f[i][0] = x ;
f[i][2] = x ;
f[i][1] = -x ;
f[i][2] += f[i - 1][2] ;
f[i][1] += max(f[i - 1][1], f[i - 1][2]) ;
f[i][0] += max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2])) ;
if (x < 0){
f[i][2] = max(f[i][2], f[i][1]) ;
f[i][1] = max(f[i][1], f[i][0]) ;
}
}
cout << max(f[n][1], max(f[n][0], f[n][2])) << endl ;
return 0 ;
}

总结

思路题还是要自己先认真想,不然真的做了效果不大。