Educational Codeforces Round 161 (A,B,C)

发布时间:2024年01月23日

E d u c a t i o n a l C o d e f o r c e s R o u n d 161 ( R a t e d f o r D i v . 2 ) \Huge{Educational Codeforces Round 161 (Rated for Div. 2)} EducationalCodeforcesRound161(RatedforDiv.2)

题目地址:Educational Codeforces Round 161 (Rated for Div. 2)

Problems A. Tricky Template

思路

本题给出三个字符串 s t r 1 , s t r 2 , s t r 3 str1,str2,str3 str1,str2,str3,然后给出定义,只要有一对 ( s t r 1 [ i ] ! = s t r 3 [ i ] 、 s t r 2 [ i ] ! = s t r 3 [ i ] ) (str1[i]!=str3[i]、 str2[i] != str3[i]) (str1[i]!=str3[i]str2[i]!=str3[i])则符合要求,并输出 Y E S YES YES,否则输出 N O NO NO

标程

void Solved() {
    int n; cin >> n;
    string s1, s2, s3; cin >> s1 >> s2 >> s3;
    bool flag = false;
    for(int i = 0; i < n; i ++ ) {
        if(s1[i] != s3[i] && s2[i] != s3[i]) {
            flag = true; break;
        }
    }
    if(flag) cout << "YES\n";
    else cout << "NO\n";    
}

Problems B. Forming Triangles

思路

n n n个木棒,长度分别为 2 a i 2^{a_i} 2ai?,希望从中选出三根木棒拼成一个三角形,问有多少中拼法。

通过木棒长度长度分别为 2 a i 2^{a_i} 2ai?这个特殊的性质,我们可以比较明显的发现其中关于二进制的规律。

  1. 已知三角形任意两边之和大于第三边。
  2. 2 i ? 1 = 2 1 + 2 2 + . . . + 2 i ? 1 、 2 i = 2 i ? 1 + 2 i ? 1 2^i - 1=2^1+2^2+...+2^{i - 1}、2^i = 2^{i - 1} + 2^{i - 1} 2i?1=21+22+...+2i?12i=2i?1+2i?1,因此,若要用长度为 2 i 2^i 2i的木棒作为一条边,则分两种情况:
    • 以两条长度为 2 i 2^i 2i的木棒作为其余两条边。
    • 以一条长度为 2 i 2^i 2i的木棒作为第二条边,一条小于 2 i 2^i 2i的木棒作为第三条边。

因此结果为: r e s = ∑ i = 1 n C a [ i ] 2 + C a [ i ] 3 × m res=\sum_{i=1}^{n}C_{a[i]}^{2} + C_{a[i]}^{3} \times m res=i=1n?Ca[i]2?+Ca[i]3?×m m m m表示小于 2 i 2^i 2i的木棒个数。

标程

void Solved() {
    int n; cin >> n;
    vector<LL> a(n + 1);
 
    auto C2 = [&](int x) {return 1ll * x * (x - 1) / 2;};
    auto C3 = [&](int x) {return 1ll * x * (x - 1) * (x - 2) / 6;};
 
    for(int i = 1; i <= n; i ++ ) {
        int x; cin >> x;
        a[x] ++;
    }
    LL res = 0;
    int m = 0;
    for(int i = 0; i <= n; i ++ ) {
        res += C3(a[i]) + C2(a[i]) * m;
        m += a[i];
    }
    cout << res << endl;
}

Problems C. Closest Cities

思路

n n n个城市,编号分别为 1 ? n 1-n 1?n,然后给出相邻两个城市间的距离,如果城市 x x x到城市 y y y的距离最近,则能以代价 1 1 1到达 y y y,否则需要的代价是 x x x y y y的距离。并且最短距离对于两个城市来说是相互的。有若干查询,求从一个城市到另一个城市最少需要多少代价。

假设有三个城市 a , b , c a,b,c a,b,c

  1. 如果从 a b ab ab之间的距离小于 b c bc bc之间的距离,那么 b b b c c c需要花费代价为 c ? b c-b c?b
  2. 如果从 a b ab ab之间的距离大于 b c bc bc之间的距离,那么 b b b c c c需要花费代价为 1 1 1

因此我们分别从前向后和从后向前遍历两次数组,用前缀和记录代价。如果查询的时候是 a < b a<b a<b ,则按照从前向后遍历得到的数组求代价 ( b [ y ] ? b [ x ] ) (b[y] - b[x]) (b[y]?b[x])。否则按照从后向前遍历的数组求解。

标程

#define int long long
void Solved() {
    int n, m; cin >> n;
    vector<int> a(n), b(n), c(n);
 
    for(auto &i : a) cin >> i;
 
    b[0] = 0, b[1] = 1, c[n - 1] = 0, c[n - 2] = 1;
    for(int i = 2; i < n; i ++ ) {
        if(a[i - 1] - a[i - 2] > a[i] - a[i - 1])
            b[i] = b[i - 1] + 1;
        else
            b[i] = b[i - 1] + a[i] - a[i - 1];
    }
    for(int i = n - 3; i >= 0; i -- ) {
        if(abs(a[i + 1] - a[i + 2]) > abs(a[i] - a[i + 1]))
            c[i] = c[i + 1] + 1;
        else
            c[i] = c[i + 1] + abs(a[i] - a[i + 1]);
    }
 
    cin >> m;
    while(m -- ) {
        int x, y; cin >> x >> y;
        x --, y --;
        if(x < y) cout << b[y] - b[x] << endl;
        else cout << c[y] - c[x] << endl;
    }
}
文章来源:https://blog.csdn.net/weixin_73523694/article/details/135771190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。