avatar
文章
24
标签
19
首页
时间轴
标签
友链
关于
ruogu's blog
首页
时间轴
标签
友链
关于
cf1338
阅读量:|评论数:

https://codeforces.com/contest/1338

 

A

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define int ll
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e5 + 5;
int n, a[N];
const ll inf = 2e18;
//
signed main() {
  int t = getint();
  rep(tt, t) {
    n = getint();
    int pre = -inf, res = 0;
    rep(i, n) {
      int x = getint();
      int t = x - pre;
      if (t < 0) {
        t = -t;
        for (int i = 0; i < 40; i++) if (x + (1ll << i + 1) - 1 >= pre) {
          res = max(res, i + 1);
          break;
        } 
      }
      else pre = x;
    }
    printf("%d\n", res);
  } 
  return 0;
}

还Wa了两次，看看我紧张的时候写出来的丑陋的代码。。

我也不知道有什么可说的，希望下次AA不要Wa。

 

B

给定树的形态，让你对边权赋权值，使得叶子之间边权异或和为00，输出边权种类最大值和最小值。n≤105n \leq 10^5。

 

先令一个叶子弄成根。

我们要求每个叶子到根异或和为00就行。

先求最小值。若所有叶子深度值为偶数，那最小值就是11。否则一条长度为奇数的链至少也要33次。当存在深度为奇数的时候，我们考虑先从根往下连续赋11，最后需要的时候再赋22和33就可以了。

至于最大值，我们发现有些东西可以合并：

1.1.同一个点两个儿子叶子一定相同

2.2.深度为22的叶子一定没用

其余的，由于数值范围大，一定可以每条边有唯一选择。

 

一开始写错了，还以为想假了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e5 + 5;
vector<int> g[N], v[N];
int n, s, dep[N];
bool has[N];
//
void dfs(int x, int p, int d) {
  dep[x] = d;
  for (int to : g[x]) {
    if (to == p) continue;
    dfs(to, x, d + 1);
    if ((dep[to] == 2 | has[x]) && g[to].size() == 1) --n;
    //if (has[x] && g[to].size() == 1) --n;
    if (g[to].size() == 1) has[x] = true;
  } 
  if (dep[x] != 2 && g[x].size() == 1) v[dep[x] & 1].emplace_back(x);
}
int main() {
  n = getint();
  rep(i, n - 1) {
    int x = getint() - 1, y = getint() - 1;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  rep(i, n) {
    if (g[i].size() == 1) {
      s = i;
    }
  }
  dfs(s, -1, 0);
  if (v[1].size()) {
    printf("%d ", 3);
  }
  else printf("%d ", 1);
  printf("%d\n", n - 1);
  return 0;
}

 

C

一开始序列为空。每次选择还未加入序列且字典序最小的三个数(a,b,c)(a,b,c)满足a⊕b=ca \oplus b = c，把a,b,ca,b,c按顺序加入序列。1e51e5次询问n≤1016n \leq 10^{16}，输出序列第nn个数。

 

先打表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 2 3
4 8 12
5 10 15
6 11 13
7 9 14
16 32 48
17 34 51
18 35 49
19 33 50
20 40 60
21 42 63
22 43 61
23 41 62
24 44 52
25 46 55
26 47 53

第一项规律很显然是吧，第二项规律不显然，直接oeis是不行的。

但是这可能形如f1=2,f4=8,f5=10,f6=11,f7=9,f16=32f_1=2,f_4=8,f_5=10,f_6=11,f_7=9,f_{16}=32这样。

可以这样搜

1
"2" "8,10,11,9" "32,34,35,33,40,42,43,41"

引号里面是子串，外面是子序列。

然后就惊奇的发现原来是(a,a⊗2,a⊗3)(a,a \otimes 2, a \otimes 3)。。然后就可以贴板子了。。

 

回到正题，其实发现对于(a,b)(a,b)，二进制意义下每两位的变化都是：

(00,00),(01,10),(10,11),(11,01)(00, 00),(01,10),(10,11),(11,01)！！

 

这题我最后3s3s交错程序了，不过那个程序赛后交了也过不了pretestpretest。有一个注意点了：要用1ll1ll！！

这题我做的那么慢的原因是我老盯着那个表看，其实这题也许对于一段列举手玩更轻松一点，最后我是这样做了，但是来不及了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define int ll
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
int n, m, op[4];
//
void solve() {
  int nn = getint(); n = (nn - 1) / 3, m = (nn - 1) % 3;
  int l = 0;
  while (n >= (1ll << l)) {
    n -= (1ll << l); l += 2;
  }
  int res0 = n + (1ll << l);
  if (!m) {
    printf("%lld\n", res0);
    return;
  }
  int res1 = (1ll << l + 1);
  for (int i = l - 1; i >= 0; i -= 2) {
    int x = (n >> i & 1) << 1 | (n >> (i - 1) & 1);
    res1 |= (op[x] << (i - 1));
  }
  if (m == 1) printf("%lld\n", res1);
  else printf("%lld\n", res0 ^ res1);
}
signed main() {
  int t = getint();
  op[0] = 0;
  op[1] = 2;
  op[2] = 3;
  op[3] = 1;
  rep(tt, t) {
    solve();
  }
  return 0;
}

 

D

cf1338d_1

有边与相交等价。求最长的连续包含（AA包含BB包含CC这样的）。n≤105n \leq 10^5。

 

这题我想的麻烦的不得了，还是不会。

这题的结论是：

1.1.定义一条链的权值为所有离这条链距离小于等于11的点的最大独立集；

2.2.答案为图上所有链权值的最大值。

为什么只能与这条链距离为11呢？考虑一个圈一个圈套着，大概如果你要答案增加11，必须在中间插入一个圈（不能在两端加入圈，否则就是链选的太短），但是由于又要相交，中间根本插入不了。

大抵可以看看题解。

https://codeforces.com/blog/entry/75913

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e5 + 5;
int n, f[N][2], res = 1;
vector<int> g[N];
//
void dfs(int x, int p) {
  int c = 0; f[x][1] = 1;
  for (int to : g[x]) if (to != p) {
    dfs(to, x); ++c;
  }
  int pre[2] = {0, 0};
  for (int to : g[x]) if (to != p) {
    f[x][1] = max(f[x][1], f[to][0] + 1);
    f[x][0] = max(f[x][0], max(f[to][1], f[to][0]) + c - 1);
    res = max(res, f[to][1] + pre[0]);
    res = max(res, f[to][0] + pre[1]);
    pre[0] = max(pre[0], max(f[to][1], f[to][0]) + c + (p >= 0) - 2);
    pre[1] = max(pre[1], max(pre[0], f[to][0] + 1));
  }
  res = max(res, max(f[x][0], f[x][1]));
}
int main() {
  n = getint();
  rep(i, n - 1) {
    int x = getint() - 1, y = getint() - 1;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  dfs(0, -1);
  printf("%d\n", res);
  return 0;
}

 

E

https://ruogu-alter.github.io/2020/04/14/cf1338e/

文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/04/13/cf1338/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog！
总结
评论
簡