比赛链接：http://hihocoder.com/contest/hihointerview27/problems
A.Big Plus
模拟水
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int n;
char G[maxn][maxn]; bool ok(int x, int y) {
return x >= && x < n && y >= && y < n;
}
int check(int x, int y) {
int s = ;
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++;
return s - ;
} int main() {
// freopen("in", "r", stdin);
memset(G, , sizeof(G));
while(~scanf("%d", &n)) {
for(int i = ; i < n; i++) {
scanf("%s", G[i]);
}
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
G[i][j] -= '';
}
}
int ret = ;
for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(G[i][j] == ) {
ret = max(ret, check(i, j));
}
}
}
printf("%d\n", ret);
}
return ;
}
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)的解法。
#include <bits/stdc++.h>
using namespace std; typedef struct Node {
int s, t;
}Node;
const int maxn = ;
int n, x, y;
Node p[maxn]; int dp[maxn][];
int a[maxn], b[maxn]; bool cmp(Node a, Node b) {
if(a.s == b.s) return a.t < b.t;
return a.s < b.s;
} void st() {
for(int i = ; i <= n; i++) dp[i][] = b[i];
int k = int(log(n+1.0)/log(2.0));
for(int j = ; j <= k; j++) {
for(int i = ; i + ( << j) - <= n; i++) {
dp[i][j] = max(dp[i][j-], dp[i+(<<(j-))][j-]);
}
}
} int query(int l, int r) {
int k = int(log(r-l+1.0)/log(2.0));
return max(dp[l][k], dp[r-(<<k)+][k]);
} int bs(int lo, int hi, int x) {
int pos;
while(lo <= hi) {
int mid = (lo + hi) >> ;
if(a[mid] <= x) {
pos = mid;
lo = mid + ;
}
else hi = mid - ;
}
return pos;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d%d%d",&n,&x,&y)) {
for(int i = ; i <= n; i++) {
scanf("%d%d",&p[i].s,&p[i].t);
}
sort(p+, p+n+, cmp);
for(int i = ; i <= n; i++) {
a[i] = p[i].s;
b[i] = p[i].t;
}
st();
int ret = ;
bool flag = ;
while(x < y) {
int pos = bs(, n, x);
int t = query(, pos);
if(x == t) {
flag = ;
break;
}
x = t;
ret++;
}
if(flag) puts("-1");
else printf("%d\n", ret);
}
return ;
}
C.Split Array
题意仅仅是要求分成的小数组里有且仅有k个数字并且连续。那么从头到尾扫一边，每一次都提出一个数字就行了。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int n, m, k, a;
int cnt[maxn]; int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d",&n,&k);
memset(cnt, , sizeof(cnt));
m = ;
for(int i = ; i <= n; i++) {
scanf("%d", &a);
cnt[a]++;
m = max(m, a);
}
bool flag = ;
for(int i = ; i <= m; i++) {
if(flag == ) break;
if(cnt[i] > ) {
while(cnt[i] > ) {
for(int j = i; j < i + k; j++) {
if(cnt[j] > ) cnt[j]--;
else {
flag = ;
break;
}
}
}
}
}
if(flag) puts("NO");
else puts("YES");
}
return ;
}