首页 > 其他分享 >Codeforces Round 892 (Div. 2)(vp)

Codeforces Round 892 (Div. 2)(vp)

时间:2023-08-13 19:33:11浏览次数:44  
标签:892 int sum cin vp vector 数组 ans Div

Codeforces Round 892 (Div. 2)

A United We Stand

题意:给一个数组,让你把它分成两个数组,第二个数组里的数不能是第一个数组里的数的除数,先输出两个数组的长度,依次输出两个数组的数,如果无法分出来,输出-1

思路:如果数的种类只有一种一定不行,反之一定行,对于可行的情况,我们把最大的数放在第二部分,其他的数放在第一部分,一定满足条件

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for(auto &i : a)cin >> i, mp[i]++;
    sort(rALL(a));
    if(mp.size() == 1)cout << -1 << endl;
    else {
        cout << n - mp[a[0]] << ' ' << mp[a[0]] << endl;
        for(auto i : a)if(i != a[0])cout << i << ' ';
        cout << endl;
        for(auto i : a)if(i == a[0])cout << i << ' ';
        cout << endl;
    }
}

B Olya and Game with Arrays

题意:给一个类似二维数组,但是不规则,通过无限次操作使得每一行最小的数的和最大,操作:最多可以将一个(可能是 0 )整数从每个数组移动到另一个数组。需要注意的是,整数只能从一个数组中移动一次,但整数可以添加到一个数组中多次,而且所有移动都是同时完成的

思路:要是总和最大,尽可能是每一行的最小值最大,而所有数的最小一定固定占据一行,而每一个数最多移动一次,所以我们把每一行的最小的数移到一行,其他行的次小值就变成最小值,一定是最优的,总而言之就是所有数的最小值\(+\)每一行的次小值\(-\)每一行次小值的最小的那个就是答案

void solve() {
    int n;
    cin >> n;
    int mn = INT_MAX;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        vector<int> a(m);
        for(auto &j : a)cin >> j;
        sort(ALL(a));
        mn = min(mn, a[0]);
        ans.push_back(a[1]);
    }
    sort(rALL(ans));
    int sum = mn;
    for(int i = 0; i < n - 1; i++)sum += ans[i];
    cout << sum << endl;
}

C Another Permutation Problem

题意:找到一个\(n\)的排列\(p\),满足:\((\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)\)

思路:看见排列,我直接打表,打表的代码和图片如下,我们可以发现最优解的排列只是在\(n,n-1,n-2,n-3,\dots,1\)的基础上向右移动获得的,我们可以暴力的去枚举每一中情况,时间复杂度:\(O(n)\),而且此题数据范围只有250,妥妥的

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    int ans = 0;
    int mx = 0;
    for(int i = 0; i < n; i++) {
        sum = 0;
        mx = 0;
        for(int j = 1; j <= i; j++) {
            sum += j * j;
            mx = max(mx, j * j);
        }
        for(int j = i + 1, k = n; j <= n; j++, k--) {
            sum += k * j;
            mx = max(k * j, mx);
        }
        ans = max(ans, sum - mx);
    }
    cout << ans << endl;
}

打表的代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> ans;
    int an = 0;
    for (int i = 1; i <= n; i++)a[i] = i;
    do {
        int res = 0;
        int re = 0;
        for (int i = 1; i <= n; i++)res += a[i] * i, re = max(re, a[i] * i);
        if (an < res - re) {
            an = res - re;
            ans = a;
        }
    } while (next_permutation(a.begin() + 1, a.end()));
    cout << n << ' ' << an << endl;
    for (int i = 1; i <= n; i++)cout << ans[i] << ' ';
    cout << endl;
}
2 2
2 1
3 7
1 3 2
4 17
1 2 4 3
5 35
1 2 5 4 3
6 62
1 2 3 6 5 4
7 100
1 2 3 4 7 6 5
8 152
1 2 3 4 8 7 6 5
9 219
1 2 3 4 5 9 8 7 6
10 303
1 2 3 4 5 6 10 9 8 7
11 406
1 2 3 4 5 6 7 11 10 9 8

标签:892,int,sum,cin,vp,vector,数组,ans,Div
From: https://www.cnblogs.com/north-h/p/17627064.html

相关文章

  • Codeforces Round 892 (Div. 2)
    手速慢了,掉分C.AnotherPermutationProblemProblem-C-Codeforces题意给定一个正整数\(n\),设序列\(p\)为\(n\)的排列,求\(\sum_{i=1}^{n}p_i\timesi-max_{j=1}^np_j\timesj\)的最大值。思路打表可知,答案的排列一定为翻转一部分后缀。暴力枚举要翻转的后缀即可。代码......
  • Codeforces Round 892 div2.C
    这C真的魔幻,官方题解完全和写的不一样,太玄学了,打表发现的规律这是打表代码:intmain(){cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)a[i]=i;LLans=0;do{autob=a;LLsum=0,mx=0;......
  • Codeforces Round 892 (Div.2)
    A.UnitedWeStand题解赛时想复杂了题目要求我们保证数组\(c\)中的数不是数组\(b\)中任意一个数的因子我们考虑将最小值置于数组\(b\)即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intmi=INF;for(inti......
  • 【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    T1签到。T2送分题。T3大模拟,但是TLE两个点。#include<bits/stdc++.h>#definelllonglong#defineintlonglong#definereregisterusingnamespacestd;constintN=1e5+5,INF=0x3f3f3f3f;intn;queue<string>Q;map<string,int>zt;//0不在;1排队;2游玩;......
  • Codeforces Round 799 (Div. 4)(vp)
    CodeforcesRound799(Div.4)AMarathonvoidsolve(){vector<int>a(4);intgoal;cin>>goal;intans=0;for(inti=0;i<3;i++){intx;cin>>x;if(goal<x)ans++;}co......
  • Codeforces Round 874 (Div. 3) 题解
    A.MusicalPuzzle字符串\(s\)的不同的长度为\(2\)的子串个数就是答案可以用set处理B.RestoretheWeather将\(a\)数组排序后,在\(b\)数组中找到第一个大于等于\(a_i-k\)的元素与\(a_i\)对应即可可以用multiset实现(用multiset自带的lower_bound()比较好,......
  • Codeforces Round 878 (Div. 3) 题解
    A.CipherShifer从头开始扫一遍即可,扫到两个相同的表示某一个字符的解密结束B.BinaryCafe首先,我们不妨把题意转换为有多少种不同的花钱方案因为每一种咖啡就是一个二进制有\(k\)位的数字的其中一位,而对于不同的方案,其二进制位不完全相同,则每一个方案对应的花费一定不同,......
  • Docker使用WVP-Pro-GB28181网络视频平台
    1--Docker拉取镜像#镜像地址:docker镜像地址dockerpull648540858/wvp_prodockerrun--envWVP_IP="192.168.18.61"-it-p18080:18080-p30000-30500:30000-30500/udp-p30000-30500:30000-30500/tcp-p80:80-p5060:5060-p5060:5060/udp648540858/wvp_pro#利用i......
  • div左右两边50%拖拽功能
    <template><divid="app"><divclass="container"><divclass="left":style="{width:leftWidth+'%'}"><h1>LeftContent</h1></div><divclass="dragbar&q......
  • Codeforces Round 881 (Div. 3)
    A.SashaandArrayColoring为了让贡献最大,每种颜色只能染两个数显然这两个数为最大值与最小值、次大值与次小值、第三大值与第三小值……以此类推即可B.LongLong为了让和最大,我们需要的就是把所有负数变成正数那么第一问的答案就是\(\sum_{i=1}^n|a_i|\)此外,因为每次变......