Blog - Floating Ocean
0%

Codeforces - Round 850 Div 2

发表于 更新于
本文字数： 6.3k 阅读时长 ≈ 11 分钟
阅读次数： Valine：

Contestant. Rank 540. Rating +126.

代码略去了快读模板

A1. Non-alternating Deck (easy version)

题意

给定 个颜色相同的卡片，取卡片顺序为 ，每次取卡片的数量依次递增，当无法继续取的时候，按照正常顺序，下一个取卡片的人取完所有卡片。输出 各取了多少卡片。

思路

暴力模拟。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt() - 1;
            int w = 2;
            boolean who = false;
            int a = 1, b = 0, cnt = 0;
            while(n >= w){
                if(who) a += w;
                else b += w;
                n -= w;
                w ++;
                cnt ++;
                if(cnt == 2) {
                    who = !who;
                    cnt = 0;
                }
            }
            if(who) a += n;
            else b += n;
            console.print(a + " " + b + "\n");
        }
        console.close();
    }

}

快速打卡

A2. Alternating Deck (hard version)

题意

给定 个颜色相间的卡片，第一个为白色，取卡片顺序为 ，每次取卡片的数量依次递增，当无法继续取的时候，按照正常顺序，下一个取卡片的人取完所有卡片。输出 各取了多少白色卡片和多少黑色卡片。

思路

暴力模拟。

多加几个变量标记即可。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt() - 1;
            int w = 2;
            boolean who = false;
            int a1 = 1, b1 = 0, a2 = 0, b2 = 0, cnt = 0;
            while(n >= w){
                if(who) {
                    a1 += w / 2 + w % 2;
                    a2 += w / 2;
                }
                else {
                    b1 += w / 2;
                    b2 += w / 2 + w % 2;
                }
                n -= w;
                w ++;
                cnt ++;
                if(cnt == 2) {
                    who = !who;
                    cnt = 0;
                }
            }
            if(who) {
                a1 += n / 2 + n % 2;
                a2 += n / 2;
            }
            else {
                b1 += n / 2;
                b2 += n / 2 + n % 2;
            }
            console.print(a1 + " " + a2 + " " + b1 + " " + b2 + "\n");
        }
        console.close();
    }

}

依然是快速打卡

B. Cake Assembly Line

题意

给定 个蛋糕的中心点 以及 个巧克力酱的固定涂抹范围的中心点 ，蛋糕的大小为 ，巧克力酱的涂抹范围为 。所有蛋糕均在传送带上，且相对位置不变。输出是否可以移动传送带，让所有的巧克力酱都涂在蛋糕上。

思路

我们设 。

显然，我们不可能模拟移动，因为数据范围太大了。

考虑到每一个蛋糕都有对应的最小和最大移动距离，那么我们只需枚举所有蛋糕，更新最小移动距离的最大值和最大移动距离的最小值即可，这样操作之后， 内的所有移动距离都可以满足条件了。

我们以左边界为参考点，那么对于一个蛋糕，移动距离的最小值为 ，最大值为 。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt(), w = console.nextInt(), h = console.nextInt();
            long[] a = new long[n], b = new long[n];
            for(int i=0;i<n;i++) a[i] = console.nextInt();
            for(int i=0;i<n;i++) b[i] = console.nextInt();
            long min = Long.MIN_VALUE, max = Long.MAX_VALUE;
            for(int i=0;i<n;i++){
                long al = a[i] - w, ar = a[i] + w, bl = b[i] - h, br = b[i] + h;
                min = Math.max(min, br - ar);
                max = Math.min(max, bl - al);
            }
            console.println(min <= max ? "YES" : "NO");
        }
        console.close();
    }

}

只要一个参考点就够了

C. Monsters (easy version)

题意

给定一个序列 ，定义两种操作为：

  1. 选择任意一个非 数，将其减 ；
  2. 将整个序列所有非 数减 ，若减完后出现至少一个数为 ，那么本操作循环执行。

输出让整个序列为 的操作 的最小数量。

思路

显然，我们只需升序排序序列，然后构造一个不递减，相邻数之差 的序列即可。

如 ，将其构造为 。

答案即为原序列和该序列的差。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = console.nextInt();
            Arrays.sort(a);
            long cnt = 0, w = 0;
            for(int i=0;i<n;i++){
                if(a[i] != w){
                    w ++;
                    cnt += a[i] - w;
                }
            }
            console.println(cnt);
        }
        console.close();
    }

}

逾越丁真，鉴定为不开long long

D. Letter Exchange

题意

给定 个由 构成的长度为 的字符串，定义一次操作为指定两个人互换他们的任意一个字符。输出操作数的最小值以及对应的操作方案。

思路

思维+模拟。

首先，由于题给限制，方案一定是存在的，那么互换字符会出现两种可能：

  1. 缺了 ，但多了 ； 缺了 ，但多了 ；那么 交换一下；
  2. 缺了 ，但多了 ； 缺了 ，但多了 ； 缺了 ，但多了 ；那么三者互换一下。

对于上述操作，操作 的交换次数是 ，操作 的交换次数是 。

显然，若只执行上面的两个操作，只要不出现无意义操作，操作数一定是最小的。

那么，我们可以执行完所有操作 后再执行操作 ，因为配对是最容易的，而且配对结束后，剩下的字符一定是满足操作 的条件的。

那么我们可以用数组存储所有 多 少 的数量，然后略微暴力模拟一下即可。

时间复杂度：懒得分析

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            List<List<Integer>> a = new ArrayList<>();
            for(int i=0;i<6;i++) a.add(new ArrayList<>()); //0 wi, 1 wn, 2 iw, 3 in, 4 nw, 5 ni
            for(int i=1;i<=n;i++){
                String now = console.next();
                int[] cnt = new int[3];
                for(int j=0;j<3;j++){
                    char e = now.charAt(j);
                    if(e == 'w') cnt[0] ++;
                    else if(e == 'i') cnt[1] ++;
                    else cnt[2] ++;
                }
                if(cnt[0] == 1 && cnt[1] == 1 && cnt[2] == 1) continue;
                if(cnt[0] == 3) {
                    a.get(0).add(i);
                    a.get(1).add(i);
                }else if(cnt[1] == 3){
                    a.get(2).add(i);
                    a.get(3).add(i);
                }else if(cnt[2] == 3){
                    a.get(4).add(i);
                    a.get(5).add(i);
                }else if(cnt[0] == 2 && cnt[1] == 0){
                    a.get(0).add(i);
                }else if(cnt[0] == 2 && cnt[2] == 0){
                    a.get(1).add(i);
                }else if(cnt[1] == 2 && cnt[0] == 0){
                    a.get(2).add(i);
                }else if(cnt[1] == 2 && cnt[2] == 0){
                    a.get(3).add(i);
                }else if(cnt[2] == 2 && cnt[0] == 0){
                    a.get(4).add(i);
                }else if(cnt[2] == 2 && cnt[1] == 0){
                    a.get(5).add(i);
                }
            }
            int cnt = Math.min(a.get(0).size(), a.get(2).size()) + Math.min(a.get(1).size(), a.get(4).size()) + Math.min(a.get(3).size(), a.get(5).size());
            int left = Math.max(a.get(0).size(), a.get(2).size()) + Math.max(a.get(1).size(), a.get(4).size()) + Math.max(a.get(3).size(), a.get(5).size()) - cnt;
            cnt += left / 3 * 2;
            console.println(cnt);
            for(int i=0;i<Math.min(a.get(0).size(), a.get(2).size());i++){
                console.println(a.get(0).get(i) + " w " + a.get(2).get(i) + " i");
            }
            for(int i=0;i<Math.min(a.get(1).size(), a.get(4).size());i++){
                console.println(a.get(1).get(i) + " w " + a.get(4).get(i) + " n");
            }
            for(int i=0;i<Math.min(a.get(3).size(), a.get(5).size());i++){
                console.println(a.get(3).get(i) + " i " + a.get(5).get(i) + " n");
            }
            if(left > 0) {
                boolean b1 = a.get(0).size() > a.get(2).size(), b2 = a.get(1).size() > a.get(4).size(), b3 = a.get(3).size() > a.get(5).size();
                for (int i = 0; i < left / 3; i++) {
                    if(b1 && !b2 && b3){
                        console.println(a.get(0).get(a.get(2).size() + i) + " w " + a.get(3).get(a.get(5).size() + i) + " i");
                        console.println(a.get(4).get(a.get(1).size() + i) + " n " + a.get(3).get(a.get(5).size() + i) + " w");
                    }else{
                        console.println(a.get(2).get(a.get(0).size() + i) + " i " + a.get(1).get(a.get(4).size() + i) + " w");
                        console.println(a.get(5).get(a.get(3).size() + i) + " n " + a.get(1).get(a.get(4).size() + i) + " i");
                    }
                }
            }
        }
        console.close();
    }

}

依托答辩，但是Accepted.