20191011测试总结

T1：CF402D

分解质因数再判断一下是好还是坏就可以算出初始得分。

然后贪心的从后往前枚举，发现除以此gcd可以让答案增大就除，然后前面所有的gcd也都要除这个数，然后就可以过了。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m, cnt, ans, a[5005], b[5005], sum[5005], num[5005], v[100005], z[100005];
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    return gcd(y, x % y);
}
bool check(int k)
{
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (b[mid] > k)
            r = mid - 1;
        else
            l = mid;
    }
    return b[l] == k;
}
void xxs()
{
    for (int i = 2; i <= sqrt(1000000000); ++i)
    {
        if (!v[i])
        {
            v[i] = i;
            z[++cnt] = i;
        }
        for (int j = 1; j <= cnt && z[j] * i <= sqrt(1000000000) && z[j] <= v[i]; ++j)
            v[z[j] * i] = z[j];
    }
    return;
}
int main()
{
    xxs();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        if (i == 1)
            sum[i] = a[i];
        else
            sum[i] = gcd(sum[i - 1], a[i]);
    }
    num[n] = 1;
    for (int i = 1; i <= m; ++i)
        scanf("%d", &b[i]);
    for (int i = n; i >= 1; --i)
    {
        int k = a[i], tot = 0;
        for (int j = 1; j <= cnt && z[j] <= sqrt(a[i]); ++j)
            if (k % z[j] == 0)
            {
                int num = 0;
                while (k % z[j] == 0)
                {
                    ++num;
                    k /= z[j];
                }
                if (check(z[j]))
                    ans -= num;
                else
                    ans += num;
            }
        if (k > 1)
        {
            if (check(k))
                --ans;
            else
                ++ans;
        }
        k = sum[i] / num[i];
        for (int j = 1; j <= cnt && z[j] <= sqrt(sum[i] / num[i]); ++j)
            if (k % z[j] == 0)
            {
                int num = 0;
                while (k % z[j] == 0)
                {
                    ++num;
                    k /= z[j];
                }
                if (check(z[j]))
                    tot += num;
                else
                    tot -= num;
            }
        if (k > 1)
        {
            if (check(k))
                ++tot;
            else
                --tot;
        }
        if (tot > 0)
        {
            num[i - 1] = sum[i];
            ans += tot * i;
        }
        else
            num[i - 1] = num[i];
    }
    printf("%d", ans);
    return 0;
}

T2：WOJ4079

对于每个模数通过倍增跳hash来确定2^i之后的状态就可以直接算答案了，考试的时候我居然没想出来。。。大概是没睡醒吧。。。

#include <iostream>
#include <cstdio>
using namespace std;
int a, c, k, m, n, ans, tot, num[20], s[100005], lg[1000005], nxt[1000005][20], ha[1000005][20];
void read()
{
    int len = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        s[++len] = c ^ 48;
        c = getchar();
    }
    return;
}
int calc(int z)
{
    return (((long long)a * z + c) / k) % m;
}
bool check(int z)
{
    int cnt = 0, reg = n;
    for (int i = lg[n]; i >= 0; --i)
        if (reg >= (1 << i))
        {
            reg -= (1 << i);
            cnt = cnt * num[i] + ha[z][i];
            z = nxt[z][i];
        }
    return cnt == ans;
}
int main()
{
    scanf("%d%d%d%d%d", &a, &c, &k, &m, &n);
    read();
    lg[1] = 0;
    for (int i = 2; i <= n; ++i)
        lg[i] = lg[i >> 1] + 1;
    num[0] = 959;
    for (int i = 1; i <= lg[n]; ++i)
        num[i] = num[i - 1] * num[i - 1];
    for (int i = 0; i < m; ++i)
    {
        nxt[i][0] = calc(i);
        ha[i][0] = (nxt[i][0] >= (m / 2));
    }
    for (int i = 1; i <= n; ++i)
        ans = ans * 959 + s[i];
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 0; j < m; ++j)
        {
            nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
            ha[j][i] = ha[j][i - 1] * num[i - 1] + ha[nxt[j][i - 1]][i - 1];
        }
    for (int i = 0; i < m; ++i)
        if (check(i))
            ++tot;
    printf("%d", tot);
    return 0;
}

T3：WOJ2821

首先将物品按价格排序，我们可以证明如果买完i物品钱不够买物品i-1，那么钱一定至少花了一半，然后再每次二分查找当前的钱够买哪个连续的区间，就可以算出答案。

总时间复杂度O(nlognlogw)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, num[100005];
long long sum[100005];
struct node
{
    int v;
    int x;
} a[100005];
bool cmp(node aa, node bb)
{
    return aa.v < bb.v;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i].v, &a[i].x);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
    {
        num[i] = num[i - 1] + a[i].x;
        sum[i] = sum[i - 1] + (long long)a[i].v * a[i].x;
    }
    for (int i = 1; i <= m; ++i)
    {
        int ans = 0;
        long long w;
        scanf("%lld", &w);
        int top = n;
        while (top > 0 && a[1].v <= w)
        {
            int l, r;
            l = 1;
            r = top;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (w >= a[mid].v)
                    l = mid;
                else
                    r = mid - 1;
            }
            int pos = l;
            if (w >= sum[pos])
            {
                ans += num[pos];
                w -= sum[pos];
                break;
            }
            l = 1;
            r = pos;
            while (l < r)
            {
                int mid = (l + r) >> 1;
                if (w < sum[pos] - sum[mid])
                    l = mid + 1;
                else
                    r = mid;
            }
            w -= sum[pos] - sum[l];
            ans += num[pos] - num[l];
            ans += w / a[l].v;
            w %= a[l].v;
            top = l - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

感觉自己还需要提升一下思维的活跃度啊