Contestant'. Rank 1622. Rating +15.
A. Grasshopper on a Line
题意
给定一个数轴，终点 \(x\) 以及一个整数 \(k\)，定义一次操作为从当前位置向右移动 \(p\) 格，满足 \(p\mod k \neq 0\)。输出从原点走到 \(x\) 所需的最小的操作数以及方案。
思路
如果 \(x\) 不能被整除，一步即达。
可以被整除的话，\(x - 1\) 肯定不会被整除（互质），因此选择先走一格再走 \(x - 1\) 格。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
if(n % k == 0) cout << 2 << '\n' << 1 << ' ' << n - 1 << '\n';
else cout << 1 << '\n' << n << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}和之前的某个签到题很像
B. Comparison String
题意
给定一个由 \(<\) 和 \(>\) 组成的字符串，定义如果第 \(i\) 位为 \(<\)，那么 \(a_i < a_{i + 1}\)，否则 \(a_i > a_{i + 1}\)。
构造一个满足条件的序列 \(a\)，输出不同数字的最少个数。
思路
很显然，如果出现了单调的区间，那么这段长为 \(k\) 的区间内一定有 \(k\) 格不同的数字，不同单调序列的元素可以共用，因此答案即为所有单调区间的长度的最大值。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int ans = 1, sum = 1;
for(int i=0;i<n;i++){
if(s[i] == s[i + 1]) sum ++;
else sum = 1;
ans = max(ans, sum);
}
cout << ans + 1 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}不可模拟，模拟有坑
C. Best Binary String
题意
给定一个二进制字符串，其中有若干位被替换为 \(?\)。
定义对于一个二进制串，一次操作为选定一个区间并将这个区间内的数字左右翻转，代价为 \(1\)。
输出一种 \(?\) 的替换方案，使让字符串不递减的代价最小。
思路
首先，如果将问号替换成前面的数，就可以让代价最小，这是显然的。
那么，如果第一个是问号，显然我们不希望再多一个 \(1\)，因此直接放 \(0\)。
反过来也行，最后一位放 \(1\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
string s;
cin >> s;
int n = s.size();
if(s[0] == '?') s[0] = '0';
char pre = s[0];
for(int i=1;i<n;i++){
if(s[i] == '?'){
s[i] = pre;
}else pre = s[i];
}
cout << s << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}一开始写的思路差点就对了，淦
D. Bracket Coloring
题意
给定一个由左右括号组成的字符串，定义满足下面条件任意一个即为 "美丽的"：
符合语法规则；
将字符串逆序输出后得到新的字符串，新的字符串满足语法规则
定义可将字符串涂色，涂色后，任取一种颜色，将该颜色的所有括号拿出后得到的新字符串都是 "美丽的"。
输出最少颜色种数，以及对应的一种方案。
需满足涂入的颜色编号小于等于颜色种数。
思路
我们不妨直接模拟，用队列存上一个最近的可配对的括号，因而我们进行分讨：
遇到 \((\)： 如果上一个括号为 \((\)，那么放入队列中等待配对； 如果上一个括号为 \()\)，那么配对，并归入第一种颜色
遇到 \()\)： 如果上一个括号为 \()\)，那么放入队列中等待配对； 如果上一个括号为 \((\)，那么配对，并归入第二种颜色
可以证明，最多只需两种颜色，如果上述操作后仍有没有配对的括号，那就无解。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
queue<pci> q1, q2;
vector<int> ans(n, 1);
bool f1 = false, f2 = false;
for(int i=0;i<n;i++){
char now = s[i];
if(now == '('){
if(q1.empty() || q1.front().fs == '(') q1.emplace(now, i);
else{
auto e = q1.front();
q1.pop();
ans[e.sc] = ans[i] = 2;
f1 = true;
}
}else{
if(q1.empty() || q1.front().fs == ')') q1.emplace(now, i);
else{
q1.pop();
f2 = true;
}
}
}
if(q1.empty()){
cout << (f1 && f2 ? 2 : 1) << '\n';
if(f1 && f2) for(auto e : ans) cout << e << ' ';
else for(int i=0;i<n;i++) cout << 1 << ' ';
cout << '\n';
}else cout << -1 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}乱猜的居然过了（