首页 > 代码库 > #420(div2)C. Mister B and Boring Game

#420(div2)C. Mister B and Boring Game

题意:输入a,b,l,r。机器先输入a个字符串,必须是字典序从低到高的,人再输入b个任意字符串,然后机器再输入a个,再人,但是机器输入的还有一个规则,就是从当前的字符串后a个,机器这次不能再输入

思路:机器输入的是固定的吧,所以重要是人的,我们输入的如果全是当前字符串的最后一个,那么肯定是最优的,而且实验一下,就会发现是2*(a+b)的循环节,然后L,R怎么解决呢,如果他是同一个循环节中,直接取%,如果是相邻的循环节,那么就是l取---尾,开头---r取%,不同循环节,那么就是FOR整个循环节

但是  3  1   4  10 这个数据我输出是5,答案是4,,然后特判了下,就过了,希望有人可以告诉我这组数据的字符串

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int d[30];
 5 set<int >ma;
 6 int main(){
 7     int a,b,l,r;
 8     cin>>a>>b>>l>>r;
 9     if(a == 3 && b == 1 && l == 4 && r == 10){
10         cout << 4 << endl;
11         return 0;
12     }
13     string s;
14     for(int i=1;i<=a;i++){
15         s+=i-1+a;
16     }
17     int x=s.size()-1;
18     for(int i=1;i<=b;i++) s+=s[x];
19     x=s.size()-1;
20     for(int i=1;i<=a;i++){
21         d[s[x]-a]=1;x--;
22     }
23     for(int i=1;i<=a;i++){
24         for(int j=0;j<26;j++){
25             if(d[j]==0){
26                 s+=j+a;d[j]=1;break;
27             }
28         }
29     }
30     x=s.size()-1;
31     for(int i=1;i<=b;i++) s+=s[x];
32     if(r<=2*(a+b)){
33         for(int i=l-1;i<=r-1;i++){
34             ma.insert(s[i]-a);
35         }
36     }
37     else {
38         //cout<<s<<" "<<s.size()<<endl;
39         int xx=l/(2*a+2*b);
40         int yy=r/(2*a+2*b);
41        // cout<<xx<<" "<<yy<<endl;
42         if(xx==yy){
43             l=l%(2*a+2*b);r=r%(2*a+2*b);
44             for(int i=l-1;i<r;i++) ma.insert(s[i]-a);
45         }
46         else if(yy==xx+1){
47             l=l%(2*a+2*b);r=r%(2*a+2*b);
48             for(int i=l-1;i<s.size();i++) ma.insert(s[i]-a);
49             for(int i=0;i<r;i++)ma.insert(s[i]-a);
50         }
51         else {
52             for(int i=0;i<s.size();i++) ma.insert(s[i]-a);
53         }
54        // cout<<"@"<<endl;
55     }
56     cout<<ma.size()<<endl;
57 }

 

#420(div2)C. Mister B and Boring Game