Codeforces Round #806 (Div. 4)(A~F)
本文最后更新于 719 天前,其中的信息可能已经有所发展或是发生改变。

A. YES or YES?


题目大意

Origional Link

  • 判断是否是yes顺序的不区分大小写的字符串
  • 是则输出YES,否则输出NO

思想

  • 读入暴力判断

代码

#include <bits/stdc++.h>
using namespace std;

void solve(){

    string s;

    cin >> s;

    bool flag = 1;

    if(s[0] != 'y' && s[0] != 'Y') flag = 0;
    if(s[1] != 'e' && s[1] != 'E') flag = 0;
    if(s[2] != 's' && s[2] != 'S') flag = 0;

    if(s.size() == 3 && flag) cout << "YES" << endl;
    else cout << "NO" << endl;

}

int main(){

    int _;
    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

B. ICPC Balloons


题目大意

Origional Link

  • 共$A \sim Z$道题,第一次出现送出两个气球,后续出现送出一个气球
  • 求比赛共送出多少气球

思想

  • vis[i]标记是否出现过
  • 未出现的送出两个,出现过送出一个
  • 遍历字符串求和

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

typedef long long LL;

bool vis[N];

void solve(){

    memset(vis,0,sizeof vis);

    int n;

    cin >> n;

    LL cnt = 0;

    while(n--){

        char a;
        cin >> a;

        if(!vis[a]){
            cnt += 2;
            vis[a] = 1;
        }
        else cnt ++;

    }

    cout << cnt << endl;

}

int main(){

    int _;
    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

C. Cypher


题目大意

Origional Link

  • 每个密码锁有$n$个轮子,轮子上有$0\sim 9$
  • 给出最终位置显示的数字$a_i$,和第$i$个位置的$b_i$次操作
  • 求原始的数字

思想

  • 模拟
  • ans[i]存储第$i$位的最终数字,用flag存储操作的偏移量
  • 若为Uflag --,反之flag ++
  • 对于ans[i],加上其偏移量并取正整数模,即ans[i] = ( ans[i] + flag % 10 + 10 ) % 10即为原始数字

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n;

int ans[N];

void solve(){

    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> ans[i];

    for(int i = 1; i <= n; i ++){

        int m;
        cin >> m;

        int flag = 0;

        while(m--){
            char op;
            cin >> op;
            if(op == 'D') flag ++;
            else flag --;
        }

        ans[i] = (ans[i] + flag % 10 + 10) % 10;

    }

    for(int i = 1; i <= n; i ++) cout << ans[i] << " ";

    cout << endl;

}

int main(){

    int _;
    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

D. Double Strings


题目大意

Origional Link

  • 给定$n$个长度不超过$8$的字符串$s$
  • 若对于$s_i = s_j + s_k$成立,则$s_i$标记为$1$,否则标记为$0$

思想

  • $n$比较大,但$s_i$较短
  • 对于$s_i$,每次构造两个$s_i$的字串$s_i',s_i''$,对字串进行查询
  • 若两个字串都可以找到,则标记$s_i$为$1$,反之为$0$
  • 利用s[N]set<string> st同时存储所有的s[i]
  • 遍历s[i],第一个字串从s[0]开始,长度为1 <= j <= s[i].size() - 1 ,第二个字串从s[j]开始,长度为s[i].size() - j
  • 利用st.count(s)查询字串s

代码

#include <bits/stdc++.h>
using namespace std;

void solve(){

    int n;

    cin >> n;

    bool vis[n + 10];

    memset(vis,0,sizeof vis);

    set<string> st;

    string s[n + 1];

    for(int i = 0; i < n; i ++){
        cin >> s[i];
        st.insert(s[i]);
    }

    for(int i = 0; i < n; i ++){
        if(s[i].size() == 1) continue;
        for(int j = 1; j <= s[i].size() - 1; j ++){
            string s1 = s[i].substr(0,j), s2 = s[i].substr(j,s[i].size() - j);
            if(st.count(s1) == 1 && st.count(s2) == 1){
                vis[i] = 1;
                break;  
            }
        }
    }

    for(int i = 0; i < n; i ++){
        if(vis[i]) cout << 1;
        else cout << 0;
    }

    cout << endl;

}

int main(){

    int _;
    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

E. Mirror Grid


题目大意

Origional Link

  • 给定由$0$和$1$构成正方形数组
  • 将数组向右选择90度,180度,270度
  • 求如何改变原数组中的值,使得四种形态的数组里的值都一样的改变最少操作次数

思想

  • 原二维数组中的一个位置mp[i][j]旋转三次后,总共会出现在三个位置上
  • mp[j][n + 1 - i]mp[n + 1 - i][n + 1 - j]mp[n + 1 - j][i]
  • 统计原位置的值和这三个新位置的值变为相同的最小操作次数即可

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

char mp[N][N];

bool st[N][N];

void solve()
{
    int n;
    cin >> n;

    memset(st, 0, sizeof st);

    for (int i = 1; i <= n; i++) cin >> mp[i] + 1;

    int ans = 0;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if(i == j && n % 2 == 1) continue;

            if(!st[i][j]){
                int cnt = 0;
                if(mp[i][j] == '1') cnt++;

                st[i][j] = 1;
                if(mp[j][n - i + 1] == '1') cnt++;

                st[j][n - i + 1] = 1;
                if(mp[n - i + 1][n - j + 1] == '1') cnt++;

                st[n - i + 1][n - j + 1] = 1;
                if(mp[n - j + 1][i] == '1') cnt++;

                st[n - j + 1][i] = 1;

                ans += min(cnt, 4 - cnt);
            }
        }
    }

    cout << ans << endl;

}

int main(){

    int _;
    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

F. Yet Another Problem About Pairs Satisfying an Inequality


题目大意

Origional Link

  • 对于数列$a$,找到满足$a_i \lt i\lt a_j<j,1\le i,j\le n$的$i,j$对数

思想

  • 对于$a_i \lt i\lt a_j<j,1\le i,j\le n$
    • 一定满足a[i] < i,将a[i] >= i的删去,不参与后续匹配
    • 一定满足i < a[j]{i,j}的对数为i之前的满足a[i] < i的数量
  • 枚举j,二分查找最小满足i < a[j]的位置,总数量加上i之前的所有满足a[i] < i的数量

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;

int a[N];

typedef long long LL;

LL cnt;

vector<int> st;

void solve(){
    int n;
    cin >> n;

    st.clear();
    cnt = 0;

    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++){
        if (a[i] >= i) continue;
        cnt += (lower_bound(st.begin(), st.end(), a[i]) - st.begin());
        st.push_back(i);
    }

    cout << cnt << endl;
}

int main(){

    int _;

    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇