比賽鏈接：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 longusing 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("\n");}}else printf("Too Many\n"); }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 longusing 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\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 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 longusing 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\n");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

首先可以得到的是兩個數組正序乘正序?大于?正序乘亂序?大于?正序乘逆序。

所以假設在知道每個艦船的裝備欄里面裝什么樣的飛機的情況下。可以確定每一種飛機的各自歸屬。

于是只需要2^(m*n)暴力每一個裝備欄的飛機種類。然后就可以計算題目要求的了。

?

轉載于:https://www.cnblogs.com/andyqsmart/p/5269355.html

總結

以上是生活随笔為你收集整理的ACM学习历程—Hihocoder [Offer收割]编程练习赛1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。