信息学知识点测评-省选级别
信息学知识点测评-省选级别
链接：信息学知识点测评-省选级别
A：警察与小偷
给你一个有向图，每个点只有一条出边。
然后有警察和小偷分别在一个点上，然后警察小偷轮流操作，每次可以选择不动或者走向出边连接的点。
然后问你两者都在最优策略下警察是否能追上小偷。
思路
比赛的时候：
直接缩点然后判几种情况：在同一个点，走一步能到，路上没有碰到大于
2
2
2 的环。
然后其实最后一个就是直接看最后的那个环（因为只有那个位置有环）的大小即可。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node {
int to, nxt;
}e[2001], e_[2001];
int T, n, a, b, p[2001], tot, tmp;
int le[2001], KK, in[2001], sz[2001];
int dfn[2001], low[2001], sta[2001];
int le_[2001], KK_;
bool rd[2001];
void Init() {
tot = n; KK = 0; KK_ = 0;
memset(le, 0, sizeof(le));
memset(le_, 0, sizeof(le_));
memset(in, 0, sizeof(in));
memset(sz, 0, sizeof(sz));
sta[0] = 0; tmp = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(rd, 0, sizeof(rd));
}
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void add_(int x, int y) {
e_[++KK_] = (node){y, le_[x]}; le_[x] = KK_;
}
void tarjan(int now) {
dfn[now] = low[now] = ++tmp;
sta[++sta[0]] = now;
for (int i = le[now]; i; i = e[i].nxt)
if (!dfn[e[i].to]) tarjan(e[i].to), low[now] = min(low[now], low[e[i].to]);
else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);
if (low[now] == dfn[now]) {
tot++; in[now] = tot; sz[tot] = 1;
while (sta[sta[0]] != now) {
in[sta[sta[0]]] = tot; sz[tot]++; sta[0]--;
}
sta[0]--;
}
}
bool get_yes(int now) {
if (now == in[b]) {
rd[now] = 1; return 1;
}
for (int i = le_[now]; i; i = e_[i].nxt) {
if (get_yes(e_[i].to)) {
rd[now] = 1;
return 1;
}
}
return 0;
}
bool dfs(int now, bool mt) {
if (now == in[b]) mt = 1;
if (mt && sz[now] > 2) return 0;
for (int i = le_[now]; i; i = e_[i].nxt)
if (mt || rd[e_[i].to]) {
if (!dfs(e_[i].to, mt)) return 0;
}
return 1;
}
int main() {
scanf("%d", &T);
while (T--) {
Init();
scanf("%d %d %d", &n, &a, &b);
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
add(i, p[i]);
}
if (p[a] == b || a == b) {
printf("Yes\n"); continue;
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++)
if (in[i] != in[p[i]]) add_(in[i], in[p[i]]);
if (!get_yes(in[a])) {
printf("No\n"); continue;
}
if (dfs(in[a], 0)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
B：序列与操作
给你一个数组，每次问你一个区间，你要把它用最小花费变成
0
0
0。
有两种操作：把一个区间的数减一，费用是区间长度。
把一个区间的数变成
0
0
0，费用是里面每个数的乘积。
思路
其实不难看出我们可以把一个位置变成
0
0
0，然后选全部区间让它变成
0
0
0，因为乘起来有个
0
0
0 所以费用变成了
0
0
0。
那我们就搞个 ST 表求区间最小值即可。
代码
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int n, q, a[1000001], log2[1000001], f[1000001][21], l, r;
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[i][0] = a[i];
log2[0] = -1;
for (int i = 1; i <= n; i++) log2[i] = log2[i >> 1] + 1;
for (int i = 1; i <= log2[n]; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
while (q--) {
scanf("%d %d", &l, &r);
int k = log2[r - l + 1];
printf("%d\n", min(f[l][k], f[r - (1 << k) + 1][k]));
}
return 0;
}
C：动物与游戏
有一棵树，然后每个点有有个动物有若干概率会进来。
然后每个参加的动物每次会往根节点走一步。
然后问你对于每个点的动物，如果它参加，它期望能走到的点有多少个是首次被走到的（如果一个点同时被其它动物走到也算它走到）。
思路
我们考虑用树链剖分。
你会发现可能会抢它位置的就是深度比它小的，然后抢的距离是一串从根的路径，下面的点是它们两个的 LCA。
那我们可以按深度来依次搞每个点，把同一个深度的一起搞。
然后你不要管 LCA，直接用熟练剖分：
修改就直接修改到根的链上乘上不参加的几率，即这些部分要占有都要这个点不参加。
然后询问就询问到根的链，每个点的占有期望加起来。
代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 998244353
using namespace std;
struct node {
int to, nxt;
}e[200001];
int n, x, y, le[100001], KK, tmp;
int deg[100001], fa[100001], sz[100001];
int son[100001], top[100001], dfn[100001];
int xl[100001];
ll ans[100001], inv100, a[100001];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
void dfs1(int now, int father) {
deg[now] = deg[father] + 1; fa[now] = father;
sz[now] = 1;
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father) {
dfs1(e[i].to, now);
sz[now] += sz[e[i].to];
if (sz[e[i].to] > sz[son[now]]) son[now] = e[i].to;
}
}
void dfs2(int now, int father) {
dfn[now] = ++tmp;
if (son[now]) {
top[son[now]] = top[now];
dfs2(son[now], now);
}
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father && e[i].to != son[now]) {
top[e[i].to] = e[i].to;
dfs2(e[i].to, now);
}
}
bool cmp(int x, int y) {
return deg[x] < deg[y];
}
struct XD_tree {
ll val[100001 << 2], lzy[100001 << 2];
void build(int now, int l, int r) {
val[now] = r - l + 1; lzy[now] = 1;
if (l == r) return ; int mid = (l + r) >> 1;
build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
}
void up(int now) {
val[now] = (val[now << 1] + val[now << 1 | 1]) % mo;
}
void down(int now) {
if (lzy[now] == 1) return ;
val[now << 1] = val[now << 1] * lzy[now] % mo;
val[now << 1 | 1] = val[now << 1 | 1] * lzy[now] % mo;
lzy[now << 1] = lzy[now << 1] * lzy[now] % mo;
lzy[now << 1 | 1] = lzy[now << 1 | 1] * lzy[now] % mo;
lzy[now] = 1;
}
void cheng(int now, int l, int r, int L, int R, ll va) {
if (L <= l && r <= R) {
val[now] = val[now] * va % mo;
lzy[now] = lzy[now] * va % mo;
return ;
}
down(now); int mid = (l + r) >> 1;
if (L <= mid) cheng(now << 1, l
上一篇：
HR常用的人才测评工具，测什么，怎么测？
推荐阅读