CodePlus 第五次网络赛掐指会算

本文主要是介绍CodePlus 第五次网络赛掐指会算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

失踪人口暂时回归。
临近 NOIP 了，退役选手准备打一打 Div.2 来练练手（~~应该不是天气冷了，没衣服穿了~~ ）
游戏体验差，OJ 又和第一次一样卡了半天。

T1 我有矩阵，你有吗？

根据异或的性质，不难发现 $A$ 矩阵的每行每列最多只能异或一次。
所以我们可以假设 $A$ 矩阵的第一行是否被异或了，然后把所有状态递推出来，最后判断一下是否符合题设。

#include <bits/stdc++.h>
using namespace std;
int F()
{int x = 0; char ch; bool minus = 0;while(ch = getchar(), (ch > '9' || ch < '0') && ch != '-');ch == '-' ? minus = 1 : x = ch - '0';while(ch = getchar(), ch <= '9' && ch >= '0') x = x * 10 + ch - '0';return minus ? -x : x;
}int n, m, x[1010], y[1010], A[1010][1010], B[1010][1010];
int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &A[i][j]);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &B[i][j]);for(int i = 1; i <= m; ++i) if(A[1][i] != B[1][i]) y[i] = 1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if((A[i][j] ^ y[j] ^ x[i]) != B[i][j]) x[i] ^= 1;bool flag = 0;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if((A[i][j] ^ x[i] ^ y[j]) != B[i][j])flag = 1;if(!flag){ puts("Koyi"); return 0; }memset(x, 0, sizeof(x)); memset(y, 0, sizeof(y));x[1] = 1;for(int i = 1; i <= m; ++i) if(A[1][i] == B[1][i]) y[i] = 1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if((A[i][j] ^ y[j] ^ x[i]) != B[i][j]) x[i] ^= 1;flag = 1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)if((A[i][j] ^ x[i] ^ y[j]) != B[i][j])flag = 1;if(!flag){ puts("Koyi"); return 0; }puts("Budexing");return 0;
}

T2 逻辑树

一开始没看到在询问的都是叶结点，想了半天。

我想到的是一种构造方式，这种构造方式可以保证所有询问序列都是必要的，且根结点的取值一定为 $1$ 。

假设只有三个点（一个根和两个叶子， $a$ 点为先询问的叶子， $b$ 为后询问的），假设根的运算符为 and ，那么 $a$ 显然要取值为 $1$ ，才能保证询问 $b$ 时不会跳过，若为 or，则 $a$ 要为 $0$ ，按照这样的取值，根结点的取值就依赖于 $b$ 了。

如果有很多点，我们可以按照询问的叶子的顺序，每次找到这个叶子的祖先中第一个取值还未被确定的点（即这个点的取值不依赖与任意一个叶子），然后如果是 and，则该叶子取值为 $1$ ，为 or 则为 $0$ 。

需要注意的是如果是最后一个叶子，那么对应的祖先一定是根结点，而此时根结点的取值依赖与最后一个叶子的取值，所以最后一个叶子取值为 $1$ 。

这样做的复杂度为 $O (n)$ ，应为每一个点都只会被找两次。

#include <bits/stdc++.h>
using namespace std;
#define Min(_A, _B) (_A < _B ? _A : _B)
#define Max(_A, _B) (_A > _B ? _A : _B)
int F()
{int x = 0; char ch; bool minus = 0;while(ch = getchar(), (ch > '9' || ch < '0') && ch != '-');ch == '-' ? minus = 1 : x = ch - '0';while(ch = getchar(), ch <= '9' && ch >= '0') x = x * 10 + ch - '0';return minus ? -x : x;
}const int MaxN = 500010;
int Next[MaxN << 2], Point[MaxN << 1], To[MaxN << 2], q, P[MaxN << 1];
void Add(int u, int v)
{Next[++q] = Point[u]; Point[u] = q; To[q] = v;Next[++q] = Point[v]; Point[v] = q; To[q] = u;
}
int N, f[MaxN << 1][2], p[MaxN << 1][2], w[MaxN << 1], l[MaxN << 1], r[MaxN << 1], fa[MaxN << 1];
void dfs(int u, int from)
{fa[u] = from;for(int j = Point[u]; j; j = Next[j]) if(To[j] != from){if(!l[u]) l[u] = To[j]; else r[u] = To[j];dfs(To[j], u);}
}
int ans[MaxN], pre[MaxN], Q[MaxN << 1], cnt;
bool vis[MaxN];
int find(int u){ return u == pre[u] ? u : pre[u] = find(pre[u]); }
int main()
{scanf("%d", &N);for(int i = 1; i < N; ++i) scanf("%d", &w[i + N]);for(int i = 1; i <= 2 * N - 2; ++i) Add(F(), F());for(int i = 1; i <= N; ++i) P[i] = F();dfs(N + 1, 0);for(int i = 1; i <= N; ++i) pre[i] = i;for(int i = 1; i <= N; ++i){vis[P[i]] = 1;int t = P[i];while(fa[t] && vis[l[fa[t]]] && vis[r[fa[t]]]) {t = fa[t];vis[t] = 1;}if(fa[t]) ans[P[i]] = !w[fa[t]];else ans[P[i]] = 1;}for(int i = 1; i <= N; ++i) printf("%d", ans[i]);return 0;
}

T3 监控中心

认真分析题目发现，题目其实是给定一张图，图中的每个点要么属于 $A$ ，要么属于 $B$ ，告诉你哪些边连接着不同集合中的元素，求 $∣ A ∣$ 。

首先看子任务 $1$ ，一条链。我们发现如果有连续的几个 $A$ 中的元素被夹在 $B$ 中，那么我们可以利用后缀和的方式，将两个边界处的元素的位置相减，得到被夹在中间的 $A$ 中元素的个数。

再来看子任务 $2, 3$ ，一棵树。道理和子任务 $1$ 是类似的，我们只需要将后缀和改为子树和，然后也可以利用加减来得出元素的个数。需要注意你求的集合是否为 $A$ 。

子任务 $4$ ，一张图。找出任意的生成树，按照树来做。因为图给出的边有很多是没有价值的，多余的。

#include <bits/stdc++.h>
using namespace std;
int F()
{int x = 0; char ch; bool minus = 0;while(ch = getchar(), (ch > '9' || ch < '0') && ch != '-');ch == '-' ? minus = 1 : x = ch - '0';while(ch = getchar(), ch <= '9' && ch >= '0') x = x * 10 + ch - '0';return minus ? -x : x;
}
#define Abs(_A) (_A > 0 ? _A : -(_A))
const int MaxN = 1000010, MaxM = 2500010;
int n, m, Q[10000010];
struct Edge { int u, v; } e[MaxM];
int Next[MaxN << 1], To[MaxN << 1], Point[MaxN], q;
bool vis[MaxM];
void Add(int u, int v)
{Next[++q] = Point[u]; Point[u] = q; To[q] = v;Next[++q] = Point[v]; Point[v] = q; To[q] = u;
}
int l[MaxN], sum[MaxN], dfn_index;
void dfs(int u, int from)
{l[u] = ++dfn_index; ++sum[u];for(int j = Point[u]; j; j = Next[j]) if(To[j] != from){dfs(To[j], u);sum[u] += sum[To[j]];}
}
int pre[MaxN];
int find(int u){ return u == pre[u] ? u : pre[u] = find(pre[u]); }
int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= m; ++i) e[i] = (Edge){F(), F()};for(int i = 1; i <= n; ++i) pre[i] = i;for(Edge *i = e + 1; i <= e + m; ++i){int X = find(i->u), Y = find(i->v);if(X != Y){pre[X] = Y;Add(i->u, i->v);vis[i - e] = 1;}}dfs(1, 0);int q;scanf("%d", &q);for(int i = 1; i <= q; ++i){int c, tot = 0, pos = 0, tmp = 2147483647; scanf("%d", &c);for(int j = 1; j <= c; ++j) {scanf("%d", &Q[j]);if(!vis[Abs(Q[j])]) continue;if(l[e[Abs(Q[j])].u] < tmp) tmp = l[e[Abs(Q[j])].u], pos = e[Abs(Q[j])].u;if(l[e[Abs(Q[j])].v] < tmp) tmp = l[e[Abs(Q[j])].v], pos = e[Abs(Q[j])].v;}bool flag = 1;for(int j = 1; j <= c; ++j){int u, v;if(!vis[Abs(Q[j])]) continue;if(Q[j] > 0) u = e[Q[j]].u, v = e[Q[j]].v;if(Q[j] < 0) u = e[-Q[j]].v, v = e[-Q[j]].u;if(pos == v) flag = 0;if(l[u] < l[v]) tot -= sum[v];else tot += sum[u];}if(!flag) tot = n - tot;printf("%d\n", Abs(tot));}return 0;
}