20191111测试总结

三道题两道计数，出题人过于毒瘤。。。

T1：WOJ4815

送分的弱智题

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, s, l[200005];
long long ans;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    n = read();
    s = read();
    for (int i = 1; i <= n; ++i)
        l[i] = read();
    sort(l + 1, l + n + 1);
    int head = 1, tail = n;
    while (head < tail)
    {
        while (head < tail && l[head] + l[tail] > s)
            --tail;
        ans += tail - head;
        ++head;
    }
    printf("%lld", ans);
    return 0;
}

T2：WOJ4812

首先推出n^2的DP式子，然后打个表就可以发现是个斜着并且要将上下两个值相等的数数捆绑成一个块的杨辉三角。

当然，这式子也有组合意义。我们将每个a_i都加上i，每个数也就变成了偶数，然后题目就可以转换成从(n+m)/2个数中选m个数了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define mod 998244353
using namespace std;
int t, n, m, x, y, f[1000005], g[1000005];
int read()
{
    int xx = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        xx = (xx << 3) + (xx << 1) + (ch ^ 48);
        ch = getchar();
    }
    return xx * f;
}
void exgcd(int a, int b)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b);
    int tmp = x;
    x = y;
    y = tmp - a / b * y;
    return;
}
int c(int a, int b)
{
    return (long long)f[a] * g[b] % mod * g[a - b] % mod;
}
int main()
{
    t = read();
    f[0] = 1;
    g[0] = 1;
    for (int i = 1; i <= 1000000; ++i)
    {
        f[i] = (long long)f[i - 1] * i % mod;
        exgcd(f[i], mod);
        g[i] = (x % mod + mod) % mod;
    }
    for (int i = 1; i <= t; ++i)
    {
        n = read();
        m = read();
        printf("%d\n", c((n + m) / 2, m));
    }
    return 0;
}

T3：WOJ4813

毒瘤计数题，对于每个与[x,y]有所重合的区间[x,y]分三种情况讨论。

详细的就不写了，计数题反正慢慢推就对了。

#include <iostream>
#include <cstdio>
#define lch id << 1
#define rch id << 1 | 1
#define int long long
using namespace std;
int n, q, opt, ans, sum;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
struct node
{
    int l;
    int r;
    int C;
    int L;
    int R;
    int LR;
    int siz;
} tr[2000005];
void build(int id, int l, int r)
{
    tr[id].l = l;
    tr[id].r = r;
    tr[id].siz = 1;
    tr[id].L = 2 * l + 1;
    tr[id].R = 2 * r - 1;
    tr[id].C -= l * (l + 1) + r * (r - 1);
    if (l == r)
        return;
    tr[id].C += 4 * (l + 1) * (r - 1);
    tr[id].LR = 4;
    tr[id].L -= 4 * (r - 1);
    tr[id].R -= 4 * (l + 1);
    int mid = (l + r) >> 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    tr[id].siz += tr[lch].siz + tr[rch].siz;
    tr[id].C += tr[lch].C + tr[rch].C;
    tr[id].LR += tr[lch].LR + tr[rch].LR;
    tr[id].L += tr[lch].L + tr[rch].L;
    tr[id].R += tr[lch].R + tr[rch].R;
    return;
}
int solve(int id, int l, int r)
{
    if (l <= tr[id].l && tr[id].r <= r)
        return tr[id].C + (sum - l * l - r * r) * tr[id].siz + tr[id].L * l + tr[id].R * r + tr[id].LR * l * r;
    int tmp = sum;
    if (l <= tr[id].l)
        tmp -= (tr[id].l - l) * (tr[id].l - l + 1);
    if (tr[id].r <= r)
        tmp -= (r - tr[id].r) * (r - tr[id].r + 1);
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (l <= mid)
        tmp += solve(lch, l, r);
    if (r >= mid + 1)
        tmp += solve(rch, l, r);
    return tmp;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &q, &opt);
    build(1, 1, n);
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        scanf("%lld%lld", &l, &r);
        int a = (l ^ (ans * opt)) % n + 1;
        int b = (r ^ (ans * opt)) % n + 1;
        l = min(a, b);
        r = max(a, b);
        sum = (r - l + 1) * (r - l + 2);
        ans = solve(1, l, r) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}