Codeforces Round #553 (Div. 2)

た入场券 2021-11-04 13:36 260阅读 0赞

A：[http://codeforces.com/contest/1151/problem/A][http_codeforces.com_contest_1151_problem_A]

题意：给定一个字符串，输出字符串中连续的四位转换成“ACTG”的最小操作次数。

思路：分别枚举一个字符到ACTG的所有长度，使用最小的长度，for一遍比较即可。一开始认为只有2种长度，后面才意识到是3种。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int INF = 0x3f3f3f3f;
    int getA(char c)
    {
        return min(min(abs(c - 'A'),abs(c - 'A' + 26)), abs(c - 'A' - 26));
    }
    int getC(char c)
    {
        return min(min(abs(c - 'C'),abs(c - 'C' + 26 )),abs(c - 'C' - 26));
    }
    int getT(char c)
    {
        return min(min(abs(c - 'T'),abs(c - 'T' + 26)),abs(c - 'T' - 26));
    }
    int getG(char c)
    {
        return min(min(abs(c - 'G'),abs(c - 'G' + 26)),abs(c - 'G' - 26));
    }
    int main()
    {
        std::ios::sync_with_stdio(false);
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = INF;
        for(int i = 0;i <= n - 4;i++)
        {
            ans = min(ans,getA(s[i]) + getC(s[i + 1]) + getT(s[i + 2]) + getG(s[i + 3]));
        }
        cout << ans << endl;
        return 0;
    }

B：[http://codeforces.com/contest/1151/problem/B][http_codeforces.com_contest_1151_problem_B]

题意：在每行选一个数使得选出的n个数异或后大于0。

思路：这题我也是蠢了被这个异或吓到了， 其实只要把每行第一个异或起来 如果不等于0，就直接输出，等于0就枚举每行其他和第一个不一样的数就好。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 550;
    int a[maxn][maxn];
    int n, m;
     
    int main()
    {
        std::ios::sync_with_stdio(false);
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)   cin >> a[i][j];
        int ans = 0;
        for(int i = 1;i <= n;i++)   ans ^= a[i][1];
        if(ans)
        {
            cout << "TAK" << endl;
            for(int i = 1;i <= n;i++) cout << 1 << " ";
            cout << endl;
        }
        else
        {
            int x = -1;
            int t= 0;
            for(int i = 1;i <= n;i++)
            {
                bool flag = false;
                for(int j = 2; j <= m;j++)
                {
                    if(a[i][j] != a[i][1])
                    {
                        x = i,t = j; flag = true; break;
                    }
                }
                if(flag) break;
            }
            if(x == -1) cout << "NIE" << endl;
            else{
               cout << "TAK" << endl;
               for(int i = 1;i <= n;i++)
               {
                   if(i == x) cout << t << " ";
                   else cout << 1 << " ";
               }
               cout << endl;
            }
        }
     
        return 0;
    }

C:[http://codeforces.com/contest/1151/problem/C][http_codeforces.com_contest_1151_problem_C]

题意：给你两个数组，一个只有奇数（1，3，5……），一个只有偶数（2，4，6……），让你合并为一个数组（第一次从奇数组拿一个过来即为1；第二次从偶数组拿两个数进来即为2，4；第三次从奇数组拿四个数进来，即为3，5，7，9，类似后推。）

思路：分区间统计，然后等差数列求和，可以求出1-R的sum，然后前缀和思想一减，就是ans。（这题让我体会到取模的细节orz）

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod = 1e9 + 7;
    ll sum(ll x)
    {
        ll cnt[2] = {
        0,0};
        int k = 0;
        ll len = 1;
        while(x)
        {
            cnt[k] += min(len,x);
     
            x -= min(len,x);
     
            k ^= 1;
            len *= 2;
        }
        ll ans = (cnt[0]%mod)*(cnt[0]%mod)%mod;
        ans += (cnt[1]%mod)*((cnt[1]+1)%mod)%mod;
        return ans%mod;
    }
    int main()
    {
        ll l,r;
        cin >> l >> r;
        cout << (sum(r)%mod-sum(l-1)%mod + mod)%mod;
        return 0;
    }

D：D. Stas and the Queue at the Buffet

题意：n个学生，每个学生都有自己的位置，最后要使 ai\*(j - 1) + bi \*( n - j) 最小。

思路：公式变形得 ：(ai − bi)\* j \+ ( −ai \+ bi⋅n) ，那么按 （ai - bi） 排序即可。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 +10;
    struct stu{
        ll a, b;
    };
    stu v[maxn];
    bool cmp(const stu a,const stu b)
    {
        return (a.a - a.b) > (b.a - b.b);
    }
    int main()
    {
        int n;
        cin >> n;
        for(int i = 0;i < n;i ++)
        {
            cin  >> v[i].a >> v[i].b;
        }
        sort(v, v + n, cmp);
        ll sum = 0;
        for(int i = 0;i < n;i++)
        {
            sum += v[i].a * i + v[i].b*(n-i-1);
        }
        cout << sum <<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Carered/p/11312826.html

[http_codeforces.com_contest_1151_problem_A]: http://codeforces.com/contest/1151/problem/A
[http_codeforces.com_contest_1151_problem_B]: http://codeforces.com/contest/1151/problem/B
[http_codeforces.com_contest_1151_problem_C]: http://codeforces.com/contest/1151/problem/C