比賽鏈接：http://hihocoder.com/contest/hihointerview27/problems

A.Big Plus

模擬水

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 505; 5 int n; 6 char G[maxn][maxn]; 7 8 bool ok(int x, int y) { 9 return x >= 0 && x < n && y >= 0 && y < n; 10 } 11 int check(int x, int y) { 12 int s = 0; 13 while(ok(x,y-s)&&ok(x,y+s)&&ok(x-s,y)&&ok(x+s,y)&&G[x+s][y]&&G[x-s][y]&&G[x][y+s]&&G[x][y-s]) s++; 14 return s - 1; 15 } 16 17 int main() { 18 // freopen("in", "r", stdin); 19 memset(G, 0, sizeof(G)); 20 while(~scanf("%d", &n)) { 21 for(int i = 0; i < n; i++) { 22 scanf("%s", G[i]); 23 } 24 for(int i = 0; i < n; i++) { 25 for(int j = 0; j < n; j++) { 26 G[i][j] -= '0'; 27 } 28 } 29 int ret = 0; 30 for(int i = 0; i < n; i++) { 31 for(int j = 0; j < n; j++) { 32 if(G[i][j] == 1) { 33 ret = max(ret, check(i, j)); 34 } 35 } 36 } 37 printf("%d\n", ret); 38 } 39 return 0; 40 }

?

B.Interval Coverage

初始的目標是[x,y]，結束的目標應當是[y,y]： 因為排好序了的，所以先二分，找到一個區間[l,r]，使得r盡可能大，并且l不超過x，找到了這么一個l，位置的下標為pos。 那么，現在就需要在排號序后下標為[1,pos]的r中選擇最遠的，由于用st表預處理了這個東西，所以直接O(1)可以得到最遠的r=t（是值）。 其實就不需要關注這個t對應的那條線段是誰了，反正已經符合條件了，那么就更新x=t就行了，目標變成了[t,y]。討論區的意思是還有O(n)的解法。

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef struct Node { 5 int s, t; 6 }Node; 7 const int maxn = 100100; 8 int n, x, y; 9 Node p[maxn]; 10 11 int dp[maxn][20]; 12 int a[maxn], b[maxn]; 13 14 bool cmp(Node a, Node b) { 15 if(a.s == b.s) return a.t < b.t; 16 return a.s < b.s; 17 } 18 19 void st() { 20 for(int i = 1; i <= n; i++) dp[i][0] = b[i]; 21 int k = int(log(n+1.0)/log(2.0)); 22 for(int j = 1; j <= k; j++) { 23 for(int i = 1; i + (1 << j) - 1 <= n; i++) { 24 dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); 25 } 26 } 27 } 28 29 int query(int l, int r) { 30 int k = int(log(r-l+1.0)/log(2.0)); 31 return max(dp[l][k], dp[r-(1<<k)+1][k]); 32 } 33 34 int bs(int lo, int hi, int x) { 35 int pos; 36 while(lo <= hi) { 37 int mid = (lo + hi) >> 1; 38 if(a[mid] <= x) { 39 pos = mid; 40 lo = mid + 1; 41 } 42 else hi = mid - 1; 43 } 44 return pos; 45 } 46 47 int main() { 48 // freopen("in", "r", stdin); 49 while(~scanf("%d%d%d",&n,&x,&y)) { 50 for(int i = 1; i <= n; i++) { 51 scanf("%d%d",&p[i].s,&p[i].t); 52 } 53 sort(p+1, p+n+1, cmp); 54 for(int i = 1; i <= n; i++) { 55 a[i] = p[i].s; 56 b[i] = p[i].t; 57 } 58 st(); 59 int ret = 0; 60 bool flag = 0; 61 while(x < y) { 62 int pos = bs(1, n, x); 63 int t = query(1, pos); 64 if(x == t) { 65 flag = 1; 66 break; 67 } 68 x = t; 69 ret++; 70 } 71 if(flag) puts("-1"); 72 else printf("%d\n", ret); 73 } 74 return 0; 75 }

?

C.Split Array

題意僅僅是要求分成的小數組里有且僅有k個數字并且連續。那么從頭到尾掃一邊，每一次都提出一個數字就行了。

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100500; 5 int n, m, k, a; 6 int cnt[maxn]; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 int T; 11 scanf("%d", &T); 12 while(T--) { 13 scanf("%d%d",&n,&k); 14 memset(cnt, 0, sizeof(cnt)); 15 m = 0; 16 for(int i = 1; i <= n; i++) { 17 scanf("%d", &a); 18 cnt[a]++; 19 m = max(m, a); 20 } 21 bool flag = 0; 22 for(int i = 1; i <= m; i++) { 23 if(flag == 1) break; 24 if(cnt[i] > 0) { 25 while(cnt[i] > 0) { 26 for(int j = i; j < i + k; j++) { 27 if(cnt[j] > 0) cnt[j]--; 28 else { 29 flag = 1; 30 break; 31 } 32 } 33 } 34 } 35 } 36 if(flag) puts("NO"); 37 else puts("YES"); 38 } 39 return 0; 40 }

?

轉載于:https://www.cnblogs.com/kirai/p/6189376.html

總結

以上是生活随笔為你收集整理的hihoCoder太阁最新面经算法竞赛18的全部內容，希望文章能夠幫你解決所遇到的問題。

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