加几道 L1 稍微难点的。
L1-009 N个数求和
题目链接
题意：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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n;
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int main()
{
scanf("%d", &n);
int a, b;
int c = 0, d = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d/%d", &a, &b);
c = a * d + b * c;
d = b * d;
int g = abs(gcd(c, d));
c /= g;
d /= g;
}
if (c < 0) {
putchar('-');
c = -c;
}
if (c / d || !c) printf("%d", c / d);
if (c > d && c % d) putchar(' ');
if (c % d) printf("%d/%d\n", c % d, d);
return 0;
}
|
L1-064 估值一亿的AI核心代码
题目链接
题意：根据题意修改字符串。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <sstream>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
string s;
int main()
{
int t;
scanf("%d", &t);
getchar();
while (t--) {
getline(cin, s);
cout << s;
printf("\nAI:");
for (int i = 0; i < (int)s.size(); ++i) {
if (isupper(s[i]) && s[i] != 'I') s[i] = tolower(s[i]);
else if (!isalnum(s[i])) s.insert(i++, " ");
if (s[i] == '?') s[i] = '!';
}
stringstream ss(s);
string str[1005];
int cnt = 0;
while (ss >> s) str[cnt++] = s;
if (!isalnum(str[0][0])) printf(" ");
for (int i = 0; i < cnt; ++i) {
if (!isalnum(str[i][0])) cout << str[i];
else if ((str[i] == "can" || str[i] == "could") && str[i+1] == "you") cout << " I " << str[i++];
else if (str[i] == "I" || str[i] == "me") cout << " you";
else cout << " " << str[i];
}
puts("");
}
return 0;
}
|
L2-001 紧急救援
题目链接
题意：$n(2\le n\le500)$ 个城市编号 $0\sim$，m 条道路，出发地 s，目的地 e，每个城市都有一定的救援队数目，求最短路径条数及召集的最多的救援队数量并输出 s 到 e 的路径中经过的城市编号。
num[i] 和 w[i] 分别表示出发点到结点 i 最短路径条数，召集的最多的救援队数目，pre[i] 表示最短路径结点 i 的前一个结点。最后修改一下松弛方程即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 505, M = 3e5;
int n, m, s, e, tot;
int pre[N], num[N], weight[N], head[N];
int d[N], w[N], vis[N];
int ver[M], edge[M], nxt[M];
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
priority_queue<P, vector<P>, greater<P> > q;
memset(vis, 0, sizeof(vis));
memset(d, 0x3f, sizeof(d));
d[s] = 0;
num[s] = 1;
w[s] = weight[s];
q.push(P(0, s));
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (d[y] > d[x] + edge[i]) {
d[y] = d[x] + edge[i];
num[y] = num[x];
w[y] = w[x] + weight[y];
pre[y] = x;
q.push(P(d[y], y));
}
else if (d[y] == d[x] + edge[i]) {
num[y] += num[x];
if (w[y] < w[x] + weight[y]) {
w[y] = w[x] + weight[y];
pre[y] = x;
}
}
}
}
}
void print(int x) {
if (x == s) {
printf("%d", x);
return;
}
print(pre[x]);
printf(" %d", x);
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &e);
for (int i = 0; i < n; ++i) scanf("%d", &weight[i]);
while (m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
dijkstra();
printf("%d %d\n", num[e], w[e]);
print(e);
puts("");
return 0;
}
|
L2-002 链表去重
题目链接
题意：给出带整数值键值的链表 L，把绝对值重复的键值结点删除，输出去重后链表与删除的链表。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
struct node {
int key, nxt;
}a[N];
int s, n;
int cnt1, cnt2;
int vis[N], ans1[N], ans2[N];
int main()
{
scanf("%d%d", &s, &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
scanf("%d%d", &a[x].key, &a[x].nxt);
}
for (int i = s; ~i; i = a[i].nxt) {
int val = abs(a[i].key);
if (!vis[val]) {
vis[val] = 1;
ans1[++cnt1] = i;
}
else ans2[++cnt2] = i;
}
for (int i = 1; i <= cnt1; ++i) {
if (i == cnt1) printf("%05d %d -1\n", ans1[i], a[ans1[i]].key);
else printf("%05d %d %05d\n", ans1[i], a[ans1[i]].key, ans1[i+1]);
}
for (int i = 1; i <= cnt2; ++i) {
if (i == cnt2) printf("%05d %d -1\n", ans2[i], a[ans2[i]].key);
else printf("%05d %d %05d\n", ans2[i], a[ans2[i]].key, ans2[i+1]);
}
return 0;
}
|
L2-003 月饼
题目链接
题意：已知 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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;
struct mooncake {
double amount, price, unit;
friend bool operator <(mooncake a, mooncake b) {
return a.unit > b.unit;
}
}a[N];
int n, d;
int main()
{
scanf("%d%d", &n, &d);
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i].amount);
for (int i = 1; i <= n; ++i) {
scanf("%lf", &a[i].price);
a[i].unit = a[i].price / a[i].amount;
}
sort(a + 1, a + n + 1);
double ans = 0;
for (int i = 1; i <= n; ++i) {
if (a[i].amount <= d) {
ans += a[i].price;
d -= a[i].amount;
}
else {
ans += a[i].unit * d;
break;
}
}
printf("%.2lf\n", ans);
return 0;
}
|
L2-004 这是二叉搜索树吗？
题目链接
题意：给出一个长度为 n 的序列，若是二叉搜索树或镜像前序遍历的结果，输出 YES 及后序遍历结果，否则输出 NO。
假设是二叉搜索树，根据性质求出其后序遍历，长度小于 n 用镜像再试一次，长度仍然小于 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
50
51
52
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;
int n, cnt, isMirror;
int preord[N], postord[N];
void getpost(int root, int tail) {
if (root > tail) return;
int p = root + 1, q = tail;
if (!isMirror) {
while (p <= tail && preord[root] > preord[p]) p++;
while (q > root && preord[root] <= preord[q]) q--;
} else {
while (p <= tail && preord[root] <= preord[p]) p++;
while (q > root && preord[root] > preord[q]) q--;
}
if (p - q != 1) return;
getpost(root + 1, q);
getpost(p, tail);
postord[++cnt] = preord[root];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &preord[i]);
getpost(1, n);
if (cnt != n) {
isMirror = 1;
cnt = 0;
getpost(1, n);
}
if (cnt == n) {
puts("YES");
printf("%d", postord[1]);
for (int i = 2; i <= n; ++i) {
printf(" %d", postord[i]);
}
puts("");
}
else puts("NO");
return 0;
}
|
L2-005 集合相似度
题目链接
题意：两个整数集合相似度定义为：$N_c/N_t\times100%$，其中 $N_c$ 是两个集合都有的不相等整数个数，$N_t$ 是两个集合一共有的不相等整数个数，求任意一对集合的相似度。
直接用 set 存储即可不考虑重复元素，将一个集合如元素个数作为 $N_t$，遍历另一个集合每一个元素寻找前一个集合是否有该元素，有则 $N_c$++，否则 $N_t$++。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 55;
int n, m, k;
set<int> s[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &m);
int x;
for (int j = 1; j <= m; ++j) {
scanf("%d", &x);
s[i].insert(x);
}
}
scanf("%d", &k);
int a, b;
for (int i = 1; i <= k; ++i) {
scanf("%d%d", &a, &b);
int nc = 0, nt = s[b].size();
for (auto it = s[a].begin(); it != s[a].end(); ++it) {
if (s[b].find(*it) == s[b].end()) nt++;
else nc++;
}
double ans = 1.0 * nc / nt * 100;
printf("%.2lf%%\n", ans);
}
return 0;
}
|
L2-006 树的遍历
题目链接
题意：给出二叉树的后序遍历序列和中序遍历序列，输出层序遍历序列。
法一：先建树再用 bfs 输出层序遍历序列。法二：与求先序遍历类似，结点加序号对应值存在 map 中直接输出。
法一
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 35;
int n, tot;
int inord[N], postord[N], level[N];
int lch[N], rch[N];
int build(int l1, int r1, int l2, int r2) {
if (l1 > r1) return 0;
int rt = postord[r2];
int p = l1;
while (inord[p] != rt) p++;
int cnt = p - l1;
lch[rt] = build(l1, p - 1, l2, l2 + cnt - 1);
rch[rt] = build(p + 1, r1, l2 + cnt, r2 - 1);
return rt;
}
void LevelOrder() {
queue<int> q;
q.push(postord[n]);
while (!q.empty()) {
int x = q.front();
q.pop();
level[++tot] = x;
if (lch[x]) q.push(lch[x]);
if (rch[x]) q.push(rch[x]);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &postord[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &inord[i]);
build(1, n, 1, n);
LevelOrder();
printf("%d", level[1]);
for (int i = 2; i <= tot; ++i) printf(" %d", level[i]);
puts("");
return 0;
}
|
法二
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 35;
int n;
int inord[N], postord[N];
map<int, int> level;
void pre(int rt, int l, int r, int index) {
if (l > r) return;
int p = l;
while (p < r && inord[p] != postord[rt]) p++;
level[index] = postord[rt];
pre(rt - 1 - r + p, l, p - 1, index<<1);
pre(rt - 1, p + 1, r, index<<1|1);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &postord[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &inord[i]);
pre(n, 1, n, 1);
auto it = level.begin();
printf("%d", it->second);
while (++it != level.end()) printf(" %d", it->second);
puts("");
return 0;
}
|
L2-007 家庭房产
题目链接
题意：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
并查集+模拟即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005, M = 10005;
struct person {
int id, num, area;
}a[N];
struct node {
int id, people, flag;
double avgnum, avgarea;
friend bool operator <(node a, node b) {
if (a.avgarea != b.avgarea) return a.avgarea > b.avgarea;
else return a.id < b.id;
}
}ans[M];
int n, k, cnt;
int fa[M], vis[M];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx > fy) fa[fx] = fy;
else if (fx < fy) fa[fy] = fx;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < M; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i) {
int p1, p2;
scanf("%d%d%d%d", &a[i].id, &p1, &p2, &k);
vis[a[i].id] = 1;
if (~p1) {
vis[p1] = 1;
unite(a[i].id, p1);
}
if (~p2) {
vis[p2] = 1;
unite(a[i].id, p2);
}
for (int j = 1; j <= k; ++j) {
int x;
scanf("%d", &x);
vis[x] = 1;
unite(a[i].id, x);
}
scanf("%d%d", &a[i].num, &a[i].area);
}
for (int i = 1; i <= n; ++i) {
int id = find(a[i].id);
ans[id].id = id;
ans[id].avgnum += a[i].num;
ans[id].avgarea += a[i].area;
ans[id].flag = 1;
}
for (int i = 0; i < M; ++i) {
if (vis[i])
ans[find(i)].people++;
if (ans[i].flag)
cnt++;
}
for (int i = 0; i < M; ++i) {
if (ans[i].flag) {
ans[i].avgnum = 1.0 * ans[i].avgnum / ans[i].people;
ans[i].avgarea = 1.0 * ans[i].avgarea / ans[i].people;
}
}
sort(ans, ans + M);
printf("%d\n", cnt);
for (int i = 0; i < cnt; ++i) {
printf("%04d %d %.3lf %.3lf\n", ans[i].id, ans[i].people, ans[i].avgnum, ans[i].avgarea);
}
return 0;
}
|
L2-008 最长对称子串
题目链接
题意：求字符串的最长回文子序列。
用 gets 会编译错误，求最长回文子序列直接用 Manacher 算法，$p[i]$ 以 $s[i]$ 为中心的最长回文串半径，$maxr$ 为所有已找到回文串的最右端，中心为 $mid$，$i$ 关于 $mid$ 对称点 $2 * mid-i$，则 $p[i]=\min(p[2 * mid-i],maxr-i)$，之后再进行扩展。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2e3 + 5;
int n, ans;
int p[N];
char s[N];
string str;
void manacher() {
s[0] = '$', s[1] = '#';
for (int i = 0; i < n; ++i) {
s[(i<<1)+2] = str[i];
s[(i<<1)+3] = '#';
}
n = (n<<1) + 2; s[n] = 0;
int maxr = 0, mid = 0;
for (int i = 1; i < n; ++i) {
if (maxr > i) p[i] = min(p[2*mid-i], maxr - i);
else p[i] = 1;
for (; s[i+p[i]] == s[i-p[i]]; ++p[i]);
if (i + p[i] > maxr) { maxr = i + p[i]; mid = i; }
}
}
int main()
{
getline(cin, str);
n = str.length();
manacher();
for (int i = 1; i < n; ++i) ans = max(ans, p[i]);
printf("%d\n", ans - 1);
return 0;
}
|
L2-009 抢红包
题目链接
题意：给出 $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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
struct node {
int id, num, money;
friend bool operator <(node a, node b) {
if (a.money != b.money) return a.money > b.money;
else if (a.num != b.num) return a.num > b.num;
else return a.id < b.id;
}
}a[N];
int n, k;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
a[i].id = i;
scanf("%d", &k);
int x, y;
for (int j = 1; j <= k; ++j) {
scanf("%d%d", &x, &y);
a[i].money -= y;
a[x].money += y;
a[x].num++;
}
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
printf("%d %.2lf\n", a[i].id, 1.0 * a[i].money / 100);
}
return 0;
}
|
L2-010 排座位
题目链接
题意：n 个人，m 组关系，k 组询问，每次询问 x, y 是否能被安排同席。
朋友的朋友也是朋友，为传递关系，用并查集只需合并朋友关系，敌人关系用二维数组标记即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105;
int n, m, k;
int fa[N], r[N][N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) fa[fx] = fy;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) fa[i] = i;
int x, y, z;
while (m--) {
scanf("%d%d%d", &x, &y, &z);
if (z == 1) unite(x, y);
else r[x][y] = r[y][x] = 1;
}
for (int i = 1; i <= k; ++i) {
scanf("%d%d", &x, &y);
if (find(x) == find(y)) {
if (!r[x][y]) puts("No problem");
else puts("OK but...");
}
else {
if (!r[x][y]) puts("OK");
else puts("No way");
}
}
return 0;
}
|
L2-011 玩转二叉树
题目链接
题意：已知二叉树的中序遍历序列和前序遍历序列，求该树翻转后的层序遍历序列。
类似第 6 题，有点奇怪为啥法一 clang 会 RE 一个点。
法一
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 35;
int n, tot;
int preord[N], inord[N], level[N];
int lch[N], rch[N];
int build(int l1, int r1, int l2, int r2) {
if (l1 > r1 || l2 > r2) return 0;
int rt = preord[l1], p = l2;
while (inord[p] != rt) p++;
int cnt = p - l2;
lch[rt] = build(l1 + 1, l1 + cnt, l2, p - 1);
rch[rt] = build(l1 + cnt + 1, r1, p + 1, r2);
return rt;
}
void LevelOrder() {
queue<int> q;
q.push(preord[1]);
while (!q.empty()) {
int x = q.front();
q.pop();
level[++tot] = x;
if (rch[x]) q.push(rch[x]);
if (lch[x]) q.push(lch[x]);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &inord[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &preord[i]);
build(1, n, 1, n);
LevelOrder();
printf("%d", level[1]);
for (int i = 2; i <= tot; ++i) printf(" %d", level[i]);
puts("");
return 0;
}
|
法二
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 35;
int n;
int inord[N], preord[N], level[100000];
void levelorder(int rt, int l, int r, int index) {
if (l > r) return;
int p = l;
while (p < r && inord[p] != preord[rt]) p++;
level[index] = preord[rt];
levelorder(rt + 1, l, p - 1, index<<1|1);
levelorder(rt + 1 + p - l, p + 1, r, index<<1);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &inord[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &preord[i]);
levelorder(1, 1, n, 1);
int cnt = 0;
for (int i = 1; i < 100000; ++i) {
if (level[i] && cnt != n - 1) {
printf("%d ", level[i]);
cnt++;
}
else if (level[i]) {
printf("%d\n", level[i]);
break;
}
}
return 0;
}
|
L2-012 关于堆的判断
题目链接
题意：将一系列给定数字顺序插入一个初始为空的小顶堆 $H[]$。随后判断一系列相关命题是否为真。
建立一个小根堆模拟即可，边插入边向上调整。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e3 + 5;
int n, m;
int heap[N];
map<int, int> mp;
void up(int p) {
while (p > 1) {
if (heap[p] < heap[p/2]) {
swap(heap[p], heap[p/2]);
p /= 2;
}
else break;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &heap[i]);
up(i);
}
for (int i = 1; i <= n; ++i) mp[heap[i]] = i;
int x, y;
string s;
for (int i = 1; i <= m; ++i) {
scanf("%d", &x);
cin >> s;
if (s[0] == 'a') {
scanf("%d", &y);
cin >> s >> s;
if (mp[x] / 2 == mp[y] / 2) puts("T");
else puts("F");
}
else {
cin >> s >> s;
if (s[0] == 'r') {
if (mp[x] == 1) puts("T");
else puts("F");
}
else if (s[0] == 'p') {
cin >> s;
scanf("%d", &y);
if (mp[x] == mp[y] / 2) puts("T");
else puts("F");
}
else {
cin >> s;
scanf("%d", &y);
if (mp[x] / 2 == mp[y]) puts("T");
else puts("F");
}
}
}
return 0;
}
|
L2-013 红色警报
题目链接
题意：n 个城市，m 条通路，k 条信息即 k 个攻占的城市，对每个被攻占的城市，如果它会改变整个国家的连通性，则输出 Red Alert: City k is lost!，其中k是该城市的编号；否则只输出 City k is lost. 即可。。
法一：并查集，cnt 为删除某结点前连通分量个数，cur 为删除后连通分量，若个数不变 cur == cnt 或连通分量仅含该结点 cur + 1 == cnt 则不会改变整个国家连通性。法二：dfs 判断连通分量个数，cnt 为攻占前连通分量个数，cur 为攻占后连通分量个数，被攻占城市本身为一个连通分量，cur <= cnt + 1 表面未改变连通性。
法一
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505, M = 5005;
struct edge {
int u, v;
}e[M];
int n, m, k;
int fa[N], vis[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) fa[fx] = fy;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) fa[i] = i;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &e[i].u, &e[i].v);
unite(e[i].u, e[i].v);
}
int cnt = 0;
for (int i = 0; i < n; ++i) if (fa[i] == i) cnt++;
scanf("%d", &k);
int x;
for (int i = 1; i <= k; ++i) {
scanf("%d", &x);
vis[x] = 1;
for (int j = 0; j < n; ++j) fa[j] = j;
for (int j = 1; j <= m; ++j) {
if (!vis[e[j].u] && !vis[e[j].v]) unite(e[j].u, e[j].v);
}
int cur = 0;
for (int j = 0; j < n; ++j) {
if (!vis[j] && fa[j] == j) cur++;
}
if (cur + 1 == cnt || cur == cnt) printf("City %d is lost.\n", x);
else printf("Red Alert: City %d is lost!\n", x);
cnt = cur;
}
if (k == n) puts("Game Over.");
return 0;
}
|
法二
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505;
int n, m, k;
int a[N][N], vis[N];
void dfs(int x) {
vis[x] = 1;
for (int y = 0; y < n; ++y)
if (!vis[y] && a[x][y]) dfs(y);
}
int count() {
int cnt = 0;
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
cnt++;
}
}
return cnt;
}
int main()
{
scanf("%d%d", &n, &m);
int x, y;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
a[x][y] = a[y][x] = 1;
}
int cnt = count();
scanf("%d", &k);
for (int i = 0; i < k; ++i) {
scanf("%d", &x);
for (int y = 0; y < n; ++y) {
if (a[x][y]) {
a[x][y] = a[y][x] = 0;
}
}
int cur = count();
if (cur > cnt + 1) printf("Red Alert: City %d is lost!\n", x);
else printf("City %d is lost.\n", x);
cnt = cur;
}
if (k == n) puts("Game Over.");
return 0;
}
|
L2-014 列车调度
题目链接
题意：两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有 N 条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
实质是 LIS。对于任意一个进入的列车，如果序号大于每一个队列队尾序号，不能加入已有队列，需进入新的铁轨，否则选择第一个大于它序号的队尾序号，利用 stl set 自动排序的性质，一开始插入 0，最后答案为 s.size() - 1。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n;
set<int> s;
int main()
{
scanf("%d", &n);
s.insert(0);
int x;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
if (x < *s.rbegin()) {
s.erase(*(s.upper_bound(x)));
}
s.insert(x);
}
printf("%d\n", (int)s.size() - 1);
return 0;
}
|
L2-015 互评成绩
题目链接
题意：n个学生，每个人的作业会被 k 个同学评审，得到 k 个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩，按非递减顺序输出最后得分最高的 m 个成绩。
纯计算题。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
int n, k, m;
double a[N];
int main()
{
scanf("%d%d%d", &n, &k, &m);
int x, maxn, minn;
double s;
for (int i = 1; i <= n; ++i) {
s = 0;
maxn = 0, minn = 100;
for (int j = 1; j <= k; ++j) {
scanf("%d", &x);
s += x;
if (x > maxn) maxn = x;
if (x < minn) minn = x;
}
a[i] = 1.0 * (s - maxn - minn) / (k - 2);
}
sort(a + 1, a + n + 1);
printf("%.3lf", a[n-m+1]);
for (int i = n - m + 2; i <= n; ++i) printf(" %.3lf", a[i]);
puts("");
return 0;
}
|
L2-016 愿天下有情人都是失散多年的兄妹
题目链接
题意：两个人最近的共同祖先如果在五代以内则不可通婚，请你帮助一对有情人判断一下，他们究竟是否可以成婚？
bfs 判断是否五代以内。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
struct node {
int fa, ma, sex;
}a[N];
int n, k;
int vis[N], cnt[N];
bool bfs(int x, int y) {
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
queue<int> q;
q.push(x);
q.push(y);
cnt[x] = cnt[y] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
if (cnt[u] > 5) return 1;
if (vis[u]) return 0;
vis[u] = 1;
if (~a[u].fa && a[u].fa) {
q.push(a[u].fa);
cnt[a[u].fa] = cnt[u] + 1;
}
if (~a[u].ma && a[u].ma) {
q.push(a[u].ma);
cnt[a[u].ma] = cnt[u] + 1;
}
}
return 1;
}
int main()
{
scanf("%d", &n);
int id, fid, mid;
char c;
for (int i = 1; i <= n; ++i) {
scanf("%d %c %d %d", &id, &c, &fid, &mid);
if (c == 'M') a[id].sex = 0;
else a[id].sex = 1;
a[id].fa = fid, a[id].ma = mid;
if (~fid) a[fid].sex = 0;
if (~mid) a[mid].sex = 1;
}
scanf("%d", &k);
int x, y;
for (int i = 1; i <= k; ++i) {
scanf("%d%d", &x, &y);
if (a[x].sex == a[y].sex) puts("Never Mind");
else if (bfs(x, y)) puts("Yes");
else puts("No");
}
return 0;
}
|
L2-017 人以群分
题目链接
题意：社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。
排序取一半。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
int n, sum;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
sum += a[i];
}
sort(a + 1, a + n + 1);
int half = 0;
for (int i = 1; i <= n / 2; ++i) half += a[i];
printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d\n", n - n / 2, n / 2, sum - 2 * half);
return 0;
}
|
L2-018 多项式A除以B
题目链接
题意：多项式 Q 除 R，分别输出商和余。
模拟即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
int n, m;
double a[N], b[N], c[N];
int getnum(double c[], int expo) {
int cnt = 0;
for (int i = expo; i >= 0; --i)
if (abs(c[i]) + 0.05 >= 0.1) cnt++;
return cnt;
}
void print(double c[], int expo) {
int num = getnum(c, expo);
printf("%d", num);
if (!num) printf(" 0 0.0");
for (int i = expo; i >= 0; --i)
if (abs(c[i]) + 0.05 >= 0.1) printf(" %d %.1lf", i, c[i]);
puts("");
}
int main()
{
int x, max1 = 0, max2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
if (x > max1) max1 = x;
scanf("%lf", &a[x]);
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &x);
if (x > max2) max2 = x;
scanf("%lf", &b[x]);
}
int e1 = max1, e2 = max2;
while (e1 >= e2) {
double t = a[e1] / b[e2];
c[e1 - e2] = t;
for (int i = e1, j = e2; j >= 0; --i, --j) a[i] -= b[j] * t;
while (abs(a[e1]) < eps && e1 > 0) e1--;
}
print(c, max1 - max2);
print(a, e1);
return 0;
}
|
L2-019 悄悄关注
题目链接
题意：很水的模拟题。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m, sum;
map<string, int> vis, people;
vector<string> ans;
int main()
{
scanf("%d", &n);
string s;
int x;
for (int i = 1; i <= n; ++i) {
cin >> s;
vis[s] = 1;
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
cin >> s;
scanf("%d", &x);
people[s] = x;
sum += x;
}
for (map<string, int>::iterator it = people.begin(); it != people.end(); ++it) {
if (!vis[it->first]) {
if (it->second * m > sum) ans.push_back(it->first);
}
}
if (ans.empty()) puts("Bing Mei You");
else {
sort(ans.begin(), ans.end());
for (auto it = ans.begin(); it != ans.end(); ++it)
cout << *it << '\n';
}
return 0;
}
|
L2-020 功夫传人
题目链接
题意：给出师门总人数 n，祖师爷(编号为 0)功力值 z，每传一代功夫所扣百分比值 r，以及编号为 i 的人所传的徒弟k id[1] id[2] ... id[k]，k 为 0 表示这是一位得道者，后面跟放大倍数，求所有得道者功力总值。
从祖师爷开始 dfs 即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
vector<int> v[N];
int n;
double z, r, ans;
int vis[N];
void dfs(int id, double power) {
if (vis[id]) {
ans += power * v[id][0];
return;
}
for (int i = 0; i < (int)v[id].size(); ++i)
dfs(v[id][i], power * (1 - r / 100));
}
int main()
{
scanf("%d%lf%lf", &n, &z, &r);
int k, x;
for (int i = 0; i < n; ++i) {
scanf("%d", &k);
if (!k) {
vis[i] = 1;
scanf("%d", &x);
v[i].push_back(x);
}
else {
while (k--) {
scanf("%d", &x);
v[i].push_back(x);
}
}
}
dfs(0, z);
printf("%d\n", (int)ans);
return 0;
}
|
L2-021 点赞狂魔
题目链接
题意：很水的模拟题。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105;
struct user {
string name;
int cnt, sum;
bool operator < (const user &rhs) const {
if (cnt != rhs.cnt) return cnt > rhs.cnt;
return sum * rhs.cnt < rhs.sum * cnt;
}
}a[N];
int n, k;
set<int> s;
int main()
{
scanf("%d", &n);
string str;
int x;
for (int i = 1; i <= n; ++i) {
s.clear();
cin >> str; scanf("%d", &k);
for (int j = 1; j <= k; ++j) {
scanf("%d", &x);
s.insert(x);
}
a[i] = {str, (int)s.size(), k};
}
int num = min(n, 3);
partial_sort(a + 1, a + num + 1, a + n + 1);
cout << a[1].name;
for (int i = 2; i <= num; ++i) {
cout << " " << a[i].name;
}
for (int i = 1; i <= 3 - n; ++i)
printf(" -");
puts("");
return 0;
}
|
L2-022 重排链表
题目链接
题意：给定一个单链表 $L_1\to L_2\to\cdots\to L_n$，请编写程序将链表重新排列为 $L_n\to L_1\to L_{n-1}\to L_2\to\cdots$。
结构体按顺序存到 vector 中交替输出。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
struct node {
int id, dat, nxt;
}a[N];
int st, n;
vector<node> v, ans;
int main()
{
scanf("%d%d", &st, &n);
int x, y, z;
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &x, &y, &z);
a[x] = { x, y, z };
}
for (; ~st; st = a[st].nxt) v.push_back(a[st]);
int l = 0, r = v.size() - 1;
while (1) {
ans.push_back(v[r--]);
if (l > r) break;
ans.push_back(v[l++]);
if (l > r) break;
}
for (int i = 0; i < (int)ans.size(); ++i) {
if (i != (int)ans.size() - 1)
printf("%05d %d %05d\n", ans[i].id, ans[i].dat, ans[i+1].id);
else
printf("%05d %d -1\n", ans[i].id, ans[i].dat);
}
return 0;
}
|
L2-023 图着色问题
题目链接
题意：给定无向图 G=(V,E)，问可否用 K 种颜色为 V 中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505, M = 25e4 + 5;
int n, m, k, t, tot;
int head[N], color[N], vis[N];
int ver[M], nxt[M];
set<int> s;
void add(int x, int y) {
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
scanf("%d", &t);
while (t--) {
s.clear();
for (int i = 1; i <= n; ++i) {
scanf("%d", &color[i]);
s.insert(color[i]);
}
if ((int)s.size() != k) { puts("No"); continue; }
memset(vis, 0, sizeof(vis));
int flag = 0;
for (int x = 1; x <= n; ++x) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (vis[y]) continue;
if (color[x] == color[y]) { flag = 1; break; }
}
if (flag) break;
}
if (!flag) puts("Yes");
else puts("No");
}
return 0;
}
|
L2-024 部落
题目链接
题意：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
50
51
52
53
54
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
int n, q;
int fa[N];
set<int> s;
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx < fy) fa[fy] = fx;
else fa[fx] = fy;
}
int main()
{
for (int i = 1; i <= N; ++i) fa[i] = i;
scanf("%d", &n);
int k, x, y;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &k, &x);
s.insert(x);
for (int j = 2; j <= k; ++j) {
scanf("%d", &y);
s.insert(y);
unite(x, y);
}
}
int cnt = 0;
for (auto it = s.begin(); it != s.end(); ++it)
if (*it == fa[*it]) cnt++;
printf("%d %d\n", (int)s.size(), cnt);
scanf("%d", &q);
while (q--) {
scanf("%d%d", &x, &y);
printf("%c\n", find(x) == find(y) ? 'Y' : 'N');
}
return 0;
}
|
L2-025 分而治之
题目链接
题意：无向图删除一系列点后判断剩余点是否孤立。
邻接表存图并记录每个点相连点的个数。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
int n, m, k;
int c[N], cnt[N];
vector<int> g[N];
void check() {
for (int i = 1; i <= n; ++i) {
if (c[i] > 0) {
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
scanf("%d%d", &n, &m);
int x, y;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
cnt[x]++;
cnt[y]++;
g[x].push_back(y);
g[y].push_back(x);
}
scanf("%d", &k);
int t;
while (k--) {
scanf("%d", &t);
for (int i = 1; i <= n; ++i) c[i] = cnt[i];
for (int i = 1; i <= t; ++i) {
scanf("%d", &x);
c[x] = 0;
for (auto j : g[x])
c[j]--;
}
check();
}
return 0;
}
|
L2-026 小字辈
题目链接
题意：输出最大深度以及该深度的节点。
随便 bfs 一下。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
int n, ans;
vector<int> v[N];
int d[N];
int main()
{
scanf("%d", &n);
int x;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
if (~x) v[x].push_back(i);
else v[0].push_back(i);
}
queue<int> q;
q.push(v[0][0]);
d[v[0][0]] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto it = v[x].begin(); it != v[x].end(); ++it) {
q.push(*it);
d[*it] = d[x] + 1;
}
ans = max(ans, d[x]);
}
printf("%d\n", ans);
int f = 0;
for (int i = 1; i <= n; ++i) {
if (d[i] == ans) {
if (f) printf(" ");
printf("%d", i);
f = 1;
}
}
puts("");
return 0;
}
|
L2-027 名人堂与代金券
题目链接
题意：很水的模拟题。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
struct node {
string mail;
int score;
bool operator < (const node &rhs) const {
if (score != rhs.score) return score > rhs.score;
return mail < rhs.mail;
}
}a[N];
int n, g, k, sum;
int main()
{
scanf("%d%d%d", &n, &g, &k);
for (int i = 1; i <= n; ++i) {
cin >> a[i].mail; scanf("%d", &a[i].score);
if (a[i].score >= g) sum += 50;
else if (a[i].score >= 60) sum += 20;
}
sort(a + 1, a + n + 1);
printf("%d\n", sum);
printf("1 ");
cout << a[1].mail;
printf(" %d\n", a[1].score);
int rank = 1;
for (int i = 2; i <= n; ++i) {
if (a[i].score != a[i-1].score) {
rank = i;
if (rank > k) break;
}
printf("%d ", rank);
cout << a[i].mail;
printf(" %d\n", a[i].score);
}
return 0;
}
|
L2-028 秀恩爱分得快
题目链接
题意：n 个人(编号为 $0\sim n-1$)，k 张照片，每张照片两两亲密度度为 1/k，他们间的亲密度定义为所有人亲密度之和，负号表示女性，给出一对情侣 A、B，若 A、B 彼此亲密度最高，输出他们，否则分别按序号递增输出他们亲密度最高的异性。
模拟题，注意 -0 的处理。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;
int n, m;
int sex[N];
double g[N][N];
int read() {
string str;
cin >> str;
if (str == "-0") sex[0] = 1;
int num = stoi(str);
if (num < 0) num = -num, sex[num] = 1;
return num;
}
void print(int A, int B) {
if (sex[A]) printf("-");
printf("%d ", A);
if (sex[B]) printf("-");
printf("%d\n", B);
}
int main()
{
scanf("%d%d", &n, &m);
int k, num;
while (m--) {
vector<int> gender[2];
scanf("%d", &k);
for (int i = 1; i <= k; ++i) {
num = read();
if (sex[num]) gender[1].push_back(abs(num));
else gender[0].push_back(num);
}
for (int i = 0; i < (int)gender[0].size(); ++i) {
for (int j = 0; j < (int)gender[1].size(); ++j) {
g[gender[0][i]][gender[1][j]] += 1.0 / k;
g[gender[1][j]][gender[0][i]] += 1.0 / k;
}
}
}
int A = read(), B = read();
double mx1 = 0, mx2 = 0;
for (int i = 0; i < n; ++i) {
mx1 = max(mx1, g[A][i]);
mx2 = max(mx2, g[B][i]);
}
if (mx1 == g[A][B] && mx2 == g[A][B]) {
print(A, B);
}
else {
for (int i = 0; i < n; ++i)
if (g[A][i] == mx1) print(A, i);
for (int i = 0; i < n; ++i)
if (g[B][i] == mx2) print(B, i);
}
return 0;
}
|
L2-029 特立独行的幸福
题目链接
题意：对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。
模拟即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;
int vis[N], vis1[N], cnt[N];
void solve(int x) {
int num = x;
memset(vis1, 0, sizeof(vis1));
while (1) {
int res = 0;
while (x) {
res += (x % 10) * (x % 10);
x /= 10;
}
cnt[num]++;
if (res == 1) {
return;
}
vis[res] = 1;
if (vis1[res]) {
vis[num] = 1;
return;
}
vis1[res] = 1;
x = res;
}
}
bool isprime(int x) {
if (x <= 1) return 0;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) return 0;
}
return 1;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
for (int i = a; i <= b; ++i) {
solve(i);
}
int flag = 0;
for (int i = a; i <= b; ++i) {
if (!vis[i]) {
flag = 1;
if (isprime(i)) cnt[i] *= 2;
printf("%d %d\n", i, cnt[i]);
}
}
if (!flag) puts("SAD");
return 0;
}
|
L2-030 冰岛人
题目链接
题意：冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加 sson，女儿则加 sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
模拟，注意查询到两人都是五代以外才返回 true。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
struct person {
char sex;
string fa;
};
map<string, person> mp;
int n, m;
bool check(string a, string b) {
int i = 1;
for (string fa = a; !fa.empty(); fa = mp[fa].fa, ++i) {
int j = 1;
for (string fb = b; !fb.empty(); fb = mp[fb].fa, ++j) {
if (i >= 5 && j >= 5) return 1;
else if (fa == fb) return 0;
}
}
return 1;
}
int main()
{
scanf("%d", &n);
cin.tie(0);
string a, b;
for (int i = 1; i <= n; ++i) {
cin >> a >> b;
int lenb = (int)b.size();
if (b[lenb-1] == 'n') mp[a] = { 'm', b.substr(0, lenb - 4) };
else if (b[lenb-1] == 'r') mp[a] = { 'f', b.substr(0, lenb - 7) };
else mp[a].sex = b[lenb-1];
}
scanf("%d", &m);
string af, al, bf, bl;
for (int i = 1; i <= m; ++i) {
cin >> af >> al >> bf >> bl;
if (mp.find(af) == mp.end() || mp.find(bf) == mp.end() ) puts("NA");
else if (mp[af].sex == mp[bf].sex) puts("Whatever");
else printf("%s\n", check(af, bf) ? "Yes" : "No");
}
return 0;
}
|
L2-031 深入虎穴
题目链接
题意：给出了一棵树结点之间的关系，要求找最深的叶子结点。
遍历每一个叶子结点，dfs 求最大深度即可。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
int n, k;
int to[N], d[N];
void dfs(int x) {
if (to[x] == 0) {
d[x] = 1;
return;
}
if (!d[to[x]]) dfs(to[x]);
d[x] = d[to[x]] + 1;
}
int main()
{
scanf("%d", &n);
int x;
for (int i = 1; i <= n; ++i) {
scanf("%d", &k);
for (int j = 1; j <= k; ++j) {
scanf("%d", &x);
to[x] = i;
}
}
int maxd = -1, id;
for (int i = 1; i <= n; ++i) {
dfs(i);
if (maxd < d[i]) { maxd = d[i]; id = i; }
}
printf("%d\n", id);
return 0;
}
|
L2-032 彩虹瓶
题目链接
题意：给出一个固定容量的栈，给出一个进栈序列，每次可以出栈或否，问能否按递增顺序出栈。
用 stack 模拟即可
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m, k;
stack<int> s;
int main()
{
scanf("%d%d%d", &n, &m, &k);
while (k--) {
int x;
int now = 1, flag = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
s.push(x);
while (!s.empty() && s.top() == now) {
now++;
s.pop();
}
if ((int)s.size() > m) flag = 0;
}
if (s.empty() && flag) puts("YES");
else puts("NO");
while (!s.empty()) s.pop();
}
return 0;
}
|
L2-034 口罩发放
题目链接
题意：模拟题。
难点在准确理解题意。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 3e4 + 5;
struct node {
string name, id, time;
int type, pri;
friend bool operator < (node &x, node &y) {
if (x.time == y.time) return x.pri < y.pri;
return x.time < y.time;
}
}people[N];
int d, p, t, s;
map<string, int> m1, m2;
vector<node> ans1, ans2;
bool checkid(string str) {
if (str.length() != 18) return 0;
for (int i = 0; i < 18; ++i) {
if (!isdigit(str[i])) return 0;
}
return 1;
}
int main()
{
scanf("%d%d", &d, &p);
for (int i = 1; i <= d; ++i) {
scanf("%d%d", &t, &s);
vector<node> v;
node tmp;
for (int j = 1; j <= t; ++j) {
cin >> tmp.name >> tmp.id >> tmp.type >> tmp.time;
tmp.pri = j;
if (checkid(tmp.id) && tmp.type && !m2[tmp.id]) {
m2[tmp.id] = 1; ans2.push_back(tmp);
}
v.push_back(tmp);
}
sort(v.begin(), v.end());
for (auto k : v) {
if (checkid(k.id) && s) {
if (!m1[k.id]) {
m1[k.id] = i;
ans1.push_back(k);
s--;
}
else if (i - m1[k.id] - 1 >= p) {
m1[k.id] = i;
ans1.push_back(k);
s--;
}
}
}
}
for (auto i : ans1) cout << i.name << ' ' << i.id << '\n';
for (auto i : ans2) cout << i.name << ' ' << i.id << '\n';
return 0;
}
|
L2-035 完全二叉树的层序遍历
题目链接
题意：给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历序列。
很简单，后序遍历递归建树求解。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 65;
int n, cnt;
int postord[N], tree[N];
void build(int rt) {
if (rt > n) return;
build(rt<<1); build(rt<<1|1);
tree[rt] = postord[++cnt];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &postord[i]);
build(1);
printf("%d", tree[1]);
for (int i = 2; i <= n; ++i) {
printf(" %d", tree[i]);
}
puts("");
return 0;
}
|