Codeforces Round #777 (Div. 2)

A 和 B 比较简单就不写了。

C. Madoka and Childish Pranks

一个初始是全白的矩阵，每次可以选一个子矩阵染成棋盘（左上角是白色）

构造一个不超过 \(n*m\) 次的方法把矩阵染成目标样子，或输出无解。

Key ：每次染一个 \(1\ast 2\) 的，可以把右侧的变黑，\(2\ast 1\) 的可以把下侧的变黑。

因此对于每一行，我又可以从右往左依次染 \(1\ast 2\) ，除第一列任何位置都可以染黑。

对于第一列从下往上依次染 \(2\ast 1\) ，除 \((1,1)\) 位置外都可以染黑。

所以只要 \((1,1)\) 不是黑色的就都有解。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

inline int gn() {
	char c = getchar();
	for (; !isdigit(c); c = getchar());
	return c - '0';
}

#define N 107
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

int a[N][N];

vector<pair<pii,pii>> s;

inline void work() {
	s.clear();
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= m; ++j) a[i][j] = gn();
	if (a[1][1]) {puts("-1"); return;}
	for (int i = 1; i <= n; ++i)
		for (int j = m; j > 1; --j)
			if (a[i][j]) s.pb(mp(mp(i,j - 1), mp(i, j)));
	for (int i = n; i > 1; --i) 
		if (a[i][1]) s.pb(mp(mp(i - 1, 1), mp(i, 1)));
	printf("%d\n", (int)s.size());
	for (auto x : s)
		printf("%d %d %d %d\n", x.fr.fr, x.fr.sc, x.sc.fr, x.sc.sc);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

D. Madoka and the Best School in Russia

定义一个数字 \(x\) 是好的，当且仅当 \(x\) 是 \(d\) 的倍数。

定义一个数字 \(x\) 是漂亮的，当且仅当他不能被拆分成两个好的数的乘积（也就是只含有一个 \(d\) ）

给你一个好的数 \(x\) ，问你是否有至少两种不同的方法，把 \(x\) 拆成若干个漂亮的数的乘积。

方法不同即拆分得到的数集不同。

因为每个漂亮数有且仅有一个 \(d\) ，因此 \(x\) 里有几个 \(d\) ，就至多要拆成几个漂亮数。

先考虑把 \(x\) 里的 \(d\) 都去掉，剩下的数是 \(y\) ，我们至少得到一种方案是 \(d,d,\dots,d,d\ast y\)

  • 如果 \(y\) 可以拆分（不是素数），那么就肯定有解；

  • 如果 \(y\) 不可拆分：

    • 如果 \(d\) 不可拆分，肯定无解（没有可拆的了）
    • 如果 \(x\) 里只有两个 \(d\) ，肯定无解（没有可拆的了）
    • 如果 \(x\) 里有超过三个 \(d\) ，肯定有解（把 \(y\) 和 \(d\) 拆分得到的三个数，分配给另外三个 \(d\) ）
    • 如果 \(x\) 里正好有三个 \(d\) ，需要检验一下把 \(d\) 拆出来的两部分某一部分分给 \(y\) 会不会形成新的 \(d\)
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 107

inline void work() {
	int x = rd(), d = rd();
	if (x % d != 0) {puts("NO"); return;}
	if (x / d % d != 0) {puts("NO"); return;}
	int cnt = 0;
	for (; x % d == 0; x /= d, ++cnt);
	int lim = sqrt(x);
	for (int i = 2; i <= lim; ++i)
		if (x % i == 0) {puts("YES"); return;}
	if (cnt == 2) {puts("NO"); return;}
	lim = sqrt(d);
	for (int i = 2; i <= lim; ++i)
		if (d % i == 0) {
			if (cnt > 3) {puts("YES"); return;}
			if (1ll * i * x % d != 0 || 1ll * d / i * x % d != 0) {puts("YES"); return;}
		}
	puts("NO");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

E. Madoka and the Sixth-graders

题意太复杂，我简单说一下，不清楚的看原题。

给定一个共 \(n\) 个点的内向基环树森林，开始每个点上有一个数（是 \(n\) 的排列）。

每一个时刻所有点按照所在边移动一次，如果某一时刻某个点上有很多数，只保留最小的。

如果某一时刻某个点上没数了（叶子），那么按照节点编号从小到大依次往里面塞 \(n+1,n+2,\dots\)

现在给出森林的形态，和经过若干时刻后每个点上的数字 \(a_1,\dots,a_n\) 。

请你还原出来一个字典序最小的初始状态，保证有解。

Key 1 ：假设已知经过的时间是 \(t\) ，那么每个点按照边移动 \(t\) 步以后的位置上的数字一定是不超过 \(n\) 的。

证明：如果是树的部分，那么 \(n\) 以后的数字永远追不上；如果是环的部分，因为 \(n\) 以后的数字比 \(n\) 大，所以都会被舍弃。

Key 2 ：两个点如果在某一步之后同时移动到了同一个点，那么后面的路径都相同（因为每个点只有一个出边）。

找出经过的时间 \(t\) ：假设叶子个数是 \(cnt\) ，序列里最大是 \(mx\) ，那么 \(t=\frac{mx - n}{cnt}\) （每一次移动会引进 \(cnt\) 个数）。

每个位置可能会放哪个数？

根据前面提到的 Key，假设 \(u\) 走 \(t\) 步之后到达的点是 \(v\) ，那么 \(u\) 上开始的数字要么是 \(a_v\) ，要么比 \(a_v\) 大，在移动的过程中某一步被挤掉了。

也就是说，如果一个点集 \(S\) 里所有点走 \(t\) 步以后到达的点都是 \(v\) ，那么这些点初始状态里有一个必定是 \(a_v\) ，其他都比 \(a_v\) 大。

怎么找 \(v\) ：因为每个点都只有一条出边，因此可以直接倍增找

怎么贪心？

我们先令结果序列 \(b_u=a_v\) ，也就是假设每个点的初始状态就是走 \(t\) 步以后的位置上的值。

设 \(S_x=\\{u|b_u=x\\}\) ，考虑从小到大放数字 \(x\) ：

  • 如果 \(S_x\ne \emptyset\) ，那么就把 \(x\) 放到 \(S_x\) 中位置最靠前的
  • 如果 \(S_x=\emptyset\) ，那么就把 \(x\) 放到 \(S_1\cup S_2\cup\dots\cup S_{x-1}\) 中未使用的最靠前的位置里。
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
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007

int f[N][40], a[N], res[N];

bool vis[N];

queue<int> s[N];

set<int> S;

inline void work() {

    int n = rd();
    for (int i = 1; i <= n; ++i) {
        f[i][0] = rd(); vis[f[i][0]] = 1;
    }
    for (int j = 1; j < 40; ++j)
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];

    int mx = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) ++cnt;
        a[i] = rd(); mx = max(mx, a[i]);
    }
    cnt = (mx - n) / cnt;
  
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= n; ++i) {
        int u = i;
        for (int k = 30; k >= 0; --k) 
            if (cnt & (1 << k)) u = f[u][k];
        res[i] = a[u]; s[res[i]].push(i);
        vis[res[i]] = 1; //Sx不空
    }

    for (int i = 1; i <= n; ++i)
        if (vis[i]) s[i].pop(); //把i放到Si最靠前的位置

    int nw = 0;
    for (int i = 1; i <= n; ++i) 
        if (!vis[i]) {
            while (nw <= i) {
                while (s[nw].size()) {
                    S.insert(s[nw].front());
                    s[nw].pop();
                }
                ++nw;
            }
            res[*S.begin()] = i; S.erase(S.begin());
        }
    for (int i = 1; i <= n; ++i) printf("%d ", res[i]);
}

int main() {
    for (int t = 1; t; --t) work();
    return 0;
}

F. Madoka and Laziness

给定一个没有重复数值的数列 \(\{a_i\}\) ，问有多少种方式将数列划分为两个峰序列（严格单增再单减）。

两种划分不同，当且仅当至少某一个峰序列的峰值不同（认为 <a,b> 和 <b,a> 相同）。

Key ：最大值一定是其中一个峰的峰值。

这个观察有什么用呢？因为一个峰值固定，我们可以得到答案是 O(n) 的。

也就是说，我们只需要去检验，其他的每一个值是否有可能成为峰值即可。

怎么检验呢？只需要判断是否存在一种拆分方式，使得到每个位置之前是升的，过了这个位置之后是降的，并且没给这个序列的元素扔给最大值所在的序列都合法。

我们可以假设另一个峰值（峰值B）在最大值（峰值A）的右侧，然后把序列翻过来再做一遍即可。

这样就有三个阶段：

  • 到峰值A前：两个序列都上升

这一阶段序列A里只要单调递增，放多大的都可以。

我们为了后面序列B还要增的考虑，应该尽量减少序列B在这一部分的最大值。

设 \(f_i\) 为考虑前缀 \(i\) ，则 \(a_i\) 必定为某一个序列结尾，则另一个序列结尾最小值是多少。

转移很简单，接在 \(a_{i-1}\) 后，或接在 \(f_{i-1}\) 后。

1
2
if (a[i] > a[i - 1]) f[i] = min(f[i], f[i - 1]);
if (a[i] > f[i - 1]) f[i] = min(f[i], a[i - 1]);
  • 峰值A后，峰值B前：序列A下降，序列B上升

这一阶段因为两个序列单调性不同，所以贪心策略也不同。

设 \(g_{i,0}\) 表示第 \(i\) 个元素放到序列A里，另一个序列（正在上升的序列B）末尾最小是多少。

设 \(g_{i,1}\) 表示第 \(i\) 个元素放到序列B里，另一个序列（正在下降的序列A）末尾最大是多少。

转移也很简单，讨论一下接在谁后面就好了。

1
2
3
4
if (a[i] < a[i - 1]) g[i][0] = min(g[i][0], g[i - 1][0]);
if (a[i] < g[i - 1][1]) g[i][0] = min(g[i][0], a[i - 1]);
if (a[i] > a[i - 1]) g[i][1] = max(g[i][1], g[i - 1][1]);
if (a[i] > g[i - 1][0]) g[i][1] = max(g[i][1], a[i - 1]);
  • 峰值B后：两个序列都下降

倒着考虑，变成单增的，那么在保证峰值B跟着的序列合法的前提下，另一个序列（留给峰值A的）的最大值要尽可能小。

因此处理方法同第一个阶段（设为 \(h\) 数组）。

那么怎么判断是否合法嘞？把 \(a_i\) 放到序列B里，另一个序列合法（ 也就是满足 g[i][1] > h[i] ） 就可以啦～

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007
#define inf 1e9 + 7

int n, a[N], f[N], g[N][2];

inline int calc() {
  
    int p = 0; //maxpos
    for (int i = 1; i <= n; ++i) {
        f[i] = g[i][0] = inf;
        g[i][1] = -1;
        if (a[i] > a[p]) p = i;
    }

    for (int i = 1; i <= p; ++i) {
        if (a[i] > a[i - 1]) f[i] = min(f[i], f[i - 1]);
        if (a[i] > f[i - 1]) f[i] = min(f[i], a[i - 1]);
    }
  
    g[p][0] = f[p]; //承接第一阶段的最宽松约束
    for (int i = p + 1; i <= n; ++i) {
        if (a[i] < a[i - 1]) g[i][0] = min(g[i][0], g[i - 1][0]);
        if (a[i] < g[i - 1][1]) g[i][0] = min(g[i][0], a[i - 1]);
        if (a[i] > a[i - 1]) g[i][1] = max(g[i][1], g[i - 1][1]);
        if (a[i] > g[i - 1][0]) g[i][1] = max(g[i][1], a[i - 1]);
    }
  
    int ans = 0;
    for (int i = n; i > p; --i) {
        if (a[i] > a[i + 1]) f[i] = min(f[i], f[i + 1]);
        if (a[i] > f[i + 1]) f[i] = min(f[i], a[i + 1]);   
        if (g[i][1] > f[i]) ++ans;
    }
  
    return ans;
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    int ans = calc();
    reverse(a + 1, a + 1 + n);
    printf("%d\n", ans + calc());
    return 0;
}