Educational Codeforces Round 106 (Rated for Div. 2) 题解

A - Domino on Windowsill

在一个 $2\times N$ 的棋盘上,第一行的前 $a$ 个格子是白色的,第二行的前 $b$ 个格子是白色的,其他格子都是黑色的。
有 $x$ 个 $1\times 2$ 的白色棋子和 $y$ 个 $1\times 2$ 的黑色棋子(棋子可以自由旋转90度,变成 $2\times 1$ 的)。
现在要将这些棋子放在棋盘上,要求每个格子最多只能放一个棋子(不能重叠),而且白色棋子只能放在两个白色格子上,黑色棋子同理。

只要黑白格子的数量足够放棋子的,就一定有方案。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-21 23:30:09
* Source: CF 1499 A
* Problem: https://codeforces.com/contest/1499/problem/A
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N, K1, K2, W, B;

int main() {
cin >> T;
while (T--) {
cin >> N >> K1 >> K2 >> W >> B;
if (W + B > N || K1 + K2 < 2 * W || 2 * N - K1 - K2 < 2 * B) {
puts("NO");
} else puts("YES");
}
return 0;
}

B - Binary Removals

给定 $01$ 串 $s$,求是否有一个子序列 $a$,满足 $a_i\not= a_{i+1}-1$ 且删除 $s_{a_i}$ 后的 $s’$ 满足 $s’_{i-1}\leq s_i$。

$T\leq 1000, |s|\leq 100$

由于数据范围很小,那就枚举 $s’$ 的 $0\cdots01\cdots 1$ 的断点,然后判断输出的点是否存在相邻的。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-21 23:30:09
* Source: CF 1499 B
* Problem: https://codeforces.com/contest/1499/problem/B
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

int T;
string s;
vector<int> v;

int main() {
cin >> T;
while (T--) {
cin >> s;
bool flag = 0;
for (int i = 0; i < s.size() && !flag; ++i) {
bool f = 1;
v.clear();
for (int j = 0; j < i; ++j) {
if (s[j] == '1') v.push_back(j);
}
for (int j = i; j < s.size(); ++j) {
if (s[j] == '0') v.push_back(j);
}
for (int i = 1; i < v.size(); ++i) {
if (v[i] == v[i - 1] + 1) {
f = 0;
break;
}
}
flag = f;
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}

C - Minimum Grid Path

给定长为 $n$ 的序列 $a$,求序列 $b$,满足 $\sum\limits_{i=2j+1}{b_i}=\sum\limits_{i=2j}{b_i}=n$,且 $b_i\geq 1$,使它权值最小。

序列的权值定义为 $\sum{a_i\times b_i}$。

$T\leq 1000,n\leq 10^5$

假设确定了 $b$ 的长度,那么要获得最小权值,就是分别对于奇数和偶数的 $i$,让 $a_i$ 最小的 $b_i$ 最大,其他的 $b_i=1$ 。

因此可以DP,记当前奇数/偶数下标中最小的 $a_i$ 为 $x,y$。

当 $i$ 为奇数时,当 $a_i\leq x$,$f_i=f_{i-1}-(x-a_i)\times (n-i/2)$,并更新 $x=a_i$,否则 $f_i=f_{i-1}-x+a_i$。

$i$ 为偶数时同理。

复杂度 $O(n)$。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-21 23:30:09
* Source: CF 1499 C
* Problem: https://codeforces.com/contest/1499/problem/C
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N;
vector<ll> v, f;

int main() {
cin >> T;
while (T--) {
cin >> N;
v.resize(N);
for (auto &x : v) cin >> x;
f.resize(N, 0);
f[1] = (v[0] + v[1]) * N;
ll mnx = v[0], mny = v[1];
ll ans = f[1];
for (int i = 2; i < N; ++i) {
if (i % 2 == 0) {
if (v[i] < mnx) {
f[i] = f[i - 1] - (mnx - v[i]) * (N - i / 2);
mnx = v[i];
} else {
f[i] = f[i - 1] - mnx + v[i];
}
} else {
if (v[i] < mny) {
f[i] = f[i - 1] - (mny - v[i]) * (N - i / 2);
mny = v[i];
} else {
f[i] = f[i - 1] - mny + v[i];
}
}
chkMin(ans, f[i]);
}
cout << ans << endl;
}
return 0;
}

D - The Number of Pairs

给定 $c,d,x$,求有多少对正整数 $(a,b)$,满足 $c\times lcm(a,b)-d\times gcd(a,b)=x$。

$T\leq 10^4,1\leq c,d,x\leq 10^7$

设 $y=\gcd(a,b)$,则 $a=y\times y_a$ ,$b=y\times y_b$,$\gcd(y_a,y_b)=1$。

由题意得 $c\times y\times y_a\times y_b-d\times y=x$,变形出 $y_a\times y_b=\frac{\frac{x}{y}+d}{c}$。

枚举 $x$ 的因数 $y$,判断 $\frac{x}{y}+d$ 是否是 $c$ 的倍数,若是,则得到了 $y_a\times y_b$ 的值。

现在的问题转换为,求一个数能拆成多少对互质的数的乘积。

将 $y_a\times y_b$ 的进行质因数分解,写成 $\prod{p_i^{q_i}}$ 的形式。若 $y_a\times y_b$ 有 $n$ 个质因子,则 $(y_a,y_b)$ 的数量为 $2^n$(每个 $p_i^{q_i}$ 要么选择 $y_a$ 要么选择 $y_b$,有两种方案。每个质因子的选择是独立的,因此一共是 $2^n$ 种)。

怎么求每个数有多少个质因子呐?可以在欧拉筛的时候求得。

因此复杂度为 $O(10^7+T\sqrt{x})$(欧拉筛+对于每个 $x$ 枚举 $y$ 的复杂度)。

Code

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
66
67
68
69
70
/* Code Information
* Author: little_skqliao
* Time: 2021-05-21 23:30:09
* Source: CF 1499 D
* Problem: https://codeforces.com/contest/1499/problem/D
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

int T, c, d, x;
vector<int> pri, num;
int Bin[20];

void Euler(int n = 2e7) {
num.resize(n + 1, 0);
for (int i = 2; i <= n; ++i) {
if (!num[i]) {
pri.push_back(i);
num[i] = 1;
}
for (auto a : pri) {
int x = a * i;
if (x > n) break;
num[x] = num[a] + num[i];
if (i % a == 0) {
--num[x];
break;
}
}
}
}

int get(int y) {
if ((y + d) % c) return 0;
return Bin[num[(y + d) / c]];
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Euler();
Bin[0] = 1;
for (int i = 1; i <= 10; ++i) Bin[i] = Bin[i - 1] * 2;
cin >> T;
while (T--) {
cin >> c >> d >> x;
int ans = 0;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
ans += get(x / i);
if (i != x / i) ans += get(i);
}
}
cout << ans << endl;
}
return 0;
}