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;
}