原题传送门。
显然,如果我们想要把一个字符串字典序尽量小,我们把这个字符串中的字符从小到大排序就行了;反过来就是把字符串中的字符从大到小排序就行了。
我们可以暴力地对于每个字符串排序,然后对于每一个字符串都判断一遍是不是最小的就行了。
代码:
#include <iostream>
#include <algorithm>
using namespace std;int n,m;
string s[3005];
bool cmp(char s,char ss){return s>ss;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i = 1;i<=n;i++){cin>>s[i];}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){//排序if(i==j){sort(s[j].begin(),s[j].end());}else{sort(s[j].begin(),s[j].end(),cmp);}}if(false){quick_exit:continue;}for(int j = 1;j<=n;j++){if(j==i) continue;if(s[j]<s[i]){//如果有更小的,就直接输出0cout<<"0";goto quick_exit;}}cout<<1;}return 0;
}
时间复杂度 \(O(n^3 \log n)\),TLE \(2\) 个点。
我们发现,上面的思路排序了很多没用的,我们考虑预处理。
我们先把所有的字符串里的字符从大到小排序,每次遍历的时候,只需要把上次从小到大排序的字符串重新排序成从大到小的,把当前字符串排序成从小到大的,就做完了。
时间复杂度 \(O(n^2\log n)\),能够通过此题。
AC 代码:
#include <iostream>
#include <algorithm>
using namespace std;int n,m;
string s[3005];
bool cmp(char s,char ss){return s>ss;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i = 1;i<=n;i++){cin>>s[i];}for(int i = 1;i<=n;i++){//先全部排序sort(s[i].begin(),s[i].end(),cmp);}for(int i = 1;i<=n;i++){sort(s[i].begin(),s[i].end());sort(s[i-1].begin(),s[i-1].end(),cmp);//把上一个排序回来,把这一个排序过去if(false){quick_exit:continue;}for(int j = 1;j<=n;j++){//继续跑if(j==i) continue;if(s[j]<s[i]){cout<<"0";goto quick_exit;}}cout<<1;}return 0;
}