提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

Codeforces Round #806 (Div. 4)(A~F)

div round Codeforces
2023-06-13 09:12:45 时间

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存储操作的偏移量
  • 若为U则flag --，反之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 ni,j对数

思想

  • 对于a_i \lt i\lt a_j<j,1\le i,j\le n
  • 枚举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;

}

相关文章