发表更新竞赛12 分钟读完 (大约1727个字)0次访问

2021牛客寒假算法基础集训营6

2021牛客寒假算法基础集训营6的补题记录

A题 回文括号序列计数

链接：https://ac.nowcoder.com/acm/contest/9986/A
来源：牛客网

题目描述

我们定义一个字符串S是回文的，表示S的左右反转和S相同。

我们定义一个字符串是括号序列：

​ \1. 空串是括号序列。
​ \2. 两个括号序列P和Q的拼接是括号序列。
​ \3. 如果P是括号序列，’(‘+P+’)’是括号序列。

求长度为 n (0<=n<=10^9) 的回文括号序列的方案数，对 998244353 取膜。

输入描述:

第一行一个 T 表示数据组数。T<=1000000。接下来 T 行，每行一个 n 。

输出描述:

T 行。对于每组数据，你的答案。

示例1

输入

1
2
3
2
0
1

输出

1
2
1
0

思路

啥都不说了，凉心出题人。题目十分的阴间。

看看这迷人的通过率，还浪费了我大把的卡常时间。

说实话我现在还是没有看懂题，啥叫“一个字符串S是回文的，表示S的左右反转和S相同。”

PS：在题解文档出来之后，并且翻阅了好多其他人的题解之后我懂了这个“（）”为什么不是回文：它指的回文是”abba”但是很显然（与）是两个符号。所以并不是aa形而是ab形，所以“（）”并不是一个回文序列。同理根据题中所给的构造条件可知，长度大于0的串都不可能是回文串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--)
    {
        int n;
        scanf("%d", &n);
        if (n == 0) puts("1");
        else puts("0");
    }
    return 0;
}

这短小精湛的代码告诉我们，写题之前先读题。

（出题人还让答案对一个数取模，看起来跟真的似的，给忽悠瘸了）

J题 天空之城

链接：https://ac.nowcoder.com/acm/contest/9986/J
来源：牛客网

题目描述

天空之城有5个小镇，名字分别为Ada, Aed, Akk, Orz, Apq，他们也有相互的路径长度。

希达早已期盼着天空之城，如今她登上了天空之城，就想走遍天空之城的每一个城市，但是她希望自己走的路的长度越小越好，以节省体力和节约时间。

巴鲁同意了，但由于他是主力（男孩子嘛），需要帮希达计算出走遍所有城市的最短路径长度。

由于天空之城具有魔力，如果希达想再走一次自己之前走过的路，则她可以在这条路上不花费任何时间。

但是天空之城的城市太多了，他实在计算不过来，只得请你来帮帮忙了。

输入描述:

第一行，输入n，q, 表示有n个城市，q条边；

第二行，输入一个名字tmp，表示希达想要从tmp城市开始行走；

接下来q行，每行输入两个名字a,b和一个数字val, 表示a城市与b城市之间的距离为val.(注意可能有重边和自环)

输出描述:

帮助巴鲁计算出最短的路径长度，如果无法走遍所有城市，输出“No!”。

示例1

输入

1
2
3
4
5
6
7
5 5
Orz
Ada Aed 5
Orz Ada 6
Apq Aed 8
Akk Apq 12
Aed Orz 3

输出

1
28

说明

1
Ada->Aed->Orz->Aed->Apq->Akk

备注:

多组输入输出（以EOF结束），保证数据组数不超过 10 。

1 <= n <= 5000, 1 <= q <= 200000, 1 <= val <= 1e9. 每个城市的名字长度不超过10。

保证 ∑q≤200000\sum q \le 200000∑q≤200000 。

图论题，由题可知我们要求一个图中的最小生成树。

复习一下Kruskal算法。

Kruskal算法的核心是贪心算法，我们根据边权进行从小到大排序，每次取出边权最小的那一个，然后将两点加入到生成树中，在添加的过程中需要注意的是，维护一个并查集，实时监测是否出现了环，如果出现了环那么这条边舍弃，结束的条件是当加入了n-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
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int maxm = 200005;
ll n, q, ans, tot;
struct edge {
	int from, to;
	ll v;
	bool operator < (const edge &b)const{
		return v < b.v;
	}
}a[maxm];
ll f[maxn];
map<string, ll> mp;
ll find(ll x){return x == f[x] ? x : f[x] = find(f[x]);}
void Kruskal() {
	sort(a + 1, a + 1 + q);
	for (int i=1;i<=q;++i) {
		ll x = find(a[i].from);
		ll y = find(a[i].to);
		if (x != y) {
			f[x] = y;
			ans += a[i].v;
		}
	}
	ll x = find(1);
	for (int i=2;i<=n;++i) {
		if (find(i) != x) {
			cout << "No!" << endl;
			return;//这个细节错了一次，忘记输出完no后直接返回
		}
	}
	cout << ans << endl;
	return;
}

int main() {
	while (cin >> n >> q) {
		string aaa, bbb;
		mp.clear();
		tot = 0;
		ans = 0;
		for (int i=1;i<=n;++i)	f[i] = i;
		cin >> aaa;
		for (int i=1;i<=q;++i)  {
			cin >> aaa >> bbb;
			cin >> a[i].v;
			if (mp.count(aaa) == 0) mp[aaa] = ++tot;
			if (mp.count(bbb) == 0) mp[bbb] = ++tot;
			a[i].from = mp[aaa];
			a[i].to = mp[bbb];
		}
		Kruskal();
	}
	return 0;
}

来总结一下Kruskal的一些小细节，首先是并查集函数的背诵和f数组的初始化不要忘。

然后就是存贮边的结构体中要重载一下小于号的运算符，以w为排序的依据。

F题 组合数问题

链接：https://ac.nowcoder.com/acm/contest/9986/F
来源：牛客网

题目描述

小 M 很喜欢组合数。

小 Z 给了她一个数 n （n为偶数），让她计算 (n0)+(n2)+(n4)..+(nn)\binom{n}{0}+\binom{n}{2}+\binom{n}{4}..+\binom{n}{n}(0n​)+(2n​)+(4n​)..+(nn​) ，小 M 一下子就秒掉了，觉得题好简单。

因此，小 Z 给了她一个难题：给定一个数 n （n 是4的倍数），计算 (n0)+(n4)+(n8)+…+(nn)\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+…+\binom{n}{n}(0n​)+(4n​)+(8n​)+…+(nn​) ，答案对 998244353 取模。

小 M 不会做，请你来帮帮她吧！

输入描述:

1
输入一个数 n 。

输出描述:

1
输出答案对 998244353 取模的值。

示例1

输入

1
12

输出

1
992

备注:

对于所有的数据，1\le n\le 10^{18}1≤n≤10 18。

思路:

怎么说，这道题只看懂了题解，实现可能还差点东西（虚数快速幂）

这是主办方的题解记录，最后的公式导出其实是用了高中组合数学中的一些公式推得的，所以这道题考验了高中的组合数学能力和虚数快速幂代码的能力。（然而百度了一下发现好像并没有虚数快速幂的相关资料）

2021牛客寒假算法基础集训营6

https://dicemy.com/50660

作者

Dicemy

发布于

2021-02-24

更新于

2022-05-23

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关于我
×