Codeforces Round 903 (Div. 3)ABCDE

Nannan Lv5
  2023-11-10 16:56 2023-11-10 16:56 Created   2024-09-30 20:01:27 2024-09-30 20:01:27 Updated      

Codeforces Round 903 (Div. 3) ABCDE

A. Don’t Try to Count

题意：复制串若干遍，是否能在串中找到串。

思路：直接暴力，注意不要超限，会MLE

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
// 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 ns[30],nt[30];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n,m; cin>>n>>m;
        string s,t; cin>>s>>t;
        
        for(int i = 0;i <= 30; i++)
            ns[i] = nt[i] = 0;
        for(int i = 0;i < n; i++)
            ns[s[i]-'a']++;
        for(int i = 0;i < m; i++)
            nt[t[i]-'a']++;

        bool ok = true;
        for(int i = 0;i < 26; i++)if(nt[i]&&!ns[i]){
            ok = false;
            break;
        }

        if(!ok)
            cout<<"-1\n";
        else{
            bool ok = false;
            int cnt = 0;
            while(1)
            {   
                if(cnt>10)break;
                if(s.find(t) != string::npos)
                {
                    ok = true;
                    break;
                }
                s = s + s;
                cnt++;
            }
            if(ok)cout<<cnt<<"\n";
            else cout<<"-1\n";
        }
    }
    return 0;
}

B. Three Threadlets

题意：给你3根绳子，问你能否在3刀以内(可以为0刀)，使得所有绳子一样长。

思路：分析一下，我们最终一定会变成当前最短的，如果变不成，那一定不行。因为如果不变成当前最短的，那么意味着当前最短的要被切，那么其他的不可能在剩余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
// 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--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        ll minn = min({a,b,c});
        if(a%minn||b%minn||c%minn)
            cout<<"No\n";
        else{
            int ans = 0;
            if(a!=minn)
                ans += a/minn-1;
            if(b!=minn)
                ans += b/minn-1;
            if(c!=minn)
                ans += c/minn-1;

            if(ans>3)
                cout<<"No\n";
            else cout<<"Yes\n";

        }
    }
    return 0;
}

C. Perfect Square

题意：给你一个初始矩阵，问你如果要该矩阵旋转90°之后和原来的一样，最少要操作多少次。每次操作可以选择一个让他变成下一个(z的话就不变了)

思路：旋转后是要一样的，那么，我们考虑变成这四个中最大的(因为只能往大的变)，统计答案即可。

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
// 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;
char s[1010][1010];
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++)
            for(int j = 1;j <= n; j++)
                cin>>s[i][j];
        ll ans = 0;
        int m = n/2;
        /*
            a[i][j] -> a[j][N-i+1]
             ↑             ↓
            a[N-j+1][i]<-a[N-i+1][N-j+1]
        */
        for(int i = 1;i <= m; i++)
        {
            for(int j = i; j < n-i+1; j++)
            {
                char a[4] = {s[i][j],s[j][n-i+1],s[n-i+1][n-j+1], s[n-j+1][i]};
                char mx = a[0];

                for(int k = 1;k < 4; k++)
                    mx = max(mx,a[k]);
                for(int k = 0;k < 4; k++)
                    ans += mx-a[k];
            }
        }
        cout<<ans<<"\n";
        
    }

    return 0;
}

D. Divide and Equalize

题意：给你一个数组包含个正整数。每次你可以选择任意两个元素，然后让(这里整除）。问能否使得所有元素都变得一样。

思路：根据唯一分解定理，我们对每个数进行质因数分解。最后我们的每种质因子一定要可以平均分配才能使得所有数一样。

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
// 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];
map<int,int>mp;
void primer(ll x)
{
    for (ll i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0)
            {
                x = x / i;
                s++;
            }
            mp[i]+=s;
        }
    }
    if (x > 1)mp[x]++;
}

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

        bool ok = true;
        // for(auto [x,c]:mp)
        //     cout<<x<<" "<<c<<"\n";
        for(auto [x,c]:mp)if(c%n&&x!=1){
            ok = false;
            break;
        }

        if(ok)cout<<"Yes\n";
        else cout<<"No\n";

    }
    return 0;
}

E. Block Sequence

题意：给你一个序列长度为。我们定义：我们可以把元素分成第一个元素长度的块的叫做美丽数组。问最少操作多少次能变得美丽。

思路：dp。我们知道，当前的和后面的有关，我们考虑倒着dp。

定义：：～最少删多少个是美丽的。

转移：

考虑删掉：

考虑保留：

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
// 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],dp[N];
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];
        dp[n] = 1,dp[n+1] = 0;
        for(int i = n-1;i >= 1;i--)
        {
            dp[i] = dp[i+1]+1;//删除
            if(a[i]<=n-i)//保留
                dp[i] = min(dp[i],dp[i+a[i]+1]);
        }
        cout<<dp[1]<<"\n";
    }
    return 0;
}

  • Title: Codeforces Round 903 (Div. 3)ABCDE
  • Author: Nannan
  • Created at : 2023-11-10 16:56:00
  • Updated at : 2024-09-30 20:01:27
  • Link: https://redefine.ohevan.com/2023/11/10/Codeforces Round 903 (Div. 3)ABCDE/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 903 (Div. 3)ABCDE
  1. Codeforces Round 903 (Div. 3) ABCDE
    1. A. Don’t Try to Count
    2. B. Three Threadlets
    3. C. Perfect Square
    4. D. Divide and Equalize
    5. E. Block Sequence