• 欢迎光临~

算法比赛小记

开发技术 开发技术 2022-08-01 次浏览

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.获得;(尤指经努力)赢得;存在;流行;沿袭

复现

第一次写英语题,读题读得颇为心急,还好读完就能做。

感觉条件很宽裕,门的数目也限制为3就不需要写搜索,我就直接两次判断整模拟了hhh,非常不优雅

代码

#include <iostream>
using namespace std;
int door[4];
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[4];
int main(){
    int t;cin>>t;
    while (t--) {
        for (int i = 0; i <= 3; i++)cin >> d[i];
        if(d[d[0]] && d[d[d[0]]])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 被表示为
  • infinite adj.极大的;无法衡量的;无限的;无穷尽的 n.无限的事物;无穷尽的事物;上帝

复现

一眼前后缀,调试了几下就过了。

代码

#include <iostream>
using namespace std;
int a[100010];
long long sum[100010];
long long sum2[100010];
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?

他山之石

援引自https://zhuanlan.zhihu.com/p/544714145,作者严格鸽

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

令人惊叹的cnt + wh == 1判断。当时也想到了计数,但始终处理不好问号与括号的匹配。

20220802

div3,比想象中惨烈。明天补题
算法比赛小记

程序员灯塔
转载请注明原文链接:算法比赛小记
喜欢 (0)