250806 模拟赛

T1 lcp

给定三个长度为 \(n\) 的字符串 \(a,b,c\)，你需要将 \([1,n]\) 划分为连续非空的三段 \([1,i-1],[i,j-1],[j,n]\)，最小化

\[ \operatorname{lcp}(a_{第一段},b_{第二段})+\operatorname{lcp}(b_{第二段},c_{第三段})+\operatorname{lcp}(a_{第一段},c_{第三段}) \]

\(n\le 10^5\)

通过手模或打表发现答案不超过 \(3\)。因为 \(\operatorname{lcp}\) 不超过区间长度，只需把最后两个区间长度设为 \(1\) 即可。

进一步我们发现，当且仅当存在 \(1<i<j\le n\) 满足 \(a_1\ne b_i\ne c_j\) 时，答案取到 \(0\)。通过倒序枚举 \(i\)，这种情况是容易判断的。

将其他情况再分讨：

\(case~1\)：\(\forall i>1,~b_i=a_1\)。此时如果 \(c\) 也满足 \(\forall j>2,~c_j=a_1\)，那么答案只能为 \(3\)。否则，考察一个 \(c_j\ne a_1\) 的 \(j\)，只需将 \(i\) 取为 \(j-1\)，答案即可取到下界 \(1\)。

\(otherwise\)：考察一个 \(b_i\ne a_1\) 的 \(i\)，此时原式第一项恒为 \(0\)；不难发现只要取 \(j=n-1\)，答案即可又取到下界 \(1\)。

代码

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

int T, n, ans;
string a, b, c;
char key;

int cnt[26], num;

int main() {

    freopen("lcp.in", "r", stdin);
    freopen("lcp.out", "w", stdout);

    cin >> T;
    while(T--) {
        cin >> n;
        cin >> a >> b >> c;
        key = a[0];
        ans = 3;
        num = 0;
        for(int i = 0; i < 26; i++) cnt[i] = 0;
        for(int i = n - 2; i >= 1; i--) {
            if(b[i] == key && c[i + 1] != key) ans = 1;
            if(b[i] != key && (num - cnt[key - 'a'] - cnt[b[i] - 'a'])) { ans = 0; break; }
            if(b[i] != key) ans = 1;
            num -= cnt[c[i] - 'a'];
            cnt[c[i] - 'a'] = 1;
            num += cnt[c[i] - 'a'];
        }
        cout << ans << '\n';
    }

    return 0;
}

T2 perm

给定一个二元组序列 \(\{(a_i,b_i)\}\)，你需要对它进行一次重排，最小化：

\[ 2\sum_{j<i}[a_j>a_i](b_i-b_j)^2+\sum_{j<i}[a_j=a_i](b_i-b_j)+\sum_{j<i}[a_j=a_i](b_i-b_j)^2 \]

并输出最小值。

\(n\le 10^6\)

注意到原式第三项和顺序无关，只考虑前两项。发现若按 \(a\) 升序排序，则第一项取为 \(0\)；相同时按 \(b\) 降序排序，可以使第二项取到最小值。

至于答案的计算，对每一段 \(a\) 相同的段，记一个前缀的 \(s_0=\sum 1,\ s_1=\sum b_i,\ s_2=\sum b_i^2\) 即可。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1e6 + 10;

int n, ans;
int a[N], b[N];

int swp[N], tmp[N];

signed main() {

    freopen("perm.in", "r", stdin);
    freopen("perm.out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];

    for(int i = 1; i <= n; i++) swp[i] = i;
    sort(swp + 1, swp + 1 + n, [](int x, int y) {
        if(a[x] != a[y]) return a[x] < a[y];
        return b[x] > b[y];
    });

    for(int i = 1; i <= n; i++) tmp[i] = a[i];
    for(int i = 1; i <= n; i++) a[i] = tmp[swp[i]];
    for(int i = 1; i <= n; i++) tmp[i] = b[i];
    for(int i = 1; i <= n; i++) b[i] = tmp[swp[i]];

    int s0, s1, s2;
    for(int i = 1; i <= n; i++) {
        if(a[i] != a[i - 1]) {
            s0 = s1 = s2 = 0;
        } else {
            ans += b[i] * s0 - s1 + b[i] * b[i] * s0 + s2 - 2 * b[i] * s1;
        }
        s0 += 1;
        s1 += b[i];
        s2 += b[i] * b[i];
    }

    cout << ans << '\n';

    return 0;
}

T3 str

给定两个字符串数组 \(S,T\)，其中 \(S\) 包含 \(n\) 项，\(T\) 包含 \(m\) 项。将 \(S\) 中的串和 \(T\) 中的串两两拼接，\(S\) 的串在前面。问所有新串中奇回文串数量之和。

\(n,m\le 10^5\)，输入字符总数少于 \(2\times 10^6\)

拼接后，完全包含于拼接前两个串内部的奇回文串产生的贡献等于 \(m-1\) 倍的 \(S_i\) 奇回文串数量之和加上 \(n-1\) 倍的 \(T_i\) 奇回文串数量之和。现在只考虑横跨两个串的奇回文串即可。

不妨设拼接时 \(|S_i|\le |T_i|\)。先将所有 \(S_i\) 颠倒，然后对每个 \(t=T_i\) 考虑其所有奇回文前缀，记剩下的后缀为 \(x\)，那么一个 \(x\) 产生的贡献为 \(\sum_{i=1}^{n}\operatorname{lcp}(S_i,x)\)。

这种 \(\operatorname{lcp}\) 双层求和可以直接使用后缀数组。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cassert>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int S = 2e6 + 100 + N;

int T, n, m, ss;
string s[N], t[N];

string str;

int z[S];

int p[S], q[S], np, nq;

namespace SA {
    int n, m;
    int sa[S], rk[S], cnt[S], tp[S];
    int ht[S];
    int mnl[S], mnr[S], sta[S], top; 
    void sort() {
        for(int i = 1; i <= m; i++) cnt[i] = 0;
        for(int i = 1; i <= n; i++) ++cnt[rk[i]];
        for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
    }
    void get_SA() {
        n = str.size();
        m = 127;
        for(int i = 1; i <= n; i++) rk[i] = str[i - 1];
        for(int i = 1; i <= n; i++) tp[i] = i;
        sort();
        for(int w = 1; w < n; w <<= 1) {
            int p = 0;
            for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
            for(int i = 1; i <= n; i++) {
                if(sa[i] > w) tp[++p] = sa[i] - w;
            }
            sort();
            for(int i = 1; i <= n; i++) tp[i] = rk[i];
            rk[sa[1]] = 1;
            for(int i = 2; i <= n; i++) {
                if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
                    rk[sa[i]] = rk[sa[i - 1]];
                } else rk[sa[i]] = rk[sa[i - 1]] + 1;
            } 
            m = rk[sa[n]];
            if(m == n) break;
        } 
    }
    void get_height() {
        for(int i = 0; i <= n + 2; i++) mnl[i] = mnr[i] = ht[i] = 0;
        int k = 0;
        for(int i = 1; i <= n; i++) {
            if(rk[i] == 1) continue;
            k -= (bool)k;
            int j = sa[rk[i] - 1];
            int lim = min(n - j + 1, n - i + 1);
            while(k < lim && str[i + k - 1] == str[j + k - 1] && str[i + k - 1] != '$') ++k;
            ht[rk[i]] = k;
        }
        top = 0;
        for(int i = 2; i <= n; i++) {
            while(top && ht[sta[top]] > ht[i]) --top;
            if(top) mnl[i] = sta[top] + 1;
            else mnl[i] = 2;
            sta[++top] = i;
        }
        top = 0;
        for(int i = n; i >= 2; i--) {
            while(top && ht[sta[top]] >= ht[i]) --top;
            if(top) mnr[i] = sta[top] - 1;
            else mnr[i] = n;
            sta[++top] = i;
        }
    }
    int sp[S], sq[S];
    int calc() {
        int res = 0;
        for(int i = 1; i <= n; i++) sp[i] = sq[i] = 0;
        for(int i = 1; i <= np; i++) sp[rk[p[i] + 1]]++;
        for(int i = 1; i <= nq; i++) sq[rk[q[i] + 1]]++;
        for(int i = 1; i <= n; i++) sp[i] += sp[i - 1];
        for(int i = 1; i <= n; i++) sq[i] += sq[i - 1];
        for(int i = 2; i <= n; i++) {
            int x = sp[i - 1] - sp[mnl[i] - 2];
            int y = sq[mnr[i]] - sq[i - 1];
            res += x * y * ht[i];
        }
        for(int i = 2; i <= n; i++) {
            int x = sq[i - 1] - sq[mnl[i] - 2];
            int y = sp[mnr[i]] - sp[i - 1];
            res += x * y * ht[i];
        }
        return res;
    }
}

int work() {
    ss = 0;
    int res = 0;
    for(int i = 1; i <= n; i++) ss += s[i].size() + 1;
    for(int i = 1; i <= n; i++) reverse(s[i].begin(), s[i].end());
    for(int i = 1; i <= n; i++) str += "$", str += s[i];
    for(int i = 1; i <= m; i++) str += "$", str += t[i];
    for(int i = 0; i < str.size(); i++) z[i] = 0;
    str += "$";
    for(int i = 0, k = 0; i < str.size(); i++) {
        if(str[i] == '$') continue;
        if(i <= k + z[k]) z[i] = min(k + z[k] - i, z[2 * k - i]);
        int lim = min((int)str.size() - 1 - i, i);
        while(z[i] < lim && str[i + z[i] + 1] == str[i - z[i] - 1] && str[i + z[i] + 1] != '$') ++z[i];
        if(i + z[i] > k + z[k]) k = i;
    }
    for(int i = 0; i < ss; i++) {
        if(str[i] != '$') res += (z[i] + 1) * m;
    }
    for(int i = ss; i < str.size(); i++) {
        if(str[i] != '$') res += (z[i] + 1) * n;
    }
    SA::get_SA();
    SA::get_height();
    np = nq = 0;
    for(int i = 1; i < ss; i++) {
        if(str[i - 1] == '$') p[++np] = i;
    }
    for(int i = ss; i < str.size(); i++) {
        if(str[i] == '$') continue;
        if(str[i - z[i] - 1] == '$' && str[i + z[i] + 1] != '$') q[++nq] = i + z[i] + 1; 
    }
    res += SA::calc();
    np = nq = 0;
    for(int i = 1; i < ss; i++) {
        if(str[i] == '$') continue;
        if(str[i - z[i] - 1] == '$' && str[i + z[i] + 1] != '$') p[++np] = i + z[i] + 1; 
    }
    for(int i = ss; i < str.size(); i++) {
        if(str[i - 1] == '$') q[++nq] = i;
    }
    res += SA::calc();
    return res;
}

void clear() {
    str.clear();
}

signed main() {

    freopen("str.in", "r", stdin);
    freopen("str.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0); 

    cin >> T;
    while(T--) {
        cin >> n >> m;
        clear();
        for(int i = 1; i <= n; i++) cin >> s[i];
        for(int i = 1; i <= m; i++) cin >> t[i];
        cout << work() << '\n'; 
    }

    return 0;
}

我们还有另一种处理方法。考虑将所有翻转后的 \(s\) 建出 Trie，对于 \(t\) 的一个回文前缀剩下的一个后缀，通过哈希二分出极长存在于 Trie 上的前缀，然后求链上的子树和的和是容易的（因为树是静态的）。

T4 ggd

给定 \(n\) 个人，每个人都是两种角色（鸭，鹅）中的一种。现在 \(n\) 个人之间连了一些有向边（没有重边）。定义一个无序点对 \((x,y)\) 的权值：

若两者没有连边，则权值为 \(0\)；
若两者双向连边，则两者的角色必须不同，权值为鹅的权值；
若仅存在单向连边：
- 若两者身份不同，权值为 \(a_x^2+a_y^2\)；
- 否则，若都是鹅，权值为 \((a_x+a_y)^2\)；
- 否则，权值为 \((a_x-a_y)^2\)；

给定常数 \(k\)，请你选择恰好 \(k\) 个人作为鸭子，其他人为鹅，最大化权值之和。

\(n\le 1000,\ |a_i|\le 1000\)

对于双向边进行二分图染色是显然的，图会形成若干连通块，每个连通块都只有两种选择，两种选择在连通块内部也有一定的权值。

考虑如何处理横跨连通块的单向边的贡献。显然我们希望不存在这种边，这样连通块之间就相互独立了，直接背包即可。

将后两个贡献二项式展开，写成表格：

x \ y	鹅	鸭
鹅	\(a_x^2+a_y^2+2a_xa_y\)	\(a_x^2+a_y^2\)
鸭	\(a_x^2+a_y^2\)	\(a_x^2+a_y^2-2a_xa_y\)

然后就很直观了！我们可以将单向边的贡献拆成 \((a_x^2\pm a_xa_y)+(a_y^2\pm a_xa_y)\)，其中两个加减号取决于双方的类型。即使贡献中包含另一方的权值也无所谓，因为我们只需要本方的权值和另一方的类型无关即可。

时间复杂度 \(O(nk)\)。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f3f3f3f3f3f;

int n, k;
int a[N];
int adj[N][N];

int vis[N], col[N], nn;
int sum[N][2], cnt[N][2];

void dfs(int u) {
    vis[u] = nn;
    cnt[nn][col[u]]++;
    for(int v = 1; v <= n; v++) {
        if(u == v) continue;
        if(adj[u][v] && adj[v][u]) {
            if(vis[v] && col[v] == col[u]) { cout << "NO\n"; exit(0); }
            sum[nn][col[u] ^ 1] += a[u];
            if(!vis[v]) col[v] = col[u] ^ 1, dfs(v);
        } else if(adj[u][v] || adj[v][u]) {
            sum[nn][col[u] ^ 1] += a[u] * (a[u] + a[v]);
            sum[nn][col[u]] += a[u] * (a[u] - a[v]);
        }
    }
}

int f[N][N], g[N][N];
int s[N];

signed main() {

    freopen("ggd.in", "r", stdin);
    freopen("ggd.out", "w", stdout);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> adj[i][j];
        }
    }

    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            ++nn;
            dfs(i);
        }
    }

    for(int i = 1; i <= k; i++) f[0][i] = -INF;
    for(int i = 1; i <= nn; i++) {
        for(int j = 0; j <= k; j++) f[i][j] = -INF;
        for(int j = 0; j <= k; j++) {
            if(j >= cnt[i][0]) {
                int tmp = f[i - 1][j - cnt[i][0]] + sum[i][0];
                if(tmp > f[i][j]) {
                    f[i][j] = tmp;
                    g[i][j] = 0;
                }
            }
            if(j >= cnt[i][1]) {
                int tmp = f[i - 1][j - cnt[i][1]] + sum[i][1];
                if(tmp > f[i][j]) {
                    f[i][j] = tmp;
                    g[i][j] = 1;
                }
            }
        }
    }

    if(f[nn][k] < 0) { cout << "NO\n"; exit(0); }
    cout << "YES\n";

    int cur = k;
    for(int i = nn; i >= 1; i--) {
        s[i] = g[i][cur];
        cur -= cnt[i][g[i][cur]];
    }

    for(int i = 1; i <= n; i++) {
        cout << !(col[i] ^ s[vis[i]]) << ' ';
    }
    cout << '\n';

    return 0;
}