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

}