Codeforces Round #806 (Div. 4) A~G个人题解

A~C都比较简单，直接放代码啦
A. YES or YES?

 #include 
using namespace std;
typedef long long ll;
const int N = 3e5 + 7,null = 0x3f3f3f3f;
int t,fa[N],cnt[N],sz[N];

inline int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

bool check(string s)
{
    if(s.length() != 3) return false;
    if(s[0] != 'y' && s[0] != 'Y') return false;
    if(s[1] != 'e' && s[1] != 'E') return false;
    if(s[2] != 's' && s[2] != 'S') return false;
    return true;
}


int main()
{
    t = read();
    while(t --){
        string s;
        cin >> s;
        if(check(s)) cout << "YESn";
        else cout << "NOn";
    }
    return 0;
}

B. ICPC Balloons

 #include 
using namespace std;
typedef long long ll;
const int N = 3e5 + 7,null = 0x3f3f3f3f;
int t,fa[N],cnt[N],sz[N];

inline int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


int main()
{
    t = read();
    while(t --){
        int n = read(),a[30] = {0},ans = 0;
        string s;
        cin >> s;
        for(int i = 0;i < n;i ++){
            int pos = s[i] - 'A';
            a[pos] ++;
            if(a[pos] == 1) ans += 2;
            else ans += 1;
        }
        cout << ans << 'n';
    }
    return 0;
}

C. Cypher

 #include 
using namespace std;
typedef long long ll;
const int N = 3e5 + 7,null = 0x3f3f3f3f;
int t,a[110];

inline int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


int main()
{
    t = read();
    while(t --){
        int n = read();
        for(int i = 1;i <= n;i ++) a[i] = read();
        for(int i = 1;i <= n;i ++){
            int step = read(),D = 0,U = 0;
            char ch;
            for(int j = 0;j < step;j ++){
                cin >> ch;
                if(ch == 'U') U ++;
                else D ++;
            }
            a[i] = (a[i] + D - U + 10) % 10;
        }
        for(int i = 1;i <= n;i ++) cout << a[i] << ' ';
        cout << 'n';
    }
    return 0;
}

D. Double Strings

分析
题目所给的字符串长度最长是8，所以这道题只需将输入的n个字符串进行标记，然后遍历每一个字符串，截取字符串长度为j的前半部分以及后半部分，用map判断这两部分是否存在于这n个字符串当中即可，下面是我的代码

 #include 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 7,null = 0x3f3f3f3f;
int t;
string s[N];

inline int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solve()
{
    int n = read();
    map mp;
    for(int i = 1;i <= n;i ++){
        cin >> s[i];
        mp[s[i]] = 1;
    }
    for(int i = 1;i <= n;i ++){
        int ans = 0;
        for(int j = 0;j < s[i].length() - 1;j ++){
            string s1 = s[i].substr(0,j + 1);
            string s2 = s[i].substr(j + 1,s[i].length());
            //cout << s1 << ' ' << s2 << 'n';
            if(mp[s1] && mp[s2]){
                ans = 1;
                break;
            }
        }
        cout << ans;
    }
    cout << 'n';
}


int main()
{
    t = read();
    while(t --){
        solve();
    }
    return 0;
}

E. Mirror Grid
分析
题目要求将这个矩阵旋转0°，90°，180°，270°都能保持不变，那么这个矩阵在某种意义上一定是对称的。我们可以发现：
①将矩阵顺时针旋转90°后，位于(i,)上的a_ij位置变为(j,n - i + 1)；
②将矩阵顺时针旋转180°后，位于(i,)上的a_ij位置变为(n - j + 1,i)；
③将矩阵顺时针旋转270°后，位于(i,)上的a_ij位置变为(n - i + 1,n - j + 1)；
由此我们可以知道：这四个位置都必须是相等的，那么我们只需要枚举矩阵的左上角1 / 4来判断这四个位置是否全部相等，如果不是全部相等则需翻转其中一个或两个。特殊的是：对于n是奇数的矩阵，需要特别判断最中间的那一行或列。（其实说了这么多就是要让矩阵中心对称~）
下面是我的ac代码：

 #include 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 7,null = 0x3f3f3f3f;
int t;
char a[110][110];

inline int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solve()
{
    int n = read(),ans = 0;
    for(int i = 1;i <= n;i ++){
        cin >> a[i] + 1;
    }
    if(n == 1){
        cout << 0 << 'n';
        return ;
    }
    int m = n / 2;
    for(int i = 1;i <= m;i ++){
        for(int j = 1;j <= m;j ++){
            int sum0 = 0,sum1 = 0;
            if(a[i][j] == '0') sum0 ++;
            else sum1 ++;
            if(a[j][n - i + 1] == '0') sum0 ++;
            else sum1 ++;
            if(a[n - i + 1][n - j + 1] == '0') sum0 ++;
            else sum1 ++;
            if(a[n - j + 1][i] == '0') sum0 ++;
            else sum1 ++;
            ans += min(sum0,sum1);
            //cout << i << ' ' << j << 'n';
            //cout << "sum0 = " << sum0 << " sum1 = " << sum1 << 'n';
        }
    }
    //cout << "ans = " << ans << 'n';
    if(n & 1){
        for(int i = 1;i <= m;i ++){
            int sum0 = 0,sum1 = 0;
            int j = m + 1;
            if(a[i][j] == '0') sum0 ++;
            else sum1 ++;
            if(a[j][n - i + 1] == '0') sum0 ++;
            else sum1 ++;
            if(a[n - i + 1][n - j + 1] == '0') sum0 ++;
            else sum1 ++;
            if(a[n - j + 1][i] == '0') sum0 ++;
            else sum1 ++;
            ans += min(sum0,sum1);
        }
    }
    cout << ans << 'n';
}


int main()
{
    t = read();
    while(t --){
        solve();
    }
    return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality
分析
题目要求我们求满足 a_i < i < a_j < j的数对(i,j)有多少，首先我们需要知道哪些数是满足 a_i < i 的，统计在第i个数（包括第i个数）之前的所有满足这个要求的数的个数，然后，要满足 i < a_j，我们只需知道在第 a_j - 1个数之前满足a_i < i的数的个数即可。

 #include 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 7,null = 0x3f3f3f3f;
int t;
ll a[N];

inline ll read()
{
    char ch = getchar();
    ll x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solve()
{
    ll n = read(),cnt[N] = {0},ans = 0;
    for(int i = 1;i <= n;i ++){
        a[i] = read();
        cnt[i] = cnt[i - 1];
        if(a[i] < i){
            cnt[i] ++;
        }
    }
    for(int i = 1;i <= n;i ++){
        if(a[i] < i && a[i]){
            ans += cnt[a[i] - 1];
        }
    }
    cout << ans << 'n';
}


int main()
{
    t = read();
    while(t --){
        solve();
    }
    return 0;
}

G. Good Key, Bad Key

分析
其实这道题贪心做就可以了，一旦出现第一个用坏钥匙的箱子，那么后面所有的箱子都一定用坏钥匙。本题0 ≤ a_i ≤ 10⁹，所以除以超过32个2就一定变成了0，我们枚举前i个箱子用好钥匙，后面的箱子都用坏钥匙，第二重循环求后面的用坏钥匙的所有箱子能得到的硬币，虽然有两重循环，但是复杂度却不是O(n²)，而是O(n * 32)，所以不会超时。

 #include 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 7,null = 0x3f3f3f3f;
int t;
ll a[N];

inline ll read()
{
    char ch = getchar();
    ll x = 0,f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solve()
{
    ll n = read(),cnt[N] = {0},ans = 0;
    for(int i = 1;i <= n;i ++){
        a[i] = read();
        cnt[i] = cnt[i - 1];
        if(a[i] < i){
            cnt[i] ++;
        }
    }
    for(int i = 1;i <= n;i ++){
        if(a[i] < i && a[i]){
            ans += cnt[a[i] - 1];
        }
    }
    cout << ans << 'n';
}


int main()
{
    t = read();
    while(t --){
        solve();
    }
    return 0;
}

Codeforces Round #806 (Div. 4) A~G个人题解

C/C++/C#相关栏目本月热门文章