Codeforces Round 920 (Div. 3)(A-E)

发布时间:2024年01月17日

C o d e f o r c e s R o u n d 920 ( D i v . 3 ) \Huge{Codeforces Round 920 (Div. 3)} CodeforcesRound920(Div.3)

题目地址:https://codeforces.com/contest/1921

Problems A. Square

思路

题目给出了正方形各点的坐标,因此我们只需知道一条边的长度,就能求出正方形的面积。无论横纵坐标,都会有两个相等,两个不等,找出不相等的计算出距离,即为结果。

标程

void Solved() {
    vector<int> a(4), b(4);
 
    for(int i = 0; i < 4; i ++ ) {
        cin >> a[i] >> b[i];
    }
    int res = 0;
    if(a[0] != a[1]) res = abs(a[0] - a[1]);
    else res = abs(a[0] - a[2]);
 
    cout << res * res << endl;   
}

Problems B. Arranging Cats

思路

给定两个01字符串,并给出三种操作。求把第二种变为第一种需要的最少操作次数。

  1. 将0变为1。
  2. 将1变为0。
  3. 将一对10互换。

遍历一遍两个字符串,统计出不同的个数,一次操作1和一次操作2可以用操作3代替,所以结果即为 x 1 + x 2 ? M i n ( x 1 , x 2 ) x1+x2-Min(x1, x2) x1+x2?Min(x1,x2)

标程

void Solved() {
    int n; cin >> n;
    string s1, s2; cin >> s1 >> s2;
    int x1 = 0, x2 = 0;
 
    for(int i = 0; i < n; i ++ ) {
        if(s1[i] != s2[i]) {
            if(s1[i] == '1') x1 ++;
            else x2 ++;
        }
    }
    cout << x1 + x2 - min(x1, x2) << endl;
}

Problems C. Sending Messages

思路

题目给出需要发送信息的时刻,在该时刻手机需要开机才能发消息,然后题目给出 n , f , a , b n,f,a,b n,f,a,b,分别代表消息数量、手机电量、每单位手机开机的耗电量、手机关机再开机的耗电量,要求判断手机的电量是否支持发送完全部消息。

按照常规思路,当手机长时间不使用时应该关闭,这样会更加省电,因此我们判断在发送两个消息间隔期间是否需要关闭手机。遍历一遍发送信息的时刻即可。

标程

#define int long long 
void Solved() {
    int n, f, a, b; cin >> n >> f >> a >> b;
    vector<int> x(n + 1);
 
    for(int i = 1; i <= n; i ++ ) cin >> x[i];
    int res = 0;
    for(int i = 1; i <= n; i ++ ) {
        res += min((x[i] - x[i - 1]) * a, b);
    }
 
    if(res >= f) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Problems D. Very Different Array

思路

有一个长度为 n n n的数组 a a a,和一个长度为 m m m的数组 b , ( m ≥ n ) b,(m \ge n) b,(mn),要求从数组 b b b中选出 n n n个数字,使得 D = ∑ i = 1 n ∣ a i ? c i ∣ D = \sum_{i=1}^{n} |a_i - c_i| D=i=1n?ai??ci?尽可能大,并输出最大差异 D D D

  1. 容易发现,数组 a a a中最小元素一定与数组 b b b中的最小元素或者最大元素的差最大。
  2. 同理,数组 a a a中的其他元素也是,那么我们对于数组 b b b的每一次选择都是选择其第一个或是最后一个。
  3. 对于需要数组首个或最后一个元素,我们可以使用双端队列来存放数组 a , b a,b a,b
  4. 然后我们遍历数组 a a a,每次计算数组 a a a的最后一个和数组 b b b的第一个、数组 b b b的最后一个和数组 a a a的第一个。判断哪组差值大,就将哪组去掉。

标程

#define int long long 
void Solved() {
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    deque<int> s, d;
    
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;
    
    sort(ALL(a)); sort(ALL(b)); 
    for(int i = 0; i < n; i ++ ) s.push_back(a[i]);
    for(int i = 0; i < m; i ++ ) d.push_back(b[i]);
    
    int res = 0;
    for(int i = 0; i < n; i ++ ) {
        int res1 = abs(s.front() - d.back());
        int res2 = abs(s.back() - d.front());
        if(res1 >= res2) {
            s.pop_front();
            d.pop_back();
        } else {
            d.pop_front();
            s.pop_back();
        }
        res += max(res1, res2);
    }
    cout << res << endl;
}

Problems E. Eat the Chip

思路

给定一个 h × w h \times w h×w的方阵,然后给出Alice和Bob的坐标,Alice每次只能移动到下面三个格子中,Bob每次只能移动到上面三个格子中,如果谁先抓住另一个人,则其获胜。

  1. 很明显,这是一道博弈问题,Alice先手,我们考虑Alice获胜的条件。
  2. 如果只考虑行,那么Alice每次都会向上移动,Bob每次都会向下移动。Alice先手,则行差为奇数时Alice有可能赢
  3. 当Alice获胜时:
    • Alice的移动次数比Bob多一,所以两人列数差距小于2时,Alice可能赢。
    • 两人列差大于1时:
      • Bob必然选择远离Alice。
      • 但由于墙壁的限制,如果Alice可以到达墙壁,则仍能抓到Bob。
      • 否则平局。
  4. 如果列坐标差大于横坐标差,则Alice和Bob无法碰面,平局。

标程

void Solved() {
    int h, w, x1, x2, y1, y2; cin >> h >> w >> x1 >> y1 >> x2 >> y2;

    if(abs(y1 - y2) > x2 - x1) {
        cout << "Draw" << endl;
    } else if((x2 - x1) & 1) {
        int step = (x2 - x1 + 1) >> 1;
        if(abs(y1 - y2) <= 1 || (y1 < y2 ? w - y1 : y1 - 1) <= step)
            cout << "Alice" << endl;
        else
            cout << "Draw" << endl;
    } else {
        int step = (x2 - x1) >> 1;
        if(y1 == y2 || (y1 < y2 ? y2 - 1 : w - y2) <= step)
            cout << "Bob" << endl;
        else
            cout << "Draw" << endl;
    }
}
文章来源:https://blog.csdn.net/weixin_73523694/article/details/135648791
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。