CCPC2024 校内选拔赛题解

博主： tony102
发布时间：2024 年 08 月 19 日
485 次浏览
暂无评论
2081字数
分类：题解资料比赛记录

## T1 移动路线

### 方法1

从直觉上来看，顺时针的路线倾向于向右转，逆时针的路线倾向于向左转。

我们可以规定左转是 90 度，右转就是 -90 度；通过手动模拟几个样例可以发现，如果最终的角度是 360度，那么一定是逆时针的；如果是 -360 度，那么就是顺时针的。

这样，我们就可以计算出每一次前进旋转的角度，从而统计出走到终点的角度。

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

map<char, int> mp;

int cal(char a, char b) { // 计算从a方向到b方向旋转的角度
    int x = mp[a], y = mp[b];
    if(x == y) return 0;
    if(y - x == 90 || y - x == -270) return 90;
    return -90;
}

int main() {
    mp['E'] = 0, mp['N'] = 90, mp['W'] = 180, mp['S'] = 270;
    int n, sum;
    string s;
    cin>>n;
    while(n--) {
        cin>>s;
        sum = 0;
        for(int i = 0; i < s.size(); ++i) {
            char a = s[i], b;
            if(i == s.size() - 1) b = s[0];
            else b = s[i + 1];
            sum += cal(a, b);
        }
        if(sum == 360) cout<<"CCW\n";
        else cout<<"CW\n";
    }
    return 0;
}
```

### 方法2

我们画几个图其实可以观察到，逆时针一定是往左转的次数多，顺时针永远是向右转的次数多，我们只要记录往左往右转的次数即可。

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

int main() {
    int n;
    cin>>n;
    while(n--) {
        string s;
        cin>>s;
        int cnt1 = 0, cnt2 = 0;
        for(int i = 1; i < s.size(); ++i) {
            if(s[i] != s[i - 1]) {
                if(s[i - 1] == 'N') {
                    if(s[i] == 'W') ++cnt1; // 逆时针
                    else ++cnt2; // 顺时针
                }
                if(s[i - 1] == 'S') {
                    if(s[i] == 'E') ++cnt1;
                    else ++cnt2;
                }
                if(s[i - 1] == 'W') {
                    if(s[i] == 'S') ++cnt1;
                    else ++cnt2;
                } 
                if(s[i - 1] == 'E') {
                    if(s[i] == 'N') ++cnt1;
                    else ++cnt2;
                }
            }
        }
        if(cnt1 > cnt2) cout<<"CCW\n";
        else cout<<"CW\n";
    }
    return 0;
}
```

## T2 圆形切割

我们可以采用逆向思维，顺时针旋转园等价于逆时针旋转刀，我们假设第一刀为 0 度，然后我们可以记录每一刀切的角度。

用一个桶数组 $f[i]$ 表示 i 这个角度是否切了，最后枚举 $[0,365]$ 的每一个角度，如果它切了就和上一个角度求最大值。

【注意】

别忘了，最后一刀还要和第一刀 0 度求一个圆心角的差值，它也有可能是最大的。

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

int main(){
    int n, a, last = 0;
    bool f[370] = {false};
    f[0] = true;
    cin>>n;
    while(n--) {
        cin>>a;
        last = (last + a) % 360; // 当前切的角度
        f[last] = true;
    }
    last = 0;
    int ans = 0;
    for(int i = 1; i < 360; ++i) {
        if(f[i]) {
            ans = max(ans, i - last); // 与上一刀求圆心角
            last = i;
        }
    }
    ans = max(ans, 360 - last); // 最后一刀和第一刀求圆心角
    cout<<ans;
    return 0;
}
```

## T3 连加连乘

暴力枚举时间复杂度为 $O(n^2)$ 的，会超时。

对于 $\overline{A_i}$，我们可以预处理出前缀和 $sum[i]=a[1]+a[2]+\dots+a[i]$，那么 $\overline{A_i}=\left(a_1+a_2+\ldots+a_{i-1}\right)-\left(a_{i+1}+a_{i+2}+\ldots+a_n\right)=sum[i-1]-(sum[n]-sum[i])$；

对于 $\overline{B_i}$，我们可以预处理出前缀积 $pre[i]=a[1]*a[2]*\dots*a[i]$，和后缀积 $last[i]=a[n]*a[n-1]*\dots*a[i]$，那么 $\overline{B_i}=\frac{a_1 \times a_2 \times \ldots \times a_n}{a_i} \bmod (10^9+7)=pre[i-1]*last[i+1] \bmod (10^9+7)$

【注意】求连乘时，要用 long long，因为两个余数相乘可能爆掉 int。

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

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
long long a[maxn], sum[maxn], pre[maxn], last[maxn], n;

int main() {
    cin>>n;
    for(int i = 1; i <= n; ++i) {
        cin>>a[i];
        sum[i] = sum[i - 1] + a[i]; // 前缀和
    }
    pre[0] = 1;
    for(int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] * a[i] % mod; // 前缀积
    }
    last[n + 1] = 1;
    for(int i = n; i >= 1; --i) {
        last[i] = last[i + 1] * a[i] % mod; // 后缀积
    }
    for(int i = 1; i <= n; ++i) {
        long long ans1 = sum[i - 1] - (sum[n] - sum[i]);
        long long ans2 = pre[i - 1] * last[i + 1] % mod;
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}
```

## T4 牛车采矿

* 考点：**简单数学推导**、**几何（初中部分）**、分类讨论
* 难度 CSP T1+

### 测试点 1~4

当矿只有一个点的时候，答案就是两个点之间的距离，按要求输出即可。

### 测试点5~8

因为采矿车的坐标都是整数点，那么到矿区的距离就是到四个点距离的最小值。

### 测试点 9

仿照测试点5~8的思路，我们暴力枚举矩形内的所有点整数坐标点，那么矿车到矿区的距离，就是矿车与这些点的距离的最小值。

时间复杂度为 $O(n^3)$。

### 测试点 10

我们尝试用一点几何知识去分析问题。

![test6题解图片.png](https://img.picui.cn/free/2024/08/19/66c23296903b2.png)

我们可以把点分成这8块，A区域内的到矩形的距离就是到B点的距离，B区域内的点的距离就是到 BC这条边的距离。

其他地方同样照此分析。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 1000010;
int n, xl, xr, yl, yr;
int main() {
    cin >> n;
    cin >> xl >> yl >> xr >> yr;
    db ans = 1e9;
    int ansid = 0;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        db dis;
        if (xl <= x && x <= xr)
            dis = min(abs(y - yl), abs(y - yr));
        else if (yl <= y && y <= yr)
            dis = min(abs(x - xl), abs(x - xr));
        else
            dis = min(min(sqrt((x - xl) * (x - xl) + (y - yl) * (y - yl)),
                          sqrt((x - xl) * (x - xl) + (y - yr) * (y - yr))),
                      min(sqrt((x - xr) * (x - xr) + (y - yl) * (y - yl)),
                          sqrt((x - xr) * (x - xr) + (y - yr) * (y - yr))));
        if (dis < ans)
            ans = dis, ansid = i;
        printf("%.9lf ", dis);
    }
    cout << endl;
    cout << ansid << endl;
    return 0;
}
```

## T5 海明码

* 考点：**位运算**、**简单模拟**。
* 难度 CSP-J T2+

### 原理

首先因为 $a_i$ 只能是 $0/1$ ，那么若 $a_i$ 发生了改变则一定是 $1\to 0$ 或 $0\to 1$，等价于 $A_i=a_i\oplus 1$ 。

然后考虑为什么我们按照小 A 提供的过程就可以还原 ？

* 若 $C\oplus A_1\oplus A_2\oplus...\oplus A_n=0$ ，则说明 $a_1a_2...a_n=A_1A_2...A_n$ 。
  
  因为若某一个 $A_i=a_i\oplus 1$，那么 $C\oplus A_1\oplus A_2\oplus...\oplus A_n=c\oplus a_1\oplus a_2\oplus...\oplus a_n\oplus 1$ ，而 $c\oplus a_1\oplus a_2\oplus...\oplus a_n$ 是为 $0$ 的，所以 $C\oplus A_1\oplus A_2\oplus...\oplus A_n$ 就会等于 $1$。
* 若 $C\oplus A_1\oplus A_2\oplus...\oplus A_n=1$ ，按接下来的步骤处理：
  
  * 设一个未知数 $f$ 。
    
    这里的 $f$ 的含义就是被改变了的位置的下标。
  * 对于每一个 $i$ ，我们设 $d_i$ 的值为所有二进制第 $i$ 位为 $1$ 的数 $j$ 的 $A_j$ 异或和.
    
    * 若 $d_i\oplus B_i=1$ ，我们就令 $f$ 二进制的第 $i$ 位是 $1$ 。
    * 若 $d_i\oplus B_i=0$ ，我们就令 $f$ 二进制的第 $i$ 位是 $0$ 。
      
      原理和上面的类似，若 $d_i\oplus B_i=1$，则说明是一个 二进制第 $i$ 位是 $1$ 的某个下标的数被改变了，若$d_i\oplus B_i=0$ 则说明所有二进制第 $i$ 位是 $1$ 的下标的数都没被改变。
  * 最后若 $f=0$  则 $a_1a_2...a_n=A_1A_2...A_n$ 。
    
    若 $f=0$ 则说明是 $C$ 被改变了。
  * 否则对于所有 $i\neq f,a_i=A_i$ 而 $A_f=a_f\oplus1$ 。

### 测试点1~4 5~8

如果你读懂了题，那么应该是可以模拟出来的。

### 测试点9~11

留给 $O(n^2)$ 的写法。

### 测试点12~14,15~17,18~19

正常按照题目给的办法模拟。

先枚举二进制的位数 $i$ ，然后枚举每一个下标 $j$ ，计算出 $d_i$ ，然后还是按照题意处理即可。

因为不熟悉位运算而不会处理 $d_i$ 的同学可以重点学习一下。

时间复杂度 $O(n\log n)$。

### 测试点 20

如果我们再仔细观察一下 $d_i$ 形成 $f$ 的过程 ，实际上 $f$ 等价于所有 $A_i=1$ 的 $i$ 的异或和。

这样复杂度就优化到了 $O(n)$ 。

但其实正常实现的 $O(n\log n)$ 的算法也是能过的。

```
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 10000000;
char S[maxn];
int n, a[maxn];
int main() {
    cin >> n;
    int t = ceil(log2(n + 1));
    // printf("%.9lf",log2(n+1));
    scanf("%s", S + 1);
    for (int i = 1; i <= n + t + 1; ++i) a[i] = S[i] - '0';
    int op = a[n + t + 1];
    for (int i = 1; i <= n; ++i) op ^= a[i];
    // cout<<"op="<<op<<" t="<<t<<endl;
    if (op == 1) {
        int an = 0;
        for (int j = 1; j <= n; ++j)
            if (a[j])
                an ^= j;

for (int i = 0; i < t; ++i)
            if (a[n + i + 1])
                an ^= (1 << i);
        if (an)
            a[an] ^= 1;
    }
    for (int i = 1; i <= n; ++i) printf("%d", a[i]);
    return 0;
}
```

## T6 最短路问题

* 考点：**图论**，**建图方法**，**最短路**。
* 难度：CSP-J T3

### 测试点1~4

暴力应该是能过的。

### 测试点5~8

留给暴力建图，然后跑最短路算法，SPFA和dij都是可以过的。

复杂度为 $O(n^2)$。

### 测试点9~12

注意思考如果 $m=0$ ，答案是什么？ 其实就是 $i-1$ 。

那么加了一条边 $x,y,z$ 会改变什么？

我们设 $x<y$ ，那么对于 $2\le i\le x$ ，其答案还是$i-1$ ，但是对于点 $y$ 来说，其答案就是 $\min(x+z-1,y-1)$ 。

然后对于 $x+1\le i\le y-1$ 的点，他的最短路就是由 $x$ 到他和由 $y$ 到他的两条路长度中的较小值。

对于 $y+1\le i\le n$ 的点 ，他的最短路就是和由 $y$ 到他的路径。

### 测试点 13~16

我们仿照上一档的做法，我们可以做出一个推论，就是对于哪些没有连上额外边的点，我们可以把暂时忽略掉他，因为他不会对其他点的最短路做出贡献。

所以我们就可以把所有被额外边连到的点都拿出来，加上 $1$ 号节点，形成一个子图，在子图中跑最短路。

然后其他点的最短路一定是点集中的某个点在直接到他。

复杂度是 $O(n+m^2)$。

### 测试点 17~20

通过上面两档部分分的分析，如果你很敏感的话就可以发现，许多一类边是无效的。

进一步发现，其实我们只保留 $i$ 到 $i+1$ 边权为 $1$ 的双向边是足够的。

所以就可以直接跑最短路，使用dij可以做到 $O(n\log n)$ 的复杂度。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

## T7 序列分段

首先要注意到最优选取方案一定是一下三种中的一种：

* $a_x\ |\ a_{x+1},...,a_{y-1}\ |\ a_y$，其中 $a_x\sim a_y$ 的最大值在中间一段，因为划分点往两边扩展一定会让答案不增，所以最终两边就会只包含 $a_x$ 和 $a_y$ 。
  
  所以这种情况我们维护区间最大值就可以得到答案。
* $a_x,a_{x+1},...,a_{p-1}\ |\ a_{p}\ |\ a_{p+1},...,a_y$，其中 $a_x\sim a_y$ 的最大值在左边的一段，同样的道理，其划分点一定会向右边不断扩展，所以这种情况下的代价就是 $ma+a_p+\max\{a_{p+1}\sim a_y\}$ 。
  
  那么我们所要维护的就是对于一个区间 $[l,r]$ 内，$a_p+\max\{a_{p+1}\sim a_r\}(p\in[l,r])$ 的最小值，记为 $rans$。
  
  现在考虑维护这个值，也就是如何将两个区间的信息如何合并得到 $rans$？

![图2.jpg](https://img.picui.cn/free/2024/08/19/66c2323bd1561.jpg)

如图，区间 $p_2$ 的 $rans$ 是可以直接给 $p$ 贡献的，而区间 $p_1$ 会受到右边对 $\max\{a_{p+1}\sim a_r\}$ 带来影响。

但是我们注意到，在区间 $p_1$ 中，若我们得到了最靠右的位置 $x$ 使 $a_x>$ $p_2$ 中的最大值，那么

* 对于 $p\in[x+1, mid]$ ， $a_p+\max\{a_{p+1}\sim a_r\}$ 的最小值就是 $\min_{p=x+1}^{mid}{a_p}+p_2$ 中的最大值。
* 对于 $p\in[l,x]$ ，这部分的 $rans$ 就可以直接贡献给 $p$ 了。

维护最靠右的位置 $x$ 使 $a_x>$ 某个值，我们会使用线段树上二分的操作。具体来说：

* 若 $p_4$ 的最大值 $< $ $p_2$ 的最大值，那么我们就继续往 $p_3$ 递归，然后把 $p_3$ 的最小值 $+ p_2$ 的最大值往 $p$ 贡献。
* 若 $p_4$ 的最大值 $\ge$ $p_2$ 的最大值，那么我们就继续往 $p_4$ 递归，此时需要注意，$p_3$ 对 $p$ 的贡献并不就是 $p_3$ 的 $rans$，而是 $p_3$ 对 $p_1$ 的贡献（也就是我们 $p_1$ 不能直接用 $p_1$ 的 $rans$ 对 $p$ 贡献的原因），记作 $ran$ 。
  
  还要考虑如何求 $ran$ ？你会发现我们上面这一大坨求的就是 $p_1$ 的 $ran$，所以我们已经完成了任务。
* $a_x,a_{x+1},...,a_{p-1}\ |\ a_{p}\ |\ a_{p+1},...,a_y$，其中 $a_x\sim a_y$ 的最大值在右边的一段，和上面的一部分是很类似的，你甚至可以将序列翻转过来，就和上一个部分一样了。
* 总复杂度为 $O(n\log^2 n)$ 。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define ull unsigned long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
ll read() {
    ll sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 250010, mod = 1e9 + 7;
struct qqq {
    int ma, mi, rmi, lmi, rm, lm;
} tr[maxn << 2];
int a[maxn];
int query1(int p, int x, int l, int r) {
    if (l == r)
        return tr[p].ma + x;
    int mid = (l + r) >> 1;
    if (tr[p << 1].ma >= x)
        return min(query1(p << 1, x, l, mid), tr[p].lm);
    return min(query1(p << 1 | 1, x, mid + 1, r), tr[p << 1].mi + x);
}
int query2(int p, int x, int l, int r) {
    if (l == r)
        return tr[p].ma + x;
    int mid = (l + r) >> 1;
    if (tr[p << 1 | 1].ma >= x)
        return min(query2(p << 1 | 1, x, mid + 1, r), tr[p].rm);
    return min(query2(p << 1, x, l, mid), tr[p << 1 | 1].mi + x);
}
void up(int p, int l, int mid, int r) {
    tr[p].ma = max(tr[p << 1].ma, tr[p << 1 | 1].ma), tr[p].mi = min(tr[p << 1].mi, tr[p << 1 | 1].mi);
    tr[p].lm = query1(p << 1 | 1, tr[p << 1].ma, mid + 1, r);
    tr[p].lmi = min(tr[p << 1].lmi, tr[p].lm);
    tr[p].rm = query2(p << 1, tr[p << 1 | 1].ma, l, mid);
    tr[p].rmi = min(tr[p << 1 | 1].rmi, tr[p].rm);
}
void jian(int p, int l, int r) {
    if (l == r) {
        tr[p].ma = tr[p].mi = a[l], tr[p].lmi = tr[p].lm = tr[p].rm = tr[p].rmi = 1e9;
        return;
    }
    int mid = (l + r) >> 1;
    jian(p << 1, l, mid), jian(p << 1 | 1, mid + 1, r);
    up(p, l, mid, r);
}
void change(int p, int x, int l, int r) {
    if (l == r) {
        tr[p].ma = tr[p].mi = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= x)
        change(p << 1, x, l, mid);
    else
        change(p << 1 | 1, x, mid + 1, r);
    up(p, l, mid, r);
}
qqq ans;
void queryl(int p, int x, int y, int l, int r) {
    if (x <= l && r <= y) {
        if (ans.ma == -1)
            ans.rmi = tr[p].rmi, ans.ma = tr[p].ma;
        else {
            // cout<<"p="<<p<<" k="<<query2(p,ans.ma,l,r)<<endl;
            ans.rmi = min(ans.rmi, query2(p, ans.ma, l, r));
            ans.ma = max(ans.ma, tr[p].ma);
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (mid < y)
        queryl(p << 1 | 1, x, y, mid + 1, r);
    if (mid >= x)
        queryl(p << 1, x, y, l, mid);
}
void queryr(int p, int x, int y, int l, int r) {
    if (x <= l && r <= y) {
        if (ans.ma == -1)
            ans.lmi = tr[p].lmi, ans.ma = tr[p].ma;
        else {
            ans.lmi = min(ans.lmi, query1(p, ans.ma, l, r));
            ans.ma = max(ans.ma, tr[p].ma);
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= x)
        queryr(p << 1, x, y, l, mid);
    if (mid < y)
        queryr(p << 1 | 1, x, y, mid + 1, r);
}
void hh(int p, int l, int r) {
    cout << "p=" << p << " l=" << l << " r=" << r << " tr[p].mi=" << tr[p].mi << " tr[p].ma=" << tr[p].ma
         << " tr[p].lm=" << tr[p].lm << " tr[p].lmi==" << tr[p].lmi << " tr[p].rm=" << tr[p].rm
         << " tr[p].rmi=" << tr[p].rmi << endl;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    hh(p << 1, l, mid);
    hh(p << 1 | 1, mid + 1, r);
}
int n, q;
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) a[i] = read();
    jian(1, 1, n);
    // hh(1,1,n);
    for (int i = 1; i <= q; ++i) {
        int op = read(), l = read(), r = read();
        if (op == 1) {
            a[l] = r;
            change(1, l, 1, n);
        } else {
            ans.ma = -1;
            queryl(1, l, r, 1, n);
            int an = min(a[l] + a[r] + ans.ma, ans.ma + ans.rmi);
            ans.ma = -1;
            queryr(1, l, r, 1, n);
            an = min(an, ans.ma + ans.lmi);
            printf("%d\n", an);
        }
    }
    return 0;
}
```

## T8 分身游走

题目大意：给出一棵树，询问从每一个结点出发，使用$k$个分身遍历整棵树的路径长度之和的最小值。

不怎么好写的大暴力：枚举起点，遍历树，枚举到达此节点分身的数量，枚举回到此节点的父亲结点的分身数量，跑背包 DP,大概可以得到一些分。

对于$k\leq2:$

若$k=1$,则有一个分身遍历了整棵树，最终停在一个结点。可以发现，这个结点一定会是离出发点最远的结点。

若$k=2$,则两个分身一起走，最终可能会停在两个不同结点。可以发现，节省的距离最多是树的直径。

性质：在最优方案中，若有分身留在某个子树 $x$ 中，那么一定不会出现一个分身进入以 $x$ 为根的子树而又回到 $x$ 的父亲的情况。

证明：对于以$x$为根的子树，有一个分身进入不返回的代价是 $2\sum{\text{边权}}-de_{x}$，$de_x$ 表示 $x$ 到 $x$ 子树中最远的距离。

而若有另一个分身进入了 $x$ 子树并且还要返回到 $x$ 的父亲，那么最小权值就会是 $2\sum{\text{边权}}-de_{x}+x$到 $fa$ 的距离。

所以可以有dp，参考std中 `namepsace baoli` 的内容

然后就是换根，我们使用直接介绍的新型换根dp的写法，可以参考std。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 15010;
int n, m;
struct qqq {
    int y, z, ne;
} a[maxn << 1];
int h[maxn], K;
void add(int x, int y, int z) { a[++K] = (qqq){ y, z, h[x] }, h[x] = K; }
namespace baoli {
int de[maxn], f[maxn];
int ma;
int v[maxn];
void sous(int x, int fa, int now) {
    de[x] = now, f[x] = fa;
    if (de[x] > de[ma])
        ma = x;
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y;
        if (y == fa)
            continue;
        if (v[y])
            sous(y, x, now - a[i].z);
        else
            sous(y, x, now + a[i].z);
    }
}
void chuli(int x) {
    while (f[x] && !v[x]) {
        v[x] = 1, x = f[x];
    }
}
void solve() {
    for (int i = 1; i <= n; ++i) {
        memset(v, 0, sizeof(int) * (n + 1));
        int ans = 0;
        for (int j = 1; j <= K; j += 2) ans += a[j].z * 2;
        for (int j = 1; j <= m; ++j) {
            ma = 0;
            sous(i, 0, 0);
            if (!ma)
                break;
            chuli(ma);
            ans -= de[ma];
        }
        printf("%d\n", ans);
    }
}
} 
namespace baoli2 {
int f[maxn][40], g[40];
void sous(int x, int fa) {
    for (int j = 0; j <= m; ++j) f[x][j] = 0;
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y;
        if (y == fa)
            continue;
        sous(y, x);
        f[y][0] += a[i].z * 2, g[0] = 1e9;
        for (int j = 1; j <= m; ++j) f[y][j] += a[i].z * j, g[j] = 1e9;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) g[j] = min(g[j], f[y][k] + f[x][j - k]);
        for (int j = 0; j <= m; ++j) f[x][j] = g[j];
    }
}
void solve() {
    for (int i = 1; i <= n; ++i) {
        sous(i, 0);
        int ans = 1e9;
        for (int j = 0; j <= m; ++j) ans = min(ans, f[i][j]);
        printf("%d\n", ans);
    }
}
} 
int f[maxn][40], G[40];
void sous(int x, int fa) {
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y, z = a[i].z;
        if (y == fa)
            continue;
        sous(y, x);
        memset(G, 0x3f, sizeof(int) * (m + 1));
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    G[j] = min(G[j], f[y][k] + f[x][j - k] + z * 2);
                else
                    G[j] = min(G[j], f[y][k] + f[x][j - k] + z * k);
            }
        for (int j = 0; j <= m; ++j) f[x][j] = G[j];
    }
}
int pr[maxn][40], ne[maxn][40];
int g[maxn][40];
int ans[maxn];
void sous2(int x, int fa) {
    vector<pii> b;
    for (int i = h[x]; i; i = a[i].ne) b.push_back(mp(a[i].y, a[i].z));
    for (int i = 0; i < (int)b.size(); ++i) {
        memset(pr[i + 1], 0x3f, sizeof(int) * (m + 1));
        int y = b[i].fi, z = b[i].se;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    pr[i + 1][j] = min(pr[i + 1][j], f[y][k] + pr[i][j - k] + z * 2);
                else
                    pr[i + 1][j] = min(pr[i + 1][j], f[y][k] + pr[i][j - k] + z * k);
            }
    }
    int ma = 1e9;
    for (int i = 0; i <= m; ++i) ma = min(ma, pr[b.size()][i]);
    ans[x] = ma;
    memset(ne[b.size()], 0, sizeof(int) * (m + 1));
    for (int i = (int)b.size() - 1; i >= 0; --i) {
        memset(ne[i], 0x3f, sizeof(int) * (m + 1));
        int y = b[i].fi, z = b[i].se;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    ne[i][j] = min(ne[i][j], f[y][k] + ne[i + 1][j - k] + z * 2);
                else
                    ne[i][j] = min(ne[i][j], f[y][k] + ne[i + 1][j - k] + z * k);
            }
    }
    for (int i = 0; i < (int)b.size(); ++i) {
        int y = b[i].fi;
        if (y == fa)
            continue;
        memset(g[y], 0x3f, sizeof(int) * (m + 1));
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) g[y][j] = min(g[y][j], pr[i][k] + ne[i + 1][j - k]);
    }
    for (int i = 0; i < (int)b.size(); ++i) {
        int y = b[i].fi;
        if (y == fa)
            continue;
        memcpy(f[x], g[y], sizeof(int) * (m + 1));
        sous2(y, x);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    sous(1, 0);
    sous2(1, 0);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}
```

最后修改：2024 年 08 月 19 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了
Yanws
牢师求更新

CCPC2024 校内选拔赛题解

tony102 • 2024 年 08 月 19 日

## T1 移动路线

### 方法1

从直觉上来看，顺时针的路线倾向于向右转，逆时针的路线倾向于向左转。

这样，我们就可以计算出每一次前进旋转的角度，从而统计出走到终点的角度。

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

map<char, int> mp;

int cal(char a, char b) { // 计算从a方向到b方向旋转的角度
    int x = mp[a], y = mp[b];
    if(x == y) return 0;
    if(y - x == 90 || y - x == -270) return 90;
    return -90;
}

### 方法2

我们画几个图其实可以观察到，逆时针一定是往左转的次数多，顺时针永远是向右转的次数多，我们只要记录往左往右转的次数即可。

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

## T2 圆形切割

我们可以采用逆向思维，顺时针旋转园等价于逆时针旋转刀，我们假设第一刀为 0 度，然后我们可以记录每一刀切的角度。

用一个桶数组 $f[i]$ 表示 i 这个角度是否切了，最后枚举 $[0,365]$ 的每一个角度，如果它切了就和上一个角度求最大值。

【注意】

别忘了，最后一刀还要和第一刀 0 度求一个圆心角的差值，它也有可能是最大的。

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

## T3 连加连乘

暴力枚举时间复杂度为 $O(n^2)$ 的，会超时。

【注意】求连乘时，要用 long long，因为两个余数相乘可能爆掉 int。

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

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
long long a[maxn], sum[maxn], pre[maxn], last[maxn], n;

## T4 牛车采矿

* 考点：**简单数学推导**、**几何（初中部分）**、分类讨论
* 难度 CSP T1+

### 测试点 1~4

当矿只有一个点的时候，答案就是两个点之间的距离，按要求输出即可。

### 测试点5~8

因为采矿车的坐标都是整数点，那么到矿区的距离就是到四个点距离的最小值。

### 测试点 9

仿照测试点5~8的思路，我们暴力枚举矩形内的所有点整数坐标点，那么矿车到矿区的距离，就是矿车与这些点的距离的最小值。

时间复杂度为 $O(n^3)$。

### 测试点 10

我们尝试用一点几何知识去分析问题。

![test6题解图片.png](https://img.picui.cn/free/2024/08/19/66c23296903b2.png)

我们可以把点分成这8块，A区域内的到矩形的距离就是到B点的距离，B区域内的点的距离就是到 BC这条边的距离。

其他地方同样照此分析。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 1000010;
int n, xl, xr, yl, yr;
int main() {
    cin >> n;
    cin >> xl >> yl >> xr >> yr;
    db ans = 1e9;
    int ansid = 0;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        db dis;
        if (xl <= x && x <= xr)
            dis = min(abs(y - yl), abs(y - yr));
        else if (yl <= y && y <= yr)
            dis = min(abs(x - xl), abs(x - xr));
        else
            dis = min(min(sqrt((x - xl) * (x - xl) + (y - yl) * (y - yl)),
                          sqrt((x - xl) * (x - xl) + (y - yr) * (y - yr))),
                      min(sqrt((x - xr) * (x - xr) + (y - yl) * (y - yl)),
                          sqrt((x - xr) * (x - xr) + (y - yr) * (y - yr))));
        if (dis < ans)
            ans = dis, ansid = i;
        printf("%.9lf ", dis);
    }
    cout << endl;
    cout << ansid << endl;
    return 0;
}
```

## T5 海明码

* 考点：**位运算**、**简单模拟**。
* 难度 CSP-J T2+

### 原理

首先因为 $a_i$ 只能是 $0/1$ ，那么若 $a_i$ 发生了改变则一定是 $1\to 0$ 或 $0\to 1$，等价于 $A_i=a_i\oplus 1$ 。

然后考虑为什么我们按照小 A 提供的过程就可以还原 ？

### 测试点1~4 5~8

如果你读懂了题，那么应该是可以模拟出来的。

### 测试点9~11

留给 $O(n^2)$ 的写法。

### 测试点12~14,15~17,18~19

正常按照题目给的办法模拟。

先枚举二进制的位数 $i$ ，然后枚举每一个下标 $j$ ，计算出 $d_i$ ，然后还是按照题意处理即可。

因为不熟悉位运算而不会处理 $d_i$ 的同学可以重点学习一下。

时间复杂度 $O(n\log n)$。

### 测试点 20

如果我们再仔细观察一下 $d_i$ 形成 $f$ 的过程 ，实际上 $f$ 等价于所有 $A_i=1$ 的 $i$ 的异或和。

这样复杂度就优化到了 $O(n)$ 。

但其实正常实现的 $O(n\log n)$ 的算法也是能过的。

```
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 10000000;
char S[maxn];
int n, a[maxn];
int main() {
    cin >> n;
    int t = ceil(log2(n + 1));
    // printf("%.9lf",log2(n+1));
    scanf("%s", S + 1);
    for (int i = 1; i <= n + t + 1; ++i) a[i] = S[i] - '0';
    int op = a[n + t + 1];
    for (int i = 1; i <= n; ++i) op ^= a[i];
    // cout<<"op="<<op<<" t="<<t<<endl;
    if (op == 1) {
        int an = 0;
        for (int j = 1; j <= n; ++j)
            if (a[j])
                an ^= j;

## T6 最短路问题

* 考点：**图论**，**建图方法**，**最短路**。
* 难度：CSP-J T3

### 测试点1~4

暴力应该是能过的。

### 测试点5~8

留给暴力建图，然后跑最短路算法，SPFA和dij都是可以过的。

复杂度为 $O(n^2)$。

### 测试点9~12

注意思考如果 $m=0$ ，答案是什么？ 其实就是 $i-1$ 。

那么加了一条边 $x,y,z$ 会改变什么？

我们设 $x<y$ ，那么对于 $2\le i\le x$ ，其答案还是$i-1$ ，但是对于点 $y$ 来说，其答案就是 $\min(x+z-1,y-1)$ 。

然后对于 $x+1\le i\le y-1$ 的点，他的最短路就是由 $x$ 到他和由 $y$ 到他的两条路长度中的较小值。

对于 $y+1\le i\le n$ 的点 ，他的最短路就是和由 $y$ 到他的路径。

### 测试点 13~16

所以我们就可以把所有被额外边连到的点都拿出来，加上 $1$ 号节点，形成一个子图，在子图中跑最短路。

然后其他点的最短路一定是点集中的某个点在直接到他。

复杂度是 $O(n+m^2)$。

### 测试点 17~20

通过上面两档部分分的分析，如果你很敏感的话就可以发现，许多一类边是无效的。

进一步发现，其实我们只保留 $i$ 到 $i+1$ 边权为 $1$ 的双向边是足够的。

所以就可以直接跑最短路，使用dij可以做到 $O(n\log n)$ 的复杂度。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

## T7 序列分段

首先要注意到最优选取方案一定是一下三种中的一种：

![图2.jpg](https://img.picui.cn/free/2024/08/19/66c2323bd1561.jpg)

如图，区间 $p_2$ 的 $rans$ 是可以直接给 $p$ 贡献的，而区间 $p_1$ 会受到右边对 $\max\{a_{p+1}\sim a_r\}$ 带来影响。

但是我们注意到，在区间 $p_1$ 中，若我们得到了最靠右的位置 $x$ 使 $a_x>$ $p_2$ 中的最大值，那么

维护最靠右的位置 $x$ 使 $a_x>$ 某个值，我们会使用线段树上二分的操作。具体来说：

```cpp
#include <bits/stdc++.h>
#define ll long long

#define ull unsigned long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

## T8 分身游走

题目大意：给出一棵树，询问从每一个结点出发，使用$k$个分身遍历整棵树的路径长度之和的最小值。

不怎么好写的大暴力：枚举起点，遍历树，枚举到达此节点分身的数量，枚举回到此节点的父亲结点的分身数量，跑背包 DP,大概可以得到一些分。

对于$k\leq2:$

若$k=1$,则有一个分身遍历了整棵树，最终停在一个结点。可以发现，这个结点一定会是离出发点最远的结点。

若$k=2$,则两个分身一起走，最终可能会停在两个不同结点。可以发现，节省的距离最多是树的直径。

性质：在最优方案中，若有分身留在某个子树 $x$ 中，那么一定不会出现一个分身进入以 $x$ 为根的子树而又回到 $x$ 的父亲的情况。

证明：对于以$x$为根的子树，有一个分身进入不返回的代价是 $2\sum{\text{边权}}-de_{x}$，$de_x$ 表示 $x$ 到 $x$ 子树中最远的距离。

而若有另一个分身进入了 $x$ 子树并且还要返回到 $x$ 的父亲，那么最小权值就会是 $2\sum{\text{边权}}-de_{x}+x$到 $fa$ 的距离。

所以可以有dp，参考std中 `namepsace baoli` 的内容

然后就是换根，我们使用直接介绍的新型换根dp的写法，可以参考std。

```cpp
#include <bits/stdc++.h>
#define ll long long

#define db double

#define mp make_pair

#define fi first

#define se second

#define pii pair<int, int>

using namespace std;
int read() {
    int sum = 0, f = 1;
    char st = getchar();
    while (st < '0' || st > '9') {
        if (st == '-')
            f = -1;
        st = getchar();
    }
    while ('0' <= st && st <= '9') {
        sum = (sum << 3) + (sum << 1) + st - '0';
        st = getchar();
    }
    return sum * f;
}
const int maxn = 15010;
int n, m;
struct qqq {
    int y, z, ne;
} a[maxn << 1];
int h[maxn], K;
void add(int x, int y, int z) { a[++K] = (qqq){ y, z, h[x] }, h[x] = K; }
namespace baoli {
int de[maxn], f[maxn];
int ma;
int v[maxn];
void sous(int x, int fa, int now) {
    de[x] = now, f[x] = fa;
    if (de[x] > de[ma])
        ma = x;
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y;
        if (y == fa)
            continue;
        if (v[y])
            sous(y, x, now - a[i].z);
        else
            sous(y, x, now + a[i].z);
    }
}
void chuli(int x) {
    while (f[x] && !v[x]) {
        v[x] = 1, x = f[x];
    }
}
void solve() {
    for (int i = 1; i <= n; ++i) {
        memset(v, 0, sizeof(int) * (n + 1));
        int ans = 0;
        for (int j = 1; j <= K; j += 2) ans += a[j].z * 2;
        for (int j = 1; j <= m; ++j) {
            ma = 0;
            sous(i, 0, 0);
            if (!ma)
                break;
            chuli(ma);
            ans -= de[ma];
        }
        printf("%d\n", ans);
    }
}
} 
namespace baoli2 {
int f[maxn][40], g[40];
void sous(int x, int fa) {
    for (int j = 0; j <= m; ++j) f[x][j] = 0;
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y;
        if (y == fa)
            continue;
        sous(y, x);
        f[y][0] += a[i].z * 2, g[0] = 1e9;
        for (int j = 1; j <= m; ++j) f[y][j] += a[i].z * j, g[j] = 1e9;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) g[j] = min(g[j], f[y][k] + f[x][j - k]);
        for (int j = 0; j <= m; ++j) f[x][j] = g[j];
    }
}
void solve() {
    for (int i = 1; i <= n; ++i) {
        sous(i, 0);
        int ans = 1e9;
        for (int j = 0; j <= m; ++j) ans = min(ans, f[i][j]);
        printf("%d\n", ans);
    }
}
} 
int f[maxn][40], G[40];
void sous(int x, int fa) {
    for (int i = h[x]; i; i = a[i].ne) {
        int y = a[i].y, z = a[i].z;
        if (y == fa)
            continue;
        sous(y, x);
        memset(G, 0x3f, sizeof(int) * (m + 1));
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    G[j] = min(G[j], f[y][k] + f[x][j - k] + z * 2);
                else
                    G[j] = min(G[j], f[y][k] + f[x][j - k] + z * k);
            }
        for (int j = 0; j <= m; ++j) f[x][j] = G[j];
    }
}
int pr[maxn][40], ne[maxn][40];
int g[maxn][40];
int ans[maxn];
void sous2(int x, int fa) {
    vector<pii> b;
    for (int i = h[x]; i; i = a[i].ne) b.push_back(mp(a[i].y, a[i].z));
    for (int i = 0; i < (int)b.size(); ++i) {
        memset(pr[i + 1], 0x3f, sizeof(int) * (m + 1));
        int y = b[i].fi, z = b[i].se;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    pr[i + 1][j] = min(pr[i + 1][j], f[y][k] + pr[i][j - k] + z * 2);
                else
                    pr[i + 1][j] = min(pr[i + 1][j], f[y][k] + pr[i][j - k] + z * k);
            }
    }
    int ma = 1e9;
    for (int i = 0; i <= m; ++i) ma = min(ma, pr[b.size()][i]);
    ans[x] = ma;
    memset(ne[b.size()], 0, sizeof(int) * (m + 1));
    for (int i = (int)b.size() - 1; i >= 0; --i) {
        memset(ne[i], 0x3f, sizeof(int) * (m + 1));
        int y = b[i].fi, z = b[i].se;
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) {
                if (!k)
                    ne[i][j] = min(ne[i][j], f[y][k] + ne[i + 1][j - k] + z * 2);
                else
                    ne[i][j] = min(ne[i][j], f[y][k] + ne[i + 1][j - k] + z * k);
            }
    }
    for (int i = 0; i < (int)b.size(); ++i) {
        int y = b[i].fi;
        if (y == fa)
            continue;
        memset(g[y], 0x3f, sizeof(int) * (m + 1));
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k) g[y][j] = min(g[y][j], pr[i][k] + ne[i + 1][j - k]);
    }
    for (int i = 0; i < (int)b.size(); ++i) {
        int y = b[i].fi;
        if (y == fa)
            continue;
        memcpy(f[x], g[y], sizeof(int) * (m + 1));
        sous2(y, x);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    sous(1, 0);
    sous2(1, 0);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}
```

CCPC2024 校内选拔赛题解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

跟不同的人聊天的收获

Codechef CTREE Chef and Chefcoin

CF1139D Steps to One

Luogu4064 [JXOI2017]加法

CF1025D Recovering BST

CCPC2024 校内选拔赛题解

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CCPC2024 校内选拔赛 题解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CCPC2024 校内选拔赛题解