偏门网站建设,网络公司网站首页图片,长沙正规竞价优化服务,扬中炒地皮正题
题目链接:https://www.luogu.com.cn/problem/CF1654F 题目大意
给出一个长度为2n2^n2n的字符串sss#xff08;下标为0∼2n−10\sim 2^n-10∼2n−1#xff09;
你要找到一个xxx满足tisixorxt_{i}s_{i\ xor\ x}tisi xor x#xff0c;并且ttt的字典序最小。 1≤n≤…正题
题目链接:https://www.luogu.com.cn/problem/CF1654F 题目大意
给出一个长度为2n2^n2n的字符串sss下标为0∼2n−10\sim 2^n-10∼2n−1
你要找到一个xxx满足tisixorxt_{i}s_{i\ xor\ x}tisi xor x并且ttt的字典序最小。
1≤n≤181\leq n\leq 181≤n≤18 解题思路
考虑设f(i,x)f(i,x)f(i,x)表示选的值为xxx时最终的ttt的前2i2^i2i个字符。
那么我们有 f(i,x)f(i−1,x)f(i−1,xxor2i−1)f(i,x)f(i-1,x)f(i-1,x\ xor\ 2^{i-1})f(i,x)f(i−1,x)f(i−1,x xor 2i−1) 就是和另一边拼起来
发现这个部分和SASASA的有点像我们考虑倍增来做枚举这个iii。
假设我们已经得到所有f(i−1,x)f(i-1,x)f(i−1,x)的排名那么当我们比较f(i,x)f(i,x)f(i,x)和f(i,y)f(i,y)f(i,y)时优先比较f(i−1,x)f(i-1,x)f(i−1,x)和f(i−1,y)f(i-1,y)f(i−1,y)如果相等那么比较f(i−1,xxor2i−1)f(i-1,x\ xor\ 2^{i-1})f(i−1,x xor 2i−1)和f(i−1,yxor2i−1)f(i-1,y\ xor\ 2^{i-1})f(i−1,y xor 2i−1)即可。
然后我们又可以O(1)O(1)O(1)比较然后O(2nn)O(2^nn)O(2nn)得出新的iii的所有f(i,x)f(i,x)f(i,x)的排名。
时间复杂度O(2nn2)O(2^nn^2)O(2nn2) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N118;
int n,m,r,p[N],a[N],b[N];
char s[N];
bool cmp(int x,int y){if(a[x]a[y])return a[x^r]a[y^r];return a[x]a[y];
}
int main()
{scanf(%d,n);m(1n); scanf(%s,s);for(int i0;im;i)p[i]i;for(int i0;im;i)a[i]s[i]-a;sort(p,pm,cmp);for(int i0;in;i){r1i;sort(p,pm,cmp);b[p[0]]1;for(int j1;jm;j)b[p[j]]b[p[j-1]]cmp(p[j-1],p[j]);for(int j0;jm;j)a[j]b[j];}for(int i0;im;i)printf(%c,s[i^p[0]]);return 0;
}
