【赛题整理】ARC099 Sol

从atcoder某天virtual的一场比赛。发现比起之前做过的场次,似乎 $\rm A$ 还是有点弱菜,$\rm B$ 还是有点奇怪,$\rm C$ 还是比较中规中矩比较不会 ,$\rm D$ 还是不很会…

问题不大.jpg

A

给定 $n,k$ ,一个 $1\sim n$ 的排列 $\{a_n\}$。每次选择一个长度为 $k$ 的区间 $[l,r]$,向下推平为 $\min_{i=l}^r\{a_i\}$ 。求最少多少次操作可以使得所有值相同。

$n\leq 100,000$

很多人写的比较麻烦。要去扫整个 $\{a_n\}$ 。然而这题 $n$ 是可以开到 $1e18$ 的。

考虑由于所有数不相同,所以最优决策一定是从最小的那个位置开始拓展。之后每次选择区间,必然是选择一个最多与之前那个区间相交为 $1$ 个元素的区间开始。所以最后答案就是 $1+\lceil\frac{n-k}{k-1}\rceil$。跟 $\{a_n\}$ 无关。

B

定义函数 $\rm S(x)$ 表示 $x$ 各个位上数字之和。求前 $k$ 个这样的 $n$:

$k$ 的范围…$\geq 1$。

首先这个是可以猜出一部分结论的,大概就是考虑如果数字里面 $9$ 比较多的话肯定会比较符合,因为这样 $\rm S$ 值就会显然更大。其次也是可以打表的。

但是这个题本质上不存在规律。所以以上两种方式可能会挂的很惨。

考虑一种可行的构造方式。首先知道,$1$ 一定是可行的。对于每个当前的 $x$ ,选择那个使得 $y>x$ 且 $\frac{y}{\rm S(y)}$ 最小的 $y$ 来替代当前的 $x$ 。不难理解这样做是可行的。

那大概考虑如何去证明第一个性质,或者稍微形式化一点:

假设 $y$ 是 $>x$ 且 $\frac{y}{\rm S(y)}$ 最小的那个 $y$,且假设从高位到低位,$x$ 和 $y$ 第一次出现不同的地方是从低到高的 第 $p$ 位,那么会有 $y$ 的从低到高 $1\sim p$ 位均为 $9$ 。

证明时考虑如下:

1、对于 $1\sim p-1$ 位的证明是不难的。考虑假设 $y$ 不符合上述规则,那么设出一个 $y’$ ,其中 $1\sim p-1$ 均是 $9$ ,且 $y’$ 的第 $p$ 位是 $y$ 的第 $p$ 位 $-1$ 的数值。那么可以知道 $x\leq y’<y$ 且 $\mathrm{S}(y’)\geq \mathrm S(y)$ 。这样的话 $\frac{y}{\mathrm S(y)}>\frac{y’}{\mathrm S(y’)}$ 与 $y$ 的定义矛盾。所以 $1\sim p-1$ 均为 $9$。

2、再考虑第 $p$ 位。设 $y$ 的第 $p$ 位值为 $s$,设 $y’=y-10^{p-1}\cdot s$ ,那么有

那么考虑此时 $y’$ 不变,等式右边是一个凹函数(先不考虑怎么凹),在 $s=9$ 或者 $s=0$ 时取得最值。根据定义可知此处应该选择 $s=9$ (因为 $y$ 的第 $p$ 位至少要比 $x$ 的第 $p$ 位大 $1$)


综上,可知后缀必然是某些 $999…999$ 的形式。从个位数向上推就好了。复杂度在 $\Omega(n)\sim O(n\log n)$ 左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n ;
long long ans ;
long long base = 1 ;

double s(long long x){
int ret = 0 ; long long y = x ;
while (x) ret += (x % 10ll), x /= 10ll ;
return (1.0 * y) / (1.0 * ret) ;
}
int main(){
cin >> n ;
while (n --){
while (1){
if (s(ans + base) > s(ans + base * 10ll))
base *= 10ll ; else break ;
}
ans += base ;
printf("%lld\n", ans) ;
}
}

C

给定一张图。求将这张图分成两个完全子图后,最少会有多少条边的端点属于同一个完全子图。

$n\leq 700$

一道比较妙的题。首先考虑建出补图来,那么发现,如果有两个点连通,就说明不能分在一个子图里面,恰好是二分图染色的流程。

之后考虑按补图的连通块 $dp$。注意到如果补图中连通块 $A$ 和 $B$ 不连通,说明原图中所有点都连通。所以根本不需要考虑连通块之间的连边。具体的,设状态 $f_{i,j}$ 表示考虑了前 $i$ 个连通块,是否存在二分图集合的某一部(左部or右部)大小是 $j$ 。根据前面的性质这就是个背包。所以 bitset 优化转移一下即可。

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
struct edge{
int to ;
int next ;
}E[N * N] ;

int res ;
int ctn ;
int n, m ;
int nienie ;
int vis[N] ;
int clr[N] ;
int cnt[2] ;
int head[N] ;
bool A[N][N] ;
bitset <N * N> ans ;

void add(int x, int y){
to(++ ctn) = y ;
next(ctn) = head[x] ;
head[x] = ctn ;
}
void dfs(int x, int c){
vis[x] = 1 ; clr[x] = c ; cnt[c] ++ ;
for (int k = head[x] ; k ; k = next(k))
if (!vis[to(k)]) dfs(to(k), c ^ 1) ;
else if (clr[to(k)] == c) return nienie = 1, void() ;
}
int calc(int x){
return x * (x - 1) + (n - x) * (n - x - 1) ;
}
int main(){
cin >> n >> m ; ans[0] = 1 ;
int u, v ; res = 1000000000 ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d", &u, &v) ;
A[u][v] = A[v][u] = 1 ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
if (!A[i][j] && (i ^ j)) add(i, j) ;
for (int i = 1 ; i <= n ; ++ i){
if (!vis[i]){
cnt[0] = cnt[1] = 0 ; dfs(i, 0) ;
ans = (ans << cnt[0]) | (ans << cnt[1]) ;
}
}
if (nienie) return puts("-1"), 0 ;
for (int i = 1 ; i <= n ; ++ i)
if (ans[i]) res = min(res, calc(i)) ;
return cout << res / 2 << endl, 0 ;
}

D

给定一个下标范围在 $[-\infty,\infty]$ 的数组。一开始指针在 $0$ 处。给定一段操作序列。求有多少个子序列的操作结果等价于整个序列的操作结果。操作有四种,左移/右移/某个位置$+1$/某个位置$-1$ 。

$1\leq n\leq 250,000$

一拿到题首先考虑 $dp$ ,发现 $dp$ 不是很可做…

于是就发现,类似这种题目可以使用哈希。四种操作分别对应 $\times base^{-1}$、$\times base$、$+base$、$-base$ 。

考虑这样做如何去求某一段的哈希值。普通的求法原理如下:

对于每个 $p$ ,截止到 $p$ 的哈希值,如果将 $x$ 看做 $base$ 的一个等价,那么就是是

考虑将上式记作 $o(p)$ 。则片段 $[l,r]$ 的哈希值可以如此得到:

考虑如果整个串的哈希值为 $q$,那么需要统计的是 $o(r)-o(l-1)\cdot x^{r-l+1}=q$ 。考虑从前至后用 $map$ 完成这个过程。由于不知道右端点的信息,需要对原式进行变形,即:

这样就可以做到 $l,r$ 无关了。随便选前缀或者后缀统计就好了。

但是注意到本题有个额外限制,最后只需要结果相同而不需要指针位置相同。所以需要稍微处理一下即可。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define mkp make_pair
#define pll pair<LL, LL>

const LL B1 = 237ll ;
const LL B2 = 637ll ;
const int N = 300010 ;
const LL P1 = 998244353 ;
const LL P2 = 1004535809 ;

int n ;
LL ans ;
char s[N] ;
LL I1, I2 ;
LL g[N][2] ;
LL S[N], T[N] ;
map <pll, LL> buc ;

LL expow(LL a, LL b, LL p){
LL ret = 1 ;
while (b){
if (b & 1)
(ret *= a) %= p ;
(a *= a) %= p ; b >>= 1 ;
}
return ret ;
}
int main(){
cin >> n >> (s + 1) ;
g[0][0] = g[0][1] = 1ll ;
I1 = expow(B1, P1 - 2, P1) ;
I2 = expow(B2, P2 - 2, P2) ;
for (int i = 1 ; i <= n ; ++ i){
if (s[i] == '-'){
g[i][0] = g[i - 1][0] ;
g[i][1] = g[i - 1][1] ;
S[i] = (S[i - 1] - g[i][0] + P1) % P1 ;
T[i] = (T[i - 1] - g[i][1] + P2) % P2 ;
}
if (s[i] == '+'){
g[i][0] = g[i - 1][0] ;
g[i][1] = g[i - 1][1] ;
S[i] = (S[i - 1] + g[i][0]) % P1 ;
T[i] = (T[i - 1] + g[i][1]) % P2 ;
}
if (s[i] == '<'){
g[i][0] = g[i - 1][0] * I1 % P1 ;
g[i][1] = g[i - 1][1] * I2 % P2 ;
S[i] = S[i - 1] ; T[i] = T[i - 1] ;
}
if (s[i] == '>'){
g[i][0] = g[i - 1][0] * B1 % P1 ;
g[i][1] = g[i - 1][1] * B2 % P2 ;
S[i] = S[i - 1] ; T[i] = T[i - 1] ;
}
++ buc[mkp(S[i], T[i])] ;
}
++ buc[mkp(0, 0)] ; LL x, y ;
for (int i = 0 ; i < n ; ++ i){
buc[mkp(S[i] , T[i])] -- ;
x = (S[i] + S[n] * g[i][0] % P1) % P1 ;
y = (T[i] + T[n] * g[i][1] % P2) % P2 ;
ans += buc[mkp(x, y)] ;
}
cout << ans << endl ; return 0 ;
}