GDNOJ ~ DAY 0 ~ Pre-Training

[前言]

流放中山。

非常好的 pre-training，使我发现按下 Tab 键没有任何效果

就像我去年的锅到今年还没有补一样。。。

[Education CF Round 181 (Rated for Div.2)]

链接

[A]

随便乱排，早知道可以试试 shuffle 了

比较无脑的做法是倒序排，这样一定不会出现 FFT 或 NTT。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
char str[N];
void work()
{
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    sort(str + 1, str + n + 1);
    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i ++)putchar(str[i]);
    puts("");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T --)work();
    return 0;
}

[B]

注意到答案只能是 1 或 2。

判断答案是 1 十分简单，因为我们想让两个方向上最后所用步数是一样的，因此最优情况就是步数是最大公约数。

然后出除法判断一下是否小于等于 k，做完了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b, k;
void work()
{
    scanf("%lld%lld%lld", &a, &b, &k);
    LL g = __gcd(a, b);
    LL stepa = a / g, stepb = b / g;
    if (!a && !b)puts("0");
    else if (stepa <= k && stepb <= k)puts("1");
    else puts("2");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T --)work();
    return 0;
}

[C]

早知道不注意旁边的 combination 标签了。

一眼以为是数位DP，并且觉得可行性很高，然后发现忘了。

然后发现，实际上答案就是想对 2,3,5,7 这 4 个数容斥原理一下。

然后……就很好写了，用二进制状态枚举，二进制下存在对应的数乘起来，然后就与普通的容斥原理一致了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL l, r;
int w[4] = {2, 3, 5, 7};
LL get(LL n)
{
    LL res = 0;
    for (int S = 0; S < 16; S ++)
    {
        LL p = 1;
        int cnt = 0;
        for (int i = 0; i < 4; i ++)
        {
            if ((S >> i) & 1)
            {
                p *= w[i];
                cnt ++;
            }
        }
        if (cnt & 1)res -= n / p;
        else res += n / p;
    }
    return res;
}
void work()
{
    scanf("%lld%lld", &l, &r);
    printf("%lld\n", get(r) - get(l - 1));   
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T --)work();
    return 0;
}

[D]

临门一脚，没做出来。

思路大体上是对的。

把右端点按从小到大排序，定义 f_i 表示在 仅 覆盖 [1, i] 情况下，方案合法的概率。

初始状态容易写， 就是 $f0 = \prod{i = 1}^n \frac{q_i – p_i}{q_i}$

转移方程也是容易的，对于每一段来说，设左端点为 l, 右端点为 r，概率为 g ，有：

$fr = \sum{all} \frac{f_{l – 1} * g}{1 – g} $

下面的 1 – g 是因为定义的问题。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5; 
const LL mod = 998244353;
LL quick_power(LL a, LL b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int n, m;
struct node
{
    int l, r;
    LL g;
}line[N];
LL f[N];
int cmp(node a, node b)
{
    if (a.l == b.l) return a.r < b.r;
    else return a.l < b.l;
}
int main()
{
    scanf("%d%d", &m, &n);
    f[0] = 1;
    for (int i = 1; i <= m; i ++)
    {
        int a, b, p, q;
        scanf("%d%d%d%d", &a, &b, &p, &q);
        LL t = p * quick_power(q, mod - 2) % mod;
        line[i] = {a, b, t};
        f[0] = f[0] * (((1 - t) % mod + mod) % mod) % mod; 
    }
    sort(line + 1, line + m + 1, cmp);
    for (int i = 1; i <= m; i ++)
    {
        int l = line[i].l, r = line[i].r;
        LL g = line[i].g;
        LL fg = ((1 - g) % mod + mod) % mod;
        LL t = f[l - 1] * g % mod;
        t = t * quick_power(fg, mod - 2) % mod;
        f[r] = (f[r] + t) % mod;
    }
    printf("%lld\n", f[n] % mod);
    return 0;
}