首页 > 代码库 > hihoCoder太阁最新面经算法竞赛18

hihoCoder太阁最新面经算法竞赛18

2024-08-27 16:55:41   222人阅读

比赛链接：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 }

 

hihoCoder太阁最新面经算法竞赛18


联系
我们