Contestant. Rank 263. Rating +90.
A. Sum of Three
题意
给定一个整数 \(n\)，构造一种方案，使得 \(n = x + y + z\)，且 \(x \neq y \neq z; x, y, z \not \equiv 0 \pmod 3\)。
思路
分类讨论。
首先，最小的构造是 \(x = 1, y = 2, z = n - 3\)，那么显然，\(n - 3 > 2\)，即 \(n \geq 6\)。
并且，因为 \(z\) 不可以是 \(3\) 的倍数，所以 \(n\) 也不可以是 \(3\) 的倍数。
那么，如果 \(n\) 是 \(3\) 的倍数，我们考虑次小的构造：\(x = 1, y = 4, z = n - 5\)，此时 \(n - 5 > 4\)，即 \(n \geq 10\)。
此时，可以发现 \(n - 5\) 不是 \(3\) 的倍数，从而符合要求。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
if(n % 3 == 0){
if(n <= 9) {
cout << "NO\n";
return;
}
cout << "YES\n";
cout << 1 << ' ' << 4 << ' ' << n - 5 << '\n';
}else{
if(n <= 5) {
cout << "NO\n";
return;
}
cout << "YES\n";
cout << 1 << ' ' << 2 << ' ' << n - 3 << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}好久没有 \(A\) 写这么久了（
B. Fear of the Dark
题意
给定一个目标点，以及两个光源。输出最小的光源半径，使两个光源将从原点 \((0, 0)\) 到目标点的任意一条路径全都照亮。
思路
显然，半径更大，能照亮的概率更大，具有单调性，从而我们考虑二分。
我们按照下面的方式检查半径是否合法：
任意一个光源到目标点的距离小于半径；
任意一个光源到原点的距离小于半径；
任意一个光源覆盖原点和目标点，或者两个光源的距离小于半径之和
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int px, py, ax, ay, bx, by;
cin >> px >> py >> ax >> ay >> bx >> by;
auto comp = [&](double a, double b){
if(a < b) return true;
if(fabs(a - b) <= eps) return true;
return false;
};
auto dist = [&](double x1, double y1, double x2, double y2){
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
};
auto check = [&](double r) -> bool {
bool f1 = false, f2 = false, f3 = false;
if (comp(dist(px, py, ax, ay), r * r) && comp(dist(0, 0, ax, ay), r * r)) f1 = true;
if (comp(dist(px, py, bx, by), r * r) && comp(dist(0, 0, bx, by), r * r)) f1 = true;
if (comp(dist(ax, ay, bx, by), 4 * r * r)) f1 = true;
if (comp(dist(px, py, ax, ay), r * r) || comp(dist(px, py, bx, by), r * r)) f2 = true;
if (comp(dist(0, 0, ax, ay), r * r) || comp(dist(0, 0, bx, by), r * r)) f3 = true;
return f1 && f2 && f3;
};
double l = 0, r = 1e5, mid;
while(r - l > eps){
mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
cout << fixed << setprecision(9) << l << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}其实可以直接解，但精度要求不高，浮点数二分过得去
C. Decreasing String
题意
给定一个长为 \(n\) 的由小写字母组成的字符串 \(s\)，以及初始状态下等于 \(s\) 的字符串 \(p\)。
接下来会有 \(n - 1\) 次操作，每次操作会从字符串里删除一个字符，并满足删除的所有方案中，该方案删除后得到的字符串字典序最小。
对于每次操作完后得到的 \(s\)，将其拼接到 \(p\) 的后面，从而最后 \(p\) 是一个长度为 \(\frac{n(n - 1)}{2}\) 的字符串。
给定一个整数 \(x\)，输出 \(p_x\) 对应的字符。
思路
首先，删除的方案是：如果存在一个点 \(i\)，满足 \(s_i > s_{i + 1}\)，那么删除 \(s_i\)；否则，我们从最后一个字符开始往前删。
暴力模拟是不可行的，但是考虑到单点查询，我们完全可以不用推出前面操作后得到的答案。
那么我们只要处理查询的字符对应的字符串是什么即可。
我们可以简单计算得到，\(x\) 位于第几个字符串，我们记其为 \(l\)。
那么，问题转化为：维护一个长为 \(l\) 的单调序列，如果在长度大于 \(l\) 时已经递增，那么考虑从后往前删。
那么，我们直接用单调栈即可解决此题。合理使用 \(\mathtt{stl}\) 即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s;
int pos;
cin >> s >> pos;
int n = s.size();
s = " " + s;
int at = 0, sum = 0;
for(int i=1;i<=n;i++){
sum += n - i + 1;
if(sum >= pos){
at = i;
break;
}
}
pos -= ((n - (at - 1) + 1) + n) * (at - 1) / 2;
set<int> st;
int ind = 0;
st.ep(++ ind);
for(int i=2;i<=at;i++){
while(ind + 1 <= n && (st.empty() || s[ind + 1] >= s[*st.rbegin()]))
st.ep(++ ind);
st.extract(-- (st.end()));
}
for(int i=ind+1;i<=n;i++) st.ep(i);
auto ans = st.begin();
for(int i=1;i<pos;i++) ans ++;
cout << s[*ans];
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}写完才发现写了个单调栈（x
D. Monocarp and the Set
题意
对于一个序列 \(a\)，以及一个空字符串 \(s\)，定义构造方式如下：
对于 \(i \in [2, n]\)，如果 \(a_i\) 比前面的所有数都小，那么在 \(s\) 里放入一个 \(<\)；如果 \(a_i\) 比前面的所有数都大，那么放入 \(>\)；否则放入 \(?\)。
现在，给定构造好的字符串 \(s\)，并给定 \(q\) 个非独立询问：
每个询问给定一个整数 \(i\) 和一个字符 \(c\)，并将 \(s_i\) 修改为 \(c\)。
输出询问前，以及每一次询问修改后，字符串 \(s\) 对应的原序列 \(a\) 有多少种。
思路
我们考虑逆向思维。
首先，如果当前位置是 \(>\) 或 \(<\)，那么这个位置的数值是唯一确定的，否则，如果这个位置位于 \(i\)，我们就有 \(i - 1\) 种选择。
为何是 \(i - 1\) ？因为我们只能把最小值或最大值放在第一个位置，而因为这个位置是 \(?\)，所以它不可以是可以放置的最大值或最小值，从而会少一种取法。
最后累乘即可。
至于询问，我们直接模拟替换，然后更新答案即可，当然，如果第一位是 \(?\)，我们在最后输出的时候输出 \(0\) 即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
static __int128 ans;
ans = 1, x %= m;
for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
return ans;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }
void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
int ans = 1;
for(int i=1;i<n;i++){
if(s[i] == '?') ans = ans * i % mod;
}
cout << (s[0] == '?' ? 0 : ans) << '\n';
while(q --){
int x;
char c;
cin >> x >> c;
if(x != 1) {
if (s[x - 1] != '?' && c == '?') {
ans = ans * (x - 1) % mod;
} else if (s[x - 1] == '?' && c != '?') {
ans = ans * inv(x - 1) % mod;
}
}
s[x - 1] = c;
cout << (s[0] == '?' ? 0 : ans) << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}最神秘的是打表可以看出规律（x