ChangKe's Blog

UOJ Round #13:暴力练习大赛

标题已经说明了一切。
今天下午bhi神过来问我,“机房有人吗?”,我说不知道,然后发现居然有人,就跑进去了。
然后直到放学才出来。干了些什么呢?首先艹了一波ZLXSC的题解,居然被出题人赞了,开心owo
然后发现ZLXSC的时间和UR恰好无缝对接,然后连饭都没吃就开始打UR。
先看题。貌似都不可做……暴力大法好。
A暴力二分+贪心,B暴力DP,C暴力分解质因数。
然后60+20+20=100,Rank50。不过Rating还是涨了,毕竟前面几场都挂了,所以底数很低。
好短啊。。。看来人太傻逼还是写不出来什么有价值的东西吧
附上代码凑字数

A

#include <cstdio>
#define INF 100010
int a[INF];
bool b[INF];
int lsa[INF];
bool lsb[INF];
int n, q;
bool ok(int x)
{
    int lsn = n;
    for (int i = 1; i <= lsn; i++)
    {
        lsa[i] = a[i];
        lsb[i] = b[i];
    }
    while (true)
    {
        int mm = INF, d = 0;
        for (int i = 1; i <= lsn; i++)
            if (!lsb[i] && mm > lsa[i])
                mm = lsa[i], d = i;
        if (!d)
            return true;
        int l = d, r = d;
        while (l >= 2 && lsa[l - 1] > lsa[d])
            l--;
        while (r <= lsn - 1 && lsa[r + 1] > lsa[d])
            r++;
        if (r - l + 1 < x)
            return false;
        else
        {
            lsn--;
            for (int i = d; i <= lsn; i++)
            {
                lsa[i] = lsa[i + 1];
                lsb[i] = lsb[i + 1];
            }
        }
    }
}
int check()
{
    int l = 1, r = n;
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        if (ok(mid))
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    return (ok(r) ? r : l);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char x = getchar();
            while (x < '0' || x > '1')
                x = getchar();
            b[j] = (x == '1');
        }
        printf("%d\n", check());
    }
    return 0;
}

B

#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 500010
#define INF 1000000001
using namespace std;
int a[MAXN], b[MAXN];
int n;
long long ans[MAXN];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", a + i, b + i);
    a[0] = -INF;
    for (int i = 1; i <= n; i++)
    {
        int j = i;
        ans[i] = 1;
        while (abs(a[j] - a[j - 1]) <= b[j] - b[j - 1])
            j--;
        for (int k = j; k < i; k++)
        {
            if (ans[i] < (long long)(i - k + 1) * (i - k + 1))
                ans[i] = (long long)(i - k + 1) * (i - k + 1);
            for (int l = 1; l < k; l++)
                if (abs(a[k] - a[l]) <= b[k] - b[l])
                    if (ans[l] + (long long)(i - k + 1) * (i - k + 1) > ans[i])
                        ans[i] = ans[l] + (long long)(i - k + 1) * (i - k + 1);
        }
        for (int k = 1; k < j; k++)
        {
            if (ans[k] + 1 > ans[i] && abs(a[i] - a[k]) <= b[i] - b[k])
                ans[i] = ans[k] + 1;
        }
    }
    long long o = 0;
    for (int i = 1; i <= n; i++)
        if (ans[i] > o)
            o = ans[i];
    printf("%lld\n", o);
    return 0;
}

C

#include <iostream>
#include <cstdio>
using namespace std;
int prime[10010010], cnt;
bool flag[10010010];
void prepare()
{
    for (int i = 2; i <= 10010000; i++)
    {
        if (!flag[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt; j++)
        {
            if (i * prime[j] > 10010000)
                break;
            flag[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main()
{
    prepare();
    int l, r;
    long long ans = 0;
    scanf("%d%d", &l, &r);
    for (int i = l; i <= r; i++)
    {
        if (!flag[i])
            continue;
        int d1 = 0, d2 = 0, ls = i;
        for (int j = 0; j < cnt; j++)
        {
            if (ls % prime[j] == 0)
            {
                d2 = d1;
                d1 = prime[j];
                while (ls % prime[j] == 0)
                    ls /= prime[j];
            }
            if (!flag[ls])
            {
                d2 = d1;
                break;
            }
        }
        ans = ans + d2;
    }
    printf("%lld", ans);
    return 0;
}