首页 > 其他分享 >Codeforces Round 905 (Div. 3) ABCDEG1

Codeforces Round 905 (Div. 3) ABCDEG1

时间:2023-11-21 19:35:26浏览次数:36  
标签:cout 905 int ll cin long Codeforces ans Div

Codeforces Round 905 (Div. 3)ABCDEG1

A. Morning

思路:签到,直接模拟。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        string s; cin>>s;
        int cnt = 0;
        int now = 1;
        for(int i = 0; i < 4; i++)
        {
            int t = s[i]-'0';
            if(t==0)t = 10;
            cnt += abs(now-t);
            cnt++;
            now = s[i]-'0';
            if(now==0)now = 10;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

B. Chemistry

题意:问你能否删掉一些字母之后重排是回文串,且满足删的次数\(\le k\)。

思路:要符合回文串,那么最多只能有一个奇数。那么我们统计奇数的个数-1和k的大小比较即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        map<char,int>mp;
        int n,k; cin>>n>>k;
        string s; cin>>s;
        s = "?"+s;
        for(int i = 1;i <= n; i++)
            mp[s[i]-'a']++;
        vector<int>v;
        for(int i = 0;i < 26; i++)
        {
            if(mp[i]%2)
                v.push_back(mp[i]);
        }
        if(v.size()<=1)
            cout<<"Yes\n";
        else
        {
            int sz = v.size();
            if(sz-1<=k)
                cout<<"Yes\n";
            else cout<<"No\n";
        }
    }


    return 0;
}

C. Raspberries

题意:给你一个数组\(a_1,a_2,...,a_n\)。在一次操作里面,你可以选择一个元素让它\(+1\)。找到最小的操作次数使得\(a_1a_2a_3...a_n\)能被\(k\)整除。

思路:这里的突破口是\(k\)和\(a_i\)的范围。其中\(k = 2,3,4,5\),\(1\le a_i\le 10\)

我们发现\(2,3,5\)都是素数,我们只需要考虑哪一个\(a_i\)能最快变成他们的倍数即可。

对于\(4\)的情况,它是合数,我们需要考虑\(2\)的倍数之积也是\(4\)的倍数。

  • 如果有2个偶数那答案是\(0\)
  • 如果一个奇数一个偶数答案是\(1\)
  • 如果两个奇数答案是\(2\)

对于特判和之前直接变成\(4\)的倍数的情况取\(min\)就是答案啦。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n,k; cin>>n>>k;
        ll ans = 1e18;
        for(int i = 1;i <= n; i++)
        {
            cin>>a[i];
            if(a[i] % k == 0)
                ans = 0;
            ans = min(ans,(a[i]/k+1)*k-a[i]);
        }
        if(ans==0){
            cout<<0<<"\n";
            continue;
        }
        if(k==4)
        {
            int cnt1 = 0,cnt2 = 0;
            for(int i = 1;i <= n; i++)
            {
                int t = a[i] % 4;
                if(t == 1)
                    cnt1++;
                else if(t == 2)
                    cnt2++;
                else if(t == 0)ans = 0;
            }
            if(cnt1>=2) ans = min(ans,2ll);
            if(cnt2 >= 2) ans = 0;
            if(cnt1>=1&&cnt2>=1)ans = min(1ll,ans);
        }
    
        cout<<ans<<"\n";
    }   


    return 0;
}

D. In Love

题意:有\(q\)次操作。操作有以下两种类型:

  • \(+lr\) 在多重集合中加入一个线段\((l,r)\)
  • \(-lr\) 在多重集合中移走一个线段\((l,r)\)

每一次回答是否存在两个线段没有交集。

思路:我们用两个堆去维护左端点的最大值和右端点的最小值,如果\(mxl>mnr\)则说明存在。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    multiset<int,greater<int>>mxl;
    multiset<int,less<int>>mnr;
    for(int i = 1;i <= n; i++)
    {
        char op; int l,r;
        cin>>op>>l>>r;
        if(op=='+')
        {
            mxl.insert(l);
            mnr.insert(r);
 
            if(mxl.size()>=1&&mnr.size()>=1&&*mxl.begin()>*mnr.begin())
                cout<<"YES\n";
            else cout<<"NO\n";
        }
        else
        {
            mxl.erase(mxl.find(l));
            mnr.erase(mnr.find(r));
 
            if(mxl.size()>=1&&mnr.size()>=1&&*mxl.begin()>*mnr.begin())
                cout<<"YES\n";
            else cout<<"NO\n";
        }
    }


    return 0;
}

E. Look Back

题意:给你一个数组\(a_1,a_2,...,a_n\),你可以通过选择一个下标\(i\)让元素\(a_i = a_i*2\)

问你最少多少次使得数组单调不减?

思路:

一开始的写法:

我二分答案去写的,可是会爆\(long\) \(long\)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];

ll qmi(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        ll cnt = 0;
        for(int i = 2;i <= n; i++)
        {
            if(a[i]<a[i-1])
            {
                ll l = 1,r = 27;
              
                while(l<=r)
                {
                    int mid = (l+r)>>1;
                    if(qmi(2,mid)*a[i]>=a[i-1])r = mid-1;
                    else l = mid + 1;
                }
                a[i] *= qmi(2,r + 1);
                cnt += r + 1;
            }
        }

        cout<<cnt<<"\n";
    }

    return 0;
}

正解:

我们可以把最终答案分成\(2\)部分即:\(a_i\times 2^x\)。这样就不会爆\(long\) \(long\)啦。

我们分类讨论:

  • \(a[i]\ge a[i-1]\)

    我只需要继承\(a[i-1]\)的系数减去\(a[i-1]\)变成\(a[i]\)的\(2\)的次数即:\(log2(a[i]/a[i-1])\)下取整

  • \(a[i]<a[i-1]\)

    我只需要继承\(a[i-1]\)的系数加上\(a[i]\)变成\(a[i-1]\)的\(2\)的次数即:\(log2(a[i]/a[i-1])\)上取整

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],t[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int q; cin>>q;
    while(q--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        for(int i = 2;i <= n; i++)
        {
            if(a[i] >= a[i-1])
                t[i] = max(0ll,(ll)(t[i-1]-floor(log2((double)a[i]/a[i-1]))));
            else
                t[i] = max(0ll,(ll)(t[i-1]+ceil(log2((double)a[i-1]/a[i]))));
        }
        ll ans = 0;
        for(int i = 1;i <= n; i++)
            ans += t[i];
        cout<<ans<<"\n";
    }


    return 0;
}

G1. Dances (Easy version)

题意:对于每组数据,给定两个长度为 \(n\) 的序列 \(a,b\),其中 \(a_1=1\), \(a_2\cdots a_n\) 与 \(b_1\cdots b_n\) 由输入得到。

你可以对两个数组任意排序,你需要在两个序列中分别删除 \(k\) 个数, 使得对于剩下 \(n-k\) 个数, 有 \(\forall 1\leq i\leq n-k\rightarrow a_i<b_i\)

求最少删除数

思路:排序+二分。

我们如果要删\(k\)个,一定是删\(a\)的前\(k\)大和\(b\)的前\(k\)小是最优的。我们直接二分答案即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N],b[N];
int n,m; 
bool judge(int x)
{
    int l1 = 1,l2 = x+1;
    while(l1<=n-x)
    {
        if(a[l1]>=b[l2])return false;
        l1++;
        l2++;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        cin>>n>>m;
        a[1] = 1;
        for(int i = 2; i <= n; i++)
            cin>>a[i];
        for(int i = 1;i <= n; i++)
            cin>>b[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);

        int l = 0,r = 1e5;
        while(l<=r)
        {
            int mid = (l+r)>>1;
            if(judge(mid))r = mid-1;
            else l = mid+1;
        }
        cout<<r+1<<"\n";
    }


    return 0;
}

标签:cout,905,int,ll,cin,long,Codeforces,ans,Div
From: https://www.cnblogs.com/nannandbk/p/17847375.html

相关文章

  • Educational Codeforces Round 99 (Rated for Div. 2)
    https://codeforces.com/contest/1455很久没有vp了,感觉思维又僵化了A题直接看样例,直接猜是长度。B题首先如果是\(x=\frac{n(n+1)}{2}\),那么就是n否则如果\(x=\frac{n(n+1)}{2}+y\),分成两类y=n,ans=n+2,y<n,我们总可以找到前面一个替换,然后恰好的到n,选取z=n-y即可C题感觉比B......
  • Educational Codeforces Round 156 (Rated for Div. 2) ABCD
    EducationalCodeforcesRound156(RatedforDiv.2)ABCDA.SumofThree题意:给定正整数\(n\),判断是否存在正整数\(a\),\(b\),\(c\)满足:\(a+b+c=n\)。\(a\),\(b\),\(c\)均不是\(3\)的倍数。如存在,输出YES并构造一组方案,否则输出NO。思路:法一:我们分类讨论。根据......
  • Codeforces Round 904 (Div. 2)
    \(A.SimpleDesign\)https://codeforces.com/contest/1884/submission/233628914\(B.HauntedHouse\)https://codeforces.com/contest/1884/submission/233629446\(C.MediumDesign\)https://codeforces.com/contest/1884/submission/233632930\(D.Counting......
  • jquery 检测div宽度变化_jquery判断浏览器宽度小于指定值改变div样式
    浏览器原本样式当浏览器宽度小于1200px时样式变为代码如下:方法一:直接修改该div样式添加w1200,会覆盖前一个样式$(function(){var_width=$(window).width();//获取浏览器宽度if(_width<1200){$(".chenbin_org").addClass("w1200");}});方法二:修改该div的class属性......
  • Codeforces Round 910 (Div. 2) - D
    目录D.AbsoluteBeautyCodeforcesRound910(Div.2)D.AbsoluteBeauty观察可知,只要当交换的\(i\)和\(j\)满足$max(a_i,b_i)<min(a_j,b_j)$或者$min(a_i,b_i)>max(a_j,b_j)$......
  • CodeForces 合集第三弹
    这个合集主要是近期的CodeForces比赛题。1898.CodeforcesRound910(Div.2)https://codeforces.com/contest/1898A.MilicaandString很容易发现答案不超过\(1\),然后分类讨论当前B的个数然后选取一个前缀赋值即可。如果已经满足条件答案就是\(0\)。反正随便做做,时间......
  • Codeforces Round 785 (Div. 2)
    A-SubtleSubstringSubtraction/**__----~~~~~~~~~~~------___*..~~//====......__--~~~*-.\_|//|||\\~~......
  • Codeforces Round 908 (Div. 2)
    Preface补一下之前期中考落下的CFyysy因为这学期又开始断电了,所以除了周五周六晚上的CF可能都不一定会去打,都会以后面补题为主A.SecretSport由于题目保证给出的状态合法,因此直接输出最后一个字符即可#include<cstdio>#include<iostream>#include<utility>#include<vect......
  • Selenium4+python被单独定义<div>的动态输入框和二级下拉框要怎么定位?
    今天在做练习题的时候,发现几个问题捣鼓了好久,写下这篇来记录问题一:有层级的复选框无法定位到二级目录 对于这种拥有二级框的选项无法定位,也不是<select>属性.我们查看下HTML,发现它是被单独封装在body内拥有动态属性的独立<div>,当窗口点击的时候才会触发. 解......
  • Codeforces Round 910 (Div. 2)
    CodeforcesRound910(Div.2)基本情况做A题的速度比之前快多了,大概20分钟搞定。B题想了一个贪心错解,想用链表实现,但是不熟练,实现太慢,而且还被hack了。但是自己hack掉了,造数据上进步。B.MilenaandAdmirer贪心思路发现一个大于下一个的数,直接对半分,如果不能对半就小的在......