20191015测试总结

T1：WOJ4218

就是一个大暴力。忘记了判断一个是否存在了导致得分很低，以后大暴力还是不能对自己的正确性太自信，要多检查啊。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t, top, s[10], row[10][10], col[10][10], squ[10][10], a[10][10][105];
char ss[20][20];
int find(int x, int y)
{
    if (x <= 3)
    {
        if (y <= 3)
            return 1;
        if (y <= 6)
            return 2;
        if (y <= 9)
            return 3;
    }
    if (x <= 6)
    {
        if (y <= 3)
            return 4;
        if (y <= 6)
            return 5;
        if (y <= 9)
            return 6;
    }
    if (x <= 9)
    {
        if (y <= 3)
            return 7;
        if (y <= 6)
            return 8;
        if (y <= 9)
            return 9;
    }
    return 0;
}
int main()
{
    for (int i = 1; i <= 19; ++i)
    {
        scanf("%s", ss[i]);
        if (!(i & 1))
            for (int j = 1; j < 19; j += 2)
                a[i >> 1][(j >> 1) + 1][0] = ss[i][j] ^ 48;
    }
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= 9; ++j)
            if (a[i][j][0])
            {
                int k = a[i][j][0];
                row[i][k] = 1;
                col[j][k] = 1;
                squ[find(i, j)][k] = 1;
            }
    scanf("%d", &t);
    for (int tt = 1; tt <= t; ++tt)
    {
        char type[10];
        scanf("%s", type);
        if (type[0] == 'I')
        {
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                    a[i][j][tt] = a[i][j][tt - 1];
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            if (a[x][y][tt])
            {
                puts("Error!");
                continue;
            }
            if (row[x][k])
            {
                puts("Error:row!");
                continue;
            }
            if (col[y][k])
            {
                puts("Error:column!");
                continue;
            }
            if (squ[find(x, y)][k])
            {
                puts("Error:square!");
                continue;
            }
            a[x][y][tt] = k;
            row[x][k] = 1;
            col[y][k] = 1;
            squ[find(x, y)][k] = 1;
            puts("OK!");
        }
        if (type[0] == 'D')
        {
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                    a[i][j][tt] = a[i][j][tt - 1];
            int x, y;
            scanf("%d%d", &x, &y);
            if (!a[x][y][tt])
            {
                puts("Error!");
                continue;
            }
            int k = a[x][y][tt];
            a[x][y][tt] = 0;
            row[x][k] = 0;
            col[y][k] = 0;
            squ[find(x, y)][k] = 0;
            puts("OK!");
        }
        if (type[0] == 'Q')
        {
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                    a[i][j][tt] = a[i][j][tt - 1];
            int x, y;
            scanf("%d%d", &x, &y);
            if (a[x][y][tt])
            {
                puts("Error!");
                continue;
            }
            top = 0;
            for (int i = 1; i <= 9; ++i)
                if (!row[x][i] && !col[y][i] && !squ[find(x, y)][i])
                    s[++top] = i;
            printf("%d\n", top);
            for (int i = 1; i <= top; ++i)
                printf("%d\n", s[i]);
        }
        if (type[0] == 'M')
        {
            memset(row, 0, sizeof(row));
            memset(col, 0, sizeof(col));
            memset(squ, 0, sizeof(squ));
            int x, y, ans[2] = {0};
            scanf("%d%d", &x, &y);
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                {
                    if (a[i][j][x])
                    {
                        int k = a[i][j][x];
                        if (!row[i][k] && !col[j][k] && !squ[find(i, j)][k])
                        {
                            a[i][j][tt] = k;
                            row[i][k] = 1;
                            col[j][k] = 1;
                            squ[find(i, j)][k] = 1;
                            ++ans[0];
                        }
                    }
                    if (!a[i][j][tt] && a[i][j][y])
                    {
                        int k = a[i][j][y];
                        if (!row[i][k] && !col[j][k] && !squ[find(i, j)][k])
                        {
                            a[i][j][tt] = k;
                            row[i][k] = 1;
                            col[j][k] = 1;
                            squ[find(i, j)][k] = 1;
                            ++ans[1];
                        }
                    }
                }
            if (x == y)
                ans[1] = ans[0];
            printf("%d %d\n", ans[0], ans[1]);
        }
        if (type[0] == 'P')
        {
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                    a[i][j][tt] = a[i][j][tt - 1];
            for (int i = 1; i <= 9; ++i)
            {
                for (int j = 1; j <= 19; ++j)
                    if (j & 1)
                        putchar('+');
                    else
                        putchar('-');
                putchar('\n');
                for (int j = 1; j <= 9; ++j)
                    printf("|%d", a[i][j][tt]);
                putchar('|');
                putchar('\n');
            }
            for (int i = 1; i <= 19; ++i)
                if (i & 1)
                    putchar('+');
                else
                    putchar('-');
            putchar('\n');
        }
    }
    return 0;
}

T2：WOJ4219

题目其实就是Johnson不等式的标准式子，不过我忘了qwq（虽然好像大家都忘了）

这种贪心当时直接从一些直接的值来考虑了， 但是套路应该是两两比较，看哪个更优。果然我做过的题还是太少。

PS：注意比较相等的时候的状况

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int t, n;
long long c[50005], sum[50005];
struct node
{
    int a;
    int b;
} a[50005];
bool cmp(node aa, node bb)
{
    if (min(aa.a, bb.b) == min(bb.a, aa.b))
        return aa.a < bb.a;
    return min(aa.a, bb.b) < min(bb.a, aa.b);
}
int main()
{
    scanf("%d", &t);
    for (int tt = 1; tt <= t; ++tt)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d%d", &a[i].a, &a[i].b);
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; ++i)
        {
            sum[i] = sum[i - 1] + a[i].a;
            c[i] = max(c[i - 1], sum[i]) + a[i].b;
        }
        printf("%lld\n", c[n]);
    }
    return 0;
}

T3：WOJ4220

非常恶心的期望题目，细节太多这里就不详细说了，自己看题解。

果然我的数学板块非常短板，需要恶补啊。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long n, k;
int num;
double pp, ans[2], an;
int main()
{
    scanf("%lld%lf", &n, &pp);
    k = n - 1;
    while (k)
    {
        k >>= 1;
        ++num;
    }
    for (int i = num; i >= 1; --i)
    {
        double p = (double)(n - ((n >> i) * (1LL << (i - 1)) + min(n - (n >> i) * (1LL << i), 1LL << (i - 1)))) / (double)n;
        ans[0] += 2.0 * (1.0 - p) * p * (1LL << (i - 1));
    }
    if (n != 1)
    {
        long long sum, cnt;
        double tot = 0.0;
        --n;
        k = 1;
        while (k <= n)
            k <<= 1;
        sum = k - 1;
        k >>= 1;
        tot += (double)sum * (n - k + 1);
        tot += (double)k * k;
        cnt = k;
        sum >>= 1;
        while (k != 1)
        {
            k >>= 1;
            sum >>= 1;
            if (n & k)
            {
                tot += (double)cnt * k;
                tot += (double)(cnt >> 1) * sum;
                cnt >>= 1;
            }
            else
                tot += (double)(cnt >> 1) * k;
        }
        ans[1] = tot / (double)(n + 1);
    }
    an = (1.0 - pp) * ans[0] + pp * ans[1];
    num = 0;
    while (an >= 10.0)
    {
        an /= 10.0;
        ++num;
    }
    while (an > 0.0 && an < 1.0)
    {
        an *= 10.0;
        --num;
    }
    printf("%.5f %d", an, num);
    return 0;
}