闲话

所以DTOI R2终于结束了
我看你们还有什么法拿我开涮

我又复述了一遍
lyin过来了
“这是啥？……lyin都是……fengwu？”
我：“啊对对对对对对对对对”
“啥意思啊这”
“您聚，所以……人多！您心里面装着的人比较的多（笑）（笑）”
“……你是在什么精神状态下说出这句话的”

然后感受了一下lyin的前装甲板
真的 外面秋季校服 里面夏季校服 再里面是秋衣 最里面是厚背心

突然想到有人给白傻子寄装甲板
以及cod战区 给自己加护甲是从前胸塞进去的动作
突然蚌埠住了

CF1515E
这题听说有 \(O(n\log n)\) 的代数工业做法 有谁能给我讲讲吗

ひとりのファンタジー 涙はいらない

センセーションだけが私なのだ

夢色のファンタジー パパは気付けない

これで最後の夜になる

杂题

CF1654F

给定一个长度为 \(2^n\)，只包含小写字母的字符串 \(s\)。你可以将字符串的下标全部异或一个 \([0,2^n)\) 的整数 \(k\)，即构造一个与 \(s\) 等长的新字符串 \(t\)，使得 \(t_i=s_{i\oplus k}\)。最小化 \(t\) 的字典序，并输出字典序最小的 \(t\)。

\(n\leq 18\)。

模拟赛考了。
数据不是cf上的，很水，被我的贪心水过了，5ms，很快

现在写一下正解。

首先瞪眼可以看出一个性质。我们可以通过操作 \(k\) 的第 \(i\) 位的 01 性来将生成序列每 \(2^i\) 段的前半部分和后半部分交换。形式化地，我们令 \(f(k,i)\) 表示由 \(k\) 生成的子序列前 \(i\) 个元素的值，上面的性质可以被表为：\(f(k,i)\) 即为 \(f(k,i-1)\) 和 \(f(k \ \text{xor}\ 2^{i-1}, i-1)\) 的拼接。

然后我们发现这个玩意的第二维在指数上。所以想到倍增。
我们设当前已经确定完前 \(i-1\) 位，现在确定第 \(i\) 位。我们发现当确定该位时前 \(i-1\) 位确定下来的段的相对顺序不会发生改变，因此考虑把原序列按 \(2^i\) 划分成段，按字典序排序后得到一段的排名，用排名替代这一段向后递归。
可以发现这样操作也可以做到查询字典序第 \(k\) 小的 \(t\)。因此加强题目也不是不可以

总时间复杂度为 \(O(n^2\ 2^n)\)，因为每一位都需要进行一次排序，使用快速排序的复杂度是 \(O(2^n \log (2^n)) = O(n 2^n)\)。如果你学过SA可以拿过来那里面的双关键字基排，复杂度被优化到 \(O(n2^n)\)，数据范围被优化到 \(n\le 21\)。

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<18) + 10;
int n, len, a[N], t[N], v[N], l;
char ch[N];

bool cmp(const int & a, const int & b) { if (v[a] == v[b]) return v[a ^ l] < v[b ^ l]; return v[a] < v[b]; }

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> ch;
    len = 1 << n;
    for(int i = 0; i < len; i++) a[i] = i, v[i] = ch[i] - 'a';
    sort(a, a+len, cmp);
    for(int i = 0; i < n; ++i) {
        l = (1<<i);
        sort(a, a+len, cmp);
        int cnt = 0;
        for (int j = 0; j < len; ++j) {
            if (j == 0 or cmp(a[j-1], a[j])) t[a[j]] = ++cnt;
            else t[a[j]] = cnt;
        } 
        for (int j = 0; j < len; ++j) v[j] = t[j];
    }
    for (int i = 0; i < len ; i++) cout << ch[i ^ a[0]];
}