A 题第一眼还以为要打线段树,发现只有两个区间不仅随便区间并一下,注意求的是区间线段数而不是点数,要减一; B 就是个模拟,照着它说的判即可; C 望过去就是 std::string + std::map (由于本人是 char 选手对 std::string 不熟悉还怕打挂),一个点是 里面 是出现次数而不是上一次出现的 ; D 一眼 dp , 显然要你 ,记 为“第 次计数器显示 的最大分数”,随便转移即可,注意开 long long
到此感觉自己手速中等(与以前的自己比有进步),估计已经被快的人甩了不少了,所以赶紧开 E
一看 E ,第一反应是处理前缀操作,把 的操作都压缩到一个东西里面,但发现不好搞,因为异或,与,或会互相影响,然后(指换了两次思路)发现每一位是可以处理的,即处理 表示“前 操作后第 位在原来是 的情况下变成了什么”,然后就简单了,注意初始化,
#include<bits/stdc++.h> constint N = 2e5 + 100; int n, c, op[N], a[N], b[N][50][2]; intmain() { scanf("%d %d", &n, &c); for (int i = 1; i <= n; ++i) scanf("%d %d", op + i, a + i); for (int j = 0; j < 30; ++j) b[0][j][0] = 0, b[0][j][1] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j < 30; ++j) for (int k = 0; k < 2; ++k) if (op[i] == 1) { if ((a[i] >> j) & 1) b[i][j][k] = b[i - 1][j][k]; else b[i][j][k] = 0; } elseif (op[i] == 2) { if ((a[i] >> j) & 1) b[i][j][k] = 1; else b[i][j][k] = b[i - 1][j][k]; } else { if ((a[i] >> j) & 1) b[i][j][k] = b[i - 1][j][k] ^ 1; else b[i][j][k] = b[i - 1][j][k]; } for (int i = 1; i <= n; ++i) { int t = 0; for (int j = 0; j < 30; ++j) { int bit = b[i][j][(c >> j) & 1]; t |= bit << j; } printf("%d\n", t); c = t; } return0; }
此时感觉 E 卡的有点久,还有近 的样子,不敢看榜,觉得自己的排名肯定特别难看,决定先看 F, G, EX
F 读了一下感觉很麻烦,可能要推些性质 + 打个数据结构; G 是个字符串,看着长度只有 估计是 dp 或者建图或者暴力之类的乱搞(总不可能是网络流把),主要是一个字符可以替换成多个字符不好搞; EX 刚读前两句“ We have a directed graph with ……”感觉图上问题没准可做,结果“ Takahashi and Aoki will play a game where they alternate turns moving the piece as follows ”,淦,博弈论吗?不可做(其实也可能不是,但我实在不想做博弈论),换题!
于是开始看 G ,约摸浪费了有 没想到啥好做法,果断改看 F ,手玩一下样例猜了个结论:一个点对答案的贡献就是它右边数字比他小且颜色和他不同的点的个数
#include<bits/stdc++.h> using LL = longlong; constint N = 3e5 + 100; int c[N], n; LL ans = 0; std::array<int, 3> a[N]; voidadd(int x, int d){ for (; x < N; x += x & -x) c[x] += d; } intask(int x) { int res = 0; for (; x; x ^= x & -x) res += c[x]; return res; } intmain() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i][1]), a[i][0] = i; for (int i = 1; i <= n; ++i) scanf("%d", &a[i][2]); for (int i = n; i; --i) { ans += ask(a[i][2] - 1) add(a[i][2], 1); } std::sort(a + 1, a + 1 + n, [&](auto x, auto y) { if (x[1] != y[1]) return x[1] < y[1]; return x[0] < y[0]; }); std::memset(c, 0, sizeof c); for (int i = n, j = n; i; --i) { if (i == n || a[i][1] != a[i + 1][1]) while (j != i) add(a[j][2], -1), --j; ans -= ask(a[i][2] - 1); add(a[i][2], 1); } printf("%lld\n", ans); return0; }