广州大学第十七届ACM大学生程序设计竞赛题解

很感谢各位参加本次同步赛，由于出题人水平有限，如果体验不好深感抱歉。

A 萤火虫

由于2操作可以将一个数改变成任意值，所以可以交换操作1和操作2的顺序，先进行完操作2再进行操作1，使得序列全0。记$s_i=\sum h_j[j\mathrm{\%}k=i]s\_i=\backslash sum\; h\_j[j\backslash \%k=i]$，只通过操作1能使得数列全部变成0，当且仅当$s_0=s_1=\mathrm{.}\mathrm{.}\mathrm{.}=s_{k-1}s\_0=s\_1=...=s\_\{k-1\}$。

每次操作1相当于对所有$s_{i}s\_i$加减同一个数，假如一开始$s_0=s_1=\mathrm{.}\mathrm{.}\mathrm{.}=s_{k-1}s\_0=s\_1=...=s\_\{k-1\}$，通过若干次操作1贪心把前n-k个数变成0后，剩下k个数每个数对应一个$s_{i}s\_i$，剩下k个数相等，所以能将其全部变成0。

假如数组每个元素都为0，通过若干次操作1后，$s_0=s_1=\mathrm{.}\mathrm{.}\mathrm{.}=s_{k-1}s\_0=s\_1=...=s\_\{k-1\}$仍然满足。

所以只需通过操作2让$s_0=s_1=\mathrm{.}\mathrm{.}\mathrm{.}=s_{k-1}s\_0=s\_1=...=s\_\{k-1\}$即可，每次改变一个数就能使$s_{i}s\_i$变成任意值。 所以答案为$min(k-cnt[s_i]),0\le i\le k-1min(k-cnt[s\_i]),0\backslash le\; i\backslash le\; k-1$

标程：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int n, k, s[N];
void work() {
    for (int i = 0; i < k; ++i)s[i] = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        s[i % k] += x;
    }
    sort(s, s + k);
    int len = 0, mxlen = 0;
    for (int i = 0; i < k; ++i) {
        if (i > 0 && s[i] == s[i - 1])len++;
        else {
            mxlen = max(mxlen, len);
            len = 1;
        }
    }
    mxlen = max(mxlen, len);
    cout << k - mxlen << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) {
        work();
    }
}

B 罗伯特

假如可以在任意时刻加入标志，那么设$dp[i][j][k][l]dp[i][j][k][l]$为到达点$i,ji,j$，放置过的标志次数为$kk$,方向为$ll$的最短距离，进行bfs即可。

注意到bfs过程中没有记录之前放置标志的位置，因为如果遇到之前放置的标记，说明走了一个环，走的这段环是没有意义的。

bfs跑出一条最短路，然后把路径上需要放置的标志改成在一开始的时候放置，在路径上从起点到终点移动。发现不会遇到在经过该点之后才放置的标志。因为之后经过该点时就是按标志走，可以直接在第一次经过该点时就按标志走。 时间复杂度$O(4\ast n\ast m\ast p)O(4*n*m*p)$，如果用$dijdij$多一个log

标程：

#include<bits/stdc++.h>
using namespace std;
struct State {
    int d, x, y, c, f;
    bool operator<(const State& b) const {
        return d > b.d;
    }
};
int dis[110][110][60][4], dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
bool vis[110][110][60][4];
char mp[110][110];
pair<int, int>convey[110][110];
void work() {
    int n, m, k, p; cin >> n >> m >> k >> p;
    while (k--) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        convey[x1][y1] = { x2,y2 };
        convey[x2][y2] = { x1,y1 };
    }
    for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) {
        cin >> mp[i][j];
        if (mp[i][j] == 'U')mp[i][j] = '0';
        if (mp[i][j] == 'R')mp[i][j] = '1';
        if (mp[i][j] == 'D')mp[i][j] = '2';
        if (mp[i][j] == 'L')mp[i][j] = '3';
    }
    for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)for (int k = 0; k <= p; ++k)for (int l = 0; l < 4; ++l)dis[i][j][k][l] = 1e9;
    dis[1][1][0][1] = 0;
    priority_queue<State>Q;
    Q.push({ 0,1,1,0,1 });
    while (Q.size()) {
        State s = Q.top(); Q.pop();
        if (vis[s.x][s.y][s.f][s.c])continue;
        vis[s.x][s.y][s.f][s.c] = 1;
        if (mp[s.x][s.y] == '.') {
            for (int i = 0; i < 4; ++i) {
                int nx = s.x + dx[i], ny = s.y + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] != '#') {
                    int nf = i, nc = s.c + (s.f != i);
                    if (convey[nx][ny].first != 0) {
                        auto q = convey[nx][ny];
                        nx = q.first, ny = q.second;
                    }
                    if (nc <= p && dis[nx][ny][nc][nf] > dis[s.x][s.y][s.c][s.f] + 1) {
                        dis[nx][ny][nc][nf] = dis[s.x][s.y][s.c][s.f] + 1;
                        Q.push({ dis[nx][ny][nc][nf],nx,ny,nc,nf });
                    }
                }
            }
        }
        if (mp[s.x][s.y] >= '0' && mp[s.x][s.y] <= '3' || mp[s.x][s.y] == '@') {
            int i = mp[s.x][s.y] - '0';
            if (mp[s.x][s.y] == '@')i = s.f;
            int nx = s.x + dx[i], ny = s.y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] != '#') {
                int nf = i, nc = s.c;
                if (convey[nx][ny].first != 0) {
                    auto q = convey[nx][ny];
                    nx = q.first, ny = q.second;
                }
                if (nc <= p && dis[nx][ny][nc][nf] > dis[s.x][s.y][s.c][s.f] + 1) {
                    dis[nx][ny][nc][nf] = dis[s.x][s.y][s.c][s.f] + 1;
                    Q.push({ dis[nx][ny][nc][nf],nx,ny,nc,nf });
                }
            }
        }
    }
    int ans = 1e9;
    for (int c = 0; c <= p; ++c) {
        for (int f = 0; f < 4; ++f) {
            ans = min(ans, dis[n][m][c][f]);
        }
    }
    if (ans == 1e9) {
        cout << "NO\n"; return;
    }
    cout << "YES\n" << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    work();
}

C 论AE自动化的重要性

把材料合成画成图，得到一张拓扑图。

$cc$个$xx$生成一个$yy$，从$xx$往$yy$加边，边权$cc$，没有入边说明无法通过合成得到，为合成起点。

bfs或者dfs跑一遍。

标程1：

#include <bits/stdc++.h>
//#include <Windows.h>
#include <iostream>
#include <fstream>
#include <ext/pb_ds/trie_policy.hpp>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define inf std::numeric_limits<ll>::max()
//#define in read()
#define pb push_back
//#define out(x) write(x);
using namespace __gnu_pbds;
using namespace std;
const ld PI = acos(-1.0);
#define Please return
#define AC 0
struct _IO
{
    _IO()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
} _io;
const ll mod=1e9+7;
ll qpow(ll n,ll k){
    ll ans=1;
    while(k){
        if(k&1){
            ans*=n;
            ans%=mod;
        }
        n*=n;
        n%=mod;
        k>>=1;
    }
    return ans;
}
const int maxn=1e5+7;
vector<pair<ll,ll>>edge[maxn];
ll v[maxn];
ll d[maxn];


int main()
{
    ll n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        edge[i].clear();
        v[i]=0;
        d[i]=0;
    }
    for(int i=0;i<k;i++){
        ll a,b;
        cin>>a>>b;
        v[a]+=b;
    }
    for(int i=0;i<m;i++){
        ll x,y,c;
        cin>>x>>y>>c;
        edge[y].push_back({x,c});
        d[x]++;
    }
    queue<ll> q;
    for(int i=1;i<=n;i++){
        if(d[i]==0){
            q.push(i);
        }
    }
    ll ans=0;
    while(!q.empty()){
        ll x=q.front();
        q.pop();
        ans+=v[x];
        ans%=mod;
        for(auto y:edge[x]){
            d[y.first]--;
            if(d[y.first]==0){
                q.push(y.first);
            }
            v[y.first]+=v[x]*y.second;
            v[y.first]%=mod;
        }
    }
    cout<<ans<<endl;
}

标程2：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
#define Ve(T) vector<T>
#define VVe(T) vector<vector<T>>

const ll mod = 1e9+7;
ll add(ll &x, ll y) { return x = (x + y + mod) % mod; }
ll mul(ll x, ll y) { return (x * y) % mod; }
ll sub(ll x, ll y) { return (x - y + mod) % mod; }

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    Ve(pii) v(k);
    for(auto &[i, j]:v) cin >> i >> j, i--;  //  i need js
    VVe(pii) e(n);
    for(int x,y,c,i=0; i<m; i++) {
        cin >> x >> y >> c; x--, y--;
        e[y].push_back({x, c});          //  x->y cnt==c
    }
    Ve(ll) dp(n, 0);
        function<void(int)> dfs = [&](int u) {
            if(dp[u]) return void();
            if(e[u].size()==0) return dp[u] = 1, void();
            ll res = 1;
            for(auto [v, c]:e[u]) dfs(v), add(res, mul(dp[v], c));
            dp[u] = res;
        };
    for(int i=0; i<n; i++) if(!dp[i]) dfs(i);
    ll ans = 0;
    for(auto [i,j]:v) add(ans, mul(dp[i], j));
    cout << ans << '\n';
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

D 轻音部的毕业旅行

u和v建边，边权c，得到无向带权图。

首先考虑从x飞往y的贡献，分析题意，这个贡献就是x到y的所有 路径上最大边权 的最小值，即最小瓶颈路上的最大边权。 按克鲁斯卡尔建最小生成树的顺序，求最小生成树链上的最大值，倍增，树剖或者dfs序都可以（标程2）。 或者建克鲁斯卡尔重构树，u和v的lca即为最小瓶颈路上的最大边权（标程1）。

询问先预处理1到n的贡献前缀和，然后每次求差分即可。

标程1：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge {
    int u, v, c;
};
bool cmp(const Edge &e_l, const Edge &e_r) { return e_l.c < e_r.c; }

struct KruskalTree {
    int n, m;
    vector<Edge> e;
    vector<vector<pair<int,int>>> eg;
    vector<int> dsu_fa, lca_dep;
    vector<vector<int>> lca_fa, lca_ma;
    void init() {
        e.resize(m+1); dsu_fa.reserve(n+2); eg.resize(n+2); lca_dep.resize(n+2);
        lca_fa.resize(n+2); lca_ma.resize(n+2);
        for(int i=0; i<=n; i++) lca_fa[i].resize(22), lca_ma[i].resize(22), dsu_fa[i] = i;
    }
    int dsu_find(int x) { return dsu_fa[x]==x?x:dsu_fa[x]=dsu_find(dsu_fa[x]); }
    void dsu_merge(int x, int y) { dsu_fa[x] = y; }
    void add(int u, int v, int c) { eg[u].push_back({v, c}); eg[v].push_back({u, c}); }
    void kruskal() {
        sort(e.begin(), e.end(), cmp);
        for(int i=1; i<=m; i++) {
            int x = dsu_find(e[i].u), y = dsu_find(e[i].v);
            if(x!=y) dsu_merge(x, y), add(e[i].u, e[i].v, e[i].c);
        }
    }
    void lca_dfs(int u) {
        for(int i=1; i<=18; i++) {
            lca_fa[u][i] = lca_fa[lca_fa[u][i-1]][i-1];
            lca_ma[u][i] = max(lca_ma[u][i-1], lca_ma[lca_fa[u][i-1]][i-1]);
        }
        for(auto [v, c]:eg[u]) { //  c++14
            if(v != lca_fa[u][0]) lca_fa[v][0] = u, lca_ma[v][0] = c, lca_dep[v] = lca_dep[u] + 1, lca_dfs(v);
        }
    }
    int lca_query(int u, int v) {
        int maxn = 0;
        if(lca_dep[u] < lca_dep[v]) swap(u, v);
        for(int i=18; i>=0; i--) {
            if(lca_dep[lca_fa[u][i]] >= lca_dep[v]) maxn = max(maxn, lca_ma[u][i]), u = lca_fa[u][i];
        }
        if(u == v) return maxn;
        for(int i=18; i>=0; i--) {
            if(lca_fa[u][i] != lca_fa[v][i]) {
                maxn = max({maxn, lca_ma[u][i], lca_ma[v][i]});
                u = lca_fa[u][i];
                v = lca_fa[v][i];
            }
        }
        maxn = max({maxn, lca_ma[u][0], lca_ma[v][0]});
        return maxn;
    }
} g;

void solve()
{
    cin >> g.n >> g.m;
    g.init();
    for(int i=1; i<=g.m; i++) cin >> g.e[i].u >> g.e[i].v >> g.e[i].c;
    g.kruskal(); g.lca_dep[1] = 1; g.lca_dfs(1);
    vector<ll> sum(g.n+2, 0);
    for(int i=2; i<=g.n; i++) sum[i] = sum[i-1] + g.lca_query(i-1, i);
    int q, l, r;
    cin >> q;
    auto query = [&](int l, int r) { return sum[r] - sum[l]; };
    while(q--) {
        cin >> l >> r;
        cout << query(l, r) << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

标程2：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define ll long long
int n, m;
struct Edge {
    int x, y, w;
    bool operator<(const Edge& b) {
        return w < b.w;
    }
};
Edge e[N];
vector<pair<int, int>> E[N];
int Fa[21][N], W[21][N], Dep[N];
ll s[N];
int fa[N];
int find(int x) {
    if (x == fa[x])return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}
void dfs(int u, int fa) {
    Dep[u] = Dep[fa] + 1;
    for (auto& p : E[u]) {
        int v = p.first, w = p.second;
        if (v == fa)continue;
        Fa[0][v] = u; W[0][v] = w;
        for (int i = 1; i < 21; ++i) {
            Fa[i][v] = Fa[i - 1][Fa[i - 1][v]];
            W[i][v] = max(W[i - 1][v], W[i - 1][Fa[i - 1][v]]);
        }
        dfs(v, u);
    }
}
int cal(int u, int v) {
    int mx = 0;
    if (Dep[u] < Dep[v])swap(u, v);
    for (int i = 20; i >= 0; --i) {
        if (Dep[Fa[i][u]] >= Dep[v])mx = max(mx, W[i][u]), u = Fa[i][u];
    }
    if (u == v)return mx;
    for (int i = 20; i >= 0; --i) {
        if (Fa[i][u] != Fa[i][v]) {
            mx = max(mx, W[i][u]);
            mx = max(mx, W[i][v]);
            u = Fa[i][u], v = Fa[i][v];
        }
    }
    mx = max(mx, W[0][u]);
    mx = max(mx, W[0][v]);
    return mx;
}
void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x, y, w; cin >> x >> y >> w;
        e[i] = { x,y,w };
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; ++i) {
        if (find(e[i].x) != find(e[i].y)) {
            E[e[i].x].push_back({ e[i].y,e[i].w });
            E[e[i].y].push_back({ e[i].x,e[i].w });
            merge(e[i].x, e[i].y);
        }
    }
    dfs(1, 0);
    for (int i = 1; i < n; ++i) {
        s[i] = cal(i, i + 1);
        s[i] += s[i - 1];
    }
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        if (l > r)swap(l, r);
        r--;
        cout << s[r] - s[l - 1] << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; T = 1;
    while (T--) {
        work();
    }
}

E 灰之魔女裁魔法树

按题意模拟即可，详见代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int d[11], n, m, k, h[N];
void update() {
    for (int i = k; i >= 1; --i) {
        if (d[i])h[d[i]]++;
        d[i] = d[i - 1];
    }
}
void add(int x) {
    d[1] = x;
    for (int i = 2; i <= k; ++i) {
        if (d[i] == x)d[i] = 0;
    }
}
void del(int x) {
    for (int i = 1; i <= k; ++i)if (d[i] == x)d[i] = 0;
}
void work() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
        int op, x; cin >> op >> x;
        if (op == 1) {
            add(x);
        }
        else if (op == 2) {
            del(x);
        }
        else {
            cout << h[x] + i - 1 << '\n';
        }
        update();
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) {
        work();
    }
}

F GZHUACM

按要求输出即可，\注意转义，可以利用c++11的原生字符串。

时间复杂度 $O(1)O(1)$ 。

标程：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    cout << R"(                     ,----,        ,--,                                                  ____
  ,----..          .'   .`|      ,--.'|                 ,---,         ,----..          ,'  , `.
 /   /   \      .'   .'   ;   ,--,  | :         ,--,   '  .' \       /   /   \      ,-+-,.' _ |
|   :     :   ,---, '    .',---.'|  : '       ,'_ /|  /  ;    '.    |   :     :  ,-+-. ;   , ||
.   |  ;. /   |   :     ./ |   | : _' |  .--. |  | : :  :       \   .   |  ;. / ,--.'|'   |  ;|
.   ; /--`    ;   | .'  /  :   : |.'  |,'_ /| :  . | :  |   /\   \  .   ; /--` |   |  ,', |  ':
;   | ;  __   `---' /  ;   |   ' '  ; :|  ' | |  . . |  :  ' ;.   : ;   | ;    |   | /  | |  ||
|   : |.' .'    /  ;  /    '   |  .'. ||  | ' |  | | |  |  ;/  \   \|   : |    '   | :  | :  |,
.   | '_.' :   ;  /  /--,  |   | :  | ':  | | :  ' ; '  :  | \  \ ,'.   | '___ ;   . |  ; |--'
'   ; : \  |  /  /  / .`|  '   : |  : ;|  ; ' |  | ' |  |  '  '--'  '   ; : .'||   : |  | ,
'   | '/  .'./__;       :  |   | '  ,/ :  | : ;  ; | |  :  :        '   | '/  :|   : '  |/
|   :    /  |   :     .'   ;   : ;--'  '  :  `--'   \|  | ,'        |   :    / ;   | |`-'
 \   \ .'   ;   |  .'      |   ,/      :  ,      .-./`--''           \   \ .'  |   ;/
  `---`     `---'          '---'        `--`----'                     `---`    '---')";
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

G Clannad

题意要在 $[1,x][1,x]$ 这 $xx\%$ 个整数里不重复地选 $n+1n+1$ 个整数，使得存在两个的差的绝对值为 $nn$ 的倍数。

假如我们把选出来的 $n+1n+1$ 个整数对 $nn$ 取模，会得到 $n+1n+1$ 个余数，那么根据鸽雀原理，必然存在两个余数相同，余数相同，说明它们的差恰好为 $nn$ 的倍数。

于是问题转换成，从 $xx$ 个整数里不重复地取 $n+1n+1$ 个整数出来，即 $C_x^{n+1}C\_\{x\}^\{n+1\}$，预处理组合数，特判 $n+1>xn+1>x$ 即可。

时间复杂度：预处理 $O(n^2)O(n^2)$ ，单次询问 $O(1)O(1)$ ，总的复杂度 $O(n^2)+O(T)O(n^2)+O(T)$ 。

标程：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5050;
const int mod = 1e9+7;
ll C[N+2][N+2];
void Init()
{
    for(int i=0; i<=N; i++) {
        C[i][0] = 1;
        for(int j=1; j<=i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
        }
    }
}
ll Cal(int n, int m) { return C[m][n]; }
void solve()
{
    int n, x;
    cin >> n >> x;
    n++;
    if(x < n) return cout << "-1\n", void();
    else return cout << Cal(n, x) << "\n", void();
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    Init();
    while(T--) {
        solve();
    }
    return 0;
}

H 性格差劲的久美子

由于出题人水平不足以及疏忽，导致H题数据有误以及题面描述不清晰，对大家造成不好的体验，我们深感歉意。数据已经修改，如果对题目有什么问题，欢迎大家在同步赛评论区指正。

题意：从A中选择一个子序列，且该子序列与B的lcs不超过1，求A中选择的子序列的最长长度。

首先若$AA$有某个元素在$BB$中不存在，一定可取，设这样的元素个数为$cntcnt$。 再考虑其余的元素，定义$(L[x],R[x])(L[x],R[x])$表示$xx$在$bb$中出现的区间，对于$aa$中的某个序列，假设之前已取了$xx$，能接着取$yy$需满足$R[y]\le L[x]R[y]\backslash le\; L[x]$，答案就是最长不增子序列长度+cnt

标程：

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int N = 2e5 + 10;
int s[N], t[N], n, m;
int Tr[N];
void add(int x, int v) {
    while (x) {
        Tr[x] = max(Tr[x], v);
        x -= lowbit(x);
    }
}
int ask(int x) {
    int ans = 0;
    while (x < N) {
        ans = max(Tr[x], ans);
        x += lowbit(x);
    }
    return ans;
}
void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i)cin >> s[i];
    cin >> m;
    for (int i = 1; i <= m; ++i)cin >> t[i];
    map<int, pair<int, int>> p;
    for (int i = 1; i <= m; ++i) {
        if (p[t[i]].first == 0)p[t[i]] = { i,i };
        else p[t[i]].second = max(p[t[i]].second, i);
    }
    int ans = 0, tot = 0;
    for (int i = 1; i <= n; ++i) {
        if (p.find(s[i]) == p.end())tot++;
        else {
            int res = ask(p[s[i]].second) + 1;
            ans = max(ans, res);
            add(p[s[i]].first, res);
        }
    }
    cout << ans + tot << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    work();
}

I Min And Max

答案最小值为从大到小逆序。相邻$w_i\ge w_{j}w\_i\backslash ge\; w\_j$，$r_i=l_{j}r\_i=l\_j$。

下面计算最大值： 计算最大浪费空间和$ss$，相邻的对$ss$有贡献，最大贡献为$w_j-w_{i}w\_j-w\_i$，且正值和负值数量相同，每个数只能被加一次和减一次，所以$ss$最大值为$nn$个数里面找到$\lfloor \frac{n}{2}\rfloor \backslash left\; \backslash lfloor\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rfloor$个数+，$\lfloor \frac{n}{2}\rfloor \backslash left\; \backslash lfloor\; \backslash frac\{n\}\{2\}\; \backslash right\; \backslash rfloor$个数-，因为超过的正负值相互抵消。

所以最大值s+$\sum w_i\backslash sum\; w\_i$，构造方法大致为$2^0\mathrm{，}{2}^{mx}\mathrm{，}{2}^1\mathrm{，}{2}^{mx-1}\mathrm{.}\mathrm{.}\mathrm{.}2^0\; ，2^\{mx\}\; ，2^1\; ，2^\{mx-1\}...$。

标程：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N = 1e5 + 10;
ll v[N];
void work() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        v[i] = (1 << x);
    }
    sort(v + 1, v + 1 + n);
    ll ans = 0, s = 0;
    for (int i = 1; i <= n; ++i) {
        if (i > (n + 1) / 2)ans += v[i] * 2;
        s += v[i];
    }
    if (n & 1)ans += v[(n + 1) / 2];
    cout << s << ' ' << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    work();
}

J 原舟二象性

fft即可，详见代码

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define inf std::numeric_limits<ll>::max()
#define pb push_back
using namespace __gnu_pbds;
using namespace std;
const ld PI = acos(-1.0);
#define Please return
#define AC 0
struct _IO
{
    _IO()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
} _io;
const ll mod=998244353;
ll qpow(ll n,ll k){
    ll ans=1;
    while(k){
        if(k&1){
            ans*=n;
            ans%=mod;
        }
        n*=n;
        n%=mod;
        k>>=1;
    }
    return ans;
}
const double eps=1e-6;
const ll maxn=4e5+7;
complex<double> a[maxn];
ll n,m;
ll l,r[maxn];
ll limit=1;
void fft(complex<double> *A,ll type)
{
    for(int i=0;i<limit;i++) 
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1;mid<limit;mid<<=1)
    {
        complex<double> Wn( cos(PI/mid) , type*sin(PI/mid) ); 
        for(int R=mid<<1,j=0;j<limit;j+=R)
        {
            complex<double> w(1,0);
            for(int k=0;k<mid;k++,w=w*Wn)
            {
                 complex<double> x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}


int main()
{
    cin>>n;
    n--;
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    while(limit<=n*2) limit<<=1,l++;
    for(int i=0;i<limit;i++)
        r[i]= ( r[i>>1]>>1 )| ( (i&1)<<(l-1) ) ;
    fft(a,1);
    for(int i=0;i<=limit;i++) a[i]=a[i]*a[i];
    fft(a,-1);
    int ans=1;
    for(int i=0;i<=n*2;i++){
        if((real(a[i])/limit)>eps){
            ans*=1;
        }
        else if((real(a[i])/limit)<-eps){
            ans*=-1;
        }
        else{
            ans*=0;
        }
    }
    if(ans==1){
        cout<<"woc yuan"<<endl;
    }
    else if(ans==-1){
        cout<<"woc zhou"<<endl;
    }
    else{
        cout<<"woc nong"<<endl;
    }
}

K 因子模仿 - easy version

容易发现，答案只取决于 $s_{r}s\_r$ ，为 $11$ 则茉美香胜利，为 $00$ 则对手胜利。

问题转化成，单点询问，和维护区间 $0101$ 异或，这里列两种解法。

解法1

维护区间 $11$ 个数，若区间长度 $lenlen$ ，区间 $11$ 个数为 $xx$ ，那么异或时相当于把 $xx$ 修改为 $len-xlen-x$ ，以线段树为例。

标程：

#include <bits/stdc++.h>
using namespace std;

//  Template: std::cout argument list
template<typename T>
void f_o(const T& arg) { std::cout << arg << '\n'; }
template<typename T, typename... Ty_>
void f_o(const T& f_arg, const Ty_&... args) { std::cout << f_arg << ' '; f_o(args...); }
typedef long long ll;

//  Modular addition and multiplication
const ll mod = 1e9+7;
ll add(ll &x, ll y) { return x = (x + y + mod) % mod; }
ll mul(ll x, ll y) { return (x * y) % mod; }


//  Max Size
const int N = 1e6+5;


//  SegmentTree Node
struct Node {
    int l, r;
    int cnt;
    bool lazy;
};

//  SegmentTree with Lazytag
struct Segment_lazytree {
#define ls (rt<<1)
#define rs (rt<<1)|1
#define lson ls,l,mid
#define rson rs,mid+1,r
    Node t[N<<2];
    bool s[N];
    void flip(int rt) { t[rt].cnt = t[rt].r-t[rt].l+1 - t[rt].cnt; }
    void push_up(int rt) { t[rt].cnt = t[ls].cnt + t[rs].cnt; }
    void push_down(int rt) {
        if(t[rt].lazy) {
            flip(ls);   t[ls].lazy ^= 1;
            flip(rs);   t[rs].lazy ^= 1;
            t[rt].lazy = 0;
        }
    }
    void build(int rt, int l, int r) {
        t[rt].l = l, t[rt].r = r, t[rt].lazy = 0;
        if(l==r) return t[rt].cnt = s[l], void();
        int mid = (l+r)>>1;
        build(lson);
        build(rson);
        push_up(rt);
    }
    void update(int rt, int ql, int qr) {
        int l = t[rt].l, r = t[rt].r, len = (r-l)+1;
        if(ql<=l && r<=qr) {
            flip(rt);
            t[rt].lazy ^= 1;
            return ;
        }
        push_down(rt);
        int mid = (l+r)>>1;
        if(ql<=mid) update(ls, ql, qr);
        if(qr>mid) update(rs, ql, qr);
        push_up(rt);
    }
    int query(int rt, int k) {
        int l = t[rt].l, r = t[rt].r;
        if(l==r && l==k) return t[rt].cnt;
        push_down(rt);
        int mid = (l+r)>>1;
        if(k>mid) return query(rs, k);
        else return query(ls, k);
    }
} seg;

//  Solution
void solve()
{
    ll n, q, a1, a2, b1, b2;
    cin >> n >> q >> a1 >> a2 >> b1 >> b2;
    for(int i=1; i<=n; i++) {
        char ch;    cin >> ch;
        seg.s[i] = (ch=='1');
    }
    seg.build(1, 1, n);
        //  query([ql, qr])
        auto query = [&](int ql, int qr) {
            f_o((seg.query(1, qr))? "Magical Splash Flare" : "HoloPsychon");
        };
    while(q--) {
        int op, ql, qr;
        cin >> op >> ql >> qr;
        if(op==1) { //  op==1:flip([ql, qr])
            seg.update(1, ql, qr);
        } else {    //  op==2:query([ql, qr])
            query(ql, qr);
        }
    }
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    clock_t time1 = clock();
#endif
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

解法2

维护位置异或次数，因为只有 $00$ 和 $11$，异或偶数次相当于不变，只要维护 $rr$ 异或次数判断奇偶即可，以树状数组为例。

标程：

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1e6 + 10;
int Tr[N], n, m, a1, b1, a2, b2;
void add(int x, int v) {
    while (x < N) {
        Tr[x] += v;
        x += lowbit(x);
    }
}
int ask(int x) {
    int res = 0;
    while (x) {
        res += Tr[x];
        x -= lowbit(x);
    }
    return res;
}
void work() {
    cin >> n >> m;
    cin >> a1 >> b1 >> a2 >> b2;
    for (int i = 1; i <= n; ++i) {
        char ch; cin >> ch;
        if (ch == '1')add(i, 1), add(i + 1, -1);
    }
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int l, r; cin >> l >> r;
            add(l, 1); add(r + 1, -1);
        }
        else {
            int l, r; cin >> l >> r;
            int res = ask(r) & 1;
            if (res) {
                cout << "Magical Splash Flare\n";
            }
            else cout << "HoloPsychon\n";
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; T = 1;
    while (T--) {
        work();
    }
}

L 因子模仿 - hard version

题意求 $a_1\cdot b_1-a_2\cdot b_{2}a\_1\backslash cdot\; b\_1\; -\; a\_2\; \backslash cdot\; b\_2$，想办法求出这四个值。

发现两个特殊的矩阵：

Mat1:[1,0]
     [1,1]

和：

Mat0:[1,1]
     [0,1]

维护矩阵：

Matx:[a1,a2]
     [b1,b2]

$MatxMatx$ 左乘 $Mat1Mat1$ 得到：

[a1+a2,a2]
[b1+b2,b2]

$MatxMatx$ 左乘 $Mat0Mat0$ 得到：

[a1,a1+a2]
[b1,b1+b2]

容易发现左乘 $Mat1Mat1$ 就是 $s_i=1s\_i=1$ 的情况，左乘 $Mat0Mat0$ 就是 $s_i=0s\_i=0$ 的情况，由于矩阵相乘具有结合律，那么询问相当于 $MatxMatx$ 左乘若干个 $Mat1Mat1$ 或 $Mat0Mat0$ ，用线段树维护后面部分区间矩阵的乘积即可。

翻转操作，可以维护两种矩阵然后交换，也可以直接转置：

[a1,a2] -> [b2,b1]
[b1,b2]    [a2,a1]

转置正确性证明：

[a1,a2] * [1,0] = [a1+a2,a2]
[b1,b2]   [1,1]   [b1+b2,b2]

[b2,b1] * [1,1] = [b2,b1+b2]
[a2,a1]   [0,1]   [a2,a1+a2]

标程1：

#include <bits/stdc++.h>
using namespace std;

//  Template: std::cout argument list
template<typename T>
void f_o(const T& arg) { std::cout << arg << '\n'; }
template<typename T, typename... Ty_>
void f_o(const T& f_arg, const Ty_&... args) { std::cout << f_arg << ' '; f_o(args...); }
typedef long long ll;

//  Modular addition and multiplication and subtraction
const ll mod = 1e9+7;
ll add(ll &x, ll y) { return x = (x + y + mod) % mod; }
ll mul(ll x, ll y) { return (x * y) % mod; }
ll sub(ll x, ll y) { return (x - y + mod) % mod; }


//  Max Size
const int N = 1e6+5;

//  Const Matrix
ll _A[2][2] = {1, 0, 1, 1}; //  Mat1
ll _B[2][2] = {1, 1, 0, 1}; //  Mat0
ll _Z[2][2] = {0, 0, 0, 0}; //  MatZero

//  Matrix
struct Mat {
    ll m[2][2];
    Mat() { for(int i=0; i<2; i++) for(int j=0; j<2; j++) this->m[i][j] = 0; }
    Mat(ll x[2][2]) { for(int i=0; i<2; i++) for(int j=0; j<2; j++) this->m[i][j] = x[i][j]; }
    friend Mat operator*(Mat a, Mat b) {
        Mat res(_Z);
        for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) add(res.m[i][j], mul(a.m[i][k], b.m[k][j]));
        return res;
    }
    void copy(const Mat &b) { for(int i=0; i<2; i++) for(int j=0; j<2; j++) this->m[i][j] = b.m[i][j]; }
} A(_A), B(_B);

//  SegmentTree Node
struct Node {
    Mat mat[2];
    bool lazy;
};

//  SegmentTree with Lazytag
struct Segment_lazytree {
#define ls (rt<<1)
#define rs (rt<<1)|1
#define lson ls,l,mid
#define rson rs,mid+1,r
    Node t[N<<2];
    bool s[N];
    void flip(Node& res) {
        swap(res.mat[0], res.mat[1]);
    }
    void push_up(int rt) {
        t[rt].mat[0] = t[ls].mat[0] * t[rs].mat[0];
        t[rt].mat[1] = t[ls].mat[1] * t[rs].mat[1];
    }
    void push_down(int rt) {
        if(t[rt].lazy) {
            flip(t[ls]);    t[ls].lazy ^= 1;
            flip(t[rs]);    t[rs].lazy ^= 1;
            t[rt].lazy = 0;
        }
    }
    void build(int rt, int l, int r) {
        t[rt].lazy = 0;
        if(l == r) {
            if(s[l]) t[rt].mat[0].copy(A), t[rt].mat[1].copy(B);
            else t[rt].mat[0].copy(B), t[rt].mat[1].copy(A);
            return ;
        }
        int mid = (l+r)>>1;
        build(lson);
        build(rson);
        push_up(rt);
    }
    void update(int rt, int l, int r, int ql, int qr) {
        if(ql<=l && r<=qr) {
            flip(t[rt]);
            t[rt].lazy ^= 1;
            return ;
        }
        push_down(rt);
        int mid = (l+r)>>1;
        if(ql<=mid) update(lson, ql, qr);
        if(qr>mid) update(rson, ql, qr);
        push_up(rt);
    }
    Mat query(int rt, int l, int r, int ql, int qr) {
        if(ql<=l && r<=qr) return t[rt].mat[0];
        push_down(rt);
        int mid = (l+r)>>1;
        if(ql > mid) return query(rson, ql, qr);
        else if(qr <= mid) return query(lson, ql, qr);
        else return query(lson, ql, qr)*query(rson, ql, qr);
    }
} seg;

/*
Matx:[a,b]
     [c,d]
Mat1:[1,0]
     [1,1]
Mat0:[1,1]
     [0,1]

Matx * Sum(Mat01-Mat10)

-> MatAns:[f(a,b),g(a,b)]
          [f(c,d),g(c,d)]

*/

//  Solution
void solve()
{
    ll n, q, a1, a2, b1, b2;
    cin >> n >> q >> a1 >> a2 >> b1 >> b2;
    ll x[2][2] = {a1, a2, b1, b2};
    Mat y(x);
    for(int i=1; i<=n; i++) {
        char ch;    cin >> ch;
        seg.s[i] = (ch=='1');
    }
    seg.build(1, 1, n);
        //  query([ql, qr])
        auto query = [&](int ql, int qr) {
            Mat sum = y * seg.query(1, 1, n, ql, qr);
            ll A1 = sum.m[0][0], A2 = sum.m[1][0], B1 = sum.m[0][1], B2 = sum.m[1][1];
            ll ans = sub(mul(A1, A2), mul(B1, B2));
            cout << ans << '\n';
        };
    while(q--) {
        int op, ql, qr;
        cin >> op >> ql >> qr;
        if(op==1) { //  op==1:flip([ql, qr])
            seg.update(1, 1, n, ql, qr);
        } else {    //  op==2:query([ql, qr])
            query(ql, qr);
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

标程2：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e6 + 10;
const int mod = 1e9 + 7;
struct mat {
    ll m[2][2];
    mat() {
        memset(m, 0, sizeof m);
    }
    mat operator*(const mat& b) {
        mat res;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    res.m[i][j] += m[i][k] * b.m[k][j];
                    res.m[i][j] %= mod;
                }
            }
        }
        return res;
    }
    void rev() {
        mat tmp = *this;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                m[i][j] = tmp.m[!i][!j];
            }
        }
    }
};
int n, q, a1, a2, b1, b2;
mat Tr[N], one, A, B;
bool rev[N];
string s;
void pushup(int rt) {
    Tr[rt] = Tr[rt << 1] * Tr[rt << 1 | 1];
}
void pushdown(int rt) {
    if (rev[rt]) {
        Tr[rt << 1].rev(); Tr[rt << 1 | 1].rev();
        rev[rt << 1] ^= 1; rev[rt << 1 | 1] ^= 1; rev[rt] ^= 1;
    }
}
void update(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        Tr[rt].rev();
        rev[rt] ^= 1;
        return;
    }
    pushdown(rt);
    int mid = l + r >> 1;
    if (ql <= mid)update(rt << 1, l, mid, ql, qr);
    if (qr > mid)update(rt << 1 | 1, mid + 1, r, ql, qr);
    pushup(rt);
}
mat ask(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return Tr[rt];
    }
    pushdown(rt);
    int mid = l + r >> 1;
    mat res = one;
    if (ql <= mid)res = res * ask(rt << 1, l, mid, ql, qr);
    if (qr > mid)res = res * ask(rt << 1 | 1, mid + 1, r, ql, qr);
    return res;
}
void build(int rt, int l, int r) {
    if (l == r) {
        if (s[l - 1] == '1')Tr[rt] = A;
        else Tr[rt] = B;
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void work() {
    cin >> n >> q;
    cin >> a1 >> a2 >> b1 >> b2;
    one.m[0][0] = one.m[1][1] = 1;
    A = B = one;
    A.m[1][0] = B.m[0][1] = 1;
    mat init;
    init.m[0][0] = a1, init.m[0][1] = a2;
    init.m[1][0] = b1, init.m[1][1] = b2;
    cin >> s;
    build(1, 1, n);
    while (q--) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1) {
            update(1, 1, n, l, r);
        }
        else {
            mat res = ask(1, 1, n, l, r);
            res = init * res;
            cout << (res.m[0][0] * res.m[1][0] % mod - res.m[0][1] * res.m[1][1] % mod + mod) % mod << '\n';
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; T = 1;
    while (T--) {
        work();
    }
}