思路1：
1.把数拆成1，2，n-3
2.如果（n-3）%3==0,那么拆成1,4,n-5，可证明n-3如果可被3整除，那么再左移两位一定除不尽
思路2：
1.如果n是奇数，那么可取一个数为2，其他两数为相邻数，如果两数其中一位被整除，那么两者往外走
2.如果n为偶，那么可取一个数为1，同理上
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
if (n <= 6 || n == 9) {
cout << "NO\n";
}
else if (n % 2) {
cout << "YES\n";
int x = (n - 2) / 2, y = n - 2 - x;
if (x % 3 == 0 || y % 3 == 0) x--, y++;
cout << 2 << ' ' << x << ' ' << y << '\n';
}
else {
cout << "YES\n";
int x = (n - 1) / 2, y = n - 1 - x;
if (x % 3 == 0 || y % 3 == 0) x--, y++;
cout << 1 << ' ' << x <<' ' << y << '\n';
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
思路：
1.如果两点在同一个圆上
2.如果俩圆相交或者相切
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define db double
db dis(int x1, int y1, int x2, int y2) {
return sqrt(1.0*(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void solve() {
int x[3] = {}, y[3] = {};
for (int i = 0; i < 3; i++) cin >> x[i] >> y[i];
db ans = 1e9;
//在一个圆上，分别计算a，b两圆
ans = min(ans, max(dis(x[0], y[0], x[1], y[1]), dis(0, 0, x[1], y[1])));
ans = min(ans, max(dis(x[0], y[0], x[2], y[2]), dis(0, 0, x[2], y[2])));
//两圆相交或相切
ans = min(ans, max(dis(x[2], y[2], x[1], y[1]) / 2, max(dis(0, 0, x[1], y[1]), dis(x[0], y[0], x[2], y[2]))));
ans = min(ans, max(dis(x[2], y[2], x[1], y[1]) / 2, max(dis(0, 0, x[2], y[2]), dis(x[0], y[0], x[1], y[1]))));
printf("%0.10lf\n", ans);
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Decreasing String
思路：
1.如果字符有序，如abcd，则从后往前删
2.如果无须，如adbc，则需要先删除d，变成abc，变成有序
3.则可以利用单调栈记录有序的字符：
3.1如果新来的字符更小，则删除头顶的字符，一直删到小于等于位置，然后把新来的位置插入头顶。
3.2如果新来的更大，直接插入
3.3并计算位置是第几次删除的
利用单调栈
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define db double
const int N = 1e6 + 10;
int id[N],t[N];//id表示第几次删除
void solve() {
string s;
cin >> s;
int n = s.length();
s = " " + s;
int m = 0;
int x = 0;
for (int i = 1; i <= n; i++) {
while (m > 0 && s[t[m]] > s[i]) id[t[m]]=++x,m--;
t[++m] = i;
}
while (m) id[t[m]] = ++x, m--;//此时有序，直接从后面删除
LL pos,now=n;//pos很大记得开LL
cin >> pos;
x = 0;
while (pos - now > 0) pos -= now, now--, ++x;//x计算删除了几次
string str = " ";
for (int i = 1; i <= n; i++) {
if (id[i] > x) str += s[i];
}
cout << str[pos];
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
正序有点难算，我们反过来从结果推，此时集合元素为n
1.倒序，如果此位置是>或<,则要删掉最大值或者最小值，只有唯一的方法
2.如果是？，位置为i，那么知道此时集合的元素为i个（i位置还没有放入元素时）,那么可放入的元素应该是除去集合内的最值，选法为i-2，累乘ans
特判：如果第一个位置为？无解，因为只可能是确切的数字
对于修改操作：
1.如果修改前的位置元素为'?'，那么就需要除以对应位置的选法（因为是取模意义下的除法，要用乘法逆元）
2.如果修改成为了'?'，则需乘上对应的选法
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define db double
const int N = 1e6 + 10,mod=998244353;
//char s[N];
void solve() {
int n, m;
cin >> n >> m;
LL ans = 1;
string s;
cin >> s;
s = " " + s;//偏移
for (int i = 3; i <=n; i++) {
if (s[i] != '?') continue;
ans =ans*(1LL*i - 2) % mod;//偏移->防止为0
}
cout << (s[2] == '?' ? 0 : ans)<<'\n';
auto qpow = [](LL a, int b) {//快速幂
LL res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
while (m--) {
int x;
cin >> x;
x++;//偏移
char c;
cin >> c;
if (s[x]== '?'&&x>2) ans = ans * qpow(1LL*x - 2, mod - 2) % mod;//x大于第一，且s[x]=='?',说明这个位置ans算过要除以这个位置上的权值（乘法逆元）
s[x] = c;
if (s[x] == '?'&& x>2) ans = ans * (1LL * x - 2) % mod;//乘上该位置的权值
cout << (s[2] == '?' ? 0 : ans) << '\n';
}
}
int main() {
int t=1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}