比赛链接：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[][] = {
, , ,
, , ,
, ,
};
int to2[][] = {
, , ,
, , ,
, ,
};
int a[][], ans[][]; bool judge(int x[][])
{
for (int i = ; i < ; ++i)
for (int j = ; j < ; ++j)
if (a[i][j] != && a[i][j] != x[i][j])
return false;
return true;
} void turn(int x[][], int y[][])
{
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
y[][] = x[][];
} void input()
{
for (int i = ; i < ; ++i)
for (int j = ; j < ; ++j)
scanf("%d", &a[i][j]);
} void work()
{
int flag = , to[][];
for (int i = ; i < ; ++i)
{
turn(to1, to);
if (judge(to))
{
flag++;
for (int x = ; x < ; ++x)
for (int y = ; y < ; ++y)
ans[x][y] = to[x][y];
}
for (int x = ; x < ; ++x)
for (int y = ; y < ; ++y)
to1[x][y] = to[x][y];
}
for (int i = ; i < ; ++i)
{
turn(to2, to);
if (judge(to))
{
flag++;
for (int x = ; x < ; ++x)
for (int y = ; y < ; ++y)
ans[x][y] = to[x][y];
}
for (int x = ; x < ; ++x)
for (int y = ; y < ; ++y)
to2[x][y] = to[x][y];
}
if (flag == )
{
for (int x = ; x < ; ++x)
{
for (int y = ; y < ; ++y)
{
if (y) printf(" ");
printf("%d", ans[x][y]);
}
printf("\n");
}
}
else printf("Too Many\n");
} int main()
{
//freopen("test.in", "r", stdin);
input();
work();
return ;
}
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 = ;
int n, p[maxN];
LL Q; LL SP(int k)
{
priority_queue<int> q;
int now = , t = , v;
LL ans = ;
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+;
}
return ans;
} bool input()
{
if (!(cin >> n >> Q)) return false;
//if (scanf("%d%d", &n, &Q) == EOF) return false;
for (int i = ; i < n; ++i)
scanf("%d", &p[i]);
return true;
} void work()
{
int lt = , rt = n, mid;
while (lt+ < rt)
{
mid = (lt+rt)>>;
if (SP(mid) <= Q) rt = mid;
else lt = mid;
}
if (SP(lt) <= Q) printf("%d\n", lt);
else if (SP(rt) <= Q) printf("%d\n", rt);
else printf("-1\n");
} int main()
{
//freopen("test.in", "r", stdin);
while (input())
work();
return ;
}
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[], b[];
LL p[]; void input()
{
scanf("%d%d%d%d", &n, &m, &k, &t);
for (int i = ; i < m; ++i) scanf("%d", &a[i]);
for (int i = ; i < m; ++i) scanf("%d", &b[i]);
} void work()
{
LL ans = ;
int f;
for (int times = ; times <= n; ++times)
{
memset(p, -, sizeof(p));
p[] = ;
for (int i = ; i < m; ++i)
{
if (b[i] == ) continue;
for (int j = ; j <= k; ++j)
{
f = max(, j-b[i]);
if (p[j] == - || p[j] > p[f]+a[i])
p[j] = p[f]+a[i];
}
}
if (p[k] == -)
{
printf("No Answer\n");
return;
}
ans += p[k];
for (int i = ; i < m; ++i) b[i] /= t;
}
cout << ans << endl;
} int main()
{
//freopen("test.in", "r", stdin);
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
input();
work();
}
return ;
}
D题：舰队游戏
http://hihocoder.com/problemset/problem/1271
首先可以得到的是两个数组正序乘正序 大于 正序乘乱序 大于 正序乘逆序。
所以假设在知道每个舰船的装备栏里面装什么样的飞机的情况下。可以确定每一种飞机的各自归属。
于是只需要2^(m*n)暴力每一个装备栏的飞机种类。然后就可以计算题目要求的了。