首页 > 其他分享 >Codeforces Round 983 Div2 A-C

Codeforces Round 983 Div2 A-C

时间:2024-11-02 16:47:37浏览次数:1  
标签:count br int 983 复杂度 Codeforces 数组 new Div2

目录


A - Circuit

题目概述

Alice 刚刚制作了一个包含 n 个灯和 2n 个开关的电路。每个组件(灯或开关)有两种状态:开或关。灯和开关的排列方式如下:

  • 每个灯连接 恰好两个开关
  • 每个开关连接 恰好一个灯。但并不知道每个开关连接到哪个灯。
  • 当所有开关都处于关闭状态时,所有灯也都处于关闭状态。
  • 如果一个开关被切换(从开到关,或从关到开),则它连接的灯的状态也会切换。

Alice 把电路带给她的姐姐 Iris,但只展示了这 2n 个开关的状态,并给了她一个谜题:在这种情况下,最多和最少可以点亮多少个灯?

Iris 非常了解妹妹的诡计,用不了一秒钟就给出了正确答案。你能做到吗?

解题思路

  1. 核心思路就是遍历一遍数组,记录一下打开的开关数量count
  2. 考虑最坏情况,最小亮灯个数,取决与打开开关的奇偶性
  3. 考虑最好情况,是count(2 * n - count)的最小值

代码实现

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
//        int t = 1;
        int t = Integer.parseInt(br.readLine());
        while (t-- != 0) {
            solve();
        }
    }

    public static void solve() throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n * 2];
        String[] input = br.readLine().split(" ");

        int count = 0;
        for (int i = 0; i < 2 * n; i++) {
            nums[i] = Integer.parseInt(input[i]);
            count += nums[i];
        }

        int max = Math.min(count, 2 * n - count);
        int min = count % 2;

        System.out.println(min + " " + max);
    }
}

复杂度分析

  • 时间复杂度O(n)
  • 空间复杂度O(n)

B - Medians

题目概述

你有一个数组 a = [1, 2, ..., n],其中 n 是奇数,并且有一个整数 k

你的任务是选择一个奇数 m 并将数组 a 分成 m 个子数组 b_1, b_2, ..., b_m,使得:

  • 数组 a 的每个元素都属于且仅属于一个子数组。
  • 对于所有 1 <= i <= m|b_i| 是奇数,即每个子数组的长度都是奇数。
  • median([median(b_1), median(b_2), ..., median(b_m)]) = k,也就是说,所有子数组的中位数的中位数必须等于 k。其中,median(c) 表示数组 c 的中位数。

一个长度为 n 的数组的子数组 a[l, r] 表示为 [a_l, a_{l+1}, ..., a_r],其中 1 <= l <= r <= n

长度为奇数的数组的中位数是将数组按非降序排序后中间的元素。例如:median([1, 2, 5, 4, 3]) = 3median([3, 2, 1]) = 2median([2, 1, 2, 2, 2]) = 2

解题思路

  1. 重点是nm都是奇数,这就避免了很多讨论,最直观的思路就是以k为分界线,左右两边均分为相同数量的组
  2. 首先对与n = 1n = 2的情况,我们可以特判,之后记录一下k左边的数字个数lefCount和右边的rightCount
  3. 当两者任意一个为0时,显然不合条件,直接返回-1,到此反例和特例就判断结束了
  4. 对于一般情况,由于n是奇数,去掉一个k后是偶数,那么leftCountrightCount一定是同奇偶性的
  5. 如果是奇数的话,可以将两边都分为min(leftCount, rightCount)
  6. 如果是偶数的话,一定可以分为两组,即1 + odd的形式

代码实现

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
//        int t = 1;
        int t = Integer.parseInt(br.readLine());
        while (t-- != 0) {
            solve();
        }
    }

    public static void solve() throws IOException {
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]), k = Integer.parseInt(nk[1]);

        if (n == 1) {
            System.out.println(1);
            System.out.println(1);
            return;
        } else if (n == 2) {
            System.out.println(-1);
            return;
        }
        int leftCount = k - 1, rightCount = n - k;
        if ((leftCount == 0 && (rightCount & 1) == 0) || rightCount == 0) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();
        int count = Math.min(leftCount, rightCount);
        if ((leftCount & 1) == 1) {
            System.out.println(count * 2 + 1);
            for (int i = 1; i <= count; i++) {
                sb.append(i).append(" ");
            }
            sb.append(k).append(" ");
            for (int i = 1; i <= count; i++) {
                sb.append(i + k).append(" ");
            }
        } else {
            count = 2;
            System.out.println(5);
            for (int i = 1; i <= count; i++) {
                sb.append(i).append(" ");
            }
            sb.append(k).append(" ");
            for (int i = 1; i <= count; i++) {
                sb.append(i + k).append(" ");
            }
        }
        System.out.println(sb);
    }
}

复杂度分析

  • 时间复杂度O(n)
  • 空间复杂度O(n)

C - Trinity

题目概述

给定一个包含 n 个元素的数组 a = [a_1, a_2, ..., a_n]

你可以进行任意次数(可以为 0)以下操作:

  • 选择两个索引 ij,其中 1 <= i, j <= n,然后将 a_i 赋值为 a_j

要求找到使数组 a 满足以下条件的最小操作次数:

  • 对于任意三个不同的索引 (x, y, z)1 <= x, y, z <= n, x ≠ y, y ≠ z, x ≠ z),满足不等式 a_x + a_y > a_za_y + a_z > a_xa_z + a_x > a_y

换句话说,任意三个元素的组合都能组成一个非退化三角形。

解题思路

  1. 先排序,问题转化为a1 + a2 > an,操作的上限是n - 2,因为我们可以将a1an之间所有的元素都变为an
  2. 考虑到与一般情况,则我们需要在数组中找到一对满足 ai + ai+1 > aj 条件的元素索引 (i, j),其中 i 在前,j 在后。这对 i, j 确保了最小和次小的元素之和大于数组的最大值。

代码实现

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
//        int t = 1;
        int t = Integer.parseInt(br.readLine());
        while (t-- != 0) {
            solve();
        }
    }

    public static void solve() throws IOException {
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        Long[] nums = new Long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Long.parseLong(input[i]);
        }

        Arrays.sort(nums);
        int left = 0, ans = n - 2;
        for (int i = 2; i < n; i++) {
            while (i - left >= 2 && nums[left] + nums[left + 1] <= nums[i]) {
                left++;
            }
            ans = Math.min(ans, n - (i - left + 1));
        }
        System.out.println(ans);
    }
}

复杂度分析

  • 时间复杂度O(nlogn)
  • 空间复杂度O(n)

D -

题目概述

解题思路

代码实现

复杂度分析

  • 时间复杂度
  • 空间复杂度

总结与思考

脑子卡了浆糊,c居然没写出来,掉打分~~~

标签:count,br,int,983,复杂度,Codeforces,数组,new,Div2
From: https://www.cnblogs.com/anyj1024/p/18522171

相关文章

  • Codeforces Round 983 (Div. 2)
    A最坏的情况就是所有开着的开关尽可能配对最好的情况就是所有开着的开关尽可能不配对#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<int,int>PII;constintN=1e6+10;constintmod=998244353;constintINF=0x3f3f3f3f;constllI......
  • Codeforces Round 983 div2 个人题解(A~D)
    CodeforcesRound983div2个人题解(A~D)Dashboard-CodeforcesRound983(Div.2)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\),定义数组的\(range\)是最大值减最小值,即极差。给出两个值\(a\)和\(b\),每步操作中,可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后(可以是\(0\)步),极差的最小值。思路(要直接看答案可以跳......
  • Codeforces Round 982 (Div. 2)解题报告
    CodeforcesRound982(Div.2)解题报告A显然答案不会小于\(2(\maxw+\maxh)\)。构造方案学习样例一,挺明显的。B有个小性质(好像没用):一旦能通过操作变成non-increasing,再对整个序列操作一次必然变为同一个数字。我们把一开始remove的数字记为A类,通过操作删掉的记为B类......
  • Educational Codeforces Round 20 E. Roma and Poker
    差分约束我们记W表示\(1\),L表示\(-1\),D表示\(0\),然后记前\(i\)位的前缀和是\(dis[i]\)。则我们可以根据题面得到如下约束。当前位是W,则有\[\left\{\begin{matrix}dis[i]-dis[i-1]\le1\\dis[i-1]-dis[i]\le-1\end{matrix}\right.\]当前位是L,则有\[\left\{\begin{m......
  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
    Preface这场其实是上周四VP的,因为当时马上要出发打济南站了,但因为挺久没写代码了所以打算临阵磨枪一下好家伙结果Div.2D不会做直接给人整麻了,不过好在看了眼榜把E2写了,后面发现这个D想到了就不难A.MeaningMean容易发现从小到大操作一定最优#include<cstdio>#inc......
  • Educational Codeforces Round 171 (Rated for Div. 2)B-D
    B.BlackCells题目:思路:首先我们发现要分奇偶讨论。偶数:很简单,取a[2]-a[1],a[4]-a[3],.........a[n]-[n-1]的最大值。奇数:我只需要知道假如删除当前的这个数剩下的数最大的间隔值,注意只能删除1,3,等奇数位,因为要保证删除后左右的数为偶数。(我的代码里面是偶数位因......
  • Codeforces Round 978(div.2) D1
    #感觉挺有意思的一道题题目:思路:观察发现对于两个人a,b如果两个人里面没有Impostor那么,你得到的回答是一样的,如果有impostor那么结果不同,那么我们就可以两个两个的询问,先找到2个人里面有impostor然后在找另外一个人来询问就行了。代码:#include<bits/stdc++.h>usin......
  • Codeforces Global Round 27,D. Yet Another Real Number Problem 题解
    单调栈+贪心题意:给定一个序列从左往右对于每个索引iii,求出其前缀的数组可以进行任意次以下操作的条件下:选择......
  • Codeforces Round 981 (Div. 3) ABCDE
    CodeforcesRound981(Div.3)ABCDEA.SakurakoandKosuke藕是看样例直接猜了结论......