这里存放一些校队训练期间（7.2-7.15）做过的题目，包括但不限于：校队训练、实习摸底测试和考核的做题和补题，自己补的 CF 题和 AtCoder 题等。
结果俩礼拜想学的东西没学多少，奇怪的知识倒是做题的时候顺便学了一堆Orz

本篇是校队上篇，另有下篇和番外篇

暑期ACM实习摸底题解

（湘潭大学校赛 + 华中科大校赛）

A. 社团招新

Description

给出学生数，已知每个社团的成员个数为奇数，每两个社团的公共成员为偶数，求这些学生能组成几个社团

Solution

已知 0 为偶数，则显然为 n 个

Code

不贴

B. 字符串

Description

两个人选择两个相同且相邻的字母删除，再将两端连起来，如果一方不能执行操作则为负，问谁会获胜

Solution

模拟计算可操作数即可

Code

不贴

D. 香蕉

Description

n 根香蕉分配给 m 个猴子，问至少有多少只猴子的香蕉数是一样的

Solution

二分答案，不难知道，要想让答案尽可能小，则必然要让尽可能多的猴子分配到香蕉，那么就应该让猴子分配到的香蕉尽可能少，所以得出在 mid 条件下总共的香蕉数 sum 为 $sum=\frac {cnt\times (cnt+1)}{2}\times mid + (m \% mid)\times (cnt+1)$ ，和 n 比较即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int T;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    T = read();
    while (T--) {
        ll n = read(), m = read();
        ll l = 1, r = m, mid = 0;
        while (l < r) {
            mid = (l + r) >> 1;
            ll sum = 0, cnt = m / mid;
            sum = (cnt * (cnt + 1) / 2) * mid + (m % mid) * (cnt + 1);
            if (sum <= n)
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

K. Contest Preparation

Description

~~众所周知~~，出题分为出题和验题（？），现在有 n 题和 m 个人，每个人会出题和验题，一小时只能完成一题的一个任务，出完的题才能验，问最少花多少时间

Solution

如果 $n==0$ 直接输出 0 ，如果 $n < m$ 直接输出 2 ，否则输出 $⌈\frac{n\times 2}{m}⌉$

Code

不贴

L. XOR Almost Everything

Description

对于一组数列，每次操作你可以选择 x 和 y ，使得所有 $a_i(i≠x)=a_i\ xor\ y$ ，问是否能将所有数置为 0

Solution

当 n 为偶数时，对每个位置进行异或 S 操作，可以使得所有数均为 0，因为每个位置均被异或了
n − 1 次 S；
当 n 为奇数时，注意到进行任意操作均不会改变 $⊕_i a_i$ 的值。由于 S ≠ 0，一定无法使所有数变为0。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int n;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read();
    if (n % 2 == 0) {
        cout << "YES" << endl;
        return 0;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int x = read();
        res ^= x;
    }
    if (res == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

M. Triangles

Description

有一个 500*500 的方格，左下角为零点，有 n 个从左下角到右上角的斜线，问他们和方格边组成的三角形数量

Solution

观察样例一给出的图，可以发现图中所有的三角形斜边均由红线组成，直角边均由黑线组成，并且每条
红线不重复地对应左上和右下两个三角形，因此只需统计有多少条红线即可。一条长度为 l 的线段包含
$l(l + 1)/2$ 条小线段，不重叠的线段数量可以直接相加。复杂度 $O(n)$

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int n;
map<pair<unsigned ll, unsigned ll>, bool> mp;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read();
    for (int i = 1; i <= n; i++) {
        mp[{ read(), read() }] = 1;
    }
    unsigned ll ans = 0;
    map<pair<unsigned ll, unsigned ll>, bool>::iterator it = mp.begin();
    while (it != mp.end()) {
        if (it->y == 0) {
            it++;
            continue;
        }
        unsigned ll cnt = 1, sum = 1 * 2;
        while (mp[{ it->x.x + cnt, it->x.y + cnt }] == 1) {
            mp[{ it->x.x + cnt, it->x.y + cnt }] = 0;
            cnt++;
            sum += cnt * 2;
        }
        ans += sum;
        it->y = 0;
    }
    cout << ans << endl;
    return 0;
}

暑期校队训练一题解

（ICPC 2018 南京区域赛）

十分魔幻的一场，竟然有两题随机，找规律题也十分迷惑 emm

A. Adrien and Austin

Description

取石子问题，n个石子，可取1~k个，求先取能不能赢

Solution

十分朴素的博弈论签道题。

分成三种情况：

0个石子则先取者输。
k==1时，每个人只能取一个石子，奇数先手赢，偶数后手赢。
其他情况下，先手从中间去一定量石子，使得两边石子数相等，然后跟后手取同样的石子，最后先手必赢

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int n, k;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), k = read();
    if (n == 0) {
        puts("Austin");
    } else if (k == 1) {
        if (n % 2 == 0) {
            puts("Austin");
        } else
            puts("Adrien");
    } else
        puts("Adrien");
    return 0;
}

G. Pyramid

Description

有如上左图黑色小三角形组成的大三角形，求连接小三角形各端点组成的正三角形有多少个

Solution

找规律题，打表可知数列为 $1,5,15,35,70,126……$ ，~~不难得出~~公式为 $n\times (n+1) \times (n+2) \times (n+3) / 24$

实现时，注意到公式有除法和取模，需要求逆元。a的逆元相当于a在 $mod\ b$ 条件下的倒数，利用费马小定理，只需要求 $a^{b-2}\%b$ 即可

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const ll N = 1e9 + 7;
int t;
ll fm(ll x, ll y)
{
    ll ans = 1;
    while (y) {
        if (y & 1)
            ans = ans * x % N;
        x = x * x % N;
        y >>= 1;
    }
    return ans;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    ll inv = fm(24, N - 2);
    t = read();
    while (t--) {
        ll n = read();
        ll ans = inv * n % N * (n + 1) % N * (n + 2) % N * (n + 3) % N;
        printf("%lld\n", ans);
    }
    return 0;
}

J. Prime Gam

Description

定义 mul(l,r) 为 $\prod \limits_{i=l}^r a_i$ ，fac(l,r) 为 mul(l,r) 不重复的质因数数量

求 $\sum_{i=1}^{n}\sum_{j=i}^{n}fac(i,j)$

Solution

显然不能暴力求解，考虑从单个数字的单个质因数的贡献出发。

对于一个在 $i$ 位置的质因数 $j$ ，由于其左侧也可能存在相同的质因数，因此我们只算他左侧最近的一个质因数之后的部分。考虑构造一个二维数组 $p[i][j]$ ，表示第i个质数在数组中出现第j次的位置，则其贡献为

$(p[prime[i]][j] - p[prime[i]][j - 1]) \times (n - p[prime[i]][j] + 1)$

因此，我们只需要预处理范围内所有的素数，对于数列中每个数分解质因数，并将其位置存进p数组中，最后按照上面的公式计算即可

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const int N = 1e6 + 5;
int n;
bool isP[N];
int prime[N], cnt = 0;
vector<int> p[N];
void getPrime()
{
    memset(isP, 1, sizeof(isP));
    isP[1] = 0;
    for (int i = 2; i < N; i++) {
        if (isP[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= N; j++) {
            isP[i * prime[j]] = 0;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    getPrime();
    n = read();
    for (int i = 0; i < N; i++) {
        p[i].push_back(0);
    }
    for (int i = 1; i <= n; i++) {
        int x = read(), tmp = x;
        if (isP[x]) {
            p[x].push_back(i);
        } else {
            for (int j = 1; prime[j] * prime[j] <= x && j <= cnt; j++) {
                if (tmp % prime[j] == 0) {
                    p[prime[j]].push_back(i);
                    while (tmp % prime[j] == 0)
                        tmp /= prime[j];
                }
            }
            if (tmp > 1)
                p[tmp].push_back(i);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= cnt; i++) {
        int s = p[prime[i]].size();
        for (int j = 1; j < s; j++) {
            ans += 1ll * (p[prime[i]][j] - p[prime[i]][j - 1]) * (n - p[prime[i]][j] + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

K. Kangaroo Puzzle

Description

在矩阵中有几只鹅，你一次可以移动所有的鹅往上下左右之一走一步，求50000步内把所有的鹅聚到一块的方案。

Solution

方格最大只有 $20\times 20$ ，由此可知，显然在五万内一定能完成任务，所以只需要random五万次走法就有很大概率能够得到方案

Code

不贴

L. Magic Potion

Description

有 n 个人和 m 只怪物，第 i 个人可以杀某几只怪物，同时有 k 瓶药水，一个人可以喝一瓶来多杀一只怪物，问最多可以杀几只怪物？

Solution

显然，人和怪物的关系可以简化为二分图，则题目所求为二分图的最大匹配，是网络流中的最大流问题。我们假设人和怪物间杀与被杀关系的流为1，设置开头连接人，结尾连接怪物，对于药水，设置一个虚拟节点，开头连接虚拟节点，流为k，虚拟节点和所有人的节点连接，流为1，则可以运用 Dinic 算法

网络流是算法竞赛中的一个重要的模型，它分为两部分：网络和流。

网络，其实就是一张有向图，其上的边权称为容量。额外地，它拥有一个源点和汇点。

流，顾名思义，就像水流或电流，也具有它们的性质。如果把网络想象成一个自来水管道网络，那流就是其中流动的水。每条边上的流不能超过它的容量，并且对于除了源点和汇点外的所有点（即中继点），流入的流量都等于流出的流量。

网络流中最常见的问题就是网络最大流。假定从源点流出的流量足够多，求能够流入汇点的最大流量。

增广路，是从源点到汇点的路径，其上所有边的残余容量均大于0。

Ford-Fulkerson 算法：引入反向边。在建边的同时，在反方向建一条边权为0的边，在扣除正向边的容量时，反向边要加上等量的容量。把反向边理解成一种撤销，走反向边就意味着撤回上次流经正向边的若干流量，这也合理解释了为什么扣除正向边容量时要给反向边加上相应的容量：反向边的容量意味着可以撤回的量。加入了反向边这种反悔机制后，我们就可以保证，当找不到增广路的时候，流到汇点的流量就是最大流。

Edmond-Karp 算法：BFS实现的FF算法。DFS很可能会“绕远路”，而BFS可以保证每次找到的都是最短的增广路。

Dinic 算法：作为FF/EK算法的优化，它选择了先用BFS分层，再用DFS寻找。所谓分层，其实就是预处理出源点到每个点的距离（注意每次循环都要预处理一次，因为有些边可能容量变为0不能再走）。我们只往层数高的方向增广，可以保证不走回头路也不绕圈子。

我们可以使用多路增广节省很多花在重复路线上的时间：在某点DFS找到一条增广路后，如果还剩下多余的流量未用，继续在该点DFS尝试找到更多增广路。

此外还有当前弧优化。因为在 Dinic 算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把head数组复制一份，但不断更新增广的起点。

Code

//Dinic 算法
int n, m, s, t, lv[MAXN], cur[MAXN]; // lv是每个点的层数，cur用于当前弧优化标记增广起点
inline bool bfs() // BFS分层
{
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    memcpy(cur, head, sizeof(head)); // 当前弧优化初始化
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1; // 如果汇点未访问过说明已经无法达到汇点，此时返回false
}
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow;
    int rmn = flow; // 剩余的流量
    for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) // 如果已经没有剩余流量则退出
    {
        cur[p] = eg; // 当前弧优化，更新当前弧
        int to = edges[eg].to, vol = edges[eg].w;
        if (vol > 0 && lv[to] == lv[p] + 1) // 往层数高的方向增广
        {
            int c = dfs(to, min(vol, rmn)); // 尽可能多地传递流量
            rmn -= c; // 剩余流量减少
            edges[eg].w -= c; // 更新残余容量
            edges[eg ^ 1].w += c; // 再次提醒，链式前向星的cnt需要初始化为1（或-1）才能这样求反向边
        }
    }
    return flow - rmn; // 返回传递出去的流量的大小
}
inline int dinic()
{
    int ans = 0;
    while (bfs())
        ans += dfs();
    return ans;
}

//题解代码
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const int N = 1e3 + 5;
int dis[N][N], pre[N], flow[N];
int n, m, k;
int bfs(int s, int e)
{
    // puts("qwq");
    queue<int> q;
    q.push(s);
    memset(pre, -1, sizeof(pre));
    flow[s] = 0x3f3f3f3f;
    while (!q.empty()) {
        int u = q.front();
        // cout << u << "::";
        q.pop();
        for (int v = 0; v <= e; v++) {
            if (dis[u][v] && pre[v] == -1) {
                pre[v] = u;
                flow[v] = min(flow[u], dis[u][v]);
                q.push(v);
            }
        }
    }
    // puts("");
    // cout << pre[e] << endl;
    // cout << flow[e] << endl;
    if (pre[e] == -1)
        return -1;
    else
        return flow[e];
}
int maxFlow(int s, int e)
{
    int delt, res = 0;
    while ((delt = bfs(s, e)) != -1) {
        // puts("qwq");
        int k = e, last = pre[k];
        while (k != s) {
            dis[last][k] -= delt;
            dis[k][last] += delt;
            k = pre[k];
            last = pre[k];
        }
        res += delt;
    }
    return res;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), m = read(), k = read();
    int h = n + m + 2;
    dis[0][1] = k;
    for (int i = 1; i <= n; i++) {
        dis[0][i + 1] = 1, dis[1][i + 1] = 1;
    }
    for (int i = 1; i <= m; i++) {
        dis[n + i + 1][h] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int t = read(), x;
        for (int j = 0; j < t; j++) {
            x = read();
            dis[i + 1][x + n + 1] = 1;
        }
    }
    cout << maxFlow(0, h) << endl;
    return 0;
}

暑期校队训练二题解

（CCPC2022湖北省赛）

B. Potion(easy version)

Description

给一个杯子，在一半处有一个刻度，每次你可以选择倒满药 or 水，然后倒出到刻度处，问能否通过以上操作获得特定的药水比例，如果没有输出-1

Solution

假设当前药的比例为 a，那么第一次接水后比例变为 $\frac{a}{2}\ or\ \frac{a+1}{2}$ ，初始状态 $a=1\ or \ -1$ .

分析可得，如果把 a 化为最简分数，那么分子总为奇数，分母总为 $2^n$ ，接水次数为 n+1 ，那么我们可以对 x 和 y 进行约分，然后判断他们是否为奇数且和是否为 2 的次幂即可

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int T;

int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    T = read();
    while (T--) {
        ll x = read(), y = read(), a = read(), b = read();
        ll g = __gcd(x, y);
        x /= g, y /= g;
        ll sum = x + y;
        ll cnt = 0;
        while (!(sum & 1)) {
            sum >>= 1;
            cnt++;
        }
        if (sum != 1)
            puts("-1");
        else
            cout << cnt + 1 << endl;
    }
    return 0;
}

F. Angel

Description

一排有 n 个洞，有一只兔子在某个洞，每个时刻必定移动到相邻的洞中，需要构造长度最短的询问序列 $q_i$ ，第 i 项表示询问在兔子第 i 次移动前是否在 $q_i$ 这个洞中，使得至少猜中一次。

Solution

考虑兔子发生移动时奇偶性必定发生改变，那么可以假设兔子的初始奇偶性。确定了奇偶性后，由于兔子一次只能走一步，所以可以把它往一边赶。最坏情况下重复两遍这个过程即可，对边界稍加讨论可以发现 $2(n − 2)$ ，大概就是这个思路下的最小值，注意特判 $n = 1, 2$ 的情况。

证明

当 n > 2 时，初始时刻在奇数位置情况的兔子和在偶数位置情况的兔子永远不会相交，且每一时刻后奇偶互换。考虑一次检查实际上是对某一类奇偶性消除了一个可能，可以发现，如果两类奇偶性都存在且存在空位，那么检查一类奇偶性会使得另一类奇偶性增加一个可能性，所以我们必须把一种奇偶性先全部消除。消除一种奇偶性情况时，另一类奇偶性会变成此类奇偶性，重复操作即可。可以发现，消除一类奇偶性至少需要 n − 2 步，则总步数至少需要 2(n − 2) 步。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int T;

int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    T = read();
    while (T--) {
        ll x = read(), y = read(), a = read(), b = read();
        ll g = __gcd(x, y);
        x /= g, y /= g;
        ll sum = x + y;
        ll cnt = 0;
        while (!(sum & 1)) {
            sum >>= 1;
            cnt++;
        }
        if (sum != 1)
            puts("-1");
        else
            cout << cnt + 1 << endl;
    }
    return 0;
}

J. Palindrome Reversion

Description

给出一个字符串，问能否反转一次子串使得字符串回文，给出方案，否则输出-1

Solution

先考虑特殊情况，当字符串已经是回文串时，直接输出 $1\ 1$ .

扩展到一般情况，先从两边将原字符串的回文部分删除，记录下删除量 $cnt$ ，一边输出时加上，剩下的即为不回文的部分。

讨论可行的情况：

两边从左到右依次相同，中间回文。反转时反转两边的子串之一

右边两个子串从左到右依次相同，左边回文。反转时反转左边和中间的子串

左边两个子串从左到右依次相同，右边回文。反转时反转右边和中间的子串

以上三种情况都是反转前缀 or 后缀，所以我们先作正向 hash 和反向 hash，同时存储进制数的幂。然后以 1 为起点向后枚举终点，如果存在方案则输出，再以末尾为终点向前枚举。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define int ll
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const unsigned ll maxn = 1e5 + 9, base = 131;
unsigned ll h1[maxn], h2[maxn], b[maxn];
char s[maxn];
int N = 0;
void initHash(char s[], int N)
{
    b[0] = 1;
    for (int i = 1; i <= N; i++) {
        b[i] = b[i - 1] * base;
    }
    for (int i = 1; i <= N; i++) {
        h1[i] = h1[i - 1] * base + s[i];
    }
    for (int i = N; i >= 1; i--) {
        h2[i] = h2[i + 1] * base + s[i];
    }
}
unsigned ll getHash1(int l, int r)
{
    return h1[r] - h1[l - 1] * b[r - l + 1];
}
unsigned ll getHash2(int l, int r)
{
    return h2[l] - h2[r + 1] * b[r - l + 1];
}
bool isRe(int l, int r)
{
    unsigned ll res1 = getHash1(1, l - 1) * b[N - l + 1] + getHash2(l, r) * b[N - r] + getHash1(r + 1, N);
    unsigned ll res2 = getHash2(r + 1, N) * b[r] + getHash1(l, r) * b[l - 1] + getHash2(1, l - 1);
    return res1 == res2;
}
signed main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    scanf("%s", s + 1);
    int l = 1, r = strlen(s + 1);
    while (l <= r && s[l] == s[r])
        l++, r--;
    int dl = l - 1;
    if (l > r) {
        puts("1 1\n");
        return 0;
    }
    for (int i = l; i <= r; i++) {
        s[++N] = s[i];
    }
    s[N + 1] = '\0';
    initHash(s, N);
    for (int i = 1; i <= N; i++) {
        if (isRe(1, i)) {
            cout << 1 + dl << ' ' << i + dl << endl;
            return 0;
        }
    }
    for (int i = N; i >= 1; i--) {
        if (isRe(i, N)) {
            cout << i + dl << ' ' << N + dl << endl;
            return 0;
        }
    }
    puts("-1 -1\n");
    return 0;
}

K. PTT

Description

给 T 组 Arcaea 的游玩成绩和谱面定数，求每次游玩的单曲 PTT

Solution

按题目给的公式算就行，注意单曲 PTT 为非负数，小于 0 需要置 0

Code

不贴

L. Chtholly and the Broken Chronograph

Description

给出一个数列 $a_1, a_2, . . . , a_n$ ，要求支持以下 4 种操作：

禁用位置 x
启用位置 x
对区间 $[l, r]$ 中启用的位置加 x
查询区间 $[l, r]$ 的和，不论每个位置状态如何

Solution

本题并不需要使用非常复杂的数据结构，仅考察了线段树的基本操作。

在线段树上的每个节点记录当前区间的和与启用状态的位置个数。 1, 2 操作单点修改状态，3 操作仅对启用位置更新和，4 操作正常查询即可。

这道题在编写过程中遇到了很多bug，主要原因还是对线段数的掌握不够深刻，许多地方忘记了传参和计算

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const int N = 1e5 + 5;
ll a[N], s[N];
struct node {
    ll l, r, cnt, sum, lazytag;
} tree[N << 2];
int n, q;
void pushup(int x)
{
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
    tree[x].cnt = tree[x << 1].cnt + tree[x << 1 | 1].cnt;
}
void pushdown(int x)
{
    node &f = tree[x], &l = tree[x << 1], &r = tree[x << 1 | 1];
    if (f.lazytag) {
        l.sum += l.cnt * f.lazytag;
        r.sum += r.cnt * f.lazytag;
        l.lazytag += f.lazytag, r.lazytag += f.lazytag;
        f.lazytag = 0;
    }
    return;
}
void build(int x, int l, int r)
{
    tree[x] = { l, r };
    tree[x].lazytag = 0;
    if (l == r) {
        tree[x].sum = a[l];
        tree[x].cnt = s[l];
        return;
    } else {
        int mid = (l + r) >> 1;
        build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
        pushup(x);
        return;
    }
}
void modify(int x, int l, int i)
{
    if (tree[x].l == tree[x].r) {
        tree[x].cnt = i;
        return;
    } else {
        
        pushdown(x);
        int mid = (tree[x].l + tree[x].r) >> 1;
        if (l <= mid) {
            modify(x << 1, l, i);
        } else {
            modify(x << 1 | 1, l, i);
        }

        pushup(x);
    }
}
void change(int x, int l, int r, int i)
{
    if (tree[x].l >= l && tree[x].r <= r) {
        tree[x].sum += tree[x].cnt * i;
        tree[x].lazytag += i;
        return;
    } else {
        pushdown(x);
        int mid = (tree[x].l + tree[x].r) >> 1;
        if (l <= mid) {
            change(x << 1, l, r, i);
        }
        if (r > mid) {
            change(x << 1 | 1, l, r, i);
        }
        pushup(x);
        return;
    }
}
ll query(int x, int l, int r)
{
    if (tree[x].l >= l && tree[x].r <= r) {
        return tree[x].sum;
    } else {
        pushdown(x);
        int mid = (tree[x].l + tree[x].r) >> 1;
        ll ans = 0;
        if (l <= mid)
            ans += query(x << 1, l, r);
        if (r > mid)
            ans += query(x << 1 | 1, l, r);
        return ans;
    }
}
int main()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        s[i] = read();
    build(1, 1, n);
    while (q--) {
        int i = read();
        if (i == 1 || i == 2) {
            ll x = read();
            modify(1, x, i - 1);
        } else if (i == 3) {
            ll l = read(), r = read(), x = read();
            change(1, l, r, x);
        } else {
            ll l = read(), r = read();
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}

暑期ACM实习摸底 题解

A. 社团招新

Description

Solution

Code

B. 字符串

Description

Solution

Code

D. 香蕉

Description

Solution

Code

K. Contest Preparation

Description

Solution

Code

L. XOR Almost Everything

Description

Solution

Code

M. Triangles

Description

Solution

Code

暑期校队训练一 题解

A. Adrien and Austin

Description

Solution

Code

G. Pyramid

Description

Solution

Code

J. Prime Gam

Description

Solution

Code

K. Kangaroo Puzzle

Description

Solution

Code

L. Magic Potion

Description

Solution

Code

暑期校队训练二 题解

B. Potion(easy version)

Description

Solution

Code

F. Angel

Description

Solution

证明

Code

J. Palindrome Reversion

Description

Solution

Code

K. PTT

Description

Solution

Code

L. Chtholly and the Broken Chronograph

Description

Solution

Code

暑期ACM实习摸底题解

暑期校队训练一题解

暑期校队训练二题解