rank 链接

签到：EF

铜牌题：BJ

银牌题：HILM

金牌题：G...

B Bitwise Exclusive-OR Sequence

\(n\) 个数，\(m\) 个关系，每个关系形如 \(a_u\oplus a_v = w\)，表示第 \(u\) 个数与第 \(v\) 数的异或运算结果为 \(w\)。求是否有这样的\(n\) 个数满足所有关系要求，如果没有输出 -1，如果有输出所有满足要求的方案中，所有数字的和的最小值。

\(n \le 100000,m\le 200000,w\lt 2^{20}\)

可以看做 \(n\) 个点，\(m\) 条边的无向图，每个连通块内都通过一些关系使得两两可达。所以，如果连通块内的一个数字确定，那么所有的数字都可以确定下来。

可以选择连通块中的某个点作为根 \(rt\)，那么可以使用 DFS 求出整个连通块中所有点与 \(rt\) 的异或值。这个过程可能会检测出问题无解的情况。由此，可以按 30 位去考虑，计算出整个连通块中每个点与 \(rt\) 异或值的每一位为 0 和 1 的个数，然后选择较小的作为答案。为什么可以选择较小的，因为 \(rt\) 的实际值是由我们去确定的，假设第 \(i\) 位上，与 \(rt\) 异或为 0 的个数为 \(a\)，为 1 的为 \(b\)，假设 \(a

也可以建 30 次图去跑，不过每次重新建图容易被卡常数。也可以每次考虑判定二分图，并利用并查集缩点，即异或为 0 的去合并，异或为 1 的连边，然后去判断二分图。实际测试起来也非常快。

#include

using namespace std;

#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)

#define per(i,j,k) for(int i=int(j);i>=int(k);i--)

typedef long long ll;

const int N = 100010, M = 400010;

int n, m, vis[N], val[N], cnt[32][2];

int head[N], ver[M], nxt[M], edge[M], tot;

bool flag;

void add(int x, int y, int z){

ver[++tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot;

}

void dfs(int x, int fa = 0) {

if(!flag) return;

vis[x] = 1;

for(int i=30;i>=0;i--){

cnt[i][val[x] >> i & 1] ++;

}

for(int i=head[x];i;i=nxt[i]) {

int y = ver[i];

if(vis[y]) {

if((val[y] ^ val[x]) != edge[i]) {

flag = false;

return;

}

} else {

val[y] = val[x] ^ edge[i];

dfs(y, x);

}

}

}

int main(){

scanf("%d%d", &n, &m);

for(int i=1;i<=m;i++){

int x, y, w;

scanf("%d%d%d", &x, &y, &w);

add(x, y, w); add(y, x, w);

}

flag = true;

ll res = 0;

for(int i=1;i<=n;i++){

if(!vis[i]) {

memset(cnt, 0, sizeof cnt);

dfs(i);

for(int j=30;j>=0;j--){

res += 1ll * min(cnt[j][0], cnt[j][1]) * (1 << j);

}

}

}

if(!flag) {

puts("-1"); return 0;

}

printf("%lld\n", res);

return 0;

}

E Edward Gaming, the Champion

判断一个串中出现了多少次 "edgnb"

#include

using namespace std;

const int N = 200010;

char s[N];

int main(){

string s;

cin >> s;

int n = s.length();

int res = 0;

for(int i=0;i<=n-5;i++){

if(s.substr(i, 5) == "edgnb") {

res ++;

}

}

cout << res << endl;

return 0;

}

F Encoded Strings I

给定一个长度为 \(n(n\le 1000)\) 的字符串\(s\)，定义函数 \(F_s\)：

\(F_s(c) = chr(G(c,S))\) ，表示将 S 中的每个字符 c 转换为 \(chr(G(c,S))\)，其中 \(G(c,S)\) 表示 S 中最后一次出现 c 之后的后缀中不同的字符个数，\(chr(i)\) 表示第 \(i\) 个字符（第个0字符是 a，第1个是 b...）。

要求你对 \(s\) 的每个非空前缀代入到函数中，得到 \(n\) 个字符串，输出按照字典序排序的最大字符串。

难在题意理解，字符串 \(aacc\) 有前缀 \(a,aa,aac,aacc\)，它们代入 \(F_s\) 得到：\(a,aa,bba,bbaa\)，答案是 \(bbaa\)。

首先预处理出每种字符最后出现的位置，再预处理出每个后缀出现的字符个数，暴力计算即可。（实现方法有很多）

#include

using namespace std;

#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)

#define per(i,j,k) for(int i=int(j);i>=int(k);i--)

typedef long long ll;

const int N = 1010;

int n;

char s[N];

int last[26], suf[N];

string get(int n) {

unordered_map mp;

for(int i=n;i>=1;i--){

suf[i] = mp.size();

mp[s[i]] ++;

}

for(int i=1;i<=n;i++){

last[s[i] - 'a'] = i;

}

string t = "";

for(int i=1;i<=n;i++){

t += char('a' + suf[last[s[i] - 'a']]);

}

return t;

}

int main(){

scanf("%d%s", &n, s + 1);

string res = "";

for(int i=1;i<=n;i++) {

res = max(res, get(i));

}

cout << res << endl;

}

G Encoded Strings II

给定一个长度为 \(n(n\le 1000)\)，且仅包含 \(a\sim t\) 的字符串，求对它的所有非空子序列使用 \(F_s\) 函数处理后，字典序最大的结果。

字符串最多包含 20 种字符，这个条件可以被我们所利用。

假如字符串只包含了\(k\) 种字符，那么最终答案肯定是 \(k\) 段连续字符，因为首个字符字典序要最大。

然后枚举 \(k\) 种字符，在子序列中出现的顺序，然后对于每一段字符，起始位置是固定的，尝试去找结束维护。

假设现在处理第 i 个字符，它代表了答案的第 \(i\) 段字符，由于希望答案尽可能的字典序更大，所以我们希望第 \(i\) 段字符也尽可能的长。

另外需要保证其他 \(k-i\) 种字符在后面可以出现，所以处理 \(f[s]\) 表示 \(k-i\) 种字符构成的二进制集合 \(s\)，使得这 \(k\) 种字符都出现的最短后缀出现的位置。

现在有了第 \(i\) 段字符可选的区间范围 \(l,r\)，\(r\) 对于每种字符可能不同，我们想找到这个范围里面，出现次数最多的字符，然后枚举它，继续递归。递归时，下次搜索的左端点是当前枚举字符在 \(r\) 之前最后一次出现的位置。

#include

using namespace std;

#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)

#define per(i,j,k) for(int i=int(j);i>=int(k);i--)

typedef long long ll;

const int N = 1005;

// sum 是前缀和，last 表示每个字符出现的最后位置，f[i] 表示 i 集合字符出现的最早后缀位置，pre[i][j] 表示 j 字符在 i 位置之前出现的最近位置。

int n, sum[N][20], last[20], f[1<<20], pre[N][20];

int cnt, num[20], vis[20];

char s[N];

void dfs(int u, int l) {

if(u == cnt) return;

int st = 0; // 找到还没有分配的字符集合 st

for(int i=0;i<20;i++) if(!vis[i] && last[i]) st |= 1 << i;

int mx = 0; // 在 l,r 中找到最多的出现次数

for(int i=0;i<20;i++) {

if(!vis[i] && last[i]) {

int r = f[st ^ (1 << i)] - 1; // st 集合中除去 i, 剩下的字符都出现的最短后缀位置。

mx = max(mx, sum[r][i] - sum[l-1][i]);

}

}

if(mx < num[u]) return; // 剪枝，第 u 段长度不够更新

if(mx > num[u]) { // 足够去更新第 u 段字符的长度，那么后面所有的长度都归 0

num[u] = mx;

for(int i=u+1;i

}

for(int i=0;i<20;i++) { // 枚举每个出现次数为 mx 的字符 i

if(!vis[i] && last[i]) {

int r = f[st ^ (1 << i)] - 1;

int x = sum[r][i] - sum[l-1][i];

if(x == mx) {

vis[i] = 1;

dfs(u + 1, pre[r][i] + 1); // 下次搜索的起点，应当是 r 之前最后一次出现 i 字符的后一个位置。

vis[i] = 0;

}

}

}

}

int main(){

scanf("%d%s", &n, s + 1);

// 预处理

for(int i=1;i<=n;i++){

memcpy(sum[i], sum[i-1], sizeof sum[i]);

memcpy(pre[i], pre[i-1], sizeof pre[i]);

int c = s[i] - 'a';

sum[i][c] ++;

pre[i][c] = i;

if(!last[c]) cnt++;

last[c] = i;

}

// 预处理 f[i]

f[0] = n + 1;

for(int i=0;i<(1<<20);i++) {

for(int j=0;j<20;j++) {

if(i >> j & 1) {

f[i] = min(f[i ^ (1 << j)], last[j]);

break;

}

}

}

dfs(0, 1);

for(int i=0;i

for(int j=0;j

}

puts("");

}

J Luggage Lock

长度为 4 的密码锁，每次可以选择连续的一段数字，向上或者向下拨动 1。求从 \(a_0a_1a_2a_3\) 转动到 \(b_0b_1b_2b_3\) 的最小步数。

正解是任何一组转移都可以转换成从 \(0000\) 开始转到 \(abcd\)，这样可以 \(BFS\) 进行预处理然后 \(O(1)\) 回答。复杂度 \(O(T)\)。（每次转移考虑一个区间，向上或者向下转，共 20 种转移）

另外一种解法是考虑每个数字最终是向上转还是向下转（可以想想它不会既向上又向下），假设 \(a\) 到 \(b\) 可以向上转 \(x\) 步，也可以向下转 \(10-x\) 步，但只考虑这两种转移，即考虑 \(2^4\) 种方案并不能AC，有些数字可能会多转一圈。（不过还没有找到特殊情况），对拍的话发现需要考虑向上转 \(x,10+x\)，向上转 \(10-x,20-x\) 等四种方案，即 \(4^4=256\) 种方案，然后求最小值。复杂度 \(O(256T)\)

#include

using namespace std;

int T;

char s[10], t[10];

int a[10][5], b[10];

int res;

int sgn(int x) {

if (x == 0) return 0;

return x > 0 ? 1 : -1;

}

void dfs(int x) {

if (x == 5) {

int ans = 0;

for (int k = 1; k <= 4; k++)

{

if (b[k] == 0) continue;

int p = 4;

for (int j = k; j <= 4; j++)

if (sgn(b[k]) != sgn(b[j])) { p = j - 1; break; }

int last = 0;

for (int c = k; c <= p; c++)

{

int kk = 0;

if (b[c] < 0) kk = -b[c];

else kk = b[c];

if (kk >= last) ans += kk - last;

last = kk;

}

k = p;

}

res = min(res, ans);

return;

}

for (int i = 0; i < 4; i++) {

b[x] = a[x][i];

dfs(x + 1);

}

}

int main() {

scanf("%d", &T);

while (T--) {

res = 1e9;

scanf("%s %s", s + 1, t + 1);

for (int i = 1; i <= 4; i++) {

int c = s[i] - t[i];

if (c < 0) c = 10 + c;

a[i][0] = c;

a[i][1] = c - 10;

a[i][2] = c + 10;

a[i][3] = c - 20;

}

dfs(1);

printf("%d\n", res);

}

return 0;

}

H Line Graph Matching

\(n\) 个点，\(m\) 条边的带权无向连通图，将其转换为线图即，原图中的点变成边，边变成点，如果原图中两个边有公共点，那么就在线图中对应的两个点连相应的带权值的边，权值为原图两个边的权值和。求线图中的最大权点匹配，即选出来一些边，它们没有公共点并且权值和最大。

\(n\le 10^5,m\le 2*10^5\)

最大权点匹配要求每两个点需要有公共边，线图中的点即原图中的边，所以原问题可以转换为最大权边匹配。只要有两个边有公共点，就可以匹配。

题目给定的是一个连通图，如果边数为偶数，那么一定可以全部匹配，如果边数为奇数，那么需要选择一条边删去。（假想的结论）

但是删除边是有要求的，如果要删的是割边，那么需要保证删除之后每个连通块边的数量都是偶数。如果删的不是割边，则不需要任何限制。

#include

using namespace std;

typedef long long ll;

const int N = 100010, M = 400010;

int head[N], ver[M], nxt[M], edge[M], vis[N];

int dfn[N], low[N], cnt[N], n, m, tot, num;

int Min;

void add(int x, int y, int z) {

ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;

}

void tarjan(int x, int in_edge) {

dfn[x] = low[x] = ++num;

for (int i=head[x]; i; i = nxt[i]) {

int y = ver[i];

if (!dfn[y]) {

tarjan(y, i);

cnt[x] += cnt[y] + 1; // x 所在的连通分量边数增加

low[x] = min(low[x], low[y]);

if (low[y] > dfn[x]) {

if (cnt[y] % 2 == 0) { // 如果该边是割边，那么要判断 y 所在连通分量边数是否为偶数

Min = min(Min, edge[i]);

}

}

else { // 如果不是割边，则不需要限制

Min = min(Min, edge[i]);

}

}

else if(i != (in_edge ^ 1)) { // 如果出现返祖边，即搜索树中，子孙指向祖先的边

if(dfn[x] > dfn[y]) { // 这条边记录到时间戳更大的点上（只是为了防止重复计数）

cnt[x] ++;

}

low[x] = min(low[x], dfn[y]);

Min = min(Min, edge[i]);

}

}

}

int main() {

scanf("%d%d", &n, &m);

tot = 1;

ll res = 0;

for (int i = 1; i <= m; i++) {

int x, y, z;

scanf("%d%d%d", &x, &y, &z);

add(x, y, z); add(y, x, z);

res += z;

}

Min = 1e9; // 如果要删边，Min 记录可以删除的边中的最小权值

tarjan(1, 0);

if(m & 1) res -= Min;

cout << res << endl;

return 0;

}

I Linear Fractional Transformation

根据线性变换保交比性，可以直接推出答案。

#include

using namespace std;

typedef long double db;

const db PI = acos(-1.0);

struct Complex {

db x, y;

Complex(db _x = 0.0, db _y = 0.0) {

x = _x;

y = _y;

}

Complex operator - (const Complex& b) const {

return Complex(x - b.x, y - b.y);

}

Complex operator + (const Complex& b) const {

return Complex(x + b.x, y + b.y);

}

Complex operator * (const Complex& b) const {

return Complex(x * b.x - y * b.y, x * b.y + y * b.x);

}

Complex operator / (const Complex& p) const {

db a = x, b = y, c = p.x, d = p.y;

return Complex((a * c + b * d) / (c * c + d * d), (b * c - a * d) / (c * c + d * d));

}

bool operator == (const Complex& b) const {

return x == b.x && y == b.y;

}

void input() {

scanf("%Lf%Lf", &x, &y);

}

void output() {

printf("%.10Lf %.10Lf\n", x, y);

}

}z[5], w[5];

int main() {

int T;

cin >> T;

while (T--) {

for (int i = 1; i <= 3; i++) {

z[i].input();

w[i].input();

}

z[4].input();

bool flag = false;

for (int i = 1; i <= 3; i++) {

if (z[i] == z[4]) {

w[i].output();

flag = true;

break;

}

}

if (flag) continue;

Complex r = ((z[4] - z[1]) * (z[3] - z[2]) * (w[3] - w[1])) / ((z[4] - z[2]) * (z[3] - z[1]) * (w[3] - w[2]));

r = (w[1] - r * w[2]) / (Complex(1, 0) - r);

r.output();

}

return 0;

}

L Perfect Matchings

\(2n\) 个点的完全图，从中删除 \(2n-1\) 条边，保证这 \(2n-1\) 条边构成一棵树，求在剩下的图中找到 \(n\) 条无公共点的边的方案数。答案对 \(998244353\) 取模。

\(n\le 2000\)

问题可以转换为在 \(2n\) 个点的树上，匹配 \(n\) 个点对保证每个点对在树上没有边直接相连。

首先，\(2n\) 个点两两配对，方案数是 \(d_{n}={C_{2n}^nn!\over {2^n}}=\prod_{i=1}^n 2i-1\)

首先 \(C_{2n}^n\) ，分成两部分，然后第一部分的每个元素依次选择另一部分去配对，方案数是\(n!\)。然后由于每个点对是无序的，共 \(n\) 对，所以要除以 \(2^n\)。最后展开可以得到等式右侧。

考虑容斥模型，条件 \(P_i\) 表示第 \(i\) 条边不选，那么包含 \(P_i\) 条件的集合为 \(S_i\)，而 \(\overline S_i\) 表示不包含第 \(i\) 条边的方案数。假设共 \(m=2n-1\) 条边，那么我们要求的是：

\[\left|\bigcap_{i=1}^{m}S_i\right|=|U|-\left|\bigcup_{i=1}^m\overline{S_i}\right|

\]

该公式表示 \(m\) 条边都不选择的方案数，就是题目的答案。\(|U|\) 表示 \(2n\) 个点任意配对，每条边都没有限制。后者需要用容斥原理去求。

每次考虑 \(x\) 个条件 \(P_i\) 不被满足，即指定 \(x\) 条边一定要选，那么它对答案的贡献符号是 \((-1)^x\)。

我们不需要一一枚举每个大小为 \(x\) 的条件集合去求并，然后去求并集大小计算贡献，因为总的集合数量太多，而我们只对集合大小感兴趣。

所以，可以直接计算当指定 \(x\) 条边一定被选，而其他 \(2n-2x\) 个点任意匹配时的方案数。

设 \(f_i\) 表示指定 \(i\) 条边的方案数，然后还需要乘上 \(d_{n-i}\) 才行，表示其他 \(2*(n-i)\) 个点两两任意配对。这组方案数表示了所有大小为 \(i\) 的条件集合并的集合大小之和。

考虑 \(f_i\) 的求解，需要使用树形DP，具体的，我们需要用状态 \(f_{x,i,0}\) 表示 \(x\) 子树中，选择了 \(i\) 条边并且 \(x\) 没有被选择时的方案数，而 \(f_{x,i,1}\) 相应表示 \(x\) 被选择时的方案数。

所以就可以遍历 \(x\) 的每个子节点 \(y\)，更新：

\(f_{x,i,0}*(f_{y,j,0}+f_{y,j,1}) \Rightarrow f_{x,i+j,0}\)

\(f_{x,i,1}*(f_{y,j,0}+f_{y,j,1})\Rightarrow f_{x,i+j,1}\)

\(f_{x,i,0}*f_{y,j,0} \Rightarrow f_{x,i+j+1,1}\)

更新思路使用了背包的滚动压缩思想，所以枚举 \(i\) 和 \(j\) 时，需要倒序枚举。这个DP复杂度看起来是 \(O(n^3)\)，但因为 \(i\) 和 \(j\) 的遍历范围会根据 \(x\) 和 \(y\) 的子树大小有所限制，所以实际复杂度是 \(O(n^2)\)。

这里复杂度大概可以理解为树上每两个点配对去计算。

对于 \(x\) 的每个子节点构成的子树，每个\(sz_y\) 需要与 \(sz_x\) 遍历一遍，大概等于 \(sz_x\) 中的每个点与其他点配对的次数。

由于我对容斥的理解有限，所以这里多花了一点篇幅介绍容斥思想。

#include

using namespace std;

#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)

#define per(i,j,k) for(int i=int(j);i>=int(k);i--)

typedef long long ll;

const int N = 4005, mod = 998244353;

int n;

vector g[N];

ll f[N][N][2], sz[N], p[N];

void dfs(int x, int fa = 0){

f[x][0][0] = sz[x] = 1;

for(auto &y : g[x]) {

if(y == fa) continue;

dfs(y, x);

for(int i = sz[x] / 2; i >= 0; i--) {

for(int j = sz[y] / 2; j >= 0; j--){

if(j > 0) {

(f[x][i + j][0] += f[x][i][0] * (f[y][j][1] + f[y][j][0]) % mod) %= mod;

(f[x][i + j][1] += f[x][i][1] * (f[y][j][1] + f[y][j][0]) % mod) %= mod;

}

(f[x][i + j + 1][1] += f[x][i][0] * f[y][j][0] % mod) %= mod;

}

}

sz[x] += sz[y];

}

}

int main(){

scanf("%d", &n);

for(int i=1;i<2*n;i++){

int u, v;

scanf("%d%d", &u, &v);

g[u].push_back(v);

g[v].push_back(u);

}

dfs(1);

ll res = 0;

p[0] = 1;

for(int i=1;i<=n;i++) p[i] = p[i-1] * (2 * i - 1) % mod;

for(int i=0;i<=n;i++){

if(i & 1) (res -= (f[1][i][0] + f[1][i][1]) * p[n - i] % mod) %= mod;

else (res += (f[1][i][0] + f[1][i][1]) * p[n - i] % mod) %= mod;

}

printf("%lld\n", (res + mod) % mod);

}

M String Problem

对于字符串的每个前缀，输出其字典序最大的子串。只需要输出左右端点即可。

长度 \(10^6\)

第一种做法是使用后缀自动机。第二种是 KMP 自动机。

具体后面补，贴一个KMP代码

#include

using namespace std;

const int N = 1000010;

int nxt[N];

char s[N];

int main(){

scanf("%s", s+1);

int n = strlen(s + 1);

int head = 1, len = 1;

printf("%d %d\n", 1, 1);

for(int i=2;i<=n;i++){

if(s[i] > s[head]) {

head = i, len = 1;

printf("%d %d\n", head, head);

continue;

}

while(nxt[len] != 0 && s[head + nxt[len]] < s[i]) {

head = head + len - nxt[len];

len = nxt[len];

}

if(s[head + nxt[len]] == s[i]) {

nxt[len + 1] = nxt[len] + 1;

len ++;

} else if(s[head + nxt[len]] > s[i]) {

nxt[++len] = 0;

}

printf("%d %d\n", head, head + len - 1);

}

return 0;

}