Educational Codeforces Round 156 (Rated for Div. 2)

A. Sum of Three

解题思路:

如果$n \leq 6 或 n =9$,无解。

若$n \% 3 == 0，t = \lfloor\frac{3}{n}\rfloor$:

若$t = 0$构造$1,4,n - 5$
否则，构造$t - 3,t ,t + 3$

若$n \% 3 == 1 : 构造1,2，n - 3$

若$n \% 3 == 2:构造1,2,n - 3$

主要就是三个数$mod\ 3$的和要等于$n \% 3$。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second

void solve()
{
    int n;
    scanf("%d", &n);
    if (n <= 6 || n == 9)
    {
        puts("NO");
    }
    else
    {
        int t = n / 3;
        int res = n % 3;
        if (res == 0)
        {
            if (t % 3 == 0)
            {
                puts("YES");
                printf("1 4 %d\n", n - 5);
            }
            else if (t % 3 == 1)
            {
                puts("YES");
                printf("%d %d %d\n", t - 3, t, t + 3);
            }
            else
            {
                puts("YES");
                printf("%d %d %d\n", t - 3, t, t + 3);
            }
        }
        else if (res == 1)
        {
            puts("YES");
            printf("1 2 %d\n", n - 3);
        }
        else
        {
            puts("YES");
            printf("1 2 %d\n", n - 3);
        }
    }
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

B. Fear of the Dark

解题思路：

答案半径具有单调性，二分答案。

一共两种情况：两个点被一个圆包住了，两个点分别被一个圆包住了并且两圆相交。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const double eps = 1e-10;

void solve()
{
    double px, py, ax, ay, bx, by;
    scanf("%lf %lf %lf %lf %lf %lf", &px, &py, &ax, &ay, &bx, &by);
    double l = 0;
    double r = 1e9;
    auto dist = [&](double x1, double y1, double x2, double y2) -> double
    {
        double x = x1 - x2;
        double y = y1 - y2;
        return sqrtl(x * x + y * y);
    };
    auto cross = [&](double x1, double y1, double x2, double y2, double r)
    {
        double res = dist(x1, y1, x2, y2);
        if (res <= 2 * r)
        {
            return true;
        }
        return false;
    };
    auto check = [&](double mid)
    {
        double pa = dist(px, py, ax, ay);
        double pb = dist(px, py, bx, by);
        double sa = dist(ax, ay, 0, 0);
        double sb = dist(bx, by, 0, 0);
        if ((sa <= mid && pa <= mid) || (sb <= mid && pb <= mid))
        {
            return true;
        }
        if (((sa <= mid && pb <= mid) || (sb <= mid && pa <= mid)) && cross(ax, ay, bx, by, mid))
        {
            return true;
        }
        return false;
    };
    while (r - l > eps)
    {
        double mid = (r + l) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.12lf\n", l);
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Decreasing String

解题思路:

我们可以先用高斯求和二分出$pos$在$s_r$这一段中。

那么我们就是要得到从初识字符串中删掉$r - 1$个字符后的最小字典序字符串。

如何得到通过删除多个字符操作最小字典序字符串？

从前往后看，如果前面的字符大于后面的字符那么先删前面的字符。

删完前面的还不够，此时我们的字符串一定是升序字符串，从后面一个个删就行了。

可用单调栈实现。

注意：$pos$开$longlong $

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second

void solve()
{
    string s;
    cin >> s;
    ll pos;
    scanf("%lld", &pos);
    int n = s.size();
    ll l = 0;
    ll r = n + 1;
    while (l + 1 < r)
    {
        ll mid = l + r >> 1;
        if ((n + (n - mid + 1)) * (mid) / 2 < (ll)pos)
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    pos -= (n + (n - l + 1)) * l / 2;
    int cnt = 0;
    stack<char> stk;
    for (int i = 0; i < n; i++)
    {
        while (cnt < l && (stk.size() && (stk.top() > s[i])))
        {
            cnt++;
            stk.pop();
        }
        if (cnt < l)
        {
            stk.push(s[i]);
        }
        else
        {
            stk.push(s[i]);
        }
    }
    string ans;
    while (cnt < l && stk.size())
    {
        stk.pop();
        cnt++;
    }
    while (stk.size())
    {
        ans += stk.top();
        stk.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << ans[pos - 1];
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

D. Monocarp and the Set

解题思路：

操作序列下标从$0 \sim (n - 2)$。

如果$s[0] == '?'$，由于前面只有一个数字，合法排列数一定为零。

往后，如果$s[i] == '?'$，意味着这一位有$i$中选法，因为前面一定已经有$i$个数字。

从后往前考虑对于符号插入位置，如果是$>$,那就只能插在末尾，如果是$<$,那就只能插入队头，如果是$?$，我们能插入$i$个空位中。$i$个空位是因为第$i$个操作时前民已经有了$i + 1$个数字.

对于$i = 0$，我们不进行统计和去除，因为$*0,/0$。$s[0] == '?'$,如果我们开始统计了，后面如果要除去他的影响我们难以处理。开始不计算也合法。因为如果$s[0] 一直等于 '?'$，答案就一直是零。$s[0] !='?'$后，原本就没统计，也不需要去除其影响。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int mod = 998244353;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    n--;
    string s;
    cin >> s;
    ll ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i] == '?')
        {
            ans = ans * i % mod;
        }
    }
    if (s[0] == '?')
    {
        puts("0");
    }
    else
    {
        printf("%lld\n", ans);
    }
    while (m--)
    {
        int idx;
        cin >> idx;
        char c;
        cin >> c;
        idx--;
        // 如果非首位操作少了一个？
        if (idx && s[idx] == '?')
        {
            ans = ans * qmi(idx, mod - 2) % mod;
        }
        s[idx] = c;
        // 如果非首位操作多了一个?
        if (idx && c == '?')
        {
            ans = ans * idx % mod;
        }
        if (s[0] == '?')
        {
            puts("0");
        }
        else
        {
            printf("%lld\n", ans);
        }
    }
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}