Codeforces Round 905 (Div.3)A~G1

Nannan Lv5
  2024-09-24 22:31 2024-09-24 22:31 Created   2024-09-30 20:01:29 2024-09-30 20:01:29 Updated      

Codeforces Round 905 (Div. 3) A~G1

A. Morning

思路：签到，直接模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 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

题意：问你能否删掉一些字母之后重排是回文串，且满足删的次数。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 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

题意：给你一个数组。在一次操作里面，你可以选择一个元素让它。找到最小的操作次数使得能被整除。

思路：这里的突破口是和的范围。其中，

我们发现都是素数，我们只需要考虑哪一个能最快变成他们的倍数即可。

对于的情况，它是合数，我们需要考虑的倍数之积也是的倍数。

  • 如果有2个偶数那答案是
  • 如果一个奇数一个偶数答案是
  • 如果两个奇数答案是

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 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

题意：有次操作。操作有以下两种类型：

  • 在多重集合中加入一个线段
  • 在多重集合中移走一个线段

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

思路：我们用两个堆去维护左端点的最大值和右端点的最小值，如果则说明存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 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

题意：给你一个数组，你可以通过选择一个下标让元素

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

思路：

一开始的写法：

我二分答案去写的，可是会爆 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 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;
}

正解：

我们可以把最终答案分成部分即：。这样就不会爆 啦。

我们分类讨论：

  • 我只需要继承的系数减去变成的的次数即：下取整

  • 我只需要继承的系数加上变成的的次数即：上取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 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)

题意：对于每组数据，给定两个长度为 的序列 ，其中 ， 与 由输入得到。

你可以对两个数组任意排序，你需要在两个序列中分别删除 个数， 使得对于剩下 个数， 有

求最少删除数

思路：排序+二分。

我们如果要删个，一定是删的前大和的前小是最优的。我们直接二分答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 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;
}

  • Title: Codeforces Round 905 (Div.3)A~G1
  • Author: Nannan
  • Created at : 2024-09-24 22:31:00
  • Updated at : 2024-09-30 20:01:29
  • Link: https://redefine.ohevan.com/2024/09/24/Codeforces Round 905 (Div. 3)ABCDEG1/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 905 (Div.3)A~G1
  1. Codeforces Round 905 (Div. 3) A~G1
    1. A. Morning
    2. B. Chemistry
    3. C. Raspberries
    4. D. In Love
    5. E. Look Back
    6. G1. Dances (Easy version)