「题解」Luogu Round 196（Div.4）

题目信息

题目链接：2024-08-21 新生每日X题
访问密码：jxufe
题目列表：

题解

模板

题解内容均使用本模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	//代码主体
    return 0;
}

需要注意的是，如果使用ios::sync_with_stdio(false)的话，不能混用cin/cout和scanf/printf。

A

难度和原来的 A + B 也差不多……的说。

1
2
3


	int x, y;
	cin >> x >> y;
	cout << (x-2016) * 12 + (y - 8) + 1;

因为现在是 $x$ 年 $y$ 月，又因为他们于 2016 年 8 月相识，所以中间月的间隔为 $(x-2016) \times 12+(y-8)$。考虑到 2016 年 8 月是他们认识的第一个月，所以输出结果要加一。

~~这真的有解释的必要吗……~~

B

单纯的条件判断……按照题目写就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


	int wa, ca, ta, wb, cb, tb;
    cin >> wa >> ca >> ta >> wb >> cb >> tb;
    string ans = "";
    if (wa != wb) {
        ans = wa > wb ? 'A' : 'B';
    } else if (ca != cb) {
        ans = ca > cb ? 'A' : 'B';
    } else {
        ans = ta < tb ? 'A' : 'B';
    }
    cout << ans;

~~关于我为什么用ans存答案：懒得改了……~~

关于三目运算符`x?y:z`

如果有人不知道这玩意的话……（应该都知道吧……）
详细可以参考其他运算符 - cppreference.com 可以简单地理解为三目运算符x?y:z等于下述代码块：

1
2
3
4


	if (x)
		y;
	else
		z;

C

本题看起来非常简单。但根据相关比赛讨论区，有部分人还是因为细节问题导致 WA

具体而言就是：

参考数据规模与约定：对于 $100%$ 的测试数据，$1\leq n \leq 2 \times 10^5$，每题的得分不超过 $10^4$。
根据浮点类型，我们可以知道float的精度位数只有 6 ~ 9 位。
因此本题如果使用float的话就会导致浮点误差较大，从而 WA。总之，根据 OI Wiki 的建议：

因为 float 类型表示范围较小，且精度不高，实际应用中常使用 double 类型表示浮点数。

所以本题切忌使用float。（话说一般来说如果在 C++ 里面浮点数默认类型就是double，所以真的有必要考虑那么多吗……）
另外一个就是关于取整函数std::ceil()的使用。它的返回值也是一个浮点数，而题目要求的输出结果是整数，所以要转换为整数（简单来说就是外面套一层int()）

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


	int n, t, s1 = 0, s2 = 0; //为什么不用int呢.jpg -> 猜你想看：不开long long见祖宗
	cin >> n;
    f(i, 0, n) { //懒得打for循环（
        cin >> t;
        s1 += t;
    }
    f(i, 0, n) { //关于这个宏定义见模板
        cin >> t;
        s2 += t;
    }
    cout << int(ceil((s1 + s2) / 2.0));

D

和图论一点关系都没的一道普通的小模拟题。难度入门

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


	int n, m, a, b;
	cin >> n >> m >> a >> b;
    int ans = 0;
    while (m --) {
        int l, t;
        bool traveled = false;
        cin >> l;
        while (l --) {
            cin >> t;
            if (t == a)
                traveled = true;
            if (traveled and t == b)
                ans ++;
        }
    }
    cout << ans;

只要判断某一车次是否先经过a再经过b就好了。

可能的 WA 情况：如果你哪根筋搭错了，在if (traveled and t == b)的代码块中加了个break;（没错，我就是要优化性能.jpg）会导致本次列车的数据串到下一次列车导致 WA。例子（好不容易从答疑帖里面扒拉出来的）

E

可能需要知道的知识：

std::pow(x,y)：用于计算一个数的幂的函数，返回x^y。相当于 Python 中的x**y。
std::set: STL 容器 - 集合
- 和数学中的集合相似，set 中不会出现值相同的元素。

边读入边处理。每读入一个数就计算出它对 $10^t$ 的模，然后塞进集合里。最后统计集合里元素的个数就行了。

一些操作

1
2
3
4
5
6


	//声明一个元素类型为int的set
	set<int> val;
	//新增元素
	val.insert(1);
	//返回容器内元素个数
	val.size();

总而言之本题的实现也非常简单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


	int n, t;
	set<int> events;
	cin >> n >> t;
    const int sp = pow(10, t);
    int a;
    f(i, 0, n) {
        cin >> a;
        events.insert(a % sp);
    }
    cout << events.size();

应伟大领袖的要求所追加的不使用 STL 的版本

萝卜青菜，各有所爱。也许有些人不喜欢使用 STL，抑或是对 STL 不太熟悉。因此在这里介绍一种不使用 STL 的版本：

我们考虑数据范围 $1 \leq t \leq 4$，可以得到上文中的sp的范围为$10 \leq sp \leq 10000$，对于这个不大的数据范围而言，我们可以开一个大小为10010的数组events来记录某个事件所对应的碎片个数。数组的下标对应事件，数组存储的便是对应碎片的个数。接着把上文中的events.insert(a % sp)改为`events[a % sp] += 1即可。

对于数组events，我们使用遍历的方法来获取其事件个数——即数组中不为 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


#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
using namespace std;

int n, t;
int events[10010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    const int sp = pow(10, t);
    int a;
    f(i, 0, n) {
        cin >> a;
        events[a % sp] += 1;
    }
    int ans = 0;
    f(i, 0, 10010) {
        if (events[i])
            ans ++;
    }
    cout << ans;
    return 0;
}

事实上不使用 STL 的版本无论是时间还是空间都优于使用 STL 的版本（都开启了 O2 优化）。
但使用 STL 对开发者而言更加友好（也就是更好写一点）（虽然本题好像体现不出来）

F

考虑到只需要输出任意一种答案即可。同时题目保证了 $n$ 是 $m$ 的倍数。我们记$p=\frac{n}{m}$因此我们观察样例不难发现我们的输出就是 $p$ 个公差为 $p$ 项数为 $m$ 的等差数列，首项依次为 $1, 2, …, p$。

考虑到数据规模不是很大，直接for循环模拟就行~~（或者说相信编译器的智慧）~~

1
2
3
4
5
6
7
8


	int n, m;
	cin >> n >> m;
    const int p = n / m;
    for (int i = 0; i < p; i ++) {
        for (int j = 1; j <= n; j += p) {
            cout << i + j << '\n';
        }
    }

G

观察到love和friend的头尾不是重叠的，所以至多的操作次数就等于字符串中friend的个数。
对于题目所给的两个样例，单纯地统计friend的个数就能 AC。
但是就如日赛所给的别名那样，自己多出几个样例总是好的。

我们考虑friend相邻（或者只隔了几个字母）的情况：

1
2
3
4


1. "friendfriend"
2. "friendfriendfriendfriend"
3. "friendabfriend"
4. "friendabcfriend"

显然的，对于字符串 1 而言，我们只需要经过 1 次替换（即把字符串替换为frieloveiend）；同样的，对于字符串 2，我们需要经过 2 次替换（替换为frieloveiendfrieloveiend即可）；对于字符串 3，我们需要经过 1 次替换（替换为firenloveriend）；而对于字符串 4，显然我们无法用一个love把两个friend都破坏掉，因此我们需要经过两次替换。

所以我们可以得出：当friend的结尾和后一个friend的开头的间隔小于等于 3 的时候，我们能用一个love把两个friend都破坏掉。

因此我们只需要获得每一个friend的开头位置（显然$结尾位置=开头位置+5$），然后再根据上面的逻辑判断需要用多少个love就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


	int ans = 0;
	string s;
	vector<int> pos;
	cin >> s;
    const int n = s.length();
    f(i, 0, n) {
        if (i + 5 < n and s[i] == 'f' and s[i + 1] == 'r' and s[i + 2] == 'i' and s[i + 3] == 'e' and s[i + 4] == 'n' and s[i + 5] == 'd') {
            pos.push_back(i);
            i += 5;
        }
    }
    const int m = pos.size();
    f(i, 0, m) {
        if (i + 1 < m and pos[i + 1] - (pos[i] + 5) <= 3)
            i ++;
        ans ++;
    }
    cout << ans;

同上不使用 STL 的版本

对于相对简单的vector操作，我们开一个足够大的数组并记录数组的大小也能达成同样的效果。
一般来说，数组的大小取决于数据规模与约定。比如本题约定 $1 \leq |S| \leq 10^6$，我们就可以开一个大小为 1000100 的数组。一般来说我们所开的数组大小要比数据最大规模稍微大一点，这样可以避免因访问越界而导致 RE。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int pos[1000100], m;
//vector<int> pos;

int main() {
	//...省略一些重复内容
		//pop.push_back(i); 和以下代码是等价的
		pos[m ++] = i;
	//...
	//因为我们已经给出了m，所以就不用获取pos的大小了
	// const int m = pos.size();
	// ...
}

对于本题而言，使用 STL 和使用数组的时间差别不大。但数组版本空间占用略小于 vector 版。

H

可能需要知道的知识：

（多维）数组
std:vector：STL容器 - 向量
- 其实一般管这玩意叫动态数组
- 为什么要使用 vector

一些操作

1
2
3
4
5
6
7
8


	//这里只会写本题所用到的操作
	//新建
	vector<int> val;
	//往末尾插一个元素
	val.push_back(114514);
	//把元素val[p]删了
	val.erase(val.begin() + pos); //关于val.begin()是什么：↓关于更多
	//关于更多：为什么不去看神奇的oi.wiki呢？

其他的见代码吧：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


	vector<int> box[110][110]; //实际上这个 vector 是开在外面的
	int n, m, k, t;
	int a, x, y;
	cin >> n >> m >> k >> t;
    while (t --) {
        cin >> a >> x >> y;
        if (box[x][y].size() < k) { //如果没满的话就不用销毁了
            cout << -1 << '\n';
        } else {
	        //让我们找最小值吧（
            int p = 0, mi = (1 << 30); // (1 << 30) 代表左移30位，相当于2^30
            f(i, 0, k) {
                if (box[x][y][i] <= mi) {
                    p = i;
                    mi = box[x][y][i];
                }
            }
            cout << mi << ' ' << k - (p + 1) << '\n';// 显然操作次数就是p距离顶端的距离
            box[x][y].erase(box[x][y].begin() + p);// 把找到的那玩意删了
        }
        box[x][y].push_back(a); //加东西
    }

关于不使用 STL 的可能性

本题使用数组实现相比使用vector实现性能几乎没有提升。因此还是首先建议使用vector实现。

使用数组实现的代码如下，和上题类似：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int box[110][110][60];
// 另外再开一个二维数组维护上面那玩意的大小
// 其实可以开成unsigned char的，因为题目给的1<=k<=50
int bs[110][110];

void erase(int x, int y, int p) {
    f(i, p, bs[x][y] --) {
        box[x][y][i] = box[x][y][i + 1];
    }
}

void push_back(int x, int y, int v) {
    box[x][y][bs[x][y] ++] = v;
}

// 后面把box[x][y].erase(box[x][y].begin() + p) 改成 erase(x, y, p)
// 以及把box[x][y].push_back(a) 改成 push_back(x, y, a) 就行

以上。

参考资料

洛谷
- 我最喜欢的 OJ（
Virtual Judge
- 学长们很喜欢的 OJ
OI Wiki
- 一个免费开放且持续更新的 编程竞赛（competitive programming） 知识整合站点
C++ 参考手册
- 一个全面的 C 和 C++ 语言及其标准库的在线参考资料