Bear and Blocks

题面翻译

题目描述

zpy又发明了一个小游戏，炸方块

有n列方块，每列方块分别有hi个方块构成，也就是高度为hi

zpy定义边缘方块是这样的：如果一个方块上下左右都有接触到其他方块或地面，就算内部方块，否则就是边缘方块

这个游戏每次可以将当前的边缘方块全部炸掉，这些炸掉的方块就会消失，余下剩余的方块，这个时候，剩余方块里不少方块变成边缘方块，又可以被炸掉了

zpy现在想知道的是，给定初始方块情况，炸多少次方块会全部消失？

样例的情况如下图：

炸3次方块全部炸光了。

输入

第一行输入n

第二行输入n个整数hi

输出

输出次数

样例输入

6
2 1 4 6 2 2

样例输出

3

提示

【样例说明】

7

3 3 3 1 3 3 3

输出：2

【数据规模和约定】

1<=n<=10^5 1<=hi<=10^9

题目描述

Limak is a little bear who loves to play.

Today he is playing by destroying block towers.

He built $n$ towers in a row.

The $i$ -th tower is made of $h_i$ identical blocks.

For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor.

Otherwise, block is boundary.

In one operation Limak destroys all boundary blocks.

His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start.

You task is to count how many operations will it take him to destroy all towers.

输入格式

The first line contains single integer $n$ ( $1<=n<=10^5$ ).

The second line contains $n$ space-separated integers $h_1,h_2,...,h_n$ ( $1<=h_i<=10^9)$ — sizes of towers.

输出格式

Print the number of operations needed to destroy all towers.

样例 #1

样例输入 #1

6
2 1 4 6 2 2

样例输出 #1

3

样例 #2

样例输入 #2

7
3 3 3 1 3 3 3

样例输出 #2

2

提示

The picture below shows all three operations for the first sample test.

Each time boundary blocks are marked with red color.

After first operation there are four blocks left and only one remains after second operation.

This last block is destroyed in third operation.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,h[N],s[N],ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	s[1]=1;
	for(int i=2;i<n;i++) s[i]=min(h[i],s[i-1]+1);
	s[n]=1;
	for(int i=n-1;i>=0;i--) s[i]=min(s[i],s[i+1]+1);
	for(int i=1;i<=n;i++) ans=max(ans,s[i]);
	cout<<ans;
    return 0;
}

Longest k-Good Segment

题面翻译

给定一个包含$n$个整数的序列$a$，$0\le a_i\le 10^6$ ，询问不重复数字个数$\le k$的最长区间的左右端点

如果有多解输出任意一组。

题目描述

The array $a$ with $n$ integers is given.

Let’s call the sequence of one or more consecutive elements in $a$ segment.

Also let’s call the segment k-good if it contains no more than $k$ different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

输入格式

The first line contains two integers $n,k$ ( $1<=k<=n<=5\cdot 10^5$ ) — the number of elements in $a$ and the parameter $k$ .

The second line contains $n$ integers $a_i$ ( $0<=a_i<=10^6$ ) — the elements of the array $a$ .

输出格式

Print two integers $l,r$ ( $1<=l<=r<=n$ ) — the index of the left and the index of the right ends of some k-good longest segment.

If there are several longest segments you can print any of them.

The elements in $a$ are numbered from $1$ to $n$ from left to right.

样例 #1

样例输入 #1

5 5
1 2 3 4 5

样例输出 #1

1 5

样例 #2

样例输入 #2

9 3
6 5 1 2 3 2 1 4 5

样例输出 #2

3 7

样例 #3

样例输入 #3

3 1
1 2 3

样例输出 #3

1 1

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,k,r=1,maxi=0,maxj=0,maxl=-1,s[N],sign=0,a[N];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) scanf("%d",&s[i]);
	for(int i=1;i<=n;i++){
		while(r<n+2&&sign<=k){
			if(!a[s[r]]) sign++;
			a[s[r++]]++;
		}
		if(r-i>maxl){
			maxl=r-i;
			maxi=i,maxj=r-2;
		}
		a[s[i]]--;
		if(!a[s[i]]) sign--;
	}
	cout<<maxi<<" "<<maxj;
    return 0;
}

Testing Robots

题目描述

The Cybernetics Failures (CF) organisation made a prototype of a bomb technician robot.

To find the possible problems it was decided to carry out a series of tests.

At the beginning of each test the robot prototype will be placed in cell $(x_0,y_0)$ of a rectangular squared field of size $x\times y$ , after that a mine will be installed into one of the squares of the field.

It is supposed to conduct exactly $x\cdot y$ tests, each time a mine is installed into a square that has never been used before.

The starting cell of the robot always remains the same.

After placing the objects on the field the robot will have to run a sequence of commands given by string $s$ , consisting only of characters ‘L’, ‘R’, ‘U’, ‘D’.

These commands tell the robot to move one square to the left, to the right, up or down, or stay idle if moving in the given direction is impossible.

As soon as the robot fulfills all the sequence of commands, it will blow up due to a bug in the code.

But if at some moment of time the robot is at the same square with the mine, it will also blow up, but not due to a bug in the code.

Moving to the left decreases coordinate $y$ , and moving to the right increases it.

Similarly, moving up decreases the $x$ coordinate, and moving down increases it.

The tests can go on for very long, so your task is to predict their results.

For each $k$ from $0$ to $length(s)$ your task is to find in how many tests the robot will run exactly $k$ commands before it blows up.

输入格式

The first line of the input contains four integers $x$ , $y$ , $x_0$ , $y_0$ ( $1<=x,y<=500,1<=x_0<=x,1<=y_0<=y$ ) — the sizes of the field and the starting coordinates of the robot.

The coordinate axis $X$ is directed downwards and axis $Y$ is directed to the right.

The second line contains a sequence of commands $s$ , which should be fulfilled by the robot.

It has length from $1$ to $100000$ characters and only consists of characters ‘L’, ‘R’, ‘U’, ‘D’.

输出格式

Print the sequence consisting of $(length(s)+1)$ numbers.

On the $k$ -th position, starting with zero, print the number of tests where the robot will run exactly $k$ commands before it blows up.

样例 #1

样例输入 #1

3 4 2 2
UURDRDRL

样例输出 #1

1 1 0 1 1 1 1 0 6

样例 #2

样例输入 #2

2 2 2 2
ULD

样例输出 #2

1 1 1 1

提示

In the first sample, if we exclude the probable impact of the mines, the robot’s route will look like that:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int x,y,x0,y0,l,ans=0;
bool sign[1000][1000];
string s;
int main(){
	cin>>x>>y>>x0>>y0;
	cin>>s;
	l=s.size();
	for(int i=0;i<l;i++){
		if(!sign[x0][y0]){
			printf("1 ");
			ans++;
			sign[x0][y0]=1;
		}
		else printf("0 ");
		if(s[i]=='U') x0=max(x0-1,1);
		else if(s[i]=='D') x0=min(x0+1,x);
		else if(s[i]=='L') y0=max(y0-1,1);
		else y0=min(y0+1,y);
	}
	cout<<x*y-ans<<endl;
    return 0;
}

Restaurant

题面翻译

一家餐馆收到了N张出租的订单。每个租赁订单连续预订餐厅一段时间，第i个订单上有开始时间l[i]和结束时间r[i]（l[i]<=r[i]）

餐厅管理层可以接受和拒绝订单。问餐厅可以接受的最大订单数是多少？

注意，餐厅不能同时做两张订单

题目描述

A restaurant received $n$ orders for the rental.

Each rental order reserve the restaurant for a continuous period of time, the $i$ -th order is characterized by two time values — the start time $l_i$ and the finish time $r_i$ ( $l_i<=r_i$ ).

Restaurant management can accept and reject orders.

What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can’t share even a moment of time.

If one order ends in the moment other starts, they can’t be accepted both.

输入格式

The first line contains integer number $n$ ( $ 1<=n<=5·10^{5} $ ) — number of orders.

The following $n$ lines contain integer values $l_i$ and $r_i$ each ( $1<=l_i<=r_i<=10^9$ ).

输出格式

Print the maximal number of orders that can be accepted.

样例 #1

样例输入 #1

2
7 11
4 7

样例输出 #1

1

样例 #2

样例输入 #2

5
1 2
2 3
3 4
4 5
5 6

样例输出 #2

3

样例 #3

样例输入 #3

6
4 8
1 5
4 7
2 5
1 3
6 8

样例输出 #3

2

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
struct stu{
	int l,r;
}s[N];
bool cmp(stu x,stu y){
	return x.r<y.r;
}
int n,k=-1,ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i].l,&s[i].r);
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(s[i].l>=k){
			ans++;
			k=s[i].r+1;
		}
	}
	cout<<ans<<endl;
    return 0;
}

Bear and Forgotten Tree 3

题面翻译

构造一棵n个点，深度h，最长链为d的树

题目描述

A tree is a connected undirected graph consisting of $n$ vertices and $n-1$ edges.

Vertices are numbered $1$ through $n$ .

Limak is a little polar bear and Radewoosh is his evil enemy.

Limak once had a tree but Radewoosh stolen it.

Bear is very sad now because he doesn’t remember much about the tree — he can tell you only three values $n$ , $d$ and $h$ :

• The tree had exactly $n$ vertices.
• The tree had diameter $d$ .
• In other words, $d$ was the biggest distance between two vertices.
• Limak also remembers that he once rooted the tree in vertex $1$ and after that its height was $h$ .
• In other words, $h$ was the biggest distance between vertex $1$ and some other vertex.

The distance between two vertices of the tree is the number of edges on the simple path between them.

Help Limak to restore his tree.

Check whether there exists a tree satisfying the given conditions.

Find any such tree and print its edges in any order.

It’s also possible that Limak made a mistake and there is no suitable tree – in this case print “-1”.

输入格式

The first line contains three integers $n$ , $d$ and $h$ ( $2<=n<=100000,1<=h<=d<=n-1$ ) — the number of vertices, diameter, and height after rooting in vertex $1$ , respectively.

输出格式

If there is no tree matching what Limak remembers, print the only line with “-1” (without the quotes).

Otherwise, describe any tree matching Limak’s description.

Print $n-1$ lines, each with two space-separated integers – indices of vertices connected by an edge.

If there are many valid trees, print any of them.

You can print edges in any order.

样例 #1

样例输入 #1

5 3 2

样例输出 #1

1 2
1 3
3 4
3 5

样例 #2

样例输入 #2

8 5 2

样例输出 #2

-1

样例 #3

样例输入 #3

8 4 2

样例输出 #3

4 8
5 7
2 3
8 1
2 1
5 6
1 5

提示

Below you can see trees printed to the output in the first sample and the third sample.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,h,d;
int main(){
	cin>>n>>d>>h;
	if(d>(h*2)||n<=d||d<h||(d==1&&n!=2)){
		puts("-1");
		return 0;
	}
	for(int i=2;i<=h+1;i++) printf("%d %d\n",i-1,i);
	if(d>h){
		printf("1 %d\n",h+2);
		for(int i=h+3;i<=d+1;i++) printf("%d %d\n",i-1,i);
	}
	for(int i=d+2;i<=n;i++) printf("%d %d\n",h,i);
    return 0;
}