首页 > 其他分享 >Codeforces Round #885 (Div. 2)

Codeforces Round #885 (Div. 2)

时间:2023-10-02 14:22:36浏览次数:50  
标签:cout 885 int nullptr Codeforces cin ++ Div define

赛时A题意理解错误,导致A调试半小时没出样例,直接提前下班-->https://codeforces.com/contest/1848

A. Jellyfish and Undertale

题意:初始时长为b的定时炸弹,没秒从n个工具中选一个加时长\(x_i\),每次加时不能超过a,并流失一秒。问:炸弹爆炸前的最长时间是多长?

思路:贪心枚举每个工具,每次加时min(a - 1, \(x_i\)),答案即为最后的b。

代码:

点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 2e5 + 10;

void solve()
{
    int a, b, c, x, mx = 0;
    cin >> a >> b >> c;
    for(int i = 0; i < c; i ++)
    {
        cin >> x;
        b += min(x, a - 1);
    }
    cout << b << '\n';
}

signed main()
{
    IOS; int _ = 1;
    cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

B. Jellyfish and Game

题意:A和B两人博弈K次,每次以最优方案交换两者中的任意苹果的值。问:最终A的苹果最大化总价值是多少?

思路:由于两者是最优的交换,奇偶性相同的交换,答案相等,故可模拟实现前两次交换;第一次若mina < maxb,交换;第二次maxa > minb,交换。

代码:

点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define i128 __int128

using namespace std;

const int N = 2e5 + 10;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k, k --;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < m; i ++) cin >> b[i];
    int x = 0, y = 0, ans = 0;
    for(int i = 1; i < n; i ++) if(a[i] < a[x]) x = i;
    for(int i = 1; i < m; i ++) if(b[i] > b[y]) y = i;
    if(a[x] < b[y]) swap(a[x], b[y]);
    if(k & 1)
    {
        x = y = 0;
        for(int i = 1; i < n; i ++) if(a[i] > a[x]) x = i;
        for(int i = 1; i < m; i ++) if(b[i] < b[y]) y = i;
        swap(a[x], b[y]);
    }
    for(int i = 0; i < n; i ++)
        ans += a[i];
    cout << ans << '\n';
}

signed main()
{
    IOS; int _ = 1;
    cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

C. Jellyfish and Green Apple

题意:有n个重量为1kg的苹果,将其均分给m个人,每次操作可以将某个苹果均分成两份。问:最少需要次操作才能使m个人分得的苹果重量相等?不能均分,输出-1。

思路1:先均分整1kg质量的苹果,\(n/m\)后由于均分,\(m/gcd(n,m)\)应为2的整数次幂,否则无解。

代码1:

点击查看代码1
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 2e5 + 10;

void solve()
{
    int n, m;
    cin >> n >> m;
    n %= m;
    int a = n / __gcd(n, m);
    int b = m / __gcd(n, m);
    // cout << __builtin_popcount(b) << ' ';
    if(__builtin_popcount(b) > 1) cout << "-1\n";
    else cout << __builtin_popcount(a) * m - n << '\n';
}

signed main()
{
    IOS; int _ = 1;
    cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

思路2:由于均分,可以枚举\(n*2^i\),累加n%m,当该值是m的整数倍时,和即为答案;当这个数非常大时,无解。

代码2:

点击查看代码2
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 2e5 + 10;

void solve()//模拟
{
    int n, m;
    cin >> n >> m;
    n %= m;
    int a = 1, ans = 0;
    while(a < 1e18)
    {
        if(n % m == 0)
        {
            cout << ans << '\n';
            return ;
        }
        n %= m;
        ans += n;
        n *= 2;
        a *= 2;
    }
    cout << "-1\n";
}

signed main()
{
    IOS; int _ = 1;
    cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

D. Jellyfish and Mex

题意:有n个自然数,最初的总价值为0,每次操作会删除任一个\(x_i\),后总价值加上MEX(x)。问:操作n次后的总价值最小是多少?

思路:由于有MEX的存在,该次操作依赖于上一次操作的结果,考虑线性dp,操作次数为n,可以记录下\(x_i\)<n出现的次数,然后找到没有出现过的最小的自然数mn,再求前i项的每项的最小总价值,转移方程:f[i]=min(f[i],f[j]+x[i]*j),答案为:f[0]-mn。

代码:

点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n, x, ma = 0, ans = 0;
    cin >> n;
    vector<int> a(n + 1, 0), res(n + 1, inf);
    for(int i = 1; i <= n; i ++)
    {
        cin >> x;
        a[min(x, n)] ++;
    }
    while(a[ma]) ma ++; res[ma] = 0;
    for(int i = ma - 1; i >= 0; i --)
        for(int j = i + 1; j <= ma; j ++)
            res[i] = min(res[i], res[j] + a[i] * j);
    cout << res[0] - ma << '\n';
}

signed main()
{
    IOS; int _ = 1;
    cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

标签:cout,885,int,nullptr,Codeforces,cin,++,Div,define
From: https://www.cnblogs.com/chfychin/p/17739911.html

相关文章

  • Codeforces 1765H 题解
    题目大意题目大意给定一个\(n\)个点和\(m\)条边的有向图,并给定\(p_1,p_2,\cdots,p_n\)表示第\(i\)个点的拓扑序必须小于等于\(p_i\),求出每个点的最小拓扑序。题解题解题目要求拓扑序尽量小,转换一下就是在反图上拓扑序尽量大。考虑拓扑排序,当一个点不得不入队......
  • div 让a内容居中方法
    <div>标签是HTML中的一个重要标签,它代表了一个文档中的一个分割区块或一个部分。在<div>标签中,我们可以放置各种内容,包括文本、图像、链接等等。有时候,我们需要将其中的链接<a>标签的内容水平居中显示,这就需要使用CSS设置div内部链接的居中显示。本文将详细讲解如何使用CSS使得<di......
  • Codeforces Round 901 (Div
    C.JellyfishandGreenApple题解显然\(n\%m=0\),答案一定为\(0\)如果\(n>m\),我们显然可以将\(n/m\)的苹果分给每个人,然后再处理$n%m$如果\(n<m\),我们一定会将所有苹果一直对半切直到\(n>m\),所以答案每次对半切一定会加\(n\)直到\(n\%m=0\)的时......
  • Codeforces Round 895 (Div. 3)
    A题简单的模拟计算,注意上取整的实现。B题计算每个房间对应的每个最迟时间点,在这些时间点最取最小值,保证能安全通过所有房间。D题拿到手就可以发现是贪心,但发现两部分会有冲突,也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数,为其他参与计算的数安排剩余数种的最......
  • Codeforces 1278D 题解
    题目大意题目大意给你\(n\)(\(1\leqslantn\leqslant5\cdot10^5\))条线段\([l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\)(\(1\lel_i<r_i\le2n\))。保证每条线段的端点为整数,且\(\foralli,j\)(\(i\nej\)),不存在\(l_i=l_j\)或\(r_i=r_j\),不存......
  • Codeforces Round 811 (Div. 3)
    A.EveryoneLovestoSleep#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,h,m,t;cin>>n>>h>>m;t=h*60+m;vector<int>a;for(inti=1,x,y;i<=n;i++)cin......
  • Codeforces 1702G2 题解
    题目大意给出一个大小为\(n\)的树,\(q\)次询问,每次给出一个大小为\(m\)的点集,判断是否有一条链覆盖这些点(这条链可以经过其他点)。\(n,\summ\leqslant2\cdot10^5\),\(q\leqslant10^5\)。提示提示1思考将$m$个点按深度排序。题解题解考虑将\(m\)个点按树......
  • CodeForces 1874B Jellyfish and Math
    洛谷传送门CF传送门看到这种操作乱七八糟不能直接算的题,可以考虑最短路。对于\(a,b,c,d,m\)按位考虑,发现相同的\((a,b,m)\)无论如何操作必然还是相同的。于是考虑对于每个可能的\((0/1,0/1,0/1)\),所有终态有\((c=0/1,d=0/1)\)或者不确定。这样我们对于一......
  • 「题解」Codeforces Round 895 (Div. 3)
    A.TwoVesselsProblem题目Sol&Code签到题#include<bits/stdc++.h>typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT,a,b,c;intmain(){scanf("%d"......
  • AT_abc254_h [ABC254Ex] Multiply or Divide by 2 题解
    打篇题解巩固一下。题意给你两个集合\(A\)和\(B\),对于任意\(A\)集合中的元素,我们可以进行\(2\)种操作:\(a_i\gets\left\lfloor\frac{a_i}{2}\right\rfloor\)或\(a_i\gets2\timesa_i\)。问最少要多少次才能使\(A\)和\(B\)中的元素相等。分析首先我们可以令\(a......