Codeforces Round 607 (Div. 2)
2025-01-26 10:53:54 # codeforces

Codeforces Round 607 (Div. 2)

A

……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--) {
        string s;
        cin>>s;
        char c = s[s.length()-1];
        if(c=='o') puts("FILIPINO");
        else if(c=='u') puts("JAPANESE");
        else puts("KOREAN");
    }
    return 0;
}

B

分析

对于s至多进行一次字母交换使得s严格小于c，如果用两层循环查找可能的最小s，再加上外层的t，总共O(n^3)，会TLE。针对仅能进行一次交换，考虑从当前位置i向后查找小于s[i]的最小字符的下标minn，如果存在s[minn]!=s[i]则说明找到了小于s[i]的最小字符，swap后即为s所有情况中的最小的串，否则i++考虑下一个位置。当处理完s后获得可能的s最小值，最后再与c进行比较即可。

需要注意的是：在查找小于s[i]的最小字符的下标minn时，要选择靠后的符合s[minn]<s[i]的minn，例如

s = AAZMOAA

c = AAAQWER

对于i=2时，s[2]=Z，向后查找minn，当i=5或6时，均为A，但是swap(s[2],s[5])后是AAAMOZA，swap(s[2],s[6])后是AAAMOAZ，这两种情况显然第二种情况s更小，所以如果有多个相同的最小字符，选择下标最大的那个s[minn]进行交换，这样s[i]与s[minn]相距最远，swap后s[i]可以放在靠后的位置，从而s整体的字典序最小。

code

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
#include<bits/stdc++.h>
using namespace std;
int t;
string s,c;
int findPos(int index) {
    int minn = index;
    for(int i=index+1;i<s.length();i++) {
        if(s[i]<=s[minn]) minn = i;		//为了查找符合情况的靠后的字符
    }
    return minn;
}
int main() {
    cin>>t;
    while(t--) {
        cin>>s>>c;
        int n = s.length();
        for(int i=0;i<n;i++) {
            int minn = findPos(i);	//从当前位置i向后查找<s[i]的最小字符下标
            if(s[i]!=s[minn]) {		//存在
                swap(s[i],s[minn]);
                break;
            }
        }
        if(s<c) cout<<s<<endl;
        else cout<<"---"<<endl;
    }
    return 0;
}

C

分析

逐步模拟第一个样例，可以发现可以实际操作的s的范围为1~x，且x为1e6，这样就把s操作的范围缩小了。当s.length<x时，需要继续向s添加c才能使ℓ追赶x，所以直接对s进行模拟；如果s.length>=x了，这说明不用再继续向s添加c了，ℓ能够追赶x，只需要计算s的长度即可，因为是先剪切再粘贴，这就相当于给s添加了sℓ-1次的字符串c，c.length = len-ℓ，所以s的长度更新为len = len + (sℓ-1)*(len-ℓ)，注意取模。

code

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const long long N = 1e9+7;
int main()
{
    int t;
    cin>>t;
    while(t--) {
        int x;
        LL len = 0;
        string s,c;
        cin>>x>>s;
        int kesai = 0;		//ℓ
 
        len = s.length();
        while(kesai!=x) {
            kesai++;
            int times = s[kesai-1]-'0';		//粘贴c的次数,即sℓ
            if(s.length()<x) {
                c = s.substr(kesai,s.length()-kesai);
                s = s.substr(0,kesai);
                while(times--) s+=c;	//向s粘贴c
                len = s.length();
            }
            else {
                len =(len+((times-1)*((len-kesai+N)%N)%N))%N;
            }
        } 
        cout<<len%N<<endl;
    }
    return 0;
}

上面会 Time limit exceeded on test 17，需要进行优化。

在if中是先让s变短，然后根据times再向s添加c，这等价于让s保持原样，只需要向s添加times-1次的c即可，这样减少了substr的操作，如下：

1
2
3
4
5
6
7
if(s.length()<x) {
    c = s.substr(kesai,s.length()-kesai);
    // s = s.substr(0,kesai);
    times--;
    while(times--) s+=c;
    len = s.length();
}

提交后通过

上一页
2025-01-26 10:53:54 # codeforces
下一页