Contestant. Rank 474. Rating +86.
A. Politics
题意
对于 \(n\) 个人，有 \(m\) 个意见，每个人需要对意见做表率（\(+\)表示同意，\(-\) 表示不同意）。
在对一个意见做完表率后，如果同意的人多，那么不同意的人将会离开；如果不同意的人多，那么同意的人将会离开；如果人数一样多，那么所有人都离开。
规定可以在所有人表率前，拿掉一些人。设第一个人为自己，那么输出自己能留到最后的条件下最后剩余的人数的最大值。
思路
首先，如果有其他人的任意一个意见的表率和自己不一样，那么最后自己或者那个不一样的人会离开，所以，所有意见的表率和自己都相同的人的个数加上 \(1\) 就是答案。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, k;
cin >> n >> k;
vector<string> s(n);
for(int i=0;i<n;i++) cin >> s[i];
int ans = 0;
for(int i=0;i<n;i++) if(s[0] == s[i]) ans ++;
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}抽象
B. Indivisible
题意
给定一个整数 \(n\)，构造一个 \(n\) 的排列，满足对于任意 \(1 \leq l < r \leq n\)，\((a_l + a_{l + 1} + \ldots + a_r) \bmod (r - l + 1) \neq 0\)。
思路
我们先来考虑两个连续的数，既然它们不能被 \(2\) 整除，那么我们不妨直接用一个奇数和一个偶数拼接。
或者换句话说，排列为奇偶相间的。
对于三个连续的数，不能被 \(3\) 整除，那么这三个数不可以是 \(a - 1, a, a + 1\)。
从这里就已经出现一定的规律了，我们不妨按照 \(2, 1, 4, 3, \ldots, 2n, 2n - 1\) 的方法构造，很巧，其他约束均满足。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
if(n == 1) cout << 1 << '\n';
else{
int cnt = (1 + n) * n / 2;
if(cnt % n == 0) cout << -1 << '\n';
else{
for(int i=1;i<=n/2;i++) cout << i * 2 << ' ' << i * 2 - 1 << ' ';
cout << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}乱猜即可
C. Almost Increasing Subsequence
题意
如果一个序列中不包含任何 连续的 三元组 \((x, y, z)\) 满足 \(x \geq y \geq z\)，那么定义该序列 几乎递增。
现在，给定一个序列以及若干询问，对于 \([l_i, r_i]\) 的区间询问，输出该区间中几乎递增的序列的最大长度。
思路
因为三元组是连续的，所以我们可以直接计算出前 \(x\) 个数中几乎递增的序列的长度。
或者说，这里采用了一种类似于前缀和的做法：
如果 \(a_{i - 2} \geq a_{i - 1} \geq a_i\)，那么 \(sum_i = sum_{i - 1}\)；
否则，\(sum_i = sum_{i - 1} + 1\)。
但是这样相减是不够的，如果左边界出现了不满足条件的三元组，这时答案会偏小。因为三元组的一部分包含在区间中时，并不会不满足条件。
因此，我们可以顺便记录统计的时候当前位置是否出现了不满足条件的三元组，即标记 \(f_i = true\)，那么如果 \(f_l = true\)，答案 \(+1\)；如果 \(f_{l + 1} = true\)，答案再 \(+1\)（当然，\(l + 1\) 要在区间中）。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1), ans(n + 1);
vector<bool> st(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
ans[0] = 0;
ans[1] = 1;
ans[2] = 2;
for (int i = 3; i <= n; i++) {
ans[i] = ans[i - 1];
if (a[i - 2] >= a[i - 1] && a[i - 1] >= a[i]) st[i] = true;
else ans[i] ++;
}
while (q --) {
int l, r;
cin >> l >> r;
int w = ans[r] - ans[l - 1];
if (st[l]) w ++;
if (r != l && st[l + 1]) w ++;
cout << w << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}好妙
D. Fish Graph
题意
给定一个无向不完全联通图，找出一个 "鱼"，并输出它的所有边。找不到输出 \(NO\)。
其中，"鱼" 定义为一个环加上其中一个点所多连出的两条边。注意，这两条边不可以和环中的其他点连接。
思路
首先，数据量很小，我们不妨直接枚举两个点 \(u, v\)，并忽略 \(u - v\) 这条边。我们从 \(u\) 节点开始 \(dfs\)，若能到 \(v\)，那么就存在了环。
此时，我们将 \(u\) 作为特殊点，那么在开始 \(dfs\) 前，我们还得满足 \(u\) 的度数大于等于 \(4\)。
设 \(dfs\) 的路径点集为 \(step\)，\(u\) 的所有子节点为 \(extra\)。
首先，我们只需随便选 \(extra\) 中的 \(4\) 个，因为最多只会有两条边在路径中。
那么，我们枚举 \(extra\)，如果 \(extra\) 中的点都不在 \(step\) 中，那么很凑巧，去掉 \(extra\) 中在路径中的两个点，剩余的两个点和这个环就可以构成一个答案。
但如果出现了，因为题目要求多出的两条边不可以和环中的其他点连接，我们就需要另行处理。
显然，我们只需考虑一种情况，也就是当 \(extra\) 中包含了路径中的两个点，但是有一条边和环中的其他点相连的时候。
此时，我们找到了一个更小的环，如果我们将这个更小的环作为答案，那么 \(extra\) 中剩余的一个点和原来在路径中的一个点就可以作为多出来的那两条边了。
因此，按照上述算法，可以保证一定可以找出一条鱼。
最后，我们将 \(step\) 和 \(extra\) 稍做处理即可得到答案。
时间复杂度：\(O(m \cdot (n + m))\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(), x.end()
void solve(){
int n, m;
cin >> n >> m;
vector<vector<int>> e(n);
for(int i=0;i<m;i++){
int u, v;
cin >> u >> v;
u --, v --;
e[u].pb(v), e[v].pb(u);
}
for(int u=0;u<n;u++){
if(e[u].size() < 4) continue;
for(auto v : e[u]){
vector<int> now, step;
bool ok = false;
vector<bool> vis(n);
auto dfs = [&](auto self, int p){
vis[p] = true;
now.pb(p);
if(p == v) { //绕回v了
step = now;
ok = true;
return;
}
for(auto to : e[p]){
if(vis[to] || (p == u && to == v)) continue;
self(self, to); //lambda递归调用
if(ok) return;
}
now.pop_back();
};
dfs(dfs, u);
if(!ok) continue;
vector<int> extra = e[u];
extra.resize(4); //挑4个即可
int mn = step.size();
for(auto x : extra){ //根据这4个来重新调整环（因为环内可能还有小环，我们拿小环更好，可以保证一定满足条件
auto it = find(all(step), x);
if(it != step.begin() + 1){
mn = min(mn, (int)(it - step.begin()) + 1);
}
}
step.resize(mn);
partition(all(extra), [&](int x){
return count(all(step), x) == 0;
}); //删掉在环中的那些点
extra.resize(2);
cout << "YES" << '\n' << step.size() + 2 << '\n';
int pre = step.back();
for(auto x : step){
cout << x + 1 << ' ' << pre + 1 << '\n';
pre = x;
}
cout << u + 1 << ' ' << extra[0] + 1 << '\n' << u + 1 << ' ' << extra[1] + 1 << '\n';
return;
}
}
cout << "NO" << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}参考了官方题解对出现 "更小环" 时的处理