比赛相关信息
比赛信息
比赛名称： The 16th Zhejiang Provincial Collegiate Programming Contest
比赛地址： Vjudge全部参赛队伍： 292 + 5*
金： 9题，1031m
银： 8题，839m
铜： 7题，837m
比赛过程回顾
| A | B | C | D | E | F | G | H | I | J | K | L | M | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 提交次数 | 1 | 1 | 1 | 1 | 1 | 10 | |||||||
| 首次提交时间 | 0:57:37 | 0:10:18 | 0:04:00 | 1:10:04 | 0:22:27 | 2:56:22 | |||||||
| 首A时间 | 0:57:37 | 0:10:18 | 0:04:00 | 1:10:04 | 0:22:27 | ||||||||
| 状态 | ✔ | ✔ | ✔ | ✔ | ✔ | ⚪补 |
共 5 题，164m，Rk 110。
✔：比赛时通过；⚪：比赛时尝试过；补：已补题。
部分题解与小结
E - Sequence in the Pocket
小评
\(\mathcal{Consider\ by\ Wida}\)
\(\mathcal{Solved\ by\ Wida}\)
打卡题（1 / 5）。由 \(\mathcal Hwh\) 开题，但是迟迟没有思路，以为是映射之类的算法，于是便去解 \(\mathcal H\) 了，后来我想了下发现就是一个纯贪心排序匹配，写了一发直接过了。
题意
给定一个长度为 \(N\) 的序列 \(A\) ，你可以从中任选一个元素将其提至序列最左侧，输出最少需要的操作次数，使得序列非降。
思路
有一步很显然的贪心是，最终，序列的样子即为排序之后的样子，故我们先用另外的数组 \(B\) 记录给定的序列，并对 \(B\) 进行排序。
然后我们思考 \(A\) 如何转化成 \(B\) 。我们发现，只有连续的最大几个元素的位置不会被改变，如样例 6738441922 ， 只有6789 不需要移动。而对于其余的需要移动的元素，我们一定能找到一个最佳的次序，使得每个元素至多只需要移动一次。依此方案进行模拟即可。
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int a[N], b[N];
bool cmp(int x, int y) { return x > y; }
int main() {
ios::sync_with_stdio(false);cin.tie(0);
int T; cin >> T;
while (T -- ) {
int n; cin >> n;
int num = 1, ans = 0;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + 1 + n, cmp);
for (int i = n; i >= 1; -- i) {
if (a[i] == b[num]) ++ num;
else ++ ans;
}
cout << ans << endl;
}
return 0;
}
F - Abbreviation
小评
\(\mathcal{}Consider\ by\ Hwh\)
\(\mathcal{}Solved\ by\ Hwh\)
打卡题（ / 5）
题意
思路
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
string s;
string t = "aeiyou";
while (T -- ) {
cin >> s;
cout << s[0];
for (int i = 1; i < s.size(); ++ i){
int f = 1;
for (int j = 0; j < t.size(); ++ j){
if (s[i] == t[j]){
f = 0;
break;
}
}
if (f) cout << s[i];
}
cout << "\n";
}
return 0;
}
G - Lucky 7 in the Pocket
小评
\(\mathcal{}Consider\ by\ Wida\)
\(\mathcal{}Solved\ by\ Wida\)
打卡（ / 5）
题意
思路
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n, T;
int main() {
cin >> T;
while(T -- > 0) {
cin >> n;
for(int i = n; i <= 10000; i ++) {
if(i % 7 == 0 && i % 4 != 0) {
cout << i << endl;
break;
}
}
}
return 0;
}
H - Singing Everywhere
小评
\(\mathcal{Consider\ by\ Wida\ \&\ Hwh}\)
\(\mathcal{}Solved\ by\ Hwh\)
打卡题（4 \ 5），这道题也想了有一段时间。由我开题，最初以为只是一个极其简单的判断题，而后 \(\mathcal Hwh\) 果断提出了反例，才开始向贪心的方向思考。本题细节较多，思维一定要清晰。
题意
给定一个长度为 \(N\) 的序列 \(A\) ，定义“不和谐”，指值大于左右两侧的元素（即 \(A_{k-1} < A_k > A_{k + 1}\) ）。你至多可以删除一个元素，使得序列“不和谐”最小，输出这个最小值。
思路
试考虑样例
24142，最优方案是删除元素 \(1\) 。
可以发现，本题只有两种删除方式：
- 删除“不和谐”元素，并且不会出现新的”不和谐“元素，这会使得“不和谐” \(-1\) ；
- 如上例，删除一般元素，这会使得“不和谐” \(-2\) ，而这是最优方案。
模拟遍历即可。
AC代码
点击查看代码
const int N = 1e6 + 7;
int a[N];
void Solve() {
int n; cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
a[0] = a[n + 1] = INF;
int ans = 0, f = 0;
for (int i = 2; i <= n - 1; ++ i) {
if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
++ ans;
}
}
for (int i = 2; i <= n - 1; ++ i) {
int L = a[i - 2], l = a[i - 1], r = a[i + 1], R = a[i + 2];
if (l == r && max(L, a[i]) < l && max(a[i], R) < r) f = 2;
if (max(l, r) < a[i] && max(L, r) > l && max(l, R) > r) f = max(f, 1);
}
cout << ans - f << endl;
}
I - Fibonacci in the Pocket
小评
\(\mathcal{}Consider\ by\ Wida\ \&\ Hwh\)
\(\mathcal{}Solved\ by\ Wida\ \&\ Hwh\)
打卡（ / 5）
题意
询问斐波那契数列的 \(L\) 到 \(R\) 项之和的奇偶性。其中 \(1\le a \le b \le 10^{10000}\) 。
思路
观察斐波那契数列可得，其排布为“奇数，奇数，偶数”的循环，故以 \(3\) 为周期进行分割即可。
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
string s, t;
while (T -- ) {
cin >> s >> t;
int a = 0, b = 0;
for (int i = 0; i < s.size(); ++ i) a += s[i] - '0';
for (int i = 0; i < t.size(); ++ i) b += t[i] - '0';
int p = a % 3, q = b % 3;
int flag = 0;
if (p == 2) flag ++ ;
if (q == 1) flag ++ ;
cout << flag % 2 << endl;
}
return 0;
}
J - Welcome Party
小评
一开始题意理解错了，以为是一道图论打卡题，于是很快的码了一发然后交上去了，结果爆了，队友 \(\mathcal {Hwh}\) 提醒之后重新改了一发结果又爆了，这之后的错误更是千奇百怪，一直到结束都没能解出来。后来补题的时候发现自己写的代码全是漏洞，然后发现了板子里面的初始化的错误，直接死亡。图论果然还是个细致活啊。
题意
开趴咯，现在一共有 \(N\) 个人要进入现场，这 \(N\) 个人一共有 \(M\) 对好友，如果某个人进入现场时发现里面没有自己的好友，那么Ta就会不爽。而编号小的人由于是领导，所以要尽可能早的场。请你安排一个合理的入场顺序，使得所有人的不爽值最小，并且输出这个不爽值下最合理的入场顺序（使得尽可能领导先入场）。
思路
赛时思路（是错的）
点击查看原因
- 本题只给出了 \(M\) 对好友关系，但是这个关系是不具有传递性的，即题中所述， \(a,b\) 是朋友， \(b,c\) 是朋友， \(a,c\) 未必是朋友。所以我以为只要是同一个团体的成员，进入顺序的先后并不会影响不爽值（即假设 \(1,3\) 和 \(2,3\) 是朋友，那么 \(1,2,3\) 属于同一个团体，不爽值的最小值即为 \(1\) ，那么进入顺序如果为 \(1,2,3\) 并不影响不爽值）。故以为只要找到连通块数量，最佳顺序恒为 \(1-n\) 输出，WA。
- \(\tt{}bfs\) 中，未将放入队列中备用的元素标记为已使用，导致重复入队，MLE。这期间在反复尝试压缩其他数组的内存占用，以及优化优先队列的排序方式（其中还包含 2 次手写队列错误导致的段错误，以及 1 次忘记清空颜色数组导致的编译错误），但是迟迟没发现问题出在优先队列的重复入队上。
- 使用 \(\tt{}dfs\) 计算连通块数量。由于本题数据量较大，反复调用 \(\tt{}dfs\) 函数导致函数栈溢出的段错误。
- 链式前向星清空时应该使 \(\tt{}h[0]\) 到 \(\tt{}h[n]\) 置 \(0\) ，错误写成到 \(\tt{}h[tot]\) （板子里也是错的！），导致WA2。
- 并查集合并时错误的将“祖先节点大的合并到祖先节点小的上去”写成“将孩子节点大的合并到孩子节点小的上去”，WA2。在这期间反复的尝试更改清空数组的范围，并且发现了答案数组 \(\tt{}ans\) 未清空，但迟迟未发现是并查集合并出现了问题。
- 链式前向星未开双倍空间，导致段错误。
正解
首先很容易的能想到，这 \(N\) 个人根据各自关系可以得到一些连通块，最小不爽值即为连通块的数量。对于每一个连通块，只需要输出其中序号最小的那个元素即可。我们可以使用带条件的并查集完成这两个操作：将大的元素连接到小的元素上去，这样每一个连通块的父节点即为这个连通块内最小的那个元素。
最后使用 \(\tt{}bfs\) 输出即可。
AC代码
点击查看代码
\(\tt{}dfs\) 思路（段错误）
//====================
#define int LL
const int N = 2e6 + 7;
int mp[N], color[N], cnt, v[N];
priority_queue<int, vector<int>, greater<int> > q;
vector<int> ans, ver[N];
//====================
void dfs(int x) {
color[x] = cnt;
for (auto i : ver[x]) {
if (color[i] != 0) continue;
dfs(i);
}
}
void bfs() {
while (!q.empty()) {
int x = q.top(); q.pop();
ans.push_back(x);
v[x] = 1;
for (auto i : ver[x]) {
if (v[i] == 1) continue; v[i] = 1;
q.push(i);
}
}
}
void Solve() {
int n, m; cin >> n >> m;
for (int i = 0; i <= n; ++ i) color[i] = v[i] = 0, mp[i] = 0x3f3f3f3f, ver[i].clear();
cnt = 0; ans.clear();
for (int i = 1; i <= m; ++ i) {
int x, y; cin >> x >> y;
ver[x].pb(y), ver[y].pb(x);
}
for (int i = 1; i <= n; ++ i) {
if (color[i] == 0) {
++ cnt;
dfs(i);
}
}
for (int i = 1; i <= n; ++ i) mp[color[i]] = min(mp[color[i]], i);
for (int i = 1; i <= cnt; ++ i) q.push(mp[i]);
bfs();
cout << cnt << endl;
for (int i = 0; i < n - 1; ++ i) cout << ans[i] << " ";
cout << ans.back() << endl;
}
正解
//====================
#define int LL
const int N = 2e6 + 7;
vector<int> ans;
priority_queue<int, vector<int>, greater<int> > q;
int fa[N], cnt, vis[N];
//====================
int ver[N], h[N], ne[N], tot;
void add(int x, int y) {
ver[++ tot] = y, ne[tot] = h[x], h[x] = tot;
}
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
x = get(x), y = get(y);
if (x < y) fa[y] = x;
else fa[x] = y;
}
void bfs() {
while (!q.empty()) {
int x = q.top(); q.pop();
ans.push_back(x);
vis[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y] == 1) continue; vis[y] = 1;
q.push(y);
}
}
}
void Solve() {
int n, m; cin >> n >> m;
for (int i = 0; i <= n; ++ i) vis[i] = h[i] = 0, fa[i] = i;
cnt = tot = 0; ans.clear();
for (int i = 1; i <= m; ++ i) {
int x, y; cin >> x >> y;
merge(x, y);
add(x, y), add(y, x);
}
for (int i = 1; i <= n; ++ i) {
if (i != fa[i]) continue;
++ cnt;
q.push(i);
}
cout << cnt << endl;
bfs();
for (int i = 0; i < n - 1; ++ i) cout << ans[i] << " ";
cout << ans.back() << endl;
}
文 / WIDA
2022.04.05 成文
首发于WIDA个人博客，仅供学习讨论
标签：Hwh,int,tt,cin,2019,ans,mathcal,TeamVP,浙江省 From： https://www.cnblogs.com/WIDA/p/16784143.html