• 欢迎光临~

# 20220722

## 比赛

Educational Codeforces Round 132 (Rated for Div. 2)

## 过了的题

### A. Three Doors

There are three doors in front of you, numbered from (1) to (3) from left to right. Each door has a lock on it, which can only be opened with a key with the same number on it as the number on the door.

There are three keys — one for each door. Two of them are hidden behind the doors, so that there is no more than one key behind each door. So two doors have one key behind them, one door doesn't have a key behind it. To obtain a key hidden behind a door, you should first unlock that door. The remaining key is in your hands.

Can you open all the doors?

#### 读题

• obtain v.获得;(尤指经努力)赢得;存在;流行;沿袭

#### 代码

``````#include <iostream>
using namespace std;
int door;
int main(){
int t;cin>>t;
while (t--) {
int flag=1,x;cin >> x;
for (int i = 1; i <= 3; i++)cin >> door[i];
if(door[x]==0){
flag=0;
}
if(door[door[x]]==0){
flag=0;
}
if(flag)cout<<"YESn";
else cout<<"NOn";
}
return 0;
}
``````

``````#include <iostream>
using namespace std;
int d;
int main(){
int t;cin>>t;
while (t--) {
for (int i = 0; i <= 3; i++)cin >> d[i];
if(d[d] && d[d[d]])cout << "YESn";
else cout<<"NOn";
}
return 0;
}
``````

### B. Also Try Minecraft

You are beta testing the new secret Terraria update. This update will add quests to the game!

Simply, the world map can be represented as an array of length nn, where the (i)-th column of the world has height (a_i).

There are mm quests you have to test. The (j)-th of them is represented by two integers (s_j) and (t_j). In this quest, you have to go from the column (s_j) to the column (t_j). At the start of the quest, you are appearing at the column (s_j).

In one move, you can go from the column (x) to the column (x−1) or to the column (x+1). In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height pp to the column with the height (q), then you get some amount of fall damage. If the height (p) is greater than the height (q), you get (p−q) fall damage, otherwise you fly up and get 00 damage.

For each of the given quests, determine the minimum amount of fall damage you can get during this quest

#### 读题

• be represented as 被表示为

#### 代码

``````#include <iostream>
using namespace std;
int a;
long long sum;
long long sum2;
int n,m;
void query(int from,int to){
if(from<=to)cout<<sum[to]-sum[from]<<endl;
else cout<<sum2[to]-sum2[from]<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1];
if(a[i]>a[i-1])continue;
if(i==1)continue;
sum[i]+=a[i-1]-a[i];
}
for(int i=n;i>=1;i--){
sum2[i]=sum2[i+1];
if(a[i]>a[i+1])continue;
if(i==n)continue;
sum2[i]+=a[i+1]-a[i];
}
int from,to;
while(m--){
cin>>from>>to;
query(from,to);
}
return 0;
}
``````

## 未过的题

### C. Recover an RBS

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

• bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
• bracket sequences ")(", "(" and ")" are not.

There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?

#### 他山之石

``````#include <iostream>
using namespace std;
string s;
void solve() {
cin >> s;
int wh = 0, cnt = 0;//问号
for (char c : s) {
if (c == '(')cnt++;
if (c == ')')cnt--;
if (c == '?')wh++;
if (cnt + wh == 1) {
cnt = 1;
wh = 0;
}
}
if (abs(cnt) == wh)cout<<"YESn";
else cout<<"NOn";
}
int main(){
int t;cin>>t;
while (t--) {
solve();
}
return 0;
}
``````

# 20220802

div3，比想象中惨烈。明天补题 