前言
这次的总体难度较高，T2 的正解时间复杂度到现在都没人严谨证明，T3 是国集的就离谱，T4 是 HNOI 的（无端鞭尸），然鹅 \(150\) 的“高分”还是很 \(**\)。
\(\text{Solution}\)
T1：出现次数超过一半的数
题意
给出一个含有 \(n(1\le n\le1000)\) 个整数的数组，请找出其中出现次数超过一半的数；若不存在，输出 \(\text{no}\)。数组中的数大于 \(-50\) 且小于 \(50\)。
思路
直接开桶即可，注意加粗部分，要整体平移，不然会 \(\rm RE\)。
\(\text{Code}\)
#include <iostream>
#include <cstdio>
using namespace std;
int a[1005], b[1005];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
b[a[i] + 50]++;
}
for (int i = 1; i <= n; i++)
{
if (b[a[i] + 50] > (n / 2))
{
printf("%d", a[i]);
return 0;
}
}
puts("no");
return 0;
}
拓展题目
来源
来源很搞笑，后排大佬在搜 T3 时看到洛谷题库上有这样一句话：
原《工资》重题请做2397
于是他搜了一下 P2397，然后：
P2397 yyy loves Maths VI (mode)
题意
同 T1，只不过保证有数量超过一半的数，所以不用输出 \(\text{no}\)（很关键）。
那么和 T1 不一样的地方在哪里呢？
对于 \(100\%\) 的数据，\(1\le n \le 2\times 10^6\)。
有人想水过，但我告诉你这空间是不够的。
内存限制：5.00MB
大草/kk
思路
既然不能开数组，那么怎么办呢？
这时，摩尔投票法出现了！
摩尔投票法 的主要思路是，记录当前最多的数 \(ans\) 及个数 \(cnt\)，若新输入的数 \(x\ne ans\)，则 \(cnt\gets cnt-1\)；若 \(x=ans\)，则 \(cnt\gets cnt+1\)。当 \(cnt=0\) 时，\(ans\gets x\)。最后答案就是 \(ans\)。
好吧显然不可能有人看懂。
举个例子：
有几个帮派正在比武，如 \(\text{Splay,FHQ-Treap,AVL}\) 等帮派，其中 \(\text{Splay}\) 帮派有 \(5\) 人，\(\text{FHQ}\) 帮派有 \(10\) 人，\(\text{AVL}\) 帮派有 \(3\) 人，那么显然 \(\text{FHQ}\) 帮派的人数超过了一半。
按照摩尔投票法开始模拟：
- \(\text{Splay}\;5\) 人；
- \(\text{FHQ}\) 来了 \(10\) 人，与 \(\text{Splay}\) 开始乱杀，一换一，\(\text{Splay}\) 全死光后，\(\text{FHQ}\) 还剩 \(5\) 人；
- \(\text{AVL}\) 来了 \(3\) 人，与 \(\text{FHQ}\) 开始乱杀，一换一，\(\text{AVL}\) 全死光后，\(\text{FHQ}\) 还剩 \(2\) 人；
战斗结束了！\(\text{FHQ}\) 还有 \(2\) 人，说明 \(\text{FHQ}\) 的人数超过了一半。
差不多就是这样，因为超过了一半，所以肯定比剩下所有数加起来还多。
但是这个算法好像不支持处理没有数量超过一半的数的情况。
\(\text{Code}\)
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n, ans = 0, cnt = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if (!cnt)
{
ans = x;
}
if (ans == x)
{
cnt++;
}
else
{
cnt--;
}
}
printf("%d\n", ans);
return 0;
}
T2：添边问题
题意
有 \(n\) 个互不相连的点，依次给出 \(t\) 条边和每条边的方向。 每给出一条边就要立即决定是否要加入这一条边，使得这张图始终是一张 \(\rm DAG\)（意思是：按顺序处理每条边，能加就加，让你模拟这个过程，自环不能加入）。计算在满足要求的情况下一共有多少条边没有被加入。注意 \(\rm DAG\) 是可以存在重边的。
思路
这里给出两种方法，都是建立在一个基础上的，即要加入边 \(<u,v>\) 时，判断从 \(v\) 出发是否能到 \(u\)，若能，说明加入 \(<u,v>\) 后会形成环，那就不能加入了。
- 题解方法：我们开一个 \(ok\) 数组记录从一点出发是否能到达另一点。加入 \(<u,v>\) 时，若 \(ok_{v,u}=true\)，说明 \(v\) 能到达 \(u\)， \(ans\gets ans+1,continue\) 即可。若 \(ok_{u,v}=true\)，说明 \(u\) 能到达 \(v\)，直接 \(continue\)。否则说明我们可以加 \(<u,v>\)，遍历 \(i=1\to n\)，若 \(ok_{i,u}=true\)，说明 \(i\) 能到达 \(u\)，记录在 \(a\) 数组里；若 \(ok_{v,i}=true\)，说明 \(v\) 能到达 \(i\)，记录在 \(b\) 数组里；连 \(<u,v>\)，说明 \(u\) 能到达 \(v\)，则 \(a\) 数组中的所有数都能到达 \(b\)，将 \(ok\gets true\) 即可。
- 记搜：考试时想出来了搜索，直接从 \(v\) 开始 \(\rm dfs\)，看能不能到达 \(u\) 即可，但考试时时间复杂度证错了，以为能 A，实际上时间复杂度为 \(\operatorname{O}(t\times(n+t))\)，只能拿到 \(40\) 分。机房大佬用记搜+玄学优化乱搞过了，主要用到了：开 \(vis\) 数组记录是否已经被搜到过，\(\rm dfs\) 多传 \(st\) 和 \(ed\) 参数，然后将 \(ok_{st,u}\gets true\)，在找子节点 \(v\) 时若 \(ok_{v,ed}=true\) 直接返回等。
关于本题时间复杂度：
我们要证明的就是往一张 \(\rm DAG\) 中最多加入多少条边仍然不出现环，经过学长们乱构造一通（但好像还是没人严谨证明）后发现在 \(n\) 级别，所以时间复杂度为 \(\operatorname{O}(tn)\)。
\(\text{Code}\)
题解方法
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 300;
bool vis[MAXN][MAXN];
vector<int> a, b;
int main()
{
int n, t, ans = 0;
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++)
{
vis[i][i] = true;
}
while (t--)
{
int u, v;
scanf("%d%d", &u, &v);
if (vis[v][u])
{
ans++;
continue;
}
if (vis[u][v])
{
continue;
}
a.clear(), b.clear();
for (int i = 1; i <= n; i++)
{
if (vis[i][u])
{
a.push_back(i);
}
if (vis[v][i])
{
b.push_back(i);
}
}
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < b.size(); j++)
{
vis[a[i]][b[j]] = true;
}
}
}
printf("%d\n", ans);
return 0;
}
记搜
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 300;
const int MAXM = 1e5 + 5;
int cnt;
int head[MAXN];
bool flag;
bool vis[MAXN], ok[MAXN][MAXN], g[MAXN][MAXN];
struct edge
{
int to, nxt;
}e[MAXM << 1];
void add(int u, int v)
{
e[++cnt] = edge{v, head[u]};
head[u] = cnt;
}
void dfs(int u, int st, int ed)
{
if (u == ed)
{
flag = true;
return;
}
vis[u] = true;
ok[st][u] = true;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (vis[v]) //如果到过就一样了
{
continue;
}
ok[u][v] = true;
if (ok[v][ed]) //直接返回
{
ok[u][ed] = true;
flag = true;
return;
}
dfs(v, st, ed);
}
}
int main()
{
int n, t, ans = 0;
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++)
{
ok[i][i] = true;
}
for (int i = 1; i <= t; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (g[u][v]) //重边
{
continue;
}
if (ok[v][u])
{
ans++;
continue;
}
flag = false;
dfs(v, v, u);
memset(vis, false, sizeof(vis));
if (flag)
{
ans++;
ok[v][u] = true;
}
else
{
g[u][v] = true;
add(u, v);
}
}
printf("%d\n", ans);
return 0;
}
T3：稳定婚姻
题意
不想介绍了太\(**\)了！
思路
接下来为大家介绍一下出场嘉宾，是 \(3\) 对 CP，分别是 sid_shi 和 zlq，xhj 和 wsy，yzh 和 cxr！（不要揍我啊\fad
突然，cxr 把 yzh 甩了找了 sid_shi，zlq 很生气，于是去找了 xhj，xhj 把 wsy 甩了。wsy 非常生气，去找了 yzh。
此时原图变成了这样：
若把红圈看成一个点，我们可以发现一个很有趣的现象：
这 \(3\) 个红圈构成了一个强连通！！！感谢出场嘉宾，请大家离场！！！有始有终，不死才怪
所以直接吧男和女对应成一个组，再看这些组是否构成了强连通即可。
读入比较麻烦，可以开一个 \(map\)。
\(\text{Code}\)
#include <iostream>
#include <cstdio>
#include <map>
#include <stack>
using namespace std;
const int MAXN = 10005;
const int MAXM = 20005;
int cnt, Time, scc;
int head[MAXN], dfn[MAXN], low[MAXN], c[MAXN], siz[MAXN];
bool ins[MAXN];
map<string, int> h;
stack<int> s;
struct edge
{
int to, nxt;
}e[MAXM];
void add(int u, int v)
{
e[++cnt] = edge{v, head[u]};
head[u] = cnt;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++Time;
s.push(u);
ins[u] = true;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (ins[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
scc++;
int v = 0;
while (u != v)
{
v = s.top();
s.pop();
ins[v] = false;
c[v] = scc;
siz[scc]++;
}
}
}
int main()
{
int n, tot = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
char u[10], v[10];
scanf("%s%s", u, v);
h[u] = i, h[v] = i; //map 映射一下
}
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
char u[10], v[10];
scanf("%s%s", u, v);
add(h[u], h[v]); //直接在组间建边
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
if (siz[c[i]] > 1) //只要出现了多个点构成的 SCC 就危了
{
puts("Unsafe");
}
else
{
puts("Safe");
}
}
return 0;
}
T4：矿场搭建
题意
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
思路
读题时需要注意的是，救援出口所在的挖煤点也有可能被炸♂，这样这个救援出口就废了。
我们先对原图进行点双缩点，然后考虑每个点双中割点的个数，设有 \(cnt\_cut\) 个割点，\(cnt\_notcut\) 个不是割点，至少需要设置 \(ans1\) 个救援出口，不同最少救援出口的设置方案总数为 \(ans2\)：
- \(cnt\_cut=0\)：在里面任选 \(2\) 点作救援出口，\(ans1\gets ans1+2,ans2\gets ans2\times\tbinom{n}{2}\)；
- \(cnt\_cut=1\)：在里面任选 \(1\) 点（非割点）作救援出口，若炸割点就用内部的救援出口，若炸救援出口就可以通过割点跑到另一个点双，\(ans1\gets ans1+1,ans2\gets ans2+(cnt\_notcut-cnt\_cut)=ans2+(cnt\_notcut-1)\)；
- \(cnt\_cut\ge2\)：无论哪个割点被炸都能通过另一个割点跑到另一个点双，啥都不用动。（关于我认为当图中的点双都有 \(2\) 个割点时输出 \(0\) 但答案为 \(2\) 想 hack 但没构造出来这件事）
\(\text{Code}\)
#include <iostream>
#include <cstdio>
#define int unsigned long long
using namespace std;
const int MAXN = 505;
int n, m, cnt, Time, rt, dcc, cnt_cut, cnt_notcut, ans1, ans2;
int head[MAXN], dfn[MAXN], low[MAXN], siz[MAXN], c[MAXN];
bool cut[MAXN];
struct edge
{
int to, nxt;
}e[MAXN << 1];
void add(int u, int v)
{
e[++cnt] = edge{v, head[u]};
head[u] = cnt;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++Time;
int flag = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v])
{
flag++;
if (u != rt || flag > 1)
{
cut[u] = true;
}
}
}
else
{
low[u] = min(low[u], dfn[v]);
}
}
}
void dfs(int u)
{
c[u] = dcc;
cnt_notcut++;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (cut[v] && c[v] != dcc)
{
cnt_cut++;
c[v] = dcc;
}
if (!c[v])
{
dfs(v);
}
}
}
void init()
{
n = cnt = Time = dcc = ans1 = 0;
ans2 = 1;
for (int i = 0; i < MAXN; i++)
{
head[i] = dfn[i] = c[i] = 0;
cut[i] = false;
}
}
signed main()
{
int t = 0;
while (scanf("%llu", &m), m)
{
init();
printf("Case %llu: ", ++t);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%llu%llu", &u, &v);
add(u, v);
add(v, u);
n = max(n, max(u, v));
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
tarjan(rt = i);
}
}
for (int i = 1; i <= n; i++)
{
if (c[i] || cut[i]) //是割点也要忽略
{
continue;
}
cnt_cut = cnt_notcut = 0;
dcc++;
dfs(i);
if (!cnt_cut)
{
ans1 += 2;
ans2 *= (cnt_notcut * (cnt_notcut - 1) >> 1);
}
else if (cnt_cut == 1)
{
ans1 += 1;
ans2 *= cnt_notcut;
}
}
printf("%llu %llu\n", ans1, ans2);
}
return 0;
}