https://codeforces.com/gym/101623

A. Ascending Photo

题意：
给一个数字串，需要花 x 刀将其切成 x + 1 个子段，满足任意排列子段后使整体有序，最小化 x 并输出

数据范围：
串长 1e6 ，元素 1 \leq h_i \leq 2e9

做法：
dp&map
反过来考虑，先全部切掉再组合，考虑怎么排可以少切一些
可以操作的空间只有相等的元素，两元素在原串与最终串中仍相邻则可少切一次，基于这个可以将原问题规约为dag考虑
dp很好考虑，从最终状态出发，f[i][j] 表示对于第 i 种元素，以其第 j 个结尾时的最小代价。转移方程如下
f[i][j] = {min}\{f[i - 1][p] + cal(i - 1, j)\}
cal 的作用大概就是算出 i 不以 j 开头时能否少切一次
总状态数为 O(n)，转移搞搞可以弄成均摊 O(1) 的，总复杂度大概是 O(nlogn)
需要注意的是：相邻相同去重，离散化，单个元素的特殊情况

AC代码：

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MAX_N = 1E6 + 100;
const int INF = MAX_N;

int n, m;
map<int, int> mp;
map<int, int> f[MAX_N];
vector<int> G[MAX_N];
int h[MAX_N];

void init() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        mp[h[i]] = 0;
    }

    int oft = 0;
    for (int i = 2; i <= n; ++i) {
        if (h[i] == h[i - 1 - oft]) {
            oft += 1;
        }
        h[i - oft] = h[i];
    }
    n -= oft;
    //相邻去重

    int cnt = 0;
    for (auto& it : mp) {
        it.second = ++cnt;
    }
    for (int i = 1; i <= n; ++i) {
        h[i] = mp[h[i]];
        G[h[i]].push_back(i);
        m = max(m, h[i]);
    }
    //离散化，转为dag
}

int main() {
    ios::sync_with_stdio(false);
    init();

    f[0][0] = INF;
    f[0][n + 1] = 0;
    for (auto it : mp) {
        int i = it.second;

        int bs = INF;
        for (auto it : f[i - 1]) {
            bs = min(bs, it.second + (int)G[i].size());
        }
        //不连接时的最小值

        int mi = bs, mip = 0;  //最小值
        int si = bs, sip = 0;  //次小值
        for (int j : G[i]) {
            if (i - 1 == h[j - 1]) {
                if (si > f[i - 1][j - 1] + (int)G[i].size() - 1) {
                    si = f[i - 1][j - 1] + (int)G[i].size() - 1;
                    sip = j;

                    if (mi > si) {
                        swap(mi, si);
                        swap(mip, sip);
                    }
                }
            }
        }

        if (G[i].size() > 1) {
            for (int j : G[i]) {
                if (j == mip)
                    f[i][j] = si;
                else
                    f[i][j] = mi;
            }
        } else {
            f[i][G[i].back()] = mi;
        }
    }

    int ans = INF;
    for (auto it : f[m]) {
        ans = min(ans, it.second);
    }
    cout << ans - 1 << endl;

    return 0;
}

用例：

7
1 2 3 4 2 3 5
//3

7
1 2 3 4 2 4 5
//3

14
2 2 3 3 5 5 1 1 2 2 3 3 4 4
//3

心路历程：
训练的时候思路是从一个假贪心出发
规约着就变成了个链式约束的n-sat，然后越走越偏最后开始网络流乱搞（如果上课好好听讲，早知道这是个NP，就不至于这样了XD）
其实当时也想过dp，转移都想的差不多了，但是复杂度算错了，主要是第二维不知道怎么想的直接当 $n$ 算了，主要没想到用map来存状态
其实不是难题，但是硬刚了5h，说明大脑还是不够升级，思路也不够广
补的时候花了1h才调好，码力也不够XD

F. Factor-Free Tree

题意：
当且仅当一棵带权二叉树的所有节点满足：其权与其所有祖先的权互质，其为Factor-Free。现给一棵二叉树的前序遍历，构造一棵Factor-Free的树，若不可能，输出impossible
数据范围：
1 \leq n \leq 10^6,\ 1 \leq a_i \leq 10^7，时限3s

做法：
分解质因数，O(n \frac{\sqrt a}{loga} )
预处理每个数的最大互质区间 l[i], r[i]，O(nloga) 空间 O(a)
对于区间 [ll, rr]， 满足 ll \leq i \leq rr, l[i] \leq ll, rr \leq r[i] 的 i 能作为这个区间的根，将区间分为 [ll, i - 1], [i + 1, rr]，递归解决
可以证明，若有多个节点满足条件，可任取一个作为根
找根直接搜索即可，从两端往中间搜，找到即结束搜索
普通暴力容易想到卡成 O(n^2) 的数据，按照上述策略搜索则不会，复杂度不会证，猜测为 O(nlogn)
总复杂度 O(n \frac{\sqrt a}{loga} + nloga + nlogn)

AC代码：

#include <iostream>
using namespace std;

const int MAX_N = 1E6 + 100;
const int MAX_A = 1E7 + 100;
const int MAX_SQRT_A = 4E3 + 100;
const int MAX_LOG_A = 27;

int pSz, pr[MAX_SQRT_A];
void initPrime(int n) {
    static bool vis[MAX_SQRT_A];
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) pr[pSz++] = i;
        for (int j = 0; j < pSz; ++j) {
            if (pr[j] * i > n) break;
            vis[pr[j] * i] = true;
            if (0 == i % pr[j]) break;
        }
    }
}

int fSz, fac[MAX_LOG_A];
void getFac(int x) {
    fSz = 0;
    for (int j = 0; j < pSz; ++j) {
        if (x % pr[j]) continue;
        fac[fSz++] = pr[j];
        while (0 == x % pr[j]) {
            x /= pr[j];
        }
    }

    if (x > 1) {
        fac[fSz++] = x;
    }
}

int n;
int ans[MAX_N];

int p[MAX_A];
int l[MAX_N], r[MAX_N];

bool solve(int ll, int rr, int fat) {
    if (ll > rr) {
        return true;
    }
    if (ll == rr) {
        ans[ll] = fat;
        return true;
    }

    for (int i = ll, j = rr; i <= j; ++i, --j) {
        if (l[i] <= ll && rr <= r[i]) {
            ans[i] = fat;
            return solve(ll, i - 1, i) && solve(i + 1, rr, i);
        }

        if (l[j] <= ll && rr <= r[j]) {
            ans[j] = fat;
            return solve(ll, j - 1, j) && solve(j + 1, rr, j);
        }
    }

    return false;
}

int main() {
    initPrime(3200);

    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int u;
        cin >> u;
        getFac(u);

        l[i] = 1;
        r[i] = n;
        for (int j = 0; j < fSz; ++j) {
            l[i] = max(l[i], p[fac[j]] + 1);
            r[p[fac[j]]] = min(r[p[fac[j]]], i - 1);
            p[fac[j]] = i;
        }
    }
    //初始化l, r

    if (solve(1, n, 0)) {
        for (int i = 1; i <= n; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

心路历程：
做法的前半大概10m就想到了，但是想不到基于l，r数组来找根的合适做法，一直觉得复杂度不对，考虑了一整天奇怪数据结构
最后突然来了灵感搜了题解，发现没人讲最后面这个怎么搞，发现不对劲，试着分析了一下复杂度发现可以不是 O(n^2) 的
做的时候当了点子王，犯了nt错误，贴在下面供以后娱乐

bool solve(int ll, int rr, int fat) {
    ...
    bool flag;  //利用堆空间未初始化的随机特性
    for (int i = ll, j = rr; i <= j;) {
        if (flag) {
            ...
        } else {
            ...
        }
        flag = !flag;
    }
    ...
}

测试之后发现，只要初始化flag就能过
对这个问题又做了进一步测试，代码如下

#include <iostream>
using namespace std;

bool go(int i) {
    bool flag;
    for (int j = 0; j < i; ++j)
    flag = !flag;
    return flag;
}

int main() {
    ios::sync_with_stdio(false);

    bool t;
    for (int i = 0; i < 2E5; ++i) t ^= go(i);
    cout << t << endl;

    return 0;
}

用的是cf的评测机，并没有发现对效率有影响，而且即使没有初始化，也是为false的（没有广泛测试）
所以最后我猜是这个东西影响了O2优化，因为不显式初始化的话，编译器并不知道初始值

J. Juggling Troupe

题意：
给一个元素为0，1，2的串，其在每个时刻会发生如下变化
假如一个位置（1\leq i \leq n）上的 a_i \geq 2 ，将会发生：a_i =a_i-2, a_{i-1} = a_{i-1} +1, a_{i + 1} = a_{i + 1} + 1
注意边界会"吞掉"数
同一时刻所有的变化同时发生
问时间足够长后，串的内容为什么

数据范围：
1 \leq n \leq 10^6, 0 \leq a_i \leq 2

做法：
打个表，发现如下两个规律：

1. 操作可拆分，例如 0012200 -> 0111101，可拆为0011200 -> 0101110 -> 0102110 -> 0111101
2. 连续的一串1中一个2会在对称位置产生0，并且区间左右延长一格，例如 00112100 -> 01101110

之后链表维护一下就好了

AC代码：

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 1E6 + 100;

int n;
char s[MAX_N];
vector<int> que;

int head, tail, m;
int l[MAX_N << 1], r[MAX_N << 1];
int lst[MAX_N << 1], nxt[MAX_N << 1];

int i;
void go(int p) {
    while (nxt[i] && p >= l[nxt[i]]) {
        i = nxt[i];
    }

    if (p > r[i]) {
        if (p == r[i] + 1 && p == l[nxt[i]] - 1) {
            r[i] = r[nxt[i]];
            if (nxt[nxt[i]]) {
                lst[nxt[nxt[i]]] = i;
            } else {
                tail = i;
            }
            nxt[i] = nxt[nxt[i]];

        } else if (p == r[i] + 1) {
            r[i] += 1;
        } else if (nxt[i] && p == l[nxt[i]] - 1) {
            l[nxt[i]] -= 1;
        } else {
            m += 1;
            l[m] = r[m] = p;
            if (lst[i]) {
                nxt[lst[i]] = m;
            } else {
                head = m;
            }
            lst[m] = lst[i];
            nxt[m] = i;
            lst[i] = m;
        }

        return;
    }

    int p0 = l[i] + r[i] - p;  //对称位置

    m += 1;
    l[m] = p0 + 1;
    r[m] = r[i] + 1;
    if (r[m] > n) r[m] = n;

    lst[m] = i;
    nxt[m] = nxt[i];
    if (nxt[i]) {
        lst[nxt[i]] = m;
    } else {
        tail = m;
    }
    nxt[i] = m;

    l[i] -= 1;
    if (l[i] <= 0) l[i] = 1;
    r[i] = p0 - 1;

    int lp = i, rp = m;
    if (lst[lp] && r[lst[lp]] + 1 == l[lp]) {
        r[lst[lp]] = r[lp];
        lst[nxt[lp]] = lst[lp];
        nxt[lst[lp]] = nxt[lp];
        i = lst[lp];
    }

    if (nxt[rp] && l[nxt[rp]] - 1 == r[rp]) {
        l[nxt[rp]] = l[rp];
        lst[nxt[rp]] = lst[rp];
        nxt[lst[rp]] = nxt[rp];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> s;
    n = strlen(s);
    int ll = 1, rr = 0;
    for (int i = 1; i <= n; ++i) {
        if ('0' == s[i - 1]) {
            if (rr >= ll) {
                m += 1;
                l[m] = ll;
                r[m] = rr;
                lst[m] = m - 1;
                nxt[m - 1] = m;
            }
            ll = i + 1;
            rr = i;
        } else {
            if ('2' == s[i - 1]) {
                que.push_back(i);
            }
            rr += 1;
        }
    }
    if (rr >= ll) {
        m += 1;
        l[m] = ll;
        r[m] = rr;
        lst[m] = m - 1;
        nxt[m - 1] = m;
    }
    // init

    if (m) {
        head = 1;
        tail = m;
    } else {
        cout << s << endl;
        return 0;
    }

    i = head;
    for (int u : que) {
        go(u);
    }

    for (int i = 1; i < min(n + 1, l[head]); ++i) {
        cout << 0;
    }
    cout.flush();
    for (int i = head; i; i = nxt[i]) {
        for (int j = max(1, l[i]); j <= min(n, r[i]); ++j) {
            cout << 1;
        }
        cout.flush();
        if (nxt[i]) {
            for (int j = max(1, r[i] + 1); j < min(n + 1, l[nxt[i]]); ++j) {
                cout << 0;
            }
            cout.flush();
        } else {
            break;
        }
    }
    for (int i = max(1, r[tail] + 1); i <= n; ++i) {
        cout << 0;
    }
    cout.flush();

    return 0;
}

心路历程：
打表找到规律还是挺快的，弄了二十来分钟吧
写链表算上调试大概弄了2h，太爬了
证明目前不会，主要是第一条，从第一条证第二题还是挺简单的
暴力程序这里就不贴了

E. English Restaurant

这应该是个概率dp，状态不行，捋不清，先占坑