当前位置： 首页 > article >正文

第十四届CCPC吉林省赛题解

article 2024/12/23 21:42:45

比赛链接

D. Trie

思路：

构建 t r i e trie trie树后建 A C AC AC自动机的 f a i l fail fail树，那么对一个串的后缀的最长公共前缀就是其在 f a i l fail fail树节点的父亲节点。那么对于询问1，假设对当前点 x 1 , x 2 , x 3 x1,x2,x3 x1,x2,x3打上新的标记，其实就相当于在 f a i l fail fail树上对于每个点以其为根的子树内打上标记。我们跑 d f s dfs dfs序，就等价于区间加标记。为了防止重复加标记，假设 x 2 x2 x2在 x 1 x1 x1的子树内，那么我们只需对 x 1 x1 x1打标记即可。问题就转化为区间修改，单点查询了。

code：


#define INF 0x3f3f3f3f3f3f3f3fll
#define inf 0x3f3f3f3f
#define pb push_back
#define se second
#define fi first
#define LL long long
#define ULL unsigned long long
#define pii pair<int, int> 
#define lowbit(x) (x & (-x))
#define all(x) (x).begin(), (x).end()
#define rep(i, x, y) for(int i = (int)x; i <= (int)y; i++)
#define per(i, x, y) for(int i = (int)x; i >= (int)y; i--)
#define D(x) cout << "BUG:  " << (x) << '\n';
#define DD(x, y) cout << "BUG:  " << (x) << "  " << (y) << '\n';
template <typename T> void inline read(T& x) {
    T f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
//----------------------------------------------------------------------------------------//


const int N = 1e5 + 50;
const int M = N << 1;
const int mod = 1e9 + 7;

template<typename T>
struct BIT{
    int n;
    T t[N];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    void add(int i, int j, T x) {
        add(i, x); add(j + 1, -x);
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};


int tr[N][26], fail[N];
int n;
int in[N], out[N], num;
vector<int> G[N];

void dfs(int u) {
    in[u] = ++num;
    for(auto t : G[u]) dfs(t);
    out[u] = num;
}

void build() {
    queue<int> q;
    for(int i = 0; i < 26; i++) if(tr[0][i]) q.push(tr[0][i]);
    while(q.size()) {
        auto u = q.front(); q.pop();
        for(int i = 0; i < 26; i++) {
            if(tr[u][i]) {
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[u][i]);
            } else tr[u][i] = tr[fail[u]][i];
        }
    }
    for(int i = 1; i < n; i++) G[fail[i]].push_back(i);
    dfs(0);
}

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        num = 0;
        for(int i = 0; i <= n + 5; i++) {
            G[i].clear();
            in[i] = out[i] = 0;
            fail[i] = 0;
            for(int j = 0; j < 26; j++) tr[i][j] = 0;
        }
        for(int i = 2; i <= n; i++) {
            int x; char c; 
            cin >> x >> c;
            tr[x - 1][c - 'a'] = i - 1;
        }
        build();
        BIT<int> bit(100000);
        int m; cin >> m;
        while(m--) {
            int op; cin >> op;
            if(op == 1) {
                int k; cin >> k;
                vector<int> b(k);
                for(int i = 0; i < k; i++) {
                    int x; cin >> x;
                    x--;
                    b[i] = x;
                }
                sort(all(b), [&](int i, int j) {
                    return in[i] < in[j];
                });
                int mx = -1;
                for(int i = 0; i < k; i++) {
                    if(in[b[i]] > mx) {
                        bit.add(in[b[i]], 1);
                        bit.add(out[b[i]] + 1, -1);
                    }
                    mx = max(mx, out[b[i]]);
                }
            } else {
                int x; cin >> x;
                x--;
                cout << bit.sum(in[x]) << '\n';
            }
        }
    }

    return 0;
}
/*

*/

E. Shorten the Array

思路：

对于一个区间，假设区间最小值为 m n mn mn.
1.其只出现一次，那么这个区间显然可以变为1
2.其出现多次，但是存在一个数不是 m n mn mn的倍数，那么依旧可以变为1
3.其出现多次，且其余数均为 m n mn mn的倍数，那么区间最后只能变为 ( c n t m n + 1 ) / 2 (cnt_{mn} + 1) / 2 (cntmn​+1)/2

code:

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n; cin >> n;
        int cnt = 0, mn = inf;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) {
            int x; cin >> x;
            a[i] = x;
            if(mn > x) {
                mn = x;
                cnt = 1;
            } else if(mn == x) {
                cnt++;
            }
        }
        if(cnt == 1) {
            cout << "1\n";
            continue;
        }
        bool ok = 1;
        for(int i = 1; i <= n; i++) {
            if(a[i] % mn != 0) {
                ok = 0; 
            }
        }
        if(!ok) cout << 1 << '\n';
        else cout << (cnt + 1) / 2 << '\n';
    }

    return 0;
}
/*

*/

F. Queue

思路：

首先区间逆序对可以树状数组求出，观察到其询问的区间长度最多只有100，那么我们每次暴力判断即可。

code:

const int N = 1e5 + 50;
const int M = N << 1;
const int mod = 1e9 + 7;
 
template<typename T>
struct BIT{
    int n;
    T t[N];
 
    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] += x;
            i += lowbit(i);
        }
    }
    void add(int i, int j, T x) {
        add(i, x); add(j + 1, -x);
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};
 
 
 
 
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        int n; cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        LL ans = 0;
        BIT<int> bit(100001);
        for(int i = n; i >= 1; i--) {
            a[i]++;
            ans += bit.sum(a[i] - 1);
            bit.add(a[i], 1);
        }
        // D(ans)
        int m; cin >> m;
        LL mn = ans;
        while(m--) {
            int l, r; 
            cin >> l >> r;
            if(l == r) continue;
            int cnt1 = 0, cnt2 = 0;
            for(int i = l + 1; i < r; i++) {
                cnt1 += a[i] < a[l];
                cnt2 += a[i] > a[r];
            }
            ans = ans - cnt1 - cnt2;
            cnt1 = cnt2 = 0;
            for(int i = l + 1; i < r; i++) {
                cnt1 += a[i] > a[l];
                cnt2 += a[i] < a[r];
            }
            ans += cnt1 + cnt2;
            if(a[l] > a[r]) ans--;
            swap(a[l], a[r]);
            if(a[l] > a[r]) ans++;
            mn = min(ans, mn);
            // D(ans)
        }
        cout << mn << '\n';
 
    }
 
    return 0;
}

G. Matrix

思路：

显然每个点改变奇数次才有贡献。
对于点 ( i , j ) (i, j) (i,j)，其改变次数 c n t = i 约数个数 ∗ j 约数个数 cnt=i_{约数个数}*j_{约数个数} cnt=i约数个数​∗j约数个数​
由数论知识易知，一个数的约数个数是奇数当且仅当其是完全平方数。
所以答案 a n s = ⌊ s q r t ( n ) ⌋ ∗ ⌊ s q r t ( m ) ⌋ ans=\lfloor sqrt(n) \rfloor * \lfloor sqrt(m) \rfloor ans=⌊sqrt(n)⌋∗⌊sqrt(m)⌋

I. World Tree

思路：

我们令 s u m 1 [ u ] sum1[u] sum1[u]为 u u u子树节点及其本身的 b [ i ] b[i] b[i]权值和， s u m 2 [ u ] sum2[u] sum2[u]为 u u u子树节点及其本身的 a [ i ] a[i] a[i]权值和.
对于当前点u，其子树内的点对其贡献显然为 a [ u ] ∗ ( s u m 1 [ u ] − b [ u ] ) a[u]*(sum1[u]-b[u]) a[u]∗(sum1[u]−b[u])。
接下来计算 u u u子树外的兄弟节点的贡献。
假设 v v v为 u u u的一个兄弟节点。
情况1：先走 v v v,那么它们两个的贡献为 s u m 2 [ v ] ∗ s u m 1 [ u ] sum2[v]*sum1[u] sum2[v]∗sum1[u]
情况2：先走 u u u,贡献为 s u m 2 [ u ] ∗ s u m 1 [ v ] sum2[u]*sum1[v] sum2[u]∗sum1[v]
如果1>2，那么先遍历 v v v子树更优。

code:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3fll
#define inf 0x3f3f3f3f
#define pb push_back
#define se second
#define fi first
#define LL long long
#define ULL unsigned long long
#define pii pair<int, int> 
#define lowbit(x) (x & (-x))
#define all(x) (x).begin(), (x).end()
#define rep(i, x, y) for(int i = (int)x; i <= (int)y; i++)
#define per(i, x, y) for(int i = (int)x; i >= (int)y; i--)
#define D(x) cout << "BUG:  " << (x) << '\n';
#define DD(x, y) cout << "BUG:  " << (x) << "  " << (y) << '\n';
template <typename T> void inline read(T& x) {
    T f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
//----------------------------------------------------------------------------------------//


const int N = 5e5 + 50;
const int M = N << 1;
const int mod = 1e9 + 7;

int n, a[N], b[N], sum1[N], sum2[N];
vector<int> G[N];
LL ans = 0;

void dfs1(int u, int fa) {
    sum1[u] = b[u];
    sum2[u] = a[u];
    for(int v : G[u]) {
        if(v != fa) {
            dfs1(v, u);
            sum1[u] += sum1[v];
            sum2[u] += sum2[v];
        }
    }
}
void dfs2(int u, int fa) {
    ans += 1LL * a[u] * (sum1[u] - b[u]);
    sort(all(G[u]), [](int i, int j) {
        return sum2[i] * 1LL * sum1[j] > sum2[j] * 1LL * sum1[i];
    });
    LL temp = sum1[u] - b[u];
    for(int v : G[u]) {
        if(v != fa) {
            dfs2(v, u);
            temp -= sum1[v];
            ans += 1LL * sum2[v] * temp; 
        }
    }
}
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while(T--) {
        cin >> n;
        ans = 0;
        for(int i = 0; i <= n; i++) {
            G[i].clear();
            sum1[i] = sum2[i] = 0;
        }
        for(int i = 1; i <= n; i++) cin >> b[i];
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i < n; i++) {
            int x, y; cin >> x >> y;
            G[x].pb(y);
            G[y].pb(x);
        }
        dfs1(1, -1);
        dfs2(1, -1);
        cout << ans << '\n';
    }

    return 0;
}
/*

*/

M. Upanishad

思路：

区间内出现偶数次的数的异或和=区间异或和 ^ 区间内所有不同的数的异或和
前者用前缀异或和可以得到，后者是树状数组的经典 t r i c k trick trick。
对于所有询问先按右端点升序排列，那么对于当前点 a [ i ] a[i] a[i]，我们维护上一个 a [ i ] a[i] a[i]出现的位置: l a s t [ a [ i ] ] last[a[i]] last[a[i]].

code:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3fll
#define inf 0x3f3f3f3f
#define pb push_back
#define se second
#define fi first
#define LL long long
#define ULL unsigned long long
#define pii pair<int, int> 
#define lowbit(x) (x & (-x))
#define all(x) (x).begin(), (x).end()
#define rep(i, x, y) for(int i = (int)x; i <= (int)y; i++)
#define per(i, x, y) for(int i = (int)x; i >= (int)y; i--)
#define D(x) cout << "BUG:  " << (x) << '\n';
#define DD(x, y) cout << "BUG:  " << (x) << "  " << (y) << '\n';
template <typename T> void inline read(T& x) {
    T f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
//----------------------------------------------------------------------------------------//


const int N = 5e5 + 50;
const int M = N << 1;
const int mod = 1e9 + 7;

template<typename T>
struct BIT{
    int n;
    T t[N];

    BIT<T> () {}
    BIT<T> (int _n): n(_n) { memset(t, 0, sizeof(t)); }
    BIT<T> (int _n, T *a): n(_n) {
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; ++ i){
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    void add(int i, T x){ 
        while (i <= n){
            t[i] ^= x;
            i += lowbit(i);
        }
    }
    void add(int i, int j, T x) {
        add(i, x); add(j + 1, -x);
    }
    T sum(int i){
        T ans = 0;
        while (i > 0){
            ans ^= t[i];
            i -= lowbit(i);
        }
        return ans;
    }
    T sum(int i, int j){
        return sum(j) - sum(i - 1);
    }
};

int n, q, a[N], sum[N];
int ans[N];
map<int, int> last;
struct Node {
    int l, r, idx;
}p[N];

signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] ^ a[i];
    }
    for(int i = 1; i <= q; i++) {
        cin >> p[i].l >> p[i].r;
        p[i].idx = i;
    }
    sort(p + 1, p + 1 + q, [&](Node x, Node y) {
        return x.r <= y.r;
    });
    BIT<int> bit(N - 5);
    int l = 1;
    for(int i = 1; i <= q; i++) {
        while(l <= p[i].r) {
            if(last.count(a[l])) {
                bit.add(last[a[l]], a[l]);
            }
            last[a[l]] = l;
            bit.add(l, a[l]);
            l++;
        }
        int res = sum[p[i].r] ^ sum[p[i].l - 1];
        res = res ^ (bit.sum(p[i].r) ^ bit.sum(p[i].l - 1));
        ans[p[i].idx] = res;
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';


    return 0;
}
/*

*/

http://www.kler.cn/a/6494.html

相关文章：

  • AI芯片常见概念
  • 天地图接口Python代码详解
  • 高效准确的PDF解析工具，赋能企业非结构化数据治理
  • 用人话讲计算机：Python篇！（十五）迭代器、生成器、装饰器
  • 简洁清爽epub 阅读器
  • arm Rk3588 更新固件
  • 20230405英语学习
  • 溯源取证-钓鱼取证 基础篇
  • NDK RTMP直播客户端一
  • Android事件分发机制小结
  • 看ChatGPT如何回答微博签到数据相关问题。
  • Linux-
  • 数据分析练习——学习一般分析步骤
  • 代码随想录算法训练营第四十四天| 518. 零钱兑换 II、377. 组合总和 Ⅳ。
  • AJAX在PHP中的应用示例代码
  • Python垃圾回收机制详解
  • 研报精选230405
  • taro之--使用nutui
  • 【新2023Q2模拟题JAVA】华为OD机试 - 矩阵最值 or 计算二维矩阵的最大值
  • 如何实现接口调用的重试
  • RocketMQ消息文件过期原理
  • 面试官：谈谈你对MySQL事务的理解
  • 初识设计模式 - 适配器模式
  • 【python设计模式】8、桥接模式
  • Python入门教程+项目实战-7.2节: 循环控制结构
  • 【Python入门第四十二天】Python丨NumPy 数组裁切