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

Codeforces Round 961 (Div. 2)

时间:2024-07-24 14:41:52浏览次数:11  
标签:961 int res tt Codeforces cin ans fi Div

题目链接:Codeforces Round 961 (Div. 2)
总结:B1wa两发可惜,C出得有点小慢。

A. Diagonals

fag:贪心

Description:给定一个\(n * n\)的棋盘,给定\(k\)个棋子,每个格子只能放一个棋子,求将棋子全部放入棋盘,至少需要占几条对角线。

Solution:求最少占用,显然贪心处理,从最长的对角线开始占用,对角线长度为\(n, n - 1, n - 1, n - 2, n - 2, ..., 1, 1\)。

void solve(){
    cin >> n >> k;

    int res = 0;
    if (k == 0){
        cout << 0 << endl;
    }
    else{
        if (k <= n)
            cout << 1 << endl;
        else{
            res = 1;
            k -= n;
            for (int i = n - 1; i; i --){
                k -= i;
                res ++;
                if (k <= 0){
                    cout << res << endl;
                    return;
                }
                k -= i;
                res ++;
                if (k <= 0){
                    cout << res << endl;
                    return;
                }
            }
        }
    }
}

B1. Bouquet (Easy Version)

fag: 模拟

Description:有\(n\)种花,每种花只用一朵,每种花的花瓣为\(a_i\),售价也为\(a_i\)。你有\(m\)元钱,问你最多能够买到多少花瓣(任意两朵花的花瓣之差不能超过\(1\))。

Solution:easy版,解法很多。这里使用前缀和+二分。

  • 先按花瓣数从小到大排序。然后开始枚举,二分找到当前花瓣 + 1的最大下标\(t\);花费不超过\(k\)的最大下标\(tt\),取\(min(t, tt)\)。

Competing:第一发细节错误;第二发没考虑到花费不超过\(k\)的下标,认为满足花瓣数的都能买。

void solve(){
    cin >> n >> k;
    vector<int> a(n + 1);
    vector<int> s(n + 1);
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    for (int i = 1; i <= n; i ++){
        s[i] = s[i - 1] + a[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i ++){
        if (a[i] > k)
            continue;
        int t = upper_bound(a.begin() + 1, a.end(), a[i] + 1) - a.begin();
        int tt = upper_bound(s.begin() + 1, s.end(), s[i - 1] + k) - s.begin();
        if (tt <= t){
            res = max(res, s[tt - 1] - s[i - 1]);
        }
        else{
            res = max(res, s[t - 1] - s[i - 1]);
        }
    }

    cout << min(k, res) << endl;
}

B2. Bouquet (Hard Version)

fag:思维 + 贪心

Description:与easy的区别为,每种花有\(c_i\)朵。

Solution:考虑使用花瓣数为\(i\)和\(i +1\)的花,先尽可能使用买第一种花,剩下的买第二种花;然后尽可能使用第二种花替代第一种花即可。

Competing:应该是能想到的吧,毕竟只能买两种花

void solve(){
    cin >> n >> k;
    vector<pii> a(n);
    for (int i = 0; i < n; i ++)
        cin >> a[i].fi;
    for (int i = 0; i < n; i ++)
        cin >> a[i].se;
    
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < n; i ++){
        // 尽可能买第一种花
        int t = k / a[i].fi;
        t = min(t, a[i].se);
        ans = max(ans, t * a[i].fi);
        if (a[i].fi + 1 != a[i + 1].fi || i + 1 == n)
            continue;
        // 剩下的买第二种花
        int res = k - t * a[i].fi;
        int tt = res / a[i + 1].fi;
        tt = min(tt, a[i + 1].se);
        res = res - tt * a[i + 1].fi;
        ans = max(ans, k - res);

        if (t == 0)
            continue;
        
        // 还剩多少
        tt = a[i + 1].se - tt;
        ans = max(ans, k - res + max(0LL, min({res, tt, t})));
        if (ans == k){
            cout << ans << endl;
            return; 
        }
    }
    cout << ans << endl;
}

C. Squaring

fag:分析

Description:给定一个数组,可以执行任意次操作,每次操作将每个数变为它的平方,求该数组变为不递减数组的最小操作次数。

Solution:显然,我们直接从前往后操作即可,但是直接平方会导致数很大,从而爆longlong。

  • 那我们试试记录前面的数执行了多少次操作,根据开始两数之前的关系能否得出该数应该执行的操作次数。
  • 对两个数取对数,\(2^xa_{i} <= 2^ya_{i+ 1}\),我们发现两个数的操作次数\(x, y\)只与最开始的值有关。
  • 我们开始预处理:如果\(a[i] < a[i - 1]\),我们令\(b[i]\)为\(a[i] >= a[i - 1]\)的操作次数;如果\(a[i] == a[i - 1]\),令\(b[i] == 0\)。如果\(a[i] > a[i - 1]\),令\(b[i]\)等于负的\(a[i - 1]\)大于等于\(a[i]\)的操作次数,相当于可以少执行几次操作。但是我们要注意如果刚好可以令\(a[i] == a[i - 1]\),那么\(b[i]\)不变,否则\(b[i]\)需要加\(1\),因为此时\(a[i - 1] > a[i]\)了。
void solve(){
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }
    
    int ans = 0;
    for (int i = 1; i < n; i ++){
        if (a[i] < a[i - 1]){
            if (a[i] == 1){
                cout << -1 << endl;
                return;
            }
            else{
                int t = a[i];
                int c = 0;
                while (t < a[i - 1]){
                    t *= t;
                    c ++;
                }
                b[i] = c;
            }
        }
        else if (a[i] == a[i - 1]){
            b[i] = 0;
        }
        else{
            int t = a[i - 1];
            if (t == 1)
                continue;
            int c = 0;
            while (t < a[i]){
                t *= t;
                c ++;
            }
            if (t == a[i])
                b[i] = -c;
            else
                b[i] = -c + 1;
        }
    }
    for (int i = 1; i < n; i ++){
        b[i] += b[i - 1];
        if (b[i] < 0)
            b[i] = 0;
        ans += b[i];
    }
    cout << max(ans, 0LL) << endl;
}

标签:961,int,res,tt,Codeforces,cin,ans,fi,Div
From: https://www.cnblogs.com/Sakura17/p/18320848

相关文章

  • Codeforces Round 961 (Div. 2)
    题目链接:CodeforcesRound961(Div.2)总结:B1wa两发可惜,C出得有点小慢。A.Diagonalsfag:贪心Description:给定一个n∗nn*n......
  • Codeforces Round 961 (Div. 2)
    A#include<bits/stdc++.h>usingnamespacestd;inta[200];voidsolve(){intn,k;cin>>n>>k;a[1]=n;for(intj=n-1,i=2;i<=1+(n-1)*2;i+=2,j--){a[i]=a[i+1]=j;}if(!k){cout<<0<<"\n......
  • Codeforces Round 961 (Div. 2) 补题记录(A~D)
    上大分,赢!A考虑将每一条对角线上可以存放的砝码数量都记录一下,从大到小排序,然后直接暴力贪心选择。此时可以发现数量一定形如\(n,n-1,n-1,n-2,n-2,n-3,n-3,\ldots,1,1\)这样的形式。直接暴力减即可。时间复杂度为\(O(n)\)。#include<bits/stdc++.h>#defineintlonglong......
  • Codeforces 1987C
    codeforcesP1987C给定一个n长度的数组,每一步都要遍历整个数组。如果某个元素是末尾元素或是比其后一个元素大,则该元素减去1直到该元素为0,求解总步数,算法复杂度要求\(O(n)\)先给出暴力解法,复杂度\(O(n^2)\): intt=0; do{ for(inti=0;i<n-1;i++){ if(a[i]......
  • C. Divisor Chain
    原题链接题解任何数一定可以被二进制表示下最低位的一及以下的二次方数整除code#include<bits/stdc++.h>#definelllonglong#definelowbit(x)((x)&(-x))usingnamespacestd;voidsolve(){intn;cin>>n;intm=log2(n);intn1=1<<m;vector......
  • Codeforces Round 957 (Div. 3)复盘
    今天打了一下DIV3,专业转了就是不一样T1Onlypluses这道题主要就是理解乘法分配律,最多的绝对是两数相乘数最大的。T2AngryMonkey这道题一遍AC,虽然很简单还是值得鼓励,主要还是数学问题,用笔写下来找到数学规律之后做起来就很快T3GorillaandPermutation这道题还是很简单......
  • Codeforces Round 952 (Div. 4)复盘
    第一次打比赛的总结Q1CreatingWords这道题其实主要考的就是对于输入语句的理解,最开始我想的是运用scanf,puts,一个语句一个语句的去读取,但是确实对各个输入语句的了解过于肤浅了,特别是哪个读不读空格之类的,其实也算是没有把题目看清楚,它的难度其实没有自己以为的那么难,因为是限......
  • Codeforces 2400+ flows 大杂烩
    CF903GYetAnotherMaxflowProblem2700关键点:最大流转最小割显然我们需要用其他方式维护最大流,考虑到最大流等于最小割,于是我们去求最小割。考虑这个图的特性不难发现左边和右边两列都至多割掉一条边,于是我们直接枚举割掉的位置,剩下的左边前缀和右边后缀所有相连的边都要割......
  • Codeforces Round 960 (Div. 2)
    xht真的好强好强,好厉害这场打得有点史,共四发罚时还是抽象了,如果没有xht就真的完了呜呜。不过也说明我是真的菜,还有把做法想出来之后验证不到位。A.SubmissionBait罚时了,15min才过/lh稍微想一下可以知道,对于最大数\(x\),若其出现次数为奇数,那么A是必胜的,反之则只能从更小......
  • [Codeforces Round 960 (Div. 2)]A-E
    CodeforcesRound960(Div.2)A-EA题意:公平博弈。给定一个数组n个数,每个数只能用一次。给一个\(mx\)。每次轮到自己操作的时候就选一个数组里的数,满足\(a[i]>=mx\),然后令\(mx=a[i]\).双方轮流做直到一方无法操作,则另一方取胜。Sol:赛时1min猜了个错解,只看最大值,只看最大值的出......