CodeCraft-20 (Div. 2)B. String Modification

http://codeforces.com/contest/1316/problem/B 题目链接

这题如果用纯模拟的方法做一定是会超时的,所以考虑用不那么暴力的方法,加入一点小技巧

容易看出,题目中当k=2时,其实就是用冒泡法发第一个字母移到最后一位。

那么只需要将首字母放到最后就可以了。

那么问题来了 当k>2时的情况呢?

只需要将前k-1位看成一个整体就行了,此时就又变成了k=2的情况,将前k-1位放到了最后;

但是要注意,当k和n不同时,看成整体的字符串内部也可能发生多次变化。但是总体只有保持不变和反转两种情况。

让我们观察 n=6,k=4 时对abcdef 中被看成整体的abc的操作过程 

1.abc->bca

2.cba->abc

3.abc->cba

可见,这种情况下要对abc进行反转。那么只需要在n-k是偶数的时候进行反转即可。

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define ar array
 6 
 7 int main() {
 8     ios::sync_with_stdio(0);
 9     cin.tie(0);
10 
11     int t;
12     cin >> t;
13     while(t--) {
14         int n;
15         string s;
16         cin >> n >> s;
17         pair<string, int> ans=make_pair(s, 1);
18         for(int i=2; i<=n; ++i) {
19             string t=s.substr(i-1), u=s.substr(0, i-1);
20             cout<<"t  "<<t<<endl<<"u  "<<u<<endl; 
21             if((n-(i-1))%2==1)
22                 reverse(u.begin(), u.end());
23             ans=min(make_pair(t+u, i), ans);
24             cout<<t+u<<endl;
25         }
26         cout << ans.first << "\n" << ans.second << "\n";
27     }
28 }

 

上一篇:CodeCraft-20 (Div. 2)E(状压DP)


下一篇:CodeCraft-19 and Codeforces Round #537 (Div. 2) E 虚树 + 树形dp(新坑)