仓库源文，站点原文

title: 题解 - Japanese Student Championship 2021 categories:

算法竞赛
题解 tags:
算法竞赛
题解
AtCoder
暴力
枚举
数学
图论
数论
字符串
数据结构
最大公约数
回文字符串
线段树
平衡树
并查集
Laplacian矩阵
Kirchhoff矩阵树定理 date: 2021-04-17 18:54:25

题目概览

题号¹	标题	做法
A	Competition	签到
B	Xor of Sequences	签到
C	Max GCD 2	签到, 枚举
D	Nowhere $P$	签到, 找规律
*E	Level K Palindrome
*F	Max Matrix	线段树 / 平衡树
G	Spanning Tree	并查集 + 矩阵树定理
*H	Shipping

官方题解

A - Competition

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 100 points

Problem Statement

A Supermarket Takahashi sells an $X$-gram beef pack for $Y$ yen

Another Supermarket Snuke has decided to sell a beef pack at a lower price per gram

In Snuke, one beef pack weighs $Z$ grams. What is the greatest possible price (a non-negative integer) for Snuke's beef pack such that it is strictly cheaper than Takahashi's beef pack per gram?

Constraints

All values in input are integers
$1\leqslant X,Y,Z\leqslant 10^3$

Input

Input is given from Standard Input in the following format:

$X\ Y\ Z$

Output

Print the answer

Sample Input 1

100 200 100

Sample Output 1

Both stores sell $100$-gram packs, so Snuke can just make it one yen cheaper than that in Takahashi

Sample Input 2

103 971 593

Sample Output 2

Takahashi sells beef for $\frac{971}{103}=9.4271...$ yen per gram. Snuke can sell $593$ grams of beef for $5590$ yen to make it $\frac{5590}{593}=9.4266...$ yen per gram

Sample Input 3

1000 1 1

Sample Output 3

The price is allowed to be $0$ yen

解题思路

$\lfloor\frac{yz}{x}\rfloor-[x\mid yz]$

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_jsc2021_a AtCoder/jsc2021_a/0.cpp %} </details>

B - Xor of Sequences

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 200 points

Problem Statement

We have two strictly increasing integer sequences $A=(A_1,A_2,...,A_N)$ and $B=(B_1,B_2,...,B_M)$

Find all integers that appear in exactly one of $A$ and $B$ and print them in ascending order

Constraints

All values in input are integers
$1\leqslant N,M\leqslant 10^3$
$1\leqslant A_1<A_2<...<A_N\leqslant 10^3$
$1\leqslant B_1<B_2<...<B_M\leqslant 10^3$

Input

Input is given from Standard Input in the following format:

$N\ M$

$A_1\ A_2\ ...\ A_N$

$B_1\ B_2\ ...\ B_M$

Output

Print all integers that appear in exactly one of $A$ and $B$

in ascending order, with space as separator

Sample Input 1

2 2
1 2
1 3

Sample Output 1

2 3

$1$ is contained in both $A$ and$B$

$2$ is contained in only $A$

$3$ is contained in only $B$

Thus, we should print $2$ and $3$

Sample Input 2

4 4
1 2 3 4
1 2 3 4

Sample Output 2

You can print an empty line or nothing

题意简述

给两串严格递增的序列, 求这两个序列的对称差

解题思路

随便做

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_jsc2021_b AtCoder/jsc2021_b/0.cpp %} </details>

C - Max GCD 2

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 300 points

Problem Statement

Given are integers $A$ and $B$. Find the maximum possible value of $\gcd(x,y)$ when we choose integers x and y so that $A\leqslant x<y\leqslant B$

Here, $\gcd(x,y)$ denotes the greatest common divisor of $x$ and $y$

Constraints

$A$ and $B$ are integers
$1\leqslant A<B\leqslant 2\times 10^5$

Input

Input is given from Standard Input in the following format:

$A\ B$

Output

Print the answer

Sample Input 1

2 4

Sample Output 1

We have three ways to choose $(x,y)$ such that $A\leqslant x<y\leqslant B$: $(2,3),(2,4),(3,4)$, where the greatest common divisors are $1,2,1$, respectively, so the maximum possible value is $2$

Sample Input 2

199999 200000

Sample Output 2

We have $\gcd(199999,200000)=1$

Sample Input 3

101 139

Sample Output 3

题意简述

给定 $A,B$, 求 $\displaystyle\max_{A\leqslant x<y\leqslant B}(x,y)$

解题思路

直接暴力枚举即可

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_jsc2021_c AtCoder/jsc2021_c/0.cpp %} </details>

D - Nowhere P

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 400 points

Problem Statement

You are given a prime number $P$ not less than $2$, which you don't like

Let's call an array of integers $A_1,A_2,...,A_N$ very good if it satisfies the following condition:

there is no $i$ with $1\leqslant i\leqslant N$ and $A_1+A_2+...+A_i\equiv0\pmod P$

Consider all $(P-1)^N$ arrays of length $N$ with elements from $1$ to $P-1$. How many of them are very good?

As this number can be very big, output it modulo $10^9+7$

Constraints

$N$ and $P$ are integers
$1\leqslant N\leqslant 10^9$
$2\leqslant P\leqslant 10^9$

Input

Input is given from Standard Input in the following format:

$N\ P$

Output

Print the count modulo $10^9+7$

Sample Input 1

3 3

Sample Output 1

Two arrays, $(1,1,2)$ and $(2,2,1)$, satisfy the condition

Sample Input 2

3 2

Sample Output 2

Sample Input 3

45108 2571593

Sample Output 3

224219544

题意简述

给定质数 $P$, 求有多少序列 $(A_1,A_2,\dots,A_N)$ 满足:

$$ \forall i\in[1,n]{\mathbb{N}},~\sum{j=1}^iA_j{\equiv}\llap{/\,}0\pmod P $$

解题思路

显然, 当 $n=1$ 时答案为 $p-1$, 对应合法序列即为 $(1),(2),...,(p-1)$

之后在这些合法序列后插入新数时, 每个序列都有且仅有一个数使得这个数插入后该序列非法 (该数即为 $(-\sum_{i}a_i)\bmod p$)

故答案为 $(p-1)(p-2)^{n-1}$

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_jsc2021_d AtCoder/jsc2021_d/0.cpp %} </details>

E - Level K Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 500 points

Problem Statement

As a token of his gratitude, Takahashi has decided to give Snuke a level-$K$ palindrome. A level-$L$ palindrome, where $L$ is a non-negative integer, is defined as follows:

Let $\operatorname{rev}(s)$ denote the reversal of a string $s$
A string $s$ is said to be a palindrome when $s=\operatorname{rev}(s)$
The empty string and a string that is not a palindrome are level-$0$ palindromes
For any non-empty level-($L-1$) palindrome $t$, the concatenation of $t$,$\operatorname{rev}(t)$ in this order is a level-$L$ palindrome
For any level-($L-1$) palindrome $t$ and any character $c$, the concatenation of $t$,$c$,$\operatorname{rev}(t)$ in this order is a level-$L$ palindrome

Now, Takahashi has a string $S$. Determine whether it is possible to make $S$ an exactly level-$K$ palindrome by doing the following action zero or more times: choose a character in $S$ and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make $S$ a level-$K$ palindrome

Constraints

$K$ is an integer
$0\leqslant K\leqslant 5\times 10^5$
$S$ consists of lowercase English letters
$1\leqslant |S|\leqslant 5\times 10^5$

Input

Input is given from Standard Input in the following format:

$K\ S$

Output

If it is possible to get an exactly level-$K$ palindrome, print the minimum number of changes needed. If it is impossible, print impossible

Sample Input 1

4
aabaaaabaa

Sample Output 1

We can find the level of aabaaaabaa as follows:

the empty string is a level-$0$ palindrome
a is a concatenation of (empty string), a, (empty string) in this order, so it is a level-$1$ palindrome
aa is a concatenation of a, a in this order, so it is a level-$2$ palindrome
aabaa is a concatenation of aa, b, aa in this order, so it is a level-$3$ palindrome
aabaaaabaa is a concatenation of aabaa, aabaa in this order, so it is a level-$4$ palindrome

Thus, aabaaaabaa is already a level-$4$ palindrome and needs no changes

Sample Input 2

2
aabaaaabaa

Sample Output 2

We can, for example, change aabaaaabaa to acbcaacbca to get a level-$2$ palindrome

Note that aabaaaabaa is not a level-$2$ palindrome

Sample Input 3

3
aabaaaabaa

Sample Output 3

impossible

Sample Input 4

5
aabaaaabaa

Sample Output 4

impossible

Sample Input 5

2
acaabcbababaaac

Sample Output 5

题意简述

本题所有的字符串均指只由小写英文字母构成的字符串

对字符串 $s$,

定义其反转为: $\operatorname{rev}(s)$, 则 $s$ 是回文串 $\iff s=\operatorname{rev}(s)$
$+$ 运算定义为字符串的拼接
定义字符串上的变换为: 将其中某一字符替换为一小写英文字母

定义 $k$ 阶回文串如下:

空串, 非回文串为 $0$ 阶回文串
对 $i$ 阶非空回文串 $s$, 定义 $s+\operatorname{rev}(s)$ 为 $i+1$ 阶回文串
对 $i$ 阶回文串 $s$ 和单个字符 $c$, 定义 $s+c+\operatorname{rev}(s)$ 为 $i+1$ 阶回文串

给一字符串 $s$, 问至少经几次变换可使其恰好为 $k$ 阶回文串

解题思路

显然, 若有解则 $k$ 不可能过大

复杂度

代码参考

F - Max Matrix

Time Limit: 3 sec / Memory Limit: 1024 MB

Score: 600 points

Problem Statement

We have a sequence a of length $N$ and a sequence $b$ of length $M$. Initially, every element in $a$ and $b$ is $0$

You are asked to process $Q$ queries. In the $i$-th query, given three integers $T_i$, $X_i$, and $Y_i$, do the following:

if $Ti=1$: replace $a{X_i}$ with $Y_i$
if $Ti=2$: replace $b{X_i}$ with $Y_i$

Then, after processing each query, print the value $\displaystyle\sum{i=1}^N\sum{j=1}^M\max(a_i,b_j)$

Constraints

$1\leqslant N\leqslant 2\times 10^5$
$1\leqslant M\leqslant 2\times 10^5$
$1\leqslant Q\leqslant 2\times 10^5$
$T_i$ is $1$ or $2$
If $T_i=1$, $1\leqslant X_i\leqslant N$
If $T_i=2$, $1\leqslant X_i\leqslant M$
$1\leqslant Y_i\leqslant 10^8$
All values in input are integers

Input

Input is given from Standard Input in the following format:

$N\ M\ Q$

$T_1\ X_1\ Y_1$

$T_2\ X_2\ Y_2$

$T_3\ X_3\ Y_3$

$\vdots$

$T_Q\ X_Q\ Y_Q$

Output

Print $Q$ integers as instructed in Problem Statement, with newline as separator

Sample Input 1

Sample Output 1

If we write $\max(a_i,b_j)$ at the $i$-th row and $j$-th column in a grid, the four queries will change it as follows:

Sample Input 2

Sample Output 2

Sample Input 3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000

Sample Output 3

20000000000000
39999900000000
59999800000000
59999800000000

The integers to be printed may not fit into a $32$-bit integer type

题意简述

有一个长为 $n$ 的全零序列 $a$ 和长为 $m$ 的全零序列 $b$, 对其做如下操作

将 $a$ 中的某个数赋一个值
将 $b$ 中的某个数赋一个值

这两种操作一共进行 $Q$ 次, 要求每次操作后都要输出 $\displaystyle\sum{i=1}^n\sum{j=1}^M\max{a_i,b_j}$

解题思路

复杂度

代码参考

G - Spanning Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 600 points

Problem Statement

We have a graph with $N$ vertices numbered $1,2,...,N$. Initially, it has no edges

Now, let us add some number of undirected edges to $G$ so that the following condition holds for any $i,j(i\ne j)$

after addition

If $A_{i,j}=1$, there is an edge directly connecting Vertex $i$ and Vertex $j$
if $A_{i,j}=0$, there is no edge directly connecting Vertex $i$ and Vertex $j$
if $A_{i,j}=-1$, either is fine

Among the graphs that can be $G$ after addition, how many are trees?

Since the count can be enormous, find it modulo $10^9+7$

Constraints

All values in input are integers
$2\leqslant N\leqslant 300$
$-1\leqslant A{i,j}=A{j,i}\leqslant 1$
$A_{i,i}=0$

Input

Input is given from Standard Input in the following format:

$N$

$A{1,1}\ ...\ A{1,N}$

$\vdots$

$A{N,1}\ ...\ A{N,N}$

Output

Print the count modulo $10^9+7$

Sample Input 1

Sample Output 1

We need an edge between Vertex $1$ and Vertex $2$, and we must not add an edge between Vertex $1$ and Vertex $4$ or between Vertex $3$ and Vertex $4$

Thus, we have the following two valid graphs:

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

11
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

Sample Output 4

357947677

When we distinguish the vertices, there are $11^9$ trees with $11$ vertices

题意简述

有 $n$ 个点, 考虑以这 $n$ 个点为顶点, 满足如下条件的所有图:

无向图
给出一个矩阵 $A$
- 若 $A_{i,j}=1$, 则点 $i$ 和点 $j$ 间有一条无向边
- 若 $A_{i,j}=0$, 则点 $i$ 和点 $j$ 间没有边
- 若 $A_{i,j}=-1$, 则为上述两种情况的任一种

求这些图中树的个数

解题思路

首先, 考虑所以已经存在的边构成的图, 如果有环了, 则答案一定为 $0$, 否则森林中的每个树都可缩成一个点, 之后用矩阵树定理即可

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:AtCoder_jsc2021_g AtCoder/jsc2021_g/0.cpp %} </details>

H - Shipping

Time Limit: 5 sec / Memory Limit: 1024 MB

Score: 600 points

Problem Statement

In the Republic of AtCoder, there are $N$ cities called City $1$ through City $N$ and $N$ canals called Canal $1$ through Canal $N$

Canal $i$ connects City $i$ and City $A_i$ bidirectionally, and you have to pay the toll of $C_i$

yen to go through it, but after paying the toll once, you can use it any number of times in any direction

It is guaranteed that you can reach from any city to any city using some canals

You are asked to deliver $M$ cargoes in this country. The $i$-th cargo should be delivered from City $X_i$ to City $Y_i$

There is no way other than using the canals to deliver the cargoes, but you yourself can travel between the cities freely without using the canals

Find the minimum total toll you have to pay to deliver all $M$ cargoes

Constraints

$3\leqslant N\leqslant 2\times 10^5$
$1\leqslant M\leqslant 2\times 10^5$
$1\leqslant A_i\leqslant N$
$A_i\ne i$
$1\leqslant C_i\leqslant 10^9$
It is possible to reach from any city to any city by using some canals
$1\leqslant X_i\leqslant N$
$1\leqslant Y_i\leqslant N$
$X_i\ne Y_i$
All values in input are integers

Input

Input is given from Standard Input in the following format:

$N\ M$

$A_1\ C_1$

$A_2\ C_2$

$A_3\ C_3$

$\vdots$

$A_N\ C_N$

$X_1\ Y_1$

$X_2\ Y_2$

$X_3\ Y_3$

$\vdots$

$X_M\ Y_M$

Output

Print the minimum total toll you have to pay, as an integer

Sample Input 1

Sample Output 1

The figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:

You can deliver the cargoes as follows to make the total toll $10$ yen:

The $1$-st cargo: use Canal $1,4$ to deliver it on the route: City $4,1,3$
The $2$-nd cargo: use Canal $3,1$ to deliver it on this route: City $2,3,1$

Sample Input 2

Sample Output 2

Multiple canals may connect the same pair of cities

Sample Input 3

Sample Output 3

题意简述

给一个带权无向图, 求满足如下条件的子图的最小边权和

$$ \forall i\in[1,M]_{\mathbb{N}},~\operatorname{dis}(x_i,y_i)\ne\infty $$

解题思路

复杂度

代码参考

打*的是还没写的题↩