Educational Codeforces Round 156 (Rated for Div. 2) ABCD
A. Sum of Three
题意：给定正整数 \(n\)，判断是否存在正整数 \(a\)，\(b\)，\(c\) 满足：
- \(a+b+c=n\)。
- \(a\)，\(b\)，\(c\) 均不是 \(3\) 的倍数。
如存在，输出 YES 并构造一组方案，否则输出 NO 。
思路：
法一：我们分类讨论。
根据余数分为：
-
\(n \% 3=0\)
最小的合法数是\(12=1+4+7\)
-
\(n \% 3=1\)
最小的合法数是\(7=1+2+4\)
-
\(n \% 3=2\)
最小的合法数是\(11=1+2+8\)
那么我们发现，\(n\le 6\)的都是不合法的，其他情况可以拆分成\(1,4,n-5\)或者\(1,2,n-3\)
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
if(n<=6)
{
cout<<"NO\n";
continue;
}
if(n%3==0)//12 = 1 + 4 + 7
{
if(n<12){
cout<<"NO\n";
continue;
}
else
{
cout<<"YES\n";
cout<<1<<" "<<4<<" "<<n-5<<"\n";
}
}
else if(n%3==1)//7 = 1 + 2 + 4
{
if(n<7)
{
cout<<"NO\n";
continue;
}
cout<<"YES\n";
cout<<1<<" "<<2<<" "<<n-3<<"\n";
}
else if(n%3==2)//11 = 1 + 2 + 8
{
if(n<8)
{
cout<<"NO\n";
continue;
}
cout<<"YES\n";
cout<<1<<" "<<2<<" "<<n-3<<"\n";
}
}
return 0;
}
法二：如果不想分类讨论呢，我们可以手玩几个样例，大胆猜测，前两个数一定能在10以内确定下来，暴力枚举即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
void solve(int n)
{
for(int x = 1; x <= n; x++)
{
for(int y = x + 1;y < n-x-y; y++)
{
int z = n-x-y;
if(x % 3 && y % 3 && z % 3 && z > 0)
{
cout<<"YES\n";
cout<<x<<" "<<y<<" "<<z<<"\n";
return;
}
}
}
cout<<"NO\n";
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
solve(n);
}
return 0;
}
B. Fear of the Dark
题意：起点是\((0,0)\)，给你终点\((p_x,p_y)\)和两个光源\((A_x,A_y),(B_x,B_y)\)。人从起点到终点且所走的路线一定要被光源覆盖。问最小的光源半径是多少？
思路：考虑合法情况：
- 两个点被同一个光源覆盖
- 两个点分别被不用光源覆盖，且两个圆有交(相切也可以)。
我们考虑二分答案，去check就行了
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
double px,py,ax,ay,bx,by;
const double eps = 1e-9;
double get(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool in(double r,double d)
{
return d<=r;
}
bool check(double r)
{
double da = get(px,py,ax,ay),db = get(px,py,bx,by);
double do1 = get(0,0,ax,ay),do2 = get(0,0,bx,by);
if((in(r,da)&&(in(r,do1)))||(in(r,do2)&&in(r,db)))
{
return true;
}
else
{
double ab = get(ax,ay,bx,by);
if(((in(r,da)&&in(r,do2))||(in(r,db)&&in(r,do1)))&&ab<=2*r)
{
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
cin>>px>>py>>ax>>ay>>bx>>by;
double l = 0, r = 1e4, mid, ans;
while(fabs(l-r)>=eps){
mid = (l+r)/2;
if(check(mid))
r = mid;
else
l = mid;
}
ans = mid;
printf("%.12f\n",ans);
}
return 0;
}
C. Decreasing String
题意：有 \(t\) 组测试点，每组测试点给出字符串 \(s_1\) 和 一个整数 \(pos\)。
以下列规则得到字符串 $ S $ ：
- 从 $ s_{i - 1} $ 中删除一个字符，字典序最小的记为 $ s_i $
- $S = s_1 + s_2 + \dots + s_n $
输出字符串 $ S $ 第 \(pos\) 个位置上的字符（即 $ S_{pos} $）。
思路：这题很神奇，思路很巧妙，本人很菜没想出，看jls的代码学习的。
正解是单调栈。
我们每次得到的字符串长度是上次的长度-1。考虑：我们要求最终串的\(pos\)位，我们真的需要知道最终的串长什么样子吗？
不用的，因为\(S = s_1+s_2+...+s_n\)，我们只要确定我们的\(pos\)是子串\(s_x\)种的第几位就行了。那么我们得先确定出\(s_x\)是第几个串，和第\(x\)个串的第几个。
我们\(for(i=0～n-1)\)
第\(i\)次的长度是\(n-i\)，一旦不够减了，说明\(pos\)在我们的这个串\(i\)里面了
确定出这两个，我们只要求出第\(i\)个串长什么样就可以轻松求得答案了。
因为是第\(i\)个串，说明我们删了\(i\)个字符，我们要保证字典序最小，说明加入的一定是个尽量单调递减的串。我们考虑用单调栈维护。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
string s; cin>>s;
ll n = s.size();
ll pos; cin>>pos;
pos--;
int x, y;
for (int i = 0; i < n; i++) {
int len = n - i;
if (pos < len) {
x = i;//编号即删的次数
y = pos;//位置
break;
}
pos -= len;
}
string ans = "";//构造第i个串
for(auto c : s) {
while(x > 0 && !ans.empty() && c < ans.back()) {
ans.pop_back();
x--;
}
ans += c;
}
cout<<ans[y];
}
return 0;
}
D.Monocarp and the Set
题意：
Monocarp有 \(n\) \((2 \leq n \leq 3 \times 10^5)\)个数字 \(1,2,...n\) 以及一个空集合。他每次以一定顺序将数字加入集合。每个步骤中，他会将一个不在集合中的数加入集合。换言之，最终加入集合的顺序是n的一个排列。
从第二次开始，每次monocarp将元素添加到集合中时，他会写下一个字符
-
如果Monocarp尝试插入的元素成为集合中的最大元素，Monocarp将写下>
-
如果Monocarp尝试插入的元素成为集合中的最小元素，Monocarp将写下<
-
如果不符合以上两种情况，Monocarp将写下?
给你一个长度为 \(n-1\) 的字符串 \(s\) ，代表Monocarp按顺序写下的字符，你需要处理 \(m\) \((1 \leq m \leq 3 \times 10^5)\) 次询问，每个询问格式如下：
- \(i\) \(c\) - 将 \(s_i\) 替换为字符 \(c\)
对于初始字符串和每次查询，请输出一个整数，代表可以得到字符串 \(s\) 的不同插入顺序的数量。由于答案可能很大，只需给出这个数模 \(998244353\) 的结果。
思路：介个题其实思维难度上不大，但是看着吓人。
我们先预处理出初始答案。我们正向考虑，如果当前是\(?\)，那么能插入的位置是除了开头和结尾的任意一个(方案数是元素个数-2)。如果是\(> or <\)，那么一定是插入到一头或一尾(方案数是1)。
那么：
- 是\(?\)：\(f[i] = f[i-1]*(i-2)\)
- 是\(> or <\)：\(f[i] = f[i-1]*1\)
对于修改操作：如果更改了，其实就是乘上原方案数的逆元再乘修改后方案数即可。
注意：考虑不合法情况，如果一开始是\(?\)肯定是无解的，特判一下就行了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 998244353;
const int N = 3e5 + 10;
int n,m;
string s;
bool fg;
ll ans = 1,inv[N];
void init()
{
s = "?"+s;
fg = (s[1]!='?');
for(int i = 2;i < n; i++)
ans = (ans*(s[i]=='?'?i-1:1))%p;
inv[1] = 1;
for (int i = 2; i <= n; ++ i) {
inv[i] = 1ll * (p - p / i + p) % p * inv[p % i] % p;
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m>>s;
init();
cout<<(fg?ans:0)<<"\n";
for(int i = 1;i <= m; i++)
{
int pos; char ty;
cin>>pos>>ty;
if(pos==1)
fg = (ty!='?');
else{
ans = (ans*(s[pos]=='?'?inv[pos-1]:1))%p;
ans = (ans*(ty=='?'?pos-1:1))%p;
}
s[pos] = ty;
cout<<(fg?ans:0)<<"\n";
}
return 0;
}