暑期校队训练三 题解

（CCPC2022江苏省赛）

A. PENTA KILL!

Description

给出几条击杀和被击杀的信息，问是否有人完成五杀。五杀指一个人连续杀死了五个不同的对手，假设一个人被杀不影响他的五杀。

Solution

简单的 STL 运用。先建一个 map 存储一个人杀死对手的次数，对于每个次数大于等于5的，建一个map存储被杀方的次数，如果大于一则表示重复击杀，将 map 清空，最后判断 map 大小是否大于等于 5 即可

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 = 1e3 + 3;
int n;
string a[N], b[N];
map<string, int> mp;
map<string, int> mp1;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read();
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        mp[a[i]]++;
    }
    bool bo = 0;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]] >= 5) {
            for (int j = i; j < n; j++) {
                if (a[i] == a[j]) {
                    mp1[b[j]]++;
                    if (mp1[b[j]] > 1) {
                        mp1[b[j]]--;
                        if (mp1.size() < 5) {
                            mp1.clear();
                            break;
                        } else {
                            break;
                        }
                    }
                }
            }
            if (mp1.size() >= 5)
                bo = 1;
        }
    }
    if (bo)
        puts("PENTA KILL!");
    else
        puts("SAD:(");
    return 0;
}

C. Jump and Treasure

Description

从坐标为 0 的位置出发从左往右跳，只能跳到整数坐标，跳跃的距离不能超过 p;

跳到第 ii 个位置获得 aia_i 个金币，[n+1,+∞)[n + 1, +∞) 是终点;

第 x 关只能跳到 x 的倍数的位置;

Q 个询问，每次询问在某个关卡中获得的最多金币数是多少.

Solution

先考虑在第 1 关怎么做，能跳的距离不超过 p，假设走到位置 i 的最优总金币数是 f[i]f [i]，有 f[i]=maxi−j≤p(f[j])+a[i]f [i] = max_{i−j≤p} (f [j]) + a[i]

这是一个经典的单调队列优化 dp 的模型.

那么在第 k 关，能跳的位置只有 0, k, 2k... 直到 n + 1 以后，一共 n/k + 1 个位置需要考虑进去。最多一共 n 关，考虑的位置总数是 ∑k=1nnk+1=n+n∑k=1n1k=O(n ln n)∑^n_{k=1} \frac n k + 1 = n + n ∑^n_{k=1} \frac 1 k = O(n\ ln\ 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;
}
const int N = 2e6 + 5;
ll dp[N], a[N];
unordered_map<ll, ll> mp;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    int n = read(), q = read(), p = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    while (q--) {
        deque<int> q;
        int x = read();
        if (mp.count(x)) {
            printf("%lld\n", mp[x]);
            continue;
        }
        if (x > p)
            puts("Noob");
        else {
            dp[0] = 0;
            q.pb(0);
            vector<int> b;
            b.pb(0);
            for (int i = x; i <= n; i += x) {
                b.pb(i);
            }
            b.pb(n + 1);
            for (int i = 1; i < b.size(); i++) {
                while (!q.empty() && b[i] - b[q.front()] > p)
                    q.pop_front();
                dp[i] = dp[q.front()] + a[b[i]];
                while (!q.empty() && dp[q.back()] <= dp[i])
                    q.pop_back();
                q.push_back(i);
            }
            mp[x] = dp[b.size() - 1];
            printf("%lld\n", mp[x]);
        }
    }
    return 0;
}

I. Cutting Suffix

Description

把一个字符串的所有后缀划分到两个集合，每个集合非空，最小化：∑i∈T1∑j∈T2LCP(sufi,sufj)∑_{i∈T1} ∑_{j∈T2} LCP(suf_i , suf_j)

Solution

乱搞题，如果这个字符串由单一字符构成，那么我们就只把最后一个后缀(单个字母)放在一个集合，其他的放在另外一个集合，答案为s.size()-1，否则随便选取一个字符，把这个字符开头的后缀放进一个集合，另一个放进其他集合，答案为 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;
}
string s;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    cin >> s;
    bool bo = 1;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] != s[i + 1]) {
            bo = 0;
            break;
        }
    }
    if (bo) {
        cout << s.size() - 1 << endl;
    } else
        puts("0");
    return 0;
}

K. aaaaaaaaaaA heH heH nuN

Description

一个正确的字符串由两部分组成：前面是nunhehheh，后面是任意个a，先给出正确的子序列数，找到对应的字符串。

Solution

构造题，观察到对于ha...a（k个a）的贡献是 2k−12^k-1，h...ha（p个h）结尾的贡献是p，所以用二进制拼凑的思想，按位凑出来，最后把剩下的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 t;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        int n = read(), cnt = 0;
        vector<int> pos;
        for (int i = 30; i >= 0; i--) {
            if (n >> i & 1) {
                pos.push_back(i);
            }
        }
        // puts("qwq");
        if (n == 0) {
            puts("a\n");
            continue;
        } else if (n == 1) {
            puts("nunhehheha\n");
            continue;
        }
        string ans = "nunhehheh";
        if (pos.back() == 0) {
            cnt++, pos.pop_back();
        }
        cnt += pos.size();
        for (int i = 0; i < pos.size(); i++) {
            if (i == pos.size() - 1) {
                int num = pos[i];
                for (int j = 1; j < num; j++) {
                    ans += 'a';
                }
                for (int j = 1; j <= cnt; j++) {
                    ans += 'h';
                }
                ans += 'a';
                break;
            }
            int num = pos[i] - pos[i + 1];
            for (int j = 1; j <= num; j++) {
                ans += 'a';
            }
            ans += 'h';
        }

        // puts("qwq");
        cout << ans << endl;
    }
    return 0;
}

暑期校队训练四 题解

A. JB Loves Math

（2022 浙江省赛）

Description

给出两个数字 a 和 b ，你需要选择两个数字 x 和 y，每次操作，你可以选择让 a 加 x 或 a 减 y，求使得 a 操作得到 b 的最小操作数

Solution

分类讨论

  1. 当 a<ba<b 时：
    1. 如果 (b−a)%2==0(b-a)\% 2==0 ，则只需要一次操作
    2. 如果 (b−a)/2%2==0(b-a)/2 \%2==0 ，则需要两次操作
    3. 否则需要三次操作
  2. 当 a>ba>b 时：
    1. 如果 (a−b)%2==0(a-b)\%2==0 ，则只需要一次操作
    2. 否则需要两次操作
  3. 当 a==ba==b 时，显然不需要操作

Code

不贴

B. JB Loves Comma

Description

给出一个字符串，在每个子串cjb后加上逗号

Solution

模拟即可

Code

不贴

C. B Wants to Earn Big Money

Description

给出股票价格 x ，如果卖方出价小于 x 则会卖出，如果买方出价大于 x 则会买入，求交易人数

Solution

模拟即可

Code

不贴

L. Candy Machine

Description

给出一列数组，从其中选取子序列，使得序列中比序列平均值大的树最多

Solution

我们不取第一个数，在剩余数中任取一个可以得到正解的子序列，我们将这个子序列加上第一个数，势必会降低整个子序列的平均值（在序列中插入一个小于平均值的数会降低序列的平均值），原序列中大于平均值的数字个数不变，正解不受影响。相应的不取任何一个前缀，在剩余数中任取一个可以得到正解的子序列，我们将这个子序列加上他的前缀，势必会降低整个子序列的平均值（因为原数组有序，前缀的平均值必然小于后面任何一个子序列的平均值），原序列中大于平均值的数字个数不变，正解不受影响。我们再用贪心的思想来分析，如果我们在的到的一个子序列加上一个前缀，降低了整体平均值，就会使得序列中的数字会有更大可能性大于平均值，更有可能的到正解，分析可以发现，包含有正解的子序列一定被包含与所有的前缀。

所以我们对数据排序，初始化前缀和的同时二分查找数量，更新 ans 即可

Code

#include <bits/stdc++.h>
#define ll long long
#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 int N = 1e6 + 3;
int n;
int a[N];
signed main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    sort(a + 1, a + 1 + n);
    int ans = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        double avg = 1.0 * sum / (1.0 * i);
        int l = 1, r = i;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[mid] <= avg)
                l = mid;
            else
                r = mid - 1;
        }
        ans = max(ans, i - l);
    }
    cout << ans << endl;
    return 0;
}

G. Easy Glide

Description

给定平面上 n 个滑行点以及起点 S 和终点 T。

行走速度为 V1，每次经过某个滑行点后可以按 V2 速度滑行 3 秒。

求从 S 滑行到 T 所需的最少时间。

n ≤ 1000

Solution

建立一张 n + 2 个点的有向图，分别表示 n 个滑行点以及起点 S 和终点 T。

由起点向每个点连单向边，边权为 S 按 V1 走到至该点所需的时间。

由每个滑行点向其它滑行点以及终点连单向边，边权为先按 V2 滑行至多 3 秒然后按 V1 行走至目的地所需的时间。

朴素 Dijkstra 求 S 到 T 的最短路。

时间复杂度 O(n2)O(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;
}
struct node {
    double x, y;
    node(double x = 0, double y = 0)
        : x(x)
        , y(y)
    {
    }
};
const int N = 1e3 + 13;
int n;
double getd(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
node s, t;
double v1, v2;
vector<node> v;
double d[N][N];
double ans[N];
bool vis[N];
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++) {
        double x = read(), y = read();
        v.pb(node(x, y));
    }
    s.x = read(), s.y = read(), t.x = read(), t.y = read();
    v1 = read(), v2 = read();
    for (int i = 1; i <= n + 1; i++) {
        if (i == n + 1) {
            d[0][i] = getd(s, t) / v1;
        } else {
            d[0][i] = getd(s, v[i - 1]) / v1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            if (i == j)
                d[i][j] = 0;
            else if (j == n + 1) {
                double tmp = getd(v[i - 1], t);
                if (tmp < 3.0 * v2) {
                    d[i][j] = tmp / v2;
                } else {
                    d[i][j] = 3.0 + (tmp - 3.0 * v2) / v1;
                }
            } else {
                double tmp = getd(v[i - 1], v[j - 1]);
                if (tmp < 3.0 * v2) {
                    d[i][j] = tmp / v2;
                } else {
                    d[i][j] = 3.0 + (tmp - 3.0 * v2) / v1;
                }
            }
        }
    }

    for (int i = 0; i <= n + 1; i++) {
        ans[i] = 1000000000;
    }
    ans[0] = 0;
    for (int i = 0; i <= n + 1; i++) {
        int k = -1;
        for (int j = 0; j <= n + 1; j++) {
            if (!vis[j] && (k == -1 || ans[j] < ans[k])) {
                k = j;
            }
        }
        vis[k] = 1;
        for (int j = 0; j <= n + 1; j++) {
            if (!vis[j] && ans[k] + d[k][j] < ans[j])
                ans[j] = ans[k] + d[k][j];
        }
    }
    printf("%.12lf\n", ans[n + 1]);
    return 0;
}

I. Barbecue

Description

给定一个长度为 n 的字符串 S，q 次询问，每次询问指定 S 的一个子串，两个人在该子串上进行博弈。

博弈双方轮流删去当前串开头或结尾的一个字符，碰到回文串的人输。

预测两人都按最优策略操作时最终谁会获胜。

n,q≤106n, q ≤ 10^6

Solution

首先通过 Hash 等方式 O(1) 特判起始串为回文串的情况。

对于接下来任意一个局面，先手操作前一定不是回文串。

若先手无法进行任何操作，则说明无论删去开头还是结尾都会得到回文串。

容易发现满足条件的串只能形如 ab, abab, ababab, . . .

这说明终止态的长度一定是偶数，因此输赢只和起始串长度的奇偶性有关。

时间复杂度 O(n+q)O(n + q)

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;
unsigned ll p = 13331;
unsigned ll hasha[N], hashb[N], power[N];
void pre(string s, int len)
{
    hasha[0] = hashb[0] = 0, power[0] = 1;
    for (int i = 1; i <= len; i++) {
        hasha[i] = hasha[i - 1] * p + (s[i] - 'a');
        hashb[i] = hashb[i - 1] * p + (s[len - i + 1] - 'a');
        power[i] = power[i - 1] * p;
    }
}
bool check(int l, int r, int len)
{
    unsigned ll h = hasha[r] - hasha[l - 1] * power[r - l + 1];
    unsigned ll g = hashb[len - l + 1] - hashb[len - r] * power[r - l + 1];
    return h == g;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    int len = read(), q = read();
    string s;
    cin >> s;
    s = ' ' + s;
    pre(s, len);
    while (q--) {
        int l = read(), r = read();
        if (check(l, r, len))
            puts("Budada");
        else {
            if ((r - l + 1) & 1) {
                puts("Putata");
            } else {
                puts("Budada");
            }
        }
    }
    return 0;
}

M. BpbBppbpBB

Description

给出B和p/b的点阵图和他们组成的点阵图，求其中两个字母的数量，图中的字母没有重叠，字母可以转换方向

Solution

因为没有重叠，可以先找到中间的白块，然后判断一下这个白块是 C 的还是 S 的，直接模拟求解即可。
因为每个图形黑方块的数量和中间白色块的数量是固定的，所以考虑推数学公式。
设有 x 个 C，y 个 S，记 sumbsum_b 为黑方块的数量，cntwcnt_w 为中间白色块的数量。
得到方程：

146∗x+100∗y=sumb146∗x+100∗y=sum_b
2∗x+y=cntw2∗x+y=cnt_w
推出 x=100∗cntw−sumb54,y=cntw−2∗xx=\frac{100∗cnt_w−sum_b}{54},y=cnt_w−2∗x。

在判断中间白块的时候，起码要判断 6 * 6 的，4 * 4 的会被卡。因为四个角的黑块都属于一个图形的时候，这个位置的白块其实不需要被记录。

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 = 1e3 + 5;
const string s[] = {
    "######",
    "##..##",
    "#....#",
    "#....#",
    "##..##",
    "######"
};
int n, m, cntw, cntb;
char a[N][N];
bool solve(int x, int y)
{
    for (int i = 0; i <= 5; i++) {
        for (int j = 0; j <= 5; j++) {
            if (x < 1 || x + i > n || y < 1 || y + j > m || a[x + i][y + j] != s[i][j])
                return 0;
        }
    }
    return 1;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '#')
                cntb++;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.')
                cntw += solve(i - 1, j - 2);
        }
    }
    int x = (cntw * 100 - cntb) / 54;
    cout << x << ' ' << cntw - 2 * x << endl;
    return 0;
}

暑期校队训练五 题解

（第15届吉林省赛）

A. Random Number Checker

Description

给出一组数列，询问奇数个数与偶数个数差有没有超过 1

Solution

模拟求解即可

Code

不贴

B. Arithmetic Exercise

Description

给出三个数A,B,K求 AB\frac{A}{B} 保留 k 位小数，四舍五入，保证不会进两位及以上。

Solution

模拟求解即可，注意末尾四舍五入的判断

Code

不贴

E. Great Detective TJC

Description

给出一组数列，问是否存在两个数的异或和为 1

Solution

由异或性质可得，两数异或和为 1，则奇数比偶数多 1，所以将数组分为奇数和偶数两组，对每一个奇数查询相对应的偶数是否存在，或者直接用map查询。

Code

不贴

G. Matrix Repair

Description

给出一个方阵，由 -1,0,1 组成，同时每行每列给出一个校验码，表示这一行（列）数字的异或和，要求方阵中的-1改为0/1使得方阵符合校验码要求，保证存在方案，若有多个方案则输出-1

Solution

每次填空，在方阵中查询只剩下一个-1的行（列），根据所在的行和列填数，同时维护一个存放行列中-1数量的数组，当数组全部为0时退出，若不存在符合条件的行和列则输出-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;
}
const int N = 1e3 + 3;
int n;
int a[N][N];
int rr[N], cc[N], r[N], c[N];
bool bo = 0;
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++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = read();
            if (a[i][j] == -1) {
                r[i]++;
                c[j]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        rr[i] = read();
    for (int i = 1; i <= n; i++)
        cc[i] = read();
    while (1) {
        int ans = -1;
        bool f = 0;
        for (int i = 1; i <= n; i++) {
            if (r[i] != 0)
                f = 1;
            if (r[i] == 1) {
                ans = i;
                break;
            }
        }
        if (ans == -1) {
            for (int i = 1; i <= n; i++) {
                if (c[i] != 0)
                    f = 1;
                if (c[i] == 1) {
                    ans = i;
                    break;
                }
            }
            if (ans == -1) {
                if (f == 0) {
                    bo = 1;
                    break;
                } else {
                    puts("-1");
                    break;
                }
            } else {
                int cnt = 0, now = 0;
                for (int i = 1; i <= n; i++) {
                    if (a[i][ans] == 1)
                        cnt++;
                    else if (a[i][ans] == -1)
                        now = i;
                }
                r[now]--, c[ans]--;
                if (cc[ans] & 1 && cnt & 1) {
                    a[now][ans] = 0;
                } else if (cc[ans] % 2 == 0 && cnt % 2 == 0) {
                    a[now][ans] = 0;
                } else
                    a[now][ans] = 1;
            }
        } else {
            int cnt = 0, now = 0;
            for (int i = 1; i <= n; i++) {
                if (a[ans][i] == 1)
                    cnt++;
                else if (a[ans][i] == -1)
                    now = i;
            }
            r[ans]--, c[now]--;
            if (rr[ans] & 1 && cnt & 1) {
                a[ans][now] = 0;
            } else if (rr[ans] % 2 == 0 && cnt % 2 == 0) {
                a[ans][now] = 0;
            } else
                a[ans][now] = 1;
        }
    }
    if (bo) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j != 1) {
                    cout << " ";
                }
                cout << a[i][j];
            }
            puts("");
        }
    }
    return 0;
}

H. Visit the Park

Description

给出一个存在重边的无向图和路径上的数，按照给出的路径遍历图上的点，同时从左往右写下各条路径上的数，问最终得出的数字的期望。

Solution

此处引入公式

img

所求的期望等于 每条路的期望×这条路的贡献每条路的期望\times 这条路的贡献，所以我们只要对路径上所有路做一次操作即可得到总共的期望。

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 mod = 998244853;
int n, m, k;
int a[300003];
map<pair<int, int>, vector<int>> mp;
map<pair<int, int>, pair<int, int>> edge;
ll fm(ll x, ll y)
{
    ll tmp = 1;
    while (y) {
        if (y & 1)
            tmp = tmp * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return tmp;
}
ll ans = 0, pos = 1, t = fm(10, mod - 2);
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        if (u < v)
            mp[{ u, v }].pb(w);
        else
            mp[{ v, u }].pb(w);
    }
    bool bo = 0;
    for (int i = 1; i < k - 1; i++) {
        pos = pos * 10 % mod;
    }//这里预处理当前路的贡献
    for (int i = 1; i <= k; i++)
        a[i] = read();
    for (int i = 1; i < k; i++) {
        int u = min(a[i], a[i + 1]), v = max(a[i], a[i + 1]);
        auto tmp = mp[{ u, v }];
        int s = tmp.size();
        if (s == 0) {
            bo = 1;
            break;
        }
        ll x = fm(s, mod - 2);
        for (int j = 0; j < s; j++) {
            ans = (ans + (pos * tmp[j]) % mod * x) % mod;//对每条路计算期望
        }
        pos = pos * t % mod;//利用乘法逆元递推下一位的贡献
    }
    if (bo)
        puts("Stupid Msacywy!");
    else
        cout << ans << endl;
    return 0;
}

K. Bracket Sequence

Description

给出括号的组数和括号的种类，问相同种类括号全部闭合的序列有多少个，需要取模

Solution

单种的序列个数遵循卡特兰数，即 h(n)=C(2n,n)/(n+1)h(n)=C(2n,n)/(n+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;
}
const ll mod = 1e9 + 7, N = 2e5 + 10;
int n, k;
ll a[N], inv[N];
ll fm(ll x, ll y)
{
    ll tmp = 1;
    while (y) {
        if (y & 1)
            tmp = tmp * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return tmp;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), k = read();
    a[0] = inv[0] = 1ll;
    for (int i = 1; i < N; i++) {
        a[i] = a[i - 1] * i % mod;
        inv[i] = inv[i - 1] * fm(i, mod - 2) % mod;
    }
    ll ans = fm(k, n) % mod;
    ans = (ans * a[2 * n] % mod * inv[n] % mod * inv[n] % mod * fm(n + 1, mod - 2) % mod) % mod;
    cout << ans << endl;
    return 0;
}

L. Suzuran Loves String

Description

一个字符串，你可以做出如下操作:

  1. 从末尾删除一个字符

  2. 从末尾加上一个字符

设d(A,B)d(A,B)指从 A 转换到 B 的最小操作数，现对每一组后缀求d(A,B)d(A,B)的最大值

Solution

分类讨论：

  1. 如果字符串没有重复，如样例，则最大值为 s.length()*2-1
  2. 如果字符串前缀存在重复，但字符串不止一个字母，则最大值为s.length()*2-i，其中 i 代表第一个不同的字母的位置
  3. 如果仅包含一个字母，则最大值为s.length()-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 T;
string s;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    T = read();
    while (T--) {
        cin >> s;
        bool bo = 0;
        int cnt = 0, x = 0, i = 0;
        for (i = 1; i < s.length(); i++) {
            if (s[i] == s[i - 1]) {
                bo = 1;
                cnt++;
            } else {
                x = i;
                break;
            }
        }
        if (i == s.length() && bo) {
            cout << s.length() - 1 << endl;
        } else if (!bo) {
            cout << (s.length() << 1) - 1 << endl;
        } else
            cout << (s.length() << 1) - x << endl;
    }
    return 0;
}

M. Sequence

Description

求序列中最大数和最小数的差与序列长度的乘积

Solution

模拟即可

Code

不贴

暑期ACM实习考核 题解

A. 最小代价

Description

给定两个字符串 s,ts,t（均由小写英文字母组成），长度分别为n,m(1≤n,m≤5⋅103)n,m(1\le n,m \le 5 \cdot 10^3)。求将 s 转换成 t 所使用的最少操作数，即最小代价。

你可以对字符串有以下三种操作：

  1. 插入任意一个字符到任意位置。

  2. 删除任意一个字符。

  3. 替换任意一个字符。

Solution

简单的DP题。

dp[i][j]dp[i][j] 表示为 s[1...i]s[1...i] 转换成 t[1...j]t[1...j] 的最小代价（使s，t下标从1开始），且 dp[i][j]dp[i][j] 可由 dp[i−1][j]dp[i-1][j] 或 dp[i−1][j−1]dp[i-1][j-1] 或 dp[i][j−1]dp[i][j-1] 转移而来

即：f[i][j]=f[i−1][j−1] (s[i−1]==t[j−1])orf[i][j]=min(f[i−1][j−1],min(f[i−1][j],f[i][j−1]))+1 (s[i−1]≠t[j−1])f[i][j] = f[i - 1][j - 1] \ (s[i - 1] == t[j - 1]) or f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1\ (s[i - 1] ≠ t[j - 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;
}
const int N = 5e3 + 3;
int n, m;
string s, t;
int f[N][N];
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), m = read();
    cin >> s >> t;
    for (int i = 1; i <= n; i++) {
        f[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        f[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                f[i][j] = f[i - 1][j - 1];
            } else
                f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

B. 最长括号匹配

Description

给定一个只含有'('和')'字符的字符串，长度为 n,(1≤n≤103)n,(1\le n \le 10^3) 。求最长有效括号子串（格式正确且连续）的长度。

Solution

设 f[i]f[i] 表示结尾为 s[i]s[i] 的子串的最长长度，因为题设所求为连续子串，所以当 s[i]==′)′s[i]==')' 时，判断前一个是不是匹配，如果是则延长合法子串，如果不是，那么查询 s[i−1]s[i-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;
}
const int N = 1e3 + 5;
string s;
int f[N];
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    cin >> s;
    int ans = 0, len = s.length();
    for (int i = 1; i < len; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(')
                f[i] = (i >= 2 ? f[i - 2] : 0) + 2;
            else if (i - f[i - 1] > 0 && s[i - f[i - 1] - 1] == '(')
                f[i] = f[i - 1] + ((i - f[i - 1]) >= 2 ? f[i - f[i - 1] - 2] : 0) + 2;
            ans = max(ans, f[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

C. 染色

Description

n个球顺序排成一行，一开始都为白色，现在需要全部染成黑色，每个数都与他相邻的节点连了一条边，每选择一个球染色，与它直接连边的球也会被染，可以重复染色，问最少几次可以把所有球染成黑色。

Solution

看起来题目很复杂，其实就是n/3上取整

Code

不贴

D. 树？

Description

给定一颗根为root，有n个节点的二叉树，非叶子节点一定有两个儿子，每个叶子节点 aia_i 包含一个数字 valueivalue_i ，每个非叶子节点包含一个运算符号“+”或者“-”，你可以从root中序遍历一次得到一个运算式子（有运算优先级，举例子说明）并计算式子的值为ans，你可以任意交换任意非叶子节点的左右儿子顺序，使得中序遍历后得到的ans最大​

Solution

要让计算结果最大，要么让加的数最大，要么让减的数最小。每次都判断计算结果是最大还是最小太麻烦，所以只要每次都计算最大和最小值就可以了，直接对二叉树进行深搜，如果碰到数字那么返回本身，否则记录交换计算的最大值和最小值后回溯，可以保证得到正确的答案。

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;
struct node {
    string x;
    int fa, son1, son2;
};

int n, root;
vector<node> a(N << 1);
vector<int> r[N << 1];
pair<ll, ll> solve(int now)
{

    if (a[now].x != "-" && a[now].x != "+") {
        ll f = a[now].x[0] == '-' ? -1ll : 1ll, sum = 0;
        for (auto i = 0; i < a[now].x.length(); i++) {
            if (a[now].x[i] == '-')
                continue;
            else
                sum = sum * 10 + (a[now].x[i] - '0');
        }
        return make_pair(sum * f, sum * f);
    } else {
        bool bot = (a[now].x == "-") ? 1 : 0;
        pair<ll, ll> lson = solve(a[now].son1), rson = solve(a[now].son2);
        if (bot == 1) {
            ll maxi = max({ lson.x - rson.y, lson.y - rson.x, lson.y - rson.y, lson.x - rson.x,
                   rson.x - lson.x, rson.y - lson.y, rson.x - lson.y, rson.y - lson.x }),
               mini = -maxi;
            return make_pair(maxi, mini);
        } else {
            ll maxi = max({ lson.x + rson.y, lson.y + rson.x, lson.y + rson.y, lson.x + rson.x }),
               mini = min({ lson.x + rson.y, lson.y + rson.x, lson.y + rson.y, lson.x + rson.x });
            return make_pair(maxi, mini);
        }
    }
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    n = read(), root = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        r[u].pb(v), r[v].pb(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x;
    }
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        int cnt = 0;
        for (auto i = 0; i < r[tmp].size(); i++) {
            if (r[tmp][i] != a[tmp].fa) {
                if (cnt == 0) {
                    a[tmp].son1 = r[tmp][i];
                    a[r[tmp][i]].fa = tmp;
                    q.push(r[tmp][i]);
                    cnt++;
                } else {
                    a[tmp].son2 = r[tmp][i];
                    a[r[tmp][i]].fa = tmp;
                    q.push(r[tmp][i]);
                }
            }
        }
    }

    cout << max(solve(root).x, solve(root).y) << endl;
    return 0;
}

E. 算数

Description

操场上有 n 个人，第 i 个人在操场人数不多于 aia_i 时会离开，问最后有多少同学留着

Solution

排序一下，从大到小判断会不会离开，如果大的不离开那么小的必然也不会离开，所以直接输出。

Code

不贴

F. OS

Description

假设当前操作系统的内存管理使用的是固定分区分配方式，并采用最佳适应(Best fit)算法来分配内存。也就是说当操作系统要为进程分配内存时，要将系统内存的空闲内存块按容量递增的方式形成空闲分区表，并找到第一个满足要求的空闲分区分配给此进程。而每为一个进程分配一个足够大的空闲分区块后，就会使得此空闲分区块的容量发生变化，所以操作系统要对上述的空闲分区表重新排序使其保持容量递增。假设当前内存中有n个空闲分区块，并有m个进程依次需要操作系统为其分配内存。问操作系统是否能顺利的为这些进程分配内存空间，如果能，请输出分配完之后的空闲分区表；如果不能请输出-1。

Solution

难点全在读题。其实就是进程从头到尾进入，内存从小到大排序，遇到能用的直接用，内存顺序调整为从小到大的。
看起来又要排序又要查找，实际上就是找一个能装下的最小的内存，直接对每个进程查找一遍即可，时间复杂度 O(mn)O(mn)，刚好过 1e4。
当然也可以压缩时间，用 multiset 之类的 STL 实现快速查找，可以压缩到 O(mlogn)O(m log n)

Code

不贴

I. 救救qq

Description

给出qq的答案和满分答案，同时给出每题的分数和qq可以修改的次数，问qq最多得积分

Solution

对的不管，不对的从大到小修改

Code

不贴

J. 排名 Rank

Description

现在有 n 个同学。第i个同学的学业成绩 AiA_i，品行成绩为 BiB_i，编号为 i。

我们需要出一份排名，其中学业成绩占比 80%， 品行成绩占比 20%。

输出一份排名有点麻烦，咱们只看一下第一是谁就好了。

成绩相同，则输出编号靠前的一位同学。（靠前即编号小的那个）

Solution

直接模拟，没什么可说的，注意用double

Code

不贴

还是排名 Always Rank

Description

在二维平面直角坐标系的第一象限上，有无数的个人，每个人都在一个坐标点上。这无数个人想要排名，
但是我们分值通过计算每个人和所有得分点的曼哈顿距离之和而得的。
第i个人的分值Score的定义如下：

Socre=∑j=1nManhattan(i,j)Socre = \sum \limits_{j=1}^nManhattan(i,j)

Manhattan(i,j)=∣xi−xj∣+∣yi−yj∣Manhattan(i, j) = |x_i - x_j| + |y_i - y_j|

输出Score最小的人有几个。

Solution

如果是奇数个点，那么最小的点肯定在最中间，所以只有一个。如果是偶数个点，那么最小的点为最中间的 x/y 各两个坐标围成的矩形。
所以直接找出来就行

Code

不贴

L. 帮帮小冷

Description

小冷有一个大小为n的数组，小冷不喜欢很大的数，他想尽可能使数组的和尽可能小，现在只有一种使数组变小的办法，若数字c为数组中每一个数的因数的话，那么便可以数组中的所有数都除以c，小冷想知道最小的数组的和。

Solution

就是求数组的公因数，除完公因数求和。

Code

不贴

M. 凸包面积

Description

如题，求点集的凸包面积

Solution

板子题，有时间的话另外开一个Blog讲计算几何的知识。

详细知识请看 XMU Pecco 佬的 算法学习笔记(63): 计算几何基础

Code

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const int mod = 2013;
const int N = 1e5 + 10;

int n;
struct Point {
    int x, y;
} point[N];
// 叉积 求 ab x ac -> >0 c在 b 左
int cross(Point a, Point b, Point c)
{
    int x1 = b.x - a.x, y1 = b.y - a.y;
    int x2 = c.x - a.x, y2 = c.y - a.y;
    return x1 * y2 - x2 * y1;
}

#define C(x) ((x) * (x))
int dis(Point a, Point b)
{
    return C(a.x - b.x) + C(a.y - b.y);
}

bool cmp(Point a, Point b)
{
    int t = cross(point[0], a, b);
    return t ? t > 0 : dis(point[0], a) > dis(point[0], b);
}

//进行处理，用栈来存元素，当有有拐趋势，则出栈。
int stk[N], top = -1;
void Graham_scan()
{
    stk[++top] = 0;
    stk[++top] = 1;
    stk[++top] = 2;
    for (int i = 3; i < n; i++) {
        while (cross(point[stk[top - 1]], point[stk[top]], point[i]) <= 0)
            --top;
        stk[++top] = i;
    }
}

signed main()
{
    IOS
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n;
        top = -1;
        for (int i = 0; i < n; i++) {
            cin >> point[i].x >> point[i].y;
            if (i) {
                if (point[i].y == point[0].y && point[i].x < point[0].x)
                    swap(point[0], point[i]);
                else if (point[i].y < point[0].y)
                    swap(point[0], point[i]);
            }
        }
        if (n < 3) {
            cout << "0.0" << endl;
            continue;
        }
        sort(point + 1, point + n, cmp);
        int cnt = 2;
        for (int i = 2; i < n; i++)
            if (cross(point[0], point[i - 1], point[i]) != 0)
                point[cnt++] = point[i];
        n = cnt;
        Graham_scan();
        double res = 0;
        for (int i = 2; i <= top; i++)
            res += cross(point[0], point[stk[i - 1]], point[stk[i]]);
        cout << fixed << setprecision(6) << (res / 2) << endl;
    }
    return 0;
}