CloudySky

纵使世界万般残酷

总有温暖值得守护

CodeforcesRound779(CF1658)

link vp 2669分； 同分 official rank 1446； carrot 表现分 1632；

A. Marin and Photoshoot

题目大意

给定一个 01 串，可以在任意位置插入 0 / 1 。求使得任意一个段 1 不少于 0 最少插入几个字符。

题目思路

不难发现对于任意两个 0 中间至少隔两个 1 。暴力求就行。

B. Marin and Anti-coprime Permutation

题目大意

定义长度为 nn 的美丽排列为 gcd⁡(1⋅p1,2⋅p2,⋯ ,n⋅pn)>1\gcd(1\cdot p_1, 2\cdot p_2, \cdots, n \cdot p_n) > 1 。

给定多个 nn，求美丽排列个数。

题目思路

直接找规律。长度为奇数时无解。长度为偶数时，设长度为 2i2i ，则答案为 ans2i=ans2(i−1)×i2ans_{2i} = ans_{2(i - 1)} \times i^2 。

C. Shinju and the Lost Permutation

题目大意

定义一个排列的 cc 值为前缀最大值元素个数。

给出一个排列的所有起始位置顺时针循环同构的 cc 值。求该排列是否存在。

题目思路

首先得以肯定的是必然有一个且仅有一个 11 当最大值在最前面时。找到 11 的位置，对于顺序枚举的其他位置，最多可以比上一个答案加一。这两点都满足就可以构造。

题目代码

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
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 1e5 + 10;
using namespace std;
 
int c[Maxn];
 
#define TRUE printf("YES\n"), void()
#define FALSE printf("NO\n"), void()
 
#define p(x) ((x) + pos > n ? (x) + pos - n : (x) + pos)
 
void work() {
  int n = read(), pos = 0;
  for (int i = 1; i <= n; ++i) c[i] = read();
  for (int i = 1; i <= n; ++i) if (c[i] == 1) pos = i;
  if (!pos) return FALSE;
  for (int i = 1; i < n; ++i)
    if (c[p(i)] > c[p(i - 1)] + 1 || c[p(i)] == 1) return FALSE;
  return TRUE;
}
 
signed main() {
  // openfile();
  int t = read();
  while (t--) work();
  return 0;
}
 
void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

D2. 388535 (Hard Version)

题目描述

给定两个数 l,rl, r 和一个长度为 r−l+1r - l + 1 的排列求把所有数异或上一个数，使得排列变成值域为 [l,r][l, r] 的排列。求这个数，保证有解。

题目思路

首先，既然本来就是个排列，那么异或上任意一个数仍然是一个排列。很关键的一个性质，不难想，但难想到。

其次，必然有一个数 aia_i 异或上 xx 之后等于 ll 。

那么，可以根据异或的可逆性，枚举 aia_i ，用 ai⊕la_i \oplus l 来求 xx。同时求出 max⁡j=1r−l+1(aj⊕x)\max_{j = 1}^{r - l + 1}(a_j\oplus x) 判断是不是等于 rr。

这个东西可以用 trietrie 树来进行快速操作。

题目代码

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
73
74
75
76
77
78
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 4e5 + 10;
using namespace std;
 
int trie[Maxn][2], tot;
 
void insert(int x) {
  for (int i = 18, p = 1; ~i; --i) {
    int ch = (x >> i) & 1;
    if (!trie[p][ch]) trie[p][ch] = ++tot;
    p = trie[p][ch];
  }
}
 
int ask_max(int x, int res = 0) {
  for (int i = 18, p = 1; ~i; --i) {
    int ch = (x >> i) & 1;
    if (trie[p][!ch]) res += (1 << i), p = trie[p][!ch];
    else p = trie[p][ch];
  }
  return res;
}
 
int ask_min(int x, int res = 0) {
  for (int i = 18, p = 1; ~i; --i) {
    int ch = (x >> i) & 1;
    if (trie[p][ch]) p = trie[p][ch];
    else res += (1 << i), p = trie[p][!ch];
  }
  return res;
}
 
int a[Maxn];
 
void work() {
  tot = 1;
  int l = read(), r = read(), ans = 0;
  for (int i = l; i <= r; ++i) insert(a[i] = read());
  for (int i = l; i <= r; ++i) {
    if (ask_max(a[i] ^ l) == r && ask_min(a[i] ^ l) == l) ans = a[i] ^ l;
  }
  print(ans);
  for (int i = 1; i <= tot; ++i) trie[i][0] = trie[i][1] = 0;
}
 
signed main() {
  // openfile();
  int t = read();
  while (t--) work();
  return 0;
}
 
void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

E. Gojou and Matrix Game

题目描述

给定一个 n×nn\times n 带权棋盘，和一个数 kk。代表距离（曼哈顿）对方上一步下的棋必须大于 kk 。可以在之前下过棋的地方再次下棋并且获得分数。

枚举先手放到的每个位置，求最优策略下最后谁能赢。

题目思路

首先如果先手下分最高的位置一定是先手能赢得。

其次，如果某个地能够把之前确定的能赢得地都看住，那么这个地也是先手能赢得。

那么结论就出来了，把所有点按照权值排序。然后扫到某个点，把之前能先手赢得位置与这个位置一一比较，如果都能看住，那么标记这个位置为先手能赢。

但是这个复杂度是过不去的。考虑曼哈顿距离 abs(x1−x2)+abs(y1−y2)abs(x_1 - x_2) + abs(y_1 - y_2) 可以变形成两种情况 abs((x1+y1)−(x2+y2))，abs((x1−y1)−(x2−y2))abs((x_1 + y_1) - (x_2 + y_2))， abs((x_1 - y_1) - (x_2 - y_2)) 所以只需要维护四个变量即可。

题目代码

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

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
void openfile();
const int Maxn = 2e3 + 10;
using namespace std;
 
struct node {
  int x, y, v;
  bool operator < (const node y) const {return v > y.v;}
} a[Maxn * Maxn];
 
int f[Maxn][Maxn], tot;
 
signed main() {
  // openfile();
  int n = read(), k = read(), mxs, mns, mxd, mnd;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) a[++tot] = {i, j, read()};
  sort(a + 1, a + n * n + 1);
  f[a[1].x][a[1].y] = 1;
  mxs = mns = a[1].x + a[1].y, mxd = mnd = a[1].x - a[1].y;
  for (int i = 2; i <= n * n; ++i) {
    int x = a[i].x, y = a[i].y;
    if (max({abs(x + y - mxs), abs(x + y - mns), abs(x - y - mxd), abs(x - y - mnd)}) <= k) {
      f[x][y] = 1;
      mxs = max(mxs, x + y), mns = min(mns, x + y);
      mxd = max(mxd, x - y), mnd = min(mnd, x - y);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) putchar(f[i][j] ? 'M' : 'G');
    puts("");
  }
  return 0;
}
 
void openfile() {
  #ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
  #endif
}

本文作者：CloudySky
写作时间： 2022-04-05
最后更新时间： 2022-04-06
遵循协议： BY-NC-SA

Top