ACM学习历程—Hihocoder [Offer收割]编程练习赛1

比赛链接：http://hihocoder.com/contest/hihointerview3/problem/1

大概有一个月没怎么打算法了。这一场的前一场BC，也打的不是很好。本来Div1的A和B应该都能AC的，但是A题由于脑子二笔了一下，最后终测T掉了。不过很奇怪，最后分数也没有跌，反而涨了，终于要接近紫名了，下一发不跌的话，应该有紫了。然后说一下这场Hihocoder吧，据说有offer面试名额，然后选了网易游戏和微软，虽然很是想去微软的，但是又二笔了几发，这就这样了。。

A题：九宫（暴力）

http://hihocoder.com/problemset/problem/1268

题目大意就是问原3x3的矩阵能否通过镜像或者旋转得到目标矩阵。

我是写了一个原矩阵和其镜像矩阵，然后分别对这两个矩阵进行旋转来匹配。

当然也可以先搞出所有矩阵，然后进行匹配。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long

using namespace std;

int to1[3][3] = {
    4, 9, 2,
    3, 5, 7,
    8, 1, 6
    };
int to2[3][3] = {
    8, 1, 6,
    3, 5, 7,
    4, 9, 2
    };
int a[3][3], ans[3][3];

bool judge(int x[3][3])
{
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (a[i][j] != 0 && a[i][j] != x[i][j])
                return false;
    return true;
}

void turn(int x[3][3], int y[3][3])
{
    y[0][0] = x[0][2];
    y[1][0] = x[0][1];
    y[2][0] = x[0][0];
    y[2][1] = x[1][0];
    y[2][2] = x[2][0];
    y[1][2] = x[2][1];
    y[0][2] = x[2][2];
    y[0][1] = x[1][2];
    y[1][1] = x[1][1];
}

void input()
{
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            scanf("%d", &a[i][j]);
}

void work()
{
    int flag = 0, to[3][3];
    for (int i = 0; i < 4; ++i)
    {
        turn(to1, to);
        if (judge(to))
        {
            flag++;
            for (int x = 0; x < 3; ++x)
                for (int y = 0; y < 3; ++y)
                    ans[x][y] = to[x][y];
        }
        for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
                to1[x][y] = to[x][y];
    }
    for (int i = 0; i < 4; ++i)
    {
        turn(to2, to);
        if (judge(to))
        {
            flag++;
            for (int x = 0; x < 3; ++x)
                for (int y = 0; y < 3; ++y)
                    ans[x][y] = to[x][y];
        }
        for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
                to2[x][y] = to[x][y];
    }
    if (flag == 1)
    {
        for (int x = 0; x < 3; ++x)
        {
            for (int y = 0; y < 3; ++y)
            {
                if (y) printf(" ");
                printf("%d", ans[x][y]);
            }
            printf("
");
        }
    }
    else printf("Too Many
");
}

int main()
{
    //freopen("test.in", "r", stdin);
    input();
    work();
    return 0;
}

View Code

B题：优化延迟（二分 && 优先队列）

http://hihocoder.com/problemset/problem/1269

这题二分缓冲区大小，然后对于每一种通过优先队列模拟过程得到最值。

不过我一开始就想好了用cin来输入long long型的，结果最后愣是二笔了一发，叫了一发”%d”。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long

using namespace std;

const int maxN = 100005;
int n, p[maxN];
LL Q;

LL SP(int k)
{
    priority_queue<int> q;
    int now = 0, t = 1, v;
    LL ans = 0;
    while (now < n || !q.empty())
    {
        while (q.size() < k && now < n) q.push(p[now++]);
        v = q.top();
        q.pop();
        ans += t*v;
        t++;
        if (ans > Q) return Q+1;
    }
    return ans;
}

bool input()
{
    if (!(cin >> n >> Q)) return false;
    //if (scanf("%d%d", &n, &Q) == EOF) return false;
    for (int i = 0; i < n; ++i)
        scanf("%d", &p[i]);
    return true;
}

void work()
{
    int lt = 1, rt = n, mid;
    while (lt+1 < rt)
    {
        mid = (lt+rt)>>1;
        if (SP(mid) <= Q) rt = mid;
        else lt = mid;
    }
    if (SP(lt) <= Q) printf("%d
", lt);
    else if (SP(rt) <= Q) printf("%d
", rt);
    else printf("-1
");
}

int main()
{
    //freopen("test.in", "r", stdin);
    while (input())
        work();
    return 0;
}

View Code

C题：建造基地（动态规划）

http://hihocoder.com/problemset/problem/1270

题目就是对每一层进行一个01背包，然后我二笔的当成普通的动态规划进行分析，然后发现需要线段树优化，然后果断T掉了，然后发现线段树的过程，只需要一个角标判断就搞定了。。最好发现就是个01背包。。这题做的时间太长了，导致最后一题只剩了个读题时间。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long

using namespace std;

int n, m, k, t;
int a[105], b[105];
LL p[10005];

void input()
{
    scanf("%d%d%d%d", &n, &m, &k, &t);
    for (int i = 0; i < m; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < m; ++i) scanf("%d", &b[i]);
}

void work()
{
    LL ans = 0;
    int f;
    for (int times = 1; times <= n; ++times)
    {
        memset(p, -1, sizeof(p));
        p[0] = 0;
        for (int i = 0; i < m; ++i)
        {
            if (b[i] == 0) continue;
            for (int j = 1; j <= k; ++j)
            {
                f = max(0, j-b[i]);
                if (p[j] == -1 || p[j] > p[f]+a[i])
                    p[j] = p[f]+a[i];
            }
        }
        if (p[k] == -1)
        {
            printf("No Answer
");
            return;
        }
        ans += p[k];
        for (int i = 0; i < m; ++i) b[i] /= t;
    }
    cout << ans << endl;
}

int main()
{
    //freopen("test.in", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int times = 1; times <= T; ++times)
    {
        input();
        work();
    }
    return 0;
}

View Code

D题：舰队游戏

http://hihocoder.com/problemset/problem/1271

首先可以得到的是两个数组正序乘正序大于正序乘乱序大于正序乘逆序。