[AGC037E] Reversing and Concatenating 题解

FFTotoro · 2022-05-12 18:52:20 · 题解

更新：修改了变量名和公式渲染。

这题可以用一种特殊的方法手动模拟。

观察题目的数据范围我们可以发现——当 k 大于 16 时，操作 k 次之后得到的最小字符串在 16 次之内就可以得到。

所以，当 k 小于等于 16 时手动模拟，否则将 k 转化为 16 再进行模拟。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,k; string s,t; cin>>n>>k>>s;
  reverse(s.begin(),s.end());
  for(k=min(k,16),t=s;k--;s=t){
    reverse(t.begin(),t.end()),s=t+s;
    for(int i=1;i<=n;i++)t=min(t,s.substr(i,n)); // 按题意模拟操作
  }
  cout<<s<<endl;
  return 0;
}