Educational Codeforces Round 95lyh's blog

Educational Codeforces Round 95。因为$A$题出了锅导致unrated了。

A. Buying Torches

答案就是：

$\lceil\frac{ky+k-1}{x-1}\rceil+k$

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
 
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        ll x, y, k;
        scanf("%lld%lld%lld", &x, &y, &k);
        ll s = k * y + k - 1;
        if (s % (x - 1) == 0)
            s = s / (x - 1);
        else
            s = s / (x - 1) + 1;
        printf("%lld\n", s + k);
    }
    return 0;
}

B. Negative Prefixes

把能排序的降序排列即可，这样可以保证它的所有前缀和都是尽可能大的。
假设此时最大的，前缀和小于$0$的位置是$i$，由于这已经是前缀和最大的情况了，其它情况只会让这个位置前移，导致$i$变小，答案不会更优。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int op[N], n, l[N];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", op + i);
        for (int i = 1; i <= n; i++) scanf("%d", l + i);
        vector<int> vec;
        for (int i = 1; i <= n; i++) {
            if (!l[i]) vec.push_back(op[i]);
        }
        sort(vec.begin(), vec.end(), greater<int>());
        int at = 0;
        for (int i = 1; i <= n; i++) {
            if (!l[i]) op[i] = vec[at++];
        }
        for (int i = 1; i <= n; i++) printf("%d ", op[i]);
        printf("\n");
    }
    return 0;
}

C. Mortal Kombat Tower

一个傻$DP$，~~这都不会做就可以退役了~~。

#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;
typedef long long ll;
int n, op[N], dp[N][2];
int DP(int x, int y)  //y=0 friend;y=1 me
{
    if (x > n) return 0;
    if (~dp[x][y]) return dp[x][y];
    if (y == 1) return dp[x][y] = min(DP(x + 1, 0), DP(x + 2, 0));
    dp[x][y] = DP(x + 1, 1) + op[x] - op[x - 1];
    if (x + 1 <= n) dp[x][y] = min(dp[x][y], DP(x + 2, 1) + op[x + 1] - op[x - 1]);
    return dp[x][y];
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", op + i), dp[i][0] = dp[i][1] = -1;
        for (int i = 1; i <= n; i++) op[i] += op[i - 1];
        printf("%d\n", DP(1, 0));
    }
    return 0;
}

D. Trash Problem

对所有数升序排序后，设最大值为$n$，最小值为$m$，显然答案就是$n-m-\max(a_{i+1}-a_i)$。
随便拿一个数据结构维护一下最大值，最小值和最大差即可。当然你也可以手写一个平衡树，~~比如我~~。

#include <bits/stdc++.h>
const int N = 300000 + 5, inf = 0x3f3f3f3f;
using namespace std;
 
struct Node
{
    int ch[2], v, key, max, min, ans;
} nd[N];
 
int root, cnt;
 
inline void update(int x)
{
    nd[x].max = max(max(nd[nd[x].ch[0]].max, nd[nd[x].ch[1]].max), nd[x].v);
    nd[x].min = min(min(nd[nd[x].ch[0]].min, nd[nd[x].ch[1]].min), nd[x].v);
    nd[x].ans = min(nd[nd[x].ch[0]].ans, nd[nd[x].ch[1]].ans);
    if (nd[x].ch[1]) nd[x].ans = min(nd[x].ans, nd[x].v - nd[nd[x].ch[1]].min);
    if (nd[x].ch[0]) nd[x].ans = min(nd[x].ans, nd[nd[x].ch[0]].max - nd[x].v);
}
 
inline int newNode(int x)
{
    nd[++cnt].v = x, nd[cnt].ch[0] = nd[cnt].ch[1] = 0;
    nd[cnt].max = nd[cnt].min = x, nd[cnt].ans = inf, nd[cnt].key = rand();
    return cnt;
}
void split(int rt, int& a, int& b, int v)
{
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[rt].v <= v)
        a = rt, split(nd[rt].ch[1], nd[a].ch[1], b, v);
    else
        b = rt, split(nd[rt].ch[0], a, nd[b].ch[0], v);
    update(rt);
}
void merge(int& rt, int a, int b)
{
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (nd[a].key > nd[b].key) {
        rt = a, merge(nd[a].ch[1], nd[a].ch[1], b);
    } else {
        rt = b, merge(nd[b].ch[0], a, nd[b].ch[0]);
    }
    update(rt);
}
void insert(int x)
{
    int a, b;
    split(root, a, b, x);
    merge(a, a, newNode(x));
    merge(root, a, b);
}
void del(int x)
{
    int a, b, c;
    split(root, a, c, x);
    split(a, a, b, x - 1);
    merge(root, a, c);
}
int n, q;
inline int getAns()
{
    if (n <= 2) return 0;
    // cout << nd[root].max << " " << nd[root].min << endl;
    return nd[root].max - nd[root].min + nd[root].ans;
}
 
int main()
{
    srand(time(0)), nd[0].min = inf;
    scanf("%d%d", &n, &q);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(x);
    printf("%d\n", getAns());
    while (q--) {
        int t, x;
        scanf("%d%d", &t, &x);
        if (t == 0)
            del(x), --n;
        else
            insert(x), ++n;
        printf("%d\n", getAns());
    }
    return 0;
}

E. Expected Damage

        高中数学题。
        将所有数分为两类，一类小于$b$，一类不小于$b$，显然一个数产生贡献等价于它前面有不少于$a$个第二类的数。
        假设两类数分别有$n$和$m$个，先考虑对于一个第一类数，它能产生贡献的情况有多少种。
        先把第二类数做一个全排列，有$m!$种情况，然后把这个第一类数插进去，有$m-a+1$种情况，然后组合一下它们的位置，有$C_{n+m}^{m+1}$种情况，剩下的随便排，有$(n-1)!$种情况。总数就是：

$m!(m-a+1)C_{n+m}^{m+1}(n-1)!$

再除以总数$(n+m)!$，即：

$\frac {m-a+1}{m+1}$

这就是它产生贡献的概率。对于第二类数产生贡献的概率，由于它本身会使$m$减少一，所以只需要把$m=m-1$代进去即可：

$\frac{m-a}{m}$

注意判不成立的情况，然后二分配合前缀和，复杂度$O(mlogn)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5, mod = 998244353;
typedef long long ll;
int n, m, d[N], sumd[N];
inline int qpow(int x, int y)
{
    int ans = 1, sta = x;
    while (y) {
        if (y & 1) ans = 1ll * ans * sta % mod;
        sta = 1ll * sta * sta % mod, y >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", d + i);
    sort(d + 1, d + n + 1);
    for (int i = 1; i <= n; i++) sumd[i] = (sumd[i - 1] + d[i]) % mod;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int l = 0, r = n, mid;
        while (l < r) {
            if (r == l + 1) break;
            mid = (l + r) >> 1;
            if (d[mid] >= b)
                r = mid;
            else
                l = mid;
        }
        int x;
        if (d[r] >= b)
            x = n - r + 1;
        else
            x = 0, r = n + 1;
        // cout << x << " " << r << endl;
        int ans = 0;
        if (x >= a) ans = 1ll * sumd[r - 1] * (x - a + 1) % mod * qpow(x + 1, mod - 2) % mod;
        if (x >= a + 1) {
            int ss = sumd[n] - sumd[r - 1];
            ans = (ans + 1ll * ss * (x - a) % mod * qpow(x, mod - 2) % mod) % mod;
        }
        printf("%d\n", (ans + mod) % mod);
    }
    return 0;
}

F. Equal Product

将等式化为以下形式：

$\frac{x_2}{x_1}=\frac{y_1}{y_2}=\frac a b$

        我们枚举$x_1$，并且枚举它的每一个因子$b$，这一步的时间复杂度是$O(nlogn)$。此时我们可以得到对应的$y_1$取值范围。由于$l\leq x_1y_1\leq r$，所以$y_1$有一个取值范围，我们把它和$[1,m]$取个交。
        注意到$a|y_1$，并且$a>b$，这意味着$y_1$应含有至少一个大于$b$的因子$a$。另一方面，可以计算出$x_2=\frac{ax_1}{b},y_2=\frac{y_1b}{a}$，如果$y_1$存在，那么$y_2$必然也是存在且合法的。但是由于$x_2\leq n$，我们需要使$x_2$尽可能小，即$a$尽可能小。于是现在问题转化为在给定区间$[L,R]$中，找一个数$x$，它存在一个因子$a>b$，并且$a$最小。
        对于这种二维问题，我们当然可以使用主席树去做，但是主席树的空间复杂度（对于这个题）高达$O(nlog^2n)$，直接$MLE$。
        注意到$y_1$的区间左右端点随$x_1$的增大时不增的，于是可以不用主席树，而是使用一维的权值线段树来搞，这样空间复杂度降到$O(nlogn)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
int n, m, cnt, root[N], nd[N << 2];
ll l, r;
vector<int> vec[N];
void modify(int x, int v, int l = 1, int r = m, int k = 1)
{
    if (l == r) {
        nd[k] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        modify(x, v, l, mid, k << 1);
    } else {
        modify(x, v, mid + 1, r, k << 1 | 1);
    }
    nd[k] = nd[k << 1] + nd[k << 1 | 1];
}
int query(int x, int l = 1, int r = m, int k = 1)
{
    if (nd[k] == 0) return -1;
    if (l == r) return l > x ? l : -1;
    int mid = (l + r) >> 1;
    if (x >= mid) return query(x, mid + 1, r, k << 1 | 1);
    int tmp = query(x, l, mid, k << 1);
    if (tmp != -1) return tmp;
    return query(x, mid + 1, r, k << 1 | 1);
}
inline void update(int L, int R)
{
    static int lat = m + 1, rat = m + 1;
    while (lat - 1 >= L) {
        for (int i = 0; i < vec[lat - 1].size(); i++) modify(vec[lat - 1][i], 1);
        --lat;
    }
    while (rat - 1 > R) {
        for (int i = 0; i < vec[rat - 1].size(); i++) modify(vec[rat - 1][i], -1);
        --rat;
    }
}
int main()
{
    scanf("%d%d%lld%lld", &n, &m, &l, &r);
    for (int i = 1; i <= n || i <= m; i++) {
        for (int j = i; j <= n || j <= m; j += i) vec[j].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        int flag = 1;
        for (int j = 0; j < vec[i].size(); j++) {
            ll L = l % i == 0 ? l / i : l / i + 1, R = min(r / i, 1ll * m), at;
            if (L > m || L > R || R <= vec[i][j]) continue;
            update(L, R), at = query(vec[i][j]);
            if (at == -1) continue;
            ll x2 = 1ll * i * at / vec[i][j];
            int y1 = (L % at == 0 ? L / at : L / at + 1) * at;
            int y2 = 1ll * vec[i][j] * y1 / at;
            if (x2 <= n) {
                printf("%d %d %d %d\n", i, y1, (int)x2, y2), flag = 0;
                break;
            }
        }
        if (flag) printf("-1\n");
    }
    return 0;
}

G. Three Occurrences

        从小到大枚举右端点，看有多少个左端点是合法的。
        维护一个数组$num[x]$，记录$x$到现在出现的次数模$3$的值，如果一个区间$[l,r]$合法，则$l-1$和$r$处的$num$数组应该相同。
        我们使用数组哈希的方法配合$map$就可以快速查询有多少个$l$满足这个条件，进而计入答案。
        但是这只是一个必要条件，不是充分条件。注意这种方法找出的可能使某些数出现$6$次或更多，需要删去一些答案。这一步只需要标记出现$3$次以上的数的左侧位置，将它们的哈希值删去即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef unsigned long long ull;
ull val[N], hs[N];
int n, num[N];
vector<int> vec[N];
map<ull, int> mmp;
int main()
{
    srand(time(0));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) val[i] = (1ll * rand() << 32) + (1ll * rand() << 16) + rand();
    ull ans = 0;
    int lt = -1, at = -1;
    ++mmp[0];
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        hs[i] = hs[i - 1] - num[x] * val[x];
        vec[x].push_back(i);
        if (vec[x].size() > 3) lt = max(lt, vec[x][0]), vec[x].erase(vec[x].begin());
        while (at + 1 < lt) --mmp[hs[at + 1]], ++at;
        num[x] = (num[x] + 1) % 3;
        hs[i] += num[x] * val[x];
        ans += mmp[hs[i]];
        ++mmp[hs[i]];
    }
    printf("%lld", ans);
    return 0;
}