A.Level Statistics

题意：

有一个游戏，给出 $n$ 组 $p_i$ 和 $c_i$ ，分别代表玩家的尝试次数和通过次数，每次尝试则尝试次数 $+1$ ，如果通过则通过次数也 $+1$ 。判断给出的这 $n$ 组数据是否合理

题解：

$p_i$ 和 $c_i$ 都是单调不降的，同时 $p_i$ 的增量肯定要大于等于 $c_i$ 的增量

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    int n, p, c, lastp = 0, lastc = 0;
    scanf("%d", &n);
    bool flag = true;
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &p, &c);
        if (p < c || p < lastp || c < lastc || p - lastp < c - lastc)
            flag = false;
        lastp = p, lastc = c;
    }
    puts(flag ? "YES" : "NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Middle Class

题意：

已知 $n$ 个人财富值 $a_i$ ，可以无限次地选取一些人将他们的财富值平分，问最后最多有多少人财富值不少于 $x$ 。

题解：

将 $a_i$ 降序排序，从头开始遍历，记录每次多出来的财富值，如果 $a_i$ 加上多出来的财富值仍小于 $x$ 则停止

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn];
void solve()
{
    ll n, x;
    scanf("%lld%lld", &n, &x);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n, greater<ll>());
    ll sum = 0, ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] >= x)
        {
            sum += a[i] - x;
            ans++;
        }
        else if (sum >= x - a[i])
        {
            sum -= x - a[i];
            ans++;
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Circle of Monsters

题意：

有一圈怪兽，每个怪兽有 $a_i$ 点生命值，每射击 $1$ 次怪兽会掉 $1$ 点生命值，当怪兽死亡时会对下一个怪兽造成 $b_i$ 点伤害，要想消灭所有怪兽最少需要射击多少次。

题解：

可知只有对其中一只怪兽需要射击 $a_i$ 次，其余的都只需要射击 $max(0,a[i]-b[(i-1+n) \% n])$ 次即可。
同时也可以发现 $\sum_{i=0}^{n-1}{ max(0,a[i]-b[(i-1+n)\%n]) }$ 是无论从哪只开始都必要的射击，那么先算出贡献，再枚举从哪只开始取最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn], b[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    ll sum = 0;
    for (int i = 0; i < n; i++)
        scanf("%lld%lld", &a[i], &b[i]);
    for (int i = 0; i < n; i++)
        sum += max(0ll, a[i] - b[(i - 1 + n) % n]);
    ll ans = 1e18;
    for (int i = 0; i < n; i++)
    {
        if (a[i] >= b[i])
            ans = min(ans, sum + b[i]);
        else
            ans = min(ans, sum + a[i]);
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Minimum Euler Cycle

题意：

给定 $n,l,r$ 表示一个有 $n$ 个节点的完全有向图，要求一种方案使得遍历的欧拉回路(所有的边都要遍历，且只能经过一次)中依次经过的节点组成的字典序最小。输出这种方案下经过的 $v_l \sim v_r$ 的节点编号

题解：

观察题目中给的 $n=3$ 的样例可以看出 $\left[ 1,2,1,3 \right] \left[ 2,3 \right] \left[ 1 \right]$
就是说对 $1 \sim n$ 的每一个节点，每次从当前点出发依次走到下一个节点再回来是字典序最小的，但是当前点走到 $n$ 时不能回来，要直接走到下一个节点去，不然就会无路可走。最终才回到 $1$ 节点
再观察可以发现对于 $1 \sim n$ 节点，每组有 $(n-i)*2$ 个节点，同时奇数位的节点就是它本身，偶数位为当前组内位置除 $2+i$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    ll n, l, r;
    scanf("%lld%lld%lld", &n, &l, &r);
    ll limit = 1ll * n * (n - 1) + 1;
    ll sum = 0, id = 1;
    for (ll i = l; i <= r && i < limit; i++)
    {
        while (sum + (n - id) * 2 < i)
            sum += (n - id) * 2, id++;
        ll d = i - sum;
        printf("%lld ", (d & 1) ? id : d / 2 + id);
    }
    if (r == limit)
        printf("1 ");
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Divisor Paths

题意：

给定一个正整数 $D$ , 以此建图

每个节点都是 $D$ 的因子
$x,y(x>y)$ 节点之间有无向边存在的条件是 $y$ 是 $x$ 因子且 $\frac{x}{y}$ 是质数
$x,y$ 之间若有边，则边权是 $x$ 的因子中不是 $y$ 的因子的个数

给出 $q$ 组询问,求 $u,v$ 之间的最短路径条数

题解：

首先可以想到，一个节点 $u$ 向另一个节点 $v$ 转移的过程中总是通过抛出一些因子来进行的，其中 $v|u$
那么 $u$ 到 $v$ 的最短路径就是 $d(u)-d(x_1)+d(x_1)-d(x-2)...+d(x_y)-d(v)=d(u)-d(v)$ ，其中 $d(x)$ 为 $x$ 的因子个数，因此当一个节点能被令一个节点整除时，两节点间的最短路径就是两节点的因子个数之差。考虑到 $u$ 和 $v$ 两者不为倍数关系时，因为节点的转移需要通过抛出一些因子来实现，所以需要找个中间节点 $x$ 使得 $u->x$ 并且 $v->x$ ，那么显而易见 $x$ 肯定为 $u$ 和 $v$ 的公因子，要使的路径最短就是使得 $d(u)-d(x)+d(v)-d(x)$ 最小，那么就是使得 $d(x)$ 最大，所以 $x=gcd(u,v)$ ，那么最终所求就是 $g(u,gcd(u,v))*g(v,gcd(u,v))$ ,其中 $g(u,v)$ 为 $u$ 和 $v$ 两点间最短路径的条数
因为一个节点 $u$ 向另一个节点 $v$ 转移的过程中总是通过抛出一些因子来进行的，那么条数就是这些中间因子的抛出顺序，那么对于 $g(u,v)$ ，其中 $v|u$ ,令 $x=\frac{u}{v}$ 则 $g(u,v)=\frac{t!}{p_1!*p_2!...p_n!}$ ，其中 $t$ 为 $x$ 中各质因子的幂之和, $p_i$ 为 $x$ 中某个质因子的幂，就是排列组合里重复剔除问题除于它的阶乘

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
map<ll, ll> m;

ll calc(ll x)
{
    if (m[x])
        return m[x];
    ll res = 0, y = x;
    for (ll i = 2; i * i <= y; i++)
        if (y % i == 0)
        {
            while (y % i == 0)
                y /= i;
            res = (res + calc(x / i)) % mod;
        }
    if (y > 1)
        res = (res + calc(x / y)) % mod;
    return m[x] = res;
}

int main()
{
    ll d, q;
    scanf("%lld%lld", &d, &q);
    m[1] = 1;
    while (q--)
    {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        ll w = __gcd(u, v);
        printf("%lld\n", calc(u / w) * calc(v / w) % mod);
    }
    return 0;
}

Educational Codeforces Round 85 (Rated for Div. 2)

A.Level Statistics

题意：

题解：

B.Middle Class

题意：

题解：

C.Circle of Monsters

题意：

题解：

D.Minimum Euler Cycle

题意：

题解：

E.Divisor Paths

题意：

题解：