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

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

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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;
}

  

上一篇:JS四舍五入保留两位小数


下一篇:perl 学习杂项笔记