「模拟测试」20171024

T1 建设图

给出一个无向图,求最少添加多少条边使得,无论删掉哪条边任意两点都可以互相到达。

题解

首先对于在边双连通分量中的点来说,相互连边是不会减少桥的个数的,所以我们先缩点。

观察一些特殊数据,我们可以得到答案为 $\lfloor \frac {\text{leaf} + 1} {2} \rfloor$,证明如下:

考虑我们每次找两个叶子节点连边,但是如果随便找的话,连边之后重缩点可能会出现新的叶子。

T1 建设图

我们将 $4, 5$ 号结点连起来,再缩点,就会产生新的叶子节点。
我们发现这种情况只会出现在两个叶子节点间的路径上只有至多一条支链的情况下。
如这种图就是两条支链,我们连接 $1, 4$,并不会产生新的叶子节点。

T1 建设图

下面考虑至少有 $4$ 个叶子的情况,选 $4$ 个,设为 $A, B, C. D$。首先考察 $A$ 到 $B$ 的路径和 $C$ 到 $D$ 的路径,如果有一条路径上其他边至少 $2$ 条,则缩这两个点可以减少两个叶子。
假设 $A$ 到 $B$ 和 $C$ 到 $D$ 的路径上都只有 $1$ 条其他边(不能没有,否则不连通)。

T1 建设图

如图所示,$AD$ 路径上至少有两条其他边,于是建一条连接 $AD$ 的边可以删去两个叶子。

边界情况:

  1. $\text{leaf} = 1$,不需要边
  2. $\text{leaf} = 2$,链,一条边
  3. $\text{leaf} = 3$,需要两条边

所以我们按照上述方式选取,可以保证不出现新叶子。
所以结论就是:

$\text{leaf} = 1$,答案为 $0$,否则为 $\lfloor \frac {\text{leaf} + 1} {2} \rfloor$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「SuperOJ 2007」建设图 24-10-2017
* 缩点
* @author xehoth
*/
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline bool read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return false;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
return true;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
const int MAXN = 100010;
std::vector<int> edge[MAXN + 1];
inline void addEdge(const int u, const int v) {
edge[u].push_back(v), edge[v].push_back(u);
}
typedef std::vector<int>::iterator Iterator;
int low[MAXN + 1], dfn[MAXN + 1], scc[MAXN + 1], cnt, deg[MAXN + 1], idx;
std::vector<int> st;
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx, st.push_back(u);
register bool flag = 0;
register int v;
for (register int i = 0; i < edge[u].size(); i++) {
if ((v = edge[u][i]) == fa && !flag) {
flag = 1;
continue;
}
if (!dfn[v])
tarjan(v, u), low[u] = std::min(low[u], low[v]);
else
low[u] = std::min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
cnt++;
register int v;
do
v = st.back(), scc[v] = cnt, st.pop_back();
while (!st.empty() && v != u);
}
}
using IO::io;
inline void solve() {
register int n, m;
io >> n >> m;
for (register int i = 1, u, v; i <= m; i++) io >> u >> v, addEdge(u, v);
tarjan(1, 1);
for (register int i = 1; i <= n; i++)
for (register Iterator p = edge[i].begin(); p != edge[i].end(); p++)
if (scc[i] != scc[*p]) deg[scc[i]]++, deg[scc[*p]]++;
register int ans = 0;
for (register int i = 1; i <= cnt; i++)
if (deg[i] == 2) ans++;
io << (ans + 1) / 2;
}
}
int main() {
// freopen("graph.in", "r", stdin);
// freopen("graph.out", "w", stdout);
solve();
return 0;
}

T2 乘积

选择至多 $k$ 个 $n$ 以内的正整数乘起来,求乘积为无平方因子数的的取法的个数。

题解

首先 $70 \%$ 的数组直接打表就可以过了,对于 $100 \%$ 的数据,我们也可以考虑打表,这里记录一下如何压缩表。

令 $f[n][k]$ 为我们原始的表,我们观察到同一行的数是单调不减的,同时当出现一个数与前一个数相等后,后面的数都是这个数,所以我们可以从这个数开始忽略后面的数,同时由于单调性我们可以将这个数组差分,这样总位数少了一半多,此时我们的表只有 $90k$ 左右了。

我们又发现对于第一列的数来说,其差分后是没有效果的,我们考虑将这一列数单独提取出来,然后将这一列数差分,然后发现增量只会是 $0 / 1$,于是我们可以将这列数再状压,这时表只有 $75k$ 了。

然后我们将这张表压 char

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
inline char encode(int x) {
x += ' ';
if (x >= '"') x++;
if (x >= '\\') x++;
return x;
}
int decode(char x) {
if (x >= '\\') x--;
if (x >= '"') x--;
return x - ' ';
}
char s[1000000], *c = s;
inline void encode(int x, int p) {
register int cnt = 0;
static int buf[30];
for (register int i = 0; i < p; i++) buf[++cnt] = x % 93, x /= 93;
while (cnt) *c++ = encode(buf[cnt--]);
}
inline int decode(const char *s, int p) {
register int ret = 0;
for (register int i = 0; i < p; i++) ret = ret * 93 + decode(s[i]);
return ret;
}

然后就只剩 $20k$ 了,我们解表还原,回答询问就好了。

代码不贴了…

T3 Math

给定两个数字 $a, n$,求有多少个 $b$ 满足 $a ^ b \equiv b ^ a \pmod{2 ^ n}$

题解

打表可以发现:

$a$ 为奇数时,$b$ 一定为奇数,且 $b \equiv a \pmod{2 ^ n}$;$a$ 为偶数时 $b$ 一定为偶数,若 $b \geq n$,$b ^ a \equiv 0 \pmod{2 ^ n}$,否则直接暴力即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「SuperOJ 2009」Math 24-10-2017
*
* @author xehoth
*/
#include <bits/stdc++.h>
namespace {
int a, n, mod;
inline int modPow(int a, int b) {
register int ret = 1;
for (; b; b >>= 1, a = ((long long)a * a) & (mod - 1))
(b & 1) ? ret = ((long long)ret * a) & (mod - 1) : 0;
return ret;
}
inline void solveCase() {
mod = 1 << n;
if (a & 1) {
std::cout << "1\n";
return;
}
register int tmp = n / a;
if (tmp * a < n) tmp++;
register int ans = mod / (1 << tmp) - n / (1 << tmp);
for (register int i = 1; i <= n; i++)
if (modPow(a, i) == modPow(i, a)) ans++;
std::cout << ans << '\n';
}
inline void solve() {
register int T;
std::cin >> T;
while (T--) {
std::cin >> a >> n;
solveCase();
}
}
}
int main() {
// freopen("sample/1.in", "r", stdin);
solve();
return 0;
}
分享到