Hihocoder 太阁最新面经算法竞赛18
source: https://hihocoder.com/contest/hihointerview27/problems
题目1 : Big Plus
描述
Given an NxN 01 matrix, find the biggest plus (+) consisting of 1s in the matrix.
size 1 plus size 2 plus size 3 plus size 4 plus
1 1 1 1
111 1 1 1
1 11111 1 1
1 1111111 1
1 1 111111111
1 1
1 1
1
1
输入
The first line contains an integer N. (1 <= N <= 500)
Then follow an NxN 01 matrix.
输出
The size of the biggest plus in the matrix.
- 样例输入5
-
00100
00100
11111
00110
10101 - 样例输出 2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 505; int n, ans;
char mp[MAXN][MAXN];
int U[MAXN][MAXN], D[MAXN][MAXN], LEF[MAXN][MAXN], RIG[MAXN][MAXN]; int main(){
int tmp;
while(scanf("%d", &n) != EOF){
for(int i=1; i<=n; ++i){
getchar();
for(int j=1; j<=n; ++j){
scanf("%c", &mp[i][j]);
}
}
memset(U, 0, sizeof(U)); memset(D, 0, sizeof(D));
memset(LEF, 0, sizeof(LEF)); memset(RIG, 0, sizeof(RIG));
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(mp[i][j] == '1'){
U[i][j] = U[i-1][j] + 1;
LEF[i][j] = LEF[i][j-1] + 1;
}
}
}
for(int i=n; i>=1; --i){
for(int j=n; j>=1; --j){
if(mp[i][j] == '1'){
D[i][j] = D[i+1][j] + 1;
RIG[i][j] = RIG[i][j+1] + 1;
}
}
}
ans = 0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(mp[i][j] == '1'){
tmp = min(min(U[i][j], RIG[i][j]), min(D[i][j], LEF[i][j]));
if(tmp-1 > ans){
ans = tmp - 1;
}
}
}
}
printf("%d\n", ans );
}
return 0;
}
题目2 : Interval Coverage
描述
You are given N intervals [S1, T1], [S2, T2], [S3, T3], ... [SN, TN] and a range [X, Y]. Select minimum number of intervals to cover range [X, Y].
输入
The first line contains 3 integers N, X and Y. (1 <= N <= 100000, 1 <= X < Y <= 1000000)
The following N lines each contain 2 integers Si, Ti denoting an interval. (1 <= Si < Ti <= 1000000)
输出
Output the minimum number of intevals to cover range [X, Y] or -1 if it is impossible.
- 样例输入
-
5 1 5
1 2
1 3
2 4
3 5
4 5 - 样例输出
-
2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
struct Interval{
int s, t;
}inte[MAXN];
int n, x, y; int cmp(const void *a, const void *b){
Interval *aa = (Interval *)a;
Interval *bb = (Interval *)b;
if(aa->s == bb->s){
return aa->t - bb->t;
}
return aa->s - bb->s;
}
int main(){
freopen("in.txt", "r", stdin); int ans, far, start;
while(scanf("%d %d %d", &n, &x, &y) != EOF){
for(int i=0; i<n; ++i){
scanf("%d %d", &inte[i].s, &inte[i].t);
}
qsort(inte, n, sizeof(inte[0]), cmp);
if(inte[0].s > x){
ans = -1;
}else{
far = max(x, inte[0].t);
start = x;
ans = 1;
for(int i=0; i<n; ++i){
if(far >= y){
break;
}
if(inte[i].s <= start){
far = max(far, inte[i].t);
}else if(inte[i].s > far){
break;
}else{
start = far;
far = max(far, inte[i].t);
++ans;
}
}
if(far < y){
ans = -1;
}
}
printf("%d\n", ans );
}
return 0;
}
题目3 : Split Array
描述
You are given an sorted integer array A and an integer K. Can you split A into several sub-arrays that each sub-array has exactly K continuous increasing integers.
For example you can split {1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6} into {1, 2, 3}, {1, 2, 3}, {3, 4, 5}, {4, 5, 6}.
输入
The first line contains an integer T denoting the number of test cases. (1 <= T <= 5)
Each test case takes 2 lines. The first line contains an integer N denoting the size of array A and an integer K. (1 <= N <= 50000, 1 <= K <= N)
The second line contains N integers denoting array A. (1 <= Ai <= 100000)
输出
For each test case output YES or NO in a separate line.
- 样例输入
-
2
12 3
1 1 2 2 3 3 3 4 4 5 5 6
12 4
1 1 2 2 3 3 3 4 4 5 5 6 - 样例输出
-
YES
NO
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 50000 + 5;
const int MAXV = 100000 + 5; int n, k, num[MAXV];
int main(){
freopen("in.txt", "r", stdin); int test_case, val, maxval, tmp, flag;
scanf("%d", &test_case); while(test_case--){
scanf("%d %d", &n, &k);
maxval = 0;
memset(num, 0, sizeof(num));
for(int i=0; i<n; ++i){
scanf("%d", &val);
num[val]++;
maxval = max(maxval, val);
}
flag = 1;
for(int i=1; i<=maxval; ++i){
if(num[i] > 0){
tmp = num[i];
for(int j=0; j<k; ++j){
num[i+j] -= tmp;
}
}else if(num[i] < 0){
flag = 0;
break;
}
}
if(flag){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}