20191102测试总结

咕咕咕

T1被卡常数了，求逆元的时候把ksm换成exgcd就过了，毒瘤出题人

T1：WOJ4790

题目很如学。。。

暴力n^3显然过不去，因此我们想到n^2枚举前两个数，然后log的复杂度内求逆元就可以求出第三个数，接着二分查找即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, p, xx, yy, cnt, a[2505];
long long ans;
struct node
{
    int a;
    int b;
    int num;
} s[2505];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read()
{
    int x = 0;
    char c = gc();
    while (!isdigit(c))
        c = gc();
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = gc();
    }
    return x;
}
inline bool cmp(node aa, node bb)
{
    if (aa.a != bb.a)
        return aa.a < bb.a;
    return aa.b < bb.b;
}
inline void exgcd(int a, int b)
{
    if (b == 0)
    {
        xx = 1;
        yy = 0;
        return;
    }
    exgcd(b, a % b);
    int tmp = xx;
    xx = yy;
    yy = tmp - a / b * yy;
    return;
}
int main()
{
    n = read();
    p = read();
    for (register int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1);
    for (register int i = 1; i <= n; ++i)
        if (a[i] != a[i - 1])
        {
            ++cnt;
            s[cnt].a = a[i] % p;
            s[cnt].b = a[i];
            s[cnt].num = 1;
        }
        else
            ++s[cnt].num;
    sort(s + 1, s + cnt + 1, cmp);
    for (register int i = 1; i <= n; ++i)
    {
        --s[i].num;
        for (register int j = i; j <= n; ++j)
        {
            if (s[j].num <= 0)
                continue;
            --s[j].num;
            exgcd((long long)s[i].a * s[j].a % p, p);
            int k = (xx % p + p) % p;
            int l = j, r = cnt;
            while (l < r)
            {
                int mid = (l + r) >> 1;
                if (k > s[mid].a)
                    l = mid + 1;
                else
                    r = mid;
            }
            int x = l;
            l = j;
            r = cnt;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (k < s[mid].a)
                    r = mid - 1;
                else
                    l = mid;
            }
            int y = l;
            if (s[x].a != k)
            {
                ++s[j].num;
                continue;
            }
            if (s[x].num <= 0)
                ++x;
            ans += y - x + 1;
            ++s[j].num;
        }
        ++s[i].num;
    }
    printf("%lld", ans);
    return 0;
}

T2：WOJ4791

我们可以贪心的发现取最后几个背包一定是最优解，然后按照最长不下降子序列的思路乱搞一下即可（标答为权值树状数组，不过我的乱搞居然过了）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int ttt, n, m, ans, len, t[100005], f[100005];
struct node
{
    int w;
    int v;
}a[100005];
bool cmp(node aa, node bb)
{
    if(aa.w != bb.w)
        return aa.w < bb.w;
    return aa.v < bb.v;
}
int main()
{
    scanf("%d", &ttt);
    for(int tt = 1; tt <= ttt; ++tt)
    {
        ans = 0;
        len = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d", &a[i].w, &a[i].v);
        sort(a + 1, a + n + 1, cmp);
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i)
            scanf("%d", &t[i]);
        sort(t + 1, t + m + 1);
        f[0] = 1000000005;
        for(int i = n; i >= 1; --i)
        {
            if(a[i].v <= f[len])
            {
                int l = 1, r = m;
                while(l < r)
                {
                    int mid = (l + r) >> 1;
                    if(t[mid] < a[i].w)
                        l = mid + 1;
                    else
                        r = mid;
                }
                if(t[l] < a[i].w)
                    continue;
                ans = max(ans, min(len + 1, m - l + 1));
                if(len + 1 <= m - l + 1)
                    f[++len] = a[i].v;
                continue;
            }
            int l = 1, r = len;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(f[mid] < a[i].v)
                    r = mid;
                else
                    l = mid + 1;
            }
            int k = l;
            l = 1;
            r = m;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(t[mid] < a[i].w)
                    l = mid + 1;
                else
                    r = mid;
            }
            if(t[l] < a[i].w)
                continue;
            ans = max(ans, min(k, m - l + 1));
            if(k <= m - l + 1)
                f[k] = a[i].v;
        }
        printf("%d\n", ans);
    }
    return 0;
}

T3：WOJ4792

计算出i个节点深度不超过d的有根树数量，然后差分一下即可。

#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n, k, l, r, a[505], vis[505], f[505][505], c[505][505];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; ++i)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
    for (int i = 1; i <= k; ++i)
    {
        scanf("%d", &a[i]);
        vis[a[i]] = 1;
    }
    scanf("%d%d", &l, &r);
    if (vis[1])
        f[1][1] = 0;
    else
        f[1][1] = 1;
    for (int d = 2; d <= n; ++d)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (i == 1)
            {
                f[i][d] = 1;
                continue;
            }
            for (int j = 1; j < i; ++j)
                f[i][d] = (f[i][d] + (long long)f[i - j][d] * f[j][d - 1] % mod * c[i - 2][j - 1] % mod) % mod;
        }
        for (int i = 1; i <= n; ++i)
            if (vis[i])
                f[i][d] = 0;
    }
    for (int i = l; i <= r; ++i)
        printf("%d ", ((f[n][i] - f[n][i - 1]) % mod + mod) % mod);
    return 0;
}