暑假集训week4

暑假集训-week4题解-暑假结构进阶

A - ST 表

ST

#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3865
const int maxn = 1e6 + 10;
int n, m;
int a[maxn], f[maxn][100]; 
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void ST_prework()
{
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int ST_query(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    ST_prework();
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        l = read(), r = read();
        printf("%ld\n",ST_query(l,r));
    }
    return 0;
}

B - 并查集

#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3367
const int maxn = 2e5;
int n, m;
int fa[maxn];
int find(int x)
{
    if (x == fa[x])
        return x;
    else
        return fa[x] = find(fa[x]);
}
void connect(int x, int y)
{
    fa[find(x)] = fa[find(y)];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int flag, x, y;
        cin >> flag >> x >> y;
        if (flag == 1)
        {
            connect(x, y);
        }
        if (flag == 2)
        {
            if (find(x) == find(y))
                cout << "Y" << endl;
            else
                cout << "N" << endl;
        }
    }
    return 0;
}

C - 字符串哈希

#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3370
map<string, bool> visit;
int num;
int n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string remp;
        cin >> remp;
        if (!visit[remp])
            visit[remp] = true, num++;
    }
    cout << num;
    return 0;
}

D - 统计难题

trie模板题，trie挺有用的

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://vjudge.csgrandeur.cn/contest/509181#problem/D
// Trie字典树
int trie[1000100][26], cnt[1000100], tot;
string remp;
void insert(string tar)
{
    int len = tar.length(), node = 0;
    for (int k = 0; k < len; k++)
    {
        int ch = tar[0] - 'a';
        if (trie[node][ch] == 0)
            trie[node][ch] = ++tot;
        node = trie[node][ch];
    }
    cnt[node]++;
}
int query(string tar) //查询以此字串开头的串有多少个
{
    int node = 0, ans = 0, len = tar.length();
    for (int i = 0; i < len; i++)
    {
        int ch = tar[i] - 'a';
        node = trie[node][ch];
        if (node == 0)
            return ans;
        ans += cnt[node];
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> remp)
    {
        insert(remp);
    }
    while (cin >> remp)
    {
        cout << query(remp) << endl;
    }
    return 0;
}

E - 树状数组 1

树状数组模板题
单点修改区间询问
假如要单点询问的话用树状数组再维护一个差分数组就行了

#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3374
// 树状数组
// 单点修改，区间询问
const int maxn = 1e6;
int tree_array[maxn];
int n, m;
void add(int x, int y)
{
    for (; x <= n; x += x & -x)
        tree_array[x] += y;
}
int ask(int r) //求1到r之间的前缀和
{
    int ans = 0;
    for (; r; r -= r & -r)
    {
        ans += tree_array[r];
    }
    return ans;
}
int query(int l, int r)
{
    return ask(r) - ask(l - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int remp;
        cin >> remp;
        add(i, remp);
    }
    for (int i = 1; i <= m; i++)
    {
        int remp, x, y;
        cin >> remp >> x >> y;
        if (remp == 1)
            add(x, y);
        else
            cout << query(x, y) << endl;
    }
    return 0;
}

F - 线段树 1

模板题

#include <bits/stdc++.h>
using namespace std;
// 线段树
// 区间询问，区间修改(RMQ)
// https://www.luogu.com.cn/problem/P3372
#define maxn 100010
int n, m;
long long a[maxn];
long long tree[4 * maxn];
long long lazy[4 * maxn];
void pushdown(int x, int left, int right)
{
    if (lazy[x] == 0)
        return;
    int mid = (left + right) >> 1;
    lazy[x << 1] += lazy[x], tree[x << 1] += lazy[x] * (mid - left + 1);
    lazy[x << 1 | 1] += lazy[x], tree[x << 1 | 1] += lazy[x] * (right - mid);
    lazy[x] = 0; //该节点已结算
}
void build(int x, int left, int right) // x为堆数组编号，left与right代表其维护的区间
{
    if (left == right)
    {
        tree[x] = a[left];
        return;
    }
    int mid = (left + right) >> 1;
    build(x << 1, left, mid);
    build(x << 1 | 1, mid + 1, right);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
long long query(int x, int left, int right, int tar_left, int tar_right)
{
    if (left == tar_left && right == tar_right)
    {
        return tree[x];
    }
    pushdown(x, left, right);
    int mid = (left + right) >> 1;
    if (tar_left <= mid && tar_right > mid)
    {
        long long leftans = query(x << 1, left, mid, tar_left, mid);
        long long rightans = query(x << 1 | 1, mid + 1, right, mid + 1, tar_right);
        return leftans + rightans;
    }
    if (tar_left <= mid && tar_right <= mid)
    {
        return query(x << 1, left, mid, tar_left, tar_right);
    }
    if (tar_left > mid && tar_right > mid)
    {
        return query(x << 1 | 1, mid + 1, right, tar_left, tar_right);
    }
}
void modify(int x, int y, int left, int right, int tar_left, int tar_right)
{
    if (left == tar_left && right == tar_right)
    {
        tree[x] += (right - left + 1) * y;
        lazy[x] += y; //懒数组标记！
        return;
    }
    pushdown(x, left, right);
    int mid = (left + right) >> 1;
    if (tar_left <= mid && tar_right > mid)
    {
        modify(x << 1, y, left, mid, tar_left, mid);
        modify(x << 1 | 1, y, mid + 1, right, mid + 1, tar_right);
    }
    if (tar_left <= mid && tar_right <= mid)
    {
        modify(x << 1, y, left, mid, tar_left, tar_right);
    }
    if (tar_left > mid && tar_right > mid)
    {
        modify(x << 1 | 1, y, mid + 1, right, tar_left, tar_right);
    }
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int remp;
        cin >> remp;
        if (remp == 1)
        {
            int x, y, k;
            cin >> x >> y >> k;
            modify(1, k, 1, n, x, y);
        }
        if (remp == 2)
        {
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }
    return 0;
}

G - Palindrome

hash加二分搜索答案，思路挺巧妙的
注意下反向hash是怎么存的 (知识增加)

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://vjudge.csgrandeur.cn/contest/509181#problem/G
// 字符串哈希《蓝书》P67
// 题解：https://www.acwing.com/solution/content/125631/
const int maxn = 2000010, P = 131;
char s[maxn];
long long h1[maxn], h2[maxn], p[maxn];
long long get(long long h[], long long l, long long r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    int cnt = 0;
    while (scanf("%s", s + 1) && strcmp(s + 1, "END"))
    {
        int n = strlen(s + 1) * 2;
        for (int i = n; i; i -= 2)
        {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }
        p[0] = 1;
        for (int i = 1, j = n; i <= n; i++, j--)
        {
            h1[i] = h1[i - 1] * P + s[i] - 'a' + 1;
            h2[i] = h2[i - 1] * P + s[j] - 'a' + 1; //倒着存进去了
            p[i] = p[i - 1] * P;
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            long long x = -1, l = 0, r = min(i - 1, n - i);
            while (l <= r)
            {
                long long mid = (l + r + 1) / 2;
                if (get(h1, i - mid, i - 1) != get(h2, n - (i + mid) + 1, n - i))
                {
                    r = mid - 1;
                }
                else
                {
                    x = mid;
                    l = mid + 1;
                }
            }
            if (s[i - x] <= 'z')
            {
                ans = max(ans, x + 1);
            }
            else
            {
                ans = max(ans, x);
            }
        }
        printf("Case %d: %d\n", ++cnt, ans);
    }
    return 0;
}

H - The XOR Largest Pair

trie的题
思路是将输入的数字想象成一个01的字符串，我们考虑贪心策略，组数字的时候尽可能让这个数字的二进制对应位置都不一样

#include <bits/stdc++.h>
using namespace std;
// tire树(01 trie树)
const int maxn = 1e6;
int n, a[maxn], tot;
int trie[1000000][2]; //每一位要么是0要么是1
// trie[x][y]的值是下一个节点的编号，x是当前编号，y是当前位置的值
void insert(int x)
{
    int p = 0;                    // root节点,用于移动的指针
    for (int i = 30; i >= 0; i--) //二进制从第0位开始
    {
        int remp = x >> i & 1; //取出第i位 (从高位开始传)
        if (trie[p][remp] == 0)
            trie[p][remp] = ++tot; //指针只想这里
        p = trie[p][remp];         //将当前指针对准这里
    }
}
int search(int x)
{
    int p = 0;        //用于移动的指针
    int temp_ans = 0; //本次搜索到最大值
    for (int i = 30; i >= 0; i--)
    {
        // 取贪心策略，我们尽量走相反位置
        int remp = x >> i & 1;
        if (trie[p][remp ^ 1]) //如果相反节点存在，直接跳过去
        {
            p = trie[p][remp ^ 1];
            temp_ans += (1 << i); //此位置确定是1，可以上去了！
        }
        else
            p = trie[p][remp]; //没有的话就原节点继续
    }
    return temp_ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        insert(x);
        ans = max(ans, search(x));
    }
    cout << ans << endl;
    return 0;
}

I - 食物链

并查集的拓展域做法，很巧妙的解法！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6;
int N, K, fa[200000];
// 拓展域做法
// fa[x]代表本类，fa[x+N]代表捕食类，fa[x+2n]代表天敌
int find(int x)
{
    if (fa[x] != x)
        return fa[x] = find(fa[x]);
    else
        return x;
}
void connect(int x, int y)
{
    fa[find(x)] = fa[find(y)];
    // fa[find(x)] = find(y);
}
int main()
{
    cin >> N >> K;
    for (int i = 1; i <= N * 3; i++)
        fa[i] = i;
    int cnt = 0;
    for (int i = 1; i <= K; i++)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (x > N || y > N)
        {
            cnt++;
            continue;
        }
        else if (opt == 1)
        {
            if (find(x + N) == find(y) || find(y + N) == find(x)) // x吃y，或者y吃x
            {
                cnt++;
            }
            else
            {
                connect(x, y);
                connect(x + N, y + N);
                connect(x + N + N, y + N + N);
            }
        }
        else if (opt == 2) // X 吃 Y
        {
            if (find(y + N) == find(x) || find(x) == find(y)) //如果y的捕食域有x，或者同类
            {
                cnt++;
            }
            else
            {
                connect(x + N, y);         // x的捕食域放入y
                connect(y + N + N, x);     // y的天敌域放入x
                connect(y + N, x + N + N); // y的捕食是x天敌
            }
        }
     
    cout << cnt << endl;
    return 0;
}