Codeforces Round #578 (Div. 2)

A. Hotelier

time limit per test1 second memory limit per test256 megabytes

Amugae has a hotel consisting of 1010 rooms. The rooms are numbered from 00 to 99 from left to right.

The hotel has two entrances — one from the left end, and another from the right end. When a customer arrives to the hotel through the left entrance, they are assigned to an empty room closest to the left entrance. Similarly, when a customer arrives at the hotel through the right entrance, they are assigned to an empty room closest to the right entrance.

One day, Amugae lost the room assignment list. Thankfully Amugae’s memory is perfect, and he remembers all of the customers: when a customer arrived, from which entrance, and when they left the hotel. Initially the hotel was empty. Write a program that recovers the room assignment list from Amugae’s memory.Input

The first line consists of an integer 𝑛n (1≤𝑛≤1051≤n≤105), the number of events in Amugae’s memory.

The second line consists of a string of length 𝑛n describing the events in chronological order. Each character represents:

  • ‘L’: A customer arrives from the left entrance.
  • ‘R’: A customer arrives from the right entrance.
  • ‘0’, ‘1’, …, ‘9’: The customer in room 𝑥x (00, 11, …, 99 respectively) leaves.

It is guaranteed that there is at least one empty room when a customer arrives, and there is a customer in the room 𝑥x when 𝑥x (00, 11, …, 99) is given. Also, all the rooms are initially empty.Output

In the only line, output the hotel room’s assignment status, from room 00 to room 99. Represent an empty room as ‘0’, and an occupied room as ‘1’, without spaces.

Examplesinput

8
LLRL1RL1

output

1010000011

input

9
L0L0LLRR9

output

1100000010

Note

In the first example, hotel room’s assignment status after each action is as follows.

  • First of all, all rooms are empty. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • L: one more customer from the left entrance. Assignment status is 1100000000.
  • R: one more customer from the right entrance. Assignment status is 1100000001.
  • L: one more customer from the left entrance. Assignment status is 1110000001.
  • 1: the customer in room 11 leaves. Assignment status is 1010000001.
  • R: one more customer from the right entrance. Assignment status is 1010000011.
  • L: one more customer from the left entrance. Assignment status is 1110000011.
  • 1: the customer in room 11 leaves. Assignment status is 1010000011.

So after all, hotel room’s final assignment status is 1010000011.

In the second example, hotel room’s assignment status after each action is as follows.

  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • 0: the customer in room 00 leaves. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000 again.
  • 0: the customer in room 00 leaves. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • L: one more customer from the left entrance. Assignment status is 1100000000.
  • R: one more customer from the right entrance. Assignment status is 1100000001.
  • R: one more customer from the right entrance. Assignment status is 1100000011.
  • 9: the customer in room 99 leaves. Assignment status is 1100000010.

So after all, hotel room’s final assignment status is 1100000010.

签到,模拟

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[11];
string s;
int main(){
    cin>>n>>s;
    rep(i,0,n-1){
        if(s[i]=='L'){
            rep(j,0,9) if(a[j]==0){a[j]=1;break;}
        }
        else if(s[i]=='R'){
            dep(j,9,0) if(a[j]==0){a[j]=1;break;}
        }
        else a[s[i]-'0']=0;
    }
    rep(i,0,9) printf("%d",a[i]);
}

 


B. Block Adventure

time limit per test1 second memory limit per test256 megabytes

Gildong is playing a video game called Block Adventure. In Block Adventure, there are 𝑛n columns of blocks in a row, and the columns are numbered from 11 to 𝑛n. All blocks have equal heights. The height of the 𝑖i-th column is represented as ℎ𝑖hi, which is the number of blocks stacked in the 𝑖i-th column.

Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the 11-st column. The goal of the game is to move the character to the top of the 𝑛n-th column.

The character also has a bag that can hold infinitely many blocks. When the character is on the top of the 𝑖i-th column, Gildong can take one of the following three actions as many times as he wants:

  • if there is at least one block on the column, remove one block from the top of the 𝑖i-th column and put it in the bag;
  • if there is at least one block in the bag, take one block out of the bag and place it on the top of the 𝑖i-th column;
  • if 𝑖<𝑛i<n and |ℎ𝑖−ℎ𝑖+1|≤𝑘|hi−hi+1|≤k, move the character to the top of the 𝑖+1i+1-st column. 𝑘k is a non-negative integer given at the beginning of the game. Note that it is only possible to move to the next column.

In actions of the first two types the character remains in the 𝑖i-th column, and the value ℎ𝑖hi changes.

The character initially has 𝑚m blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.Input

Each test contains one or more test cases. The first line contains the number of test cases 𝑡t (1≤𝑡≤10001≤t≤1000). Description of the test cases follows.

The first line of each test case contains three integers 𝑛n, 𝑚m, and 𝑘k (1≤𝑛≤1001≤n≤100, 0≤𝑚≤1060≤m≤106, 0≤𝑘≤1060≤k≤106) — the number of columns in the game, the number of blocks in the character’s bag at the beginning, and the non-negative integer 𝑘k described in the statement.

The second line of each test case contains 𝑛n integers. The 𝑖i-th integer is ℎ𝑖hi (0≤ℎ𝑖≤1060≤hi≤106), the initial height of the 𝑖i-th column.Output

For each test case, print “YES” if it is possible to win the game. Otherwise, print “NO”.

You can print each letter in any case (upper or lower).

Exampleinput

5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99

output

YES
NO
YES
NO
YES

Note

In the first case, Gildong can take one block from the 11-st column, move to the 22-nd column, put the block on the 22-nd column, then move to the 33-rd column.

In the second case, Gildong has to put the block in his bag on the 11-st column to get to the 22-nd column. But it is impossible to get to the 33-rd column because |ℎ2−ℎ3|=3>𝑘|h2−h3|=3>k and there is no way to decrease the gap.

In the fifth case, the character is already on the 𝑛n-th column from the start so the game is won instantly.

签到,贪心地每次拿最多

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,m,k,h[110];
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,n) scanf("%d",&h[i]);
    rep(i,1,n-1){
        if(h[i]>=h[i+1]) m+=min(h[i],h[i]-h[i+1]+k);
        else if(abs(h[i+1]-h[i])<=k) m+=min(h[i],h[i]-h[i+1]+k);
        else if(h[i]+m+k<h[i+1]){puts("NO");return;}
        else m-=h[i+1]-k-h[i];
    }
    puts("YES");
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

 


C. Round Corridor

time limit per test1 second memory limit per test256 megabytes

Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by 𝑛n sectors, and the outer area is equally divided by 𝑚m sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o’clock position.

The inner area’s sectors are denoted as (1,1),(1,2),…,(1,𝑛)(1,1),(1,2),…,(1,n) in clockwise direction. The outer area’s sectors are denoted as (2,1),(2,2),…,(2,𝑚)(2,1),(2,2),…,(2,m) in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has 𝑞q questions.

For each question, check if he can move between two given sectors.Input

The first line contains three integers 𝑛n, 𝑚m and 𝑞q (1≤𝑛,𝑚≤10181≤n,m≤1018, 1≤𝑞≤1041≤q≤104) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next 𝑞q lines contains four integers 𝑠𝑥sx, 𝑠𝑦sy, 𝑒𝑥ex, 𝑒𝑦ey (1≤𝑠𝑥,𝑒𝑥≤21≤sx,ex≤2; if 𝑠𝑥=1sx=1, then 1≤𝑠𝑦≤𝑛1≤sy≤n, otherwise 1≤𝑠𝑦≤𝑚1≤sy≤m; constraints on 𝑒𝑦ey are similar). Amague wants to know if it is possible to move from sector (𝑠𝑥,𝑠𝑦)(sx,sy) to sector (𝑒𝑥,𝑒𝑦)(ex,ey).Output

For each question, print “YES” if Amugae can move from (𝑠𝑥,𝑠𝑦)(sx,sy) to (𝑒𝑥,𝑒𝑦)(ex,ey), and “NO” otherwise.

You can print each letter in any case (upper or lower).

Exampleinput

4 6 3
1 1 2 3
2 6 1 2
2 6 2 4

output

YES
NO
YES

Note

Example is shown on the picture in the statement.

两个圈都分成gcd(n,m)个部分,看给的两个区域在不在一个区域就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll n,m,g;int q;
void solve(){
	ll a,b,c,d;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	if(a==c){
		ll k;
		if(a==1) k=n/g;
		else k=m/g;
		b=(b-1)/k+1; d=(d-1)/k+1;
		if(b!=d) puts("NO");
		else puts("YES");
	}
	else{
		if(a>c) swap(b,d);
		ll k1=n/g,k2=m/g;
		b=(b-1)/k1+1; d=(d-1)/k2+1;
		if(b!=d) puts("NO");
		else puts("YES");
	}
}
int main(){
	scanf("%lld%lld%d",&n,&m,&q);
	g=__gcd(n,m);
	while(q--) solve();
}

 


D. White Lines

time limit per test1.5 seconds memory limit per test256 megabytes

Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of 𝑛n rows and 𝑛ncolumns of square cells. The rows are numbered from 11 to 𝑛n, from top to bottom, and the columns are numbered from 11 to 𝑛n, from left to right. The position of a cell at row 𝑟r and column 𝑐c is represented as (𝑟,𝑐)(r,c). There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size 𝑘k (1≤𝑘≤𝑛1≤k≤n). To use the eraser, Gildong needs to click on a cell (𝑖,𝑗)(i,j) where 1≤𝑖,𝑗≤𝑛−𝑘+11≤i,j≤n−k+1. When a cell (𝑖,𝑗)(i,j) is clicked, all of the cells (𝑖′,𝑗′)(i′,j′) where 𝑖≤𝑖′≤𝑖+𝑘−1i≤i′≤i+k−1 and 𝑗≤𝑗′≤𝑗+𝑘−1j≤j′≤j+k−1become white. In other words, a square with side equal to 𝑘k cells and top left corner at (𝑖,𝑗)(i,j) is colored white.

white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.Input

The first line contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤20001≤k≤n≤2000) — the number of rows and columns, and the size of the eraser.

The next 𝑛n lines contain 𝑛n characters each without spaces. The 𝑗j-th character in the 𝑖i-th line represents the cell at (𝑖,𝑗)(i,j). Each character is given as either ‘B’ representing a black cell, or ‘W’ representing a white cell.Output

Print one integer: the maximum number of white lines after using the eraser exactly once.

Examplesinput

4 2
BWWW
WBBW
WBBW
WWWB

output

4

input

3 1
BWB
WWB
BWB

output

2

input

5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW

output

2

input

2 2
BW
WB

output

4

input

2 1
WW
WW

output

4

Note

In the first example, Gildong can click the cell (2,2)(2,2), then the working screen becomes:

BWWW
WWWW
WWWW
WWWB

Then there are four white lines — the 22-nd and 33-rd row, and the 22-nd and 33-rd column.

In the second example, clicking the cell (2,3)(2,3) makes the 22-nd row a white line.

In the third example, both the 22-nd column and 55-th row become white lines by clicking the cell (3,2)(3,2).

挺简单的一题,n^2稳过,预处理出来两个前缀和,具体看注释

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e3+100;
int n,k,l[maxn][maxn],r[maxn][maxn],u[maxn][maxn],d[maxn][maxn];
int h[maxn][maxn],s[maxn][maxn],ph[maxn],ps[maxn];
char mp[maxn][maxn];
int main(){
    scanf("%d%d\n",&n,&k);
    rep(i,1,n) scanf("%s",mp[i]+1);
    rep(i,1,n) rep(j,1,n) if(mp[i][j]=='W'){
        l[i][j]=l[i][j-1]+1; //向左连续w的数量
        u[i][j]=u[i-1][j]+1; //向上连续w的数量
    }
    dep(i,n,1) dep(j,n,1) if(mp[i][j]=='W'){
        r[i][j]=r[i][j+1]+1; //向右连续w的数量
        d[i][j]=d[i+1][j]+1; //向下连续w的数量
    }
    rep(i,1,n) rep(j,1,n){
        if(l[i][j-1]+r[i][j+k]==n-k) h[i][j]=1; //把这个点变成矩形左上角后能增加的都是w的行数
        if(u[i-1][j]+d[i+k][j]==n-k) s[i][j]=1; //把这个点变成矩形左上角后能增加的都是w的列数
        h[i][j]+=h[i-1][j];s[i][j]+=s[i][j-1];
    }
    rep(i,1,n){
        if(r[i][1]==n) ph[i]=1; //一整行都是w的行数
        if(d[1][i]==n) ps[i]=1; //一整列都是w的列数
        ph[i]+=ph[i-1];ps[i]+=ps[i-1];
    }
    int ans=0;
    rep(i,1,n-k+1) rep(j,1,n-k+1){
        int tmp=0;
        tmp+=ph[i-1]+(ph[n]-ph[i+k-1])+ps[j-1]+(ps[n]-ps[j+k-1]);
        tmp+=h[i+k-1][j]-h[i-1][j];
        tmp+=s[i][j+k-1]-s[i][j-1];
        ans=max(ans,tmp);
    }
    printf("%d\n",ans);
}

 


E. Compress Words

time limit per test1 second memory limit per test256 megabytes

Amugae has a sentence consisting of 𝑛n words. He want to compress this sentence into one word. Amugae doesn’t like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges “sample” and “please” into “samplease”.

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.Input

The first line contains an integer 𝑛n (1≤𝑛≤1051≤n≤105), the number of the words in Amugae’s sentence.

The second line contains 𝑛n words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits (‘A’, ‘B’, …, ‘Z’, ‘a’, ‘b’, …, ‘z’, ‘0’, ‘1’, …, ‘9’). The total length of the words does not exceed 106106.Output

In the only line output the compressed word after the merging process ends as described in the problem.

Examplesinput

5
I want to order pizza

output

Iwantorderpizza

input

5
sample please ease in out

output

sampleaseinout

KMP模版题,感觉比d简单

#include <bits/stdc++.h>
using namespace std;
int n;
int nxt[1000010];
string a,b;
void merge(string &a, string &b) {
    nxt[0] = -1;
    for (int i = 0, j; i < b.size(); ++i) {
        for (j = nxt[i]; j>=0 && b[j] != b[i]; j = nxt[j]);
        nxt[i+1] = ++j;
    }
    int j = 0;
    for (int i=max(0,(int)a.size()-(int)b.size());i<a.size();++i,++j){
        if (j==(int)b.size()) j=nxt[j];
        for(;j>=0&&b[j]!=a[i];j=nxt[j]);
    }
    a+=b.substr(j);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin>>b;
        merge(a,b);
    }
    cout<<a<<"\n";
}

 

发表评论,支持MarkDown语法