前言

本场比赛出题周期里，由于在备赛冲击奖牌，就把这场第二届迎新杯的出题工作基本全交给校队未来的栋梁们了。整个出题过程中，几位学弟们认真负责的态度让我非常放心，事实证明也确实带来了一套不错的题👍从去年叱咤赛场的选手身份转变为尽职尽责的出题人，他们做得很棒！
这场出题人比去年还是很善良的（），赛前不断地在降难度。（而且原本Lihg给的两个疑似蓝题+紫题都被ban了
最难的应该算是天际线那道题，思维上有一定的门槛，但也不难想。我勉强算出了这一道题，目的就是想给赛有余力oier们强调一下STL的重要性。
应该说，善良的出题人这回是没有防AK的，其实都是可做题。
非要细分的话，我赛前预估大概4 3 2的梯度（4签到+3简单+2中等，octal的个人看法）

题号 预估难度 知识点 FirstBlood
A 1 ★ 简单数学、容斥原理 ェメ
B 2 ★ 二分、数学 clhdlg
C 2 ★ DP动态规划 Ovine
D 3 ★ 贪心、优先队列 /
E 2 ★ 贪心 ェメ
F 1 ★ 思维题 翊，
G 1 ★ 贪心、简单模拟 翊，
H 1 ★（签到题） 简单数学 learner_164
I 3 ★ 组合数学、推式子
打表找规律		 翊，

赛后看了一下，虽然简单了，但也是有区分度的，各个水平的选手也都有题可做，为出题人们点赞！👍
另外预告一下：
下学期的校赛将会由YNU现役单体最强、刷题量3000+的Lihg主导出题，大家敬请期待一下！

说明：以下所有题解代码，大家关注main函数就行了，代码头部纯属个人习惯，不用深究。

A 穿越之爆裂魔法与特殊数字

【容斥原理】

首先，我想对于刚高考完的同学来说，整除 这个概念可能有点陌生了。因为大家第一次接触这个词应该是小学初中，高考数学应该是不涉及。
不过大家看样例解释应该就能get到：

a 被 b 整除 <=> a 除 b 余数为0 <=> a 是 b 的倍数

这道题就是相当于求 1−n1-n 中，有多少个数是 a,b,ca, b, c 中至少一个数的倍数。
如果是求 1−n1-n 中 xx 的倍数，要怎么求？
是不是只需要 n/xn / x (整除) 就行。
那是不是 n/a+n/b+n/cn / a + n / b + n / c ？
no，no，no。因为会有重复的。
所以就需要用到容斥原理，看张图就理解了
image-20241206164835518
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
inline void solve()
{
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    ll res = 0;
    res += n/a + n/b + n/c;
    res -= n/(a*b) + n/(a*c) + n/(b*c);
    res += n / (a*b*c);
    cout << res << endl;
}
int main()
{
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

B 机房的神秘灯光

【二分】
其实有经验的选手这道题就是会比较秒杀，因为二分的题基本都比较套路。
kk 的范围是 1e181e18 ，这也不像是有规律的数学模型，所以第一反应就应该想到二分。
要讲清楚这道题，大概有两个要点：
① 第 ii 盏灯只会被 ii 的因数改变状态。（并且 ii 的因数是小于等于 ii 的，即一定都会被选择）
② 按奇数次开关，灯关；按偶数次开关，灯才会依然开。
③ 只有平方数的因子个数是奇数，其他数的因子一定是两两不相同的数一组。
那么，实际上就是求满足 [1,n][1, n] 中非平方数的个数恰好为 kk 的最小的 nn 是多少。考虑到 kk 范围是 1e181e18 二分求解即可，复杂度为 O(log2k)O(log_2{k})，大概在64这个数量级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
inline void solve()
{
    ll k;
    cin >> k;
    // check函数，个人习惯使用的是Lambda表达式，其实就理解为函数就行
    auto check = [&](ll x) {
        ll t = sqrt(x);
        return x - t >= k;
    };
    ll l = 1, r = 4e18; // long long最大大概4e18，不如开大点
    // 二分找一个满足条件的最小值
    while(l < r) {
        ll mid = l+r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}
int main()
{
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

C 云山探险记2

【DP】

前言：去年校赛的云山探险记1也是一个比较典的DP，不过思维难度比本题高一些，欢迎有兴趣的同学去钻研一下（PS：去年那题的定位是防AK，所以一时半会儿没想通也别着急）。

题意就是有一个 nn 个数的序列，每个数可以选或不选。
选到第偶数个数时，可以收获翻倍。问选完n个数后，最大收获是多少。

这道题之所以不能直接贪心，是因为我中途可以放弃选一个数，从而使得后续有个原本是第奇数个选中的数，变为第偶数个数，这个数很大的话收获翻倍就能弥补放弃的损失。

还有个值得注意的点是，不会有连续的两个数都不被选中。（从贪心的角度上，这个行为是自损而无利的）

DP思路一

解析直接看代码里的注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    int n;
    cin >> n;
    vector<vector<ll>> dp(n+5, vector<ll>(2));
    // dp[i][0] 选了第i位后有偶数个数时的最大收获
    // dp[i][1] 选了第i位后有奇数个数时的最大收获
    // 由于第n个数不选不会有任何好处，那最优解肯定是必选第n个数的
    // 所以答案是max(dp[n][0], dp[n][1])
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    dp[1][1] = a[1];
    dp[1][0] = -2e18; //选了第1位后就只能是奇数个数
    for(int i=2; i<=n; i++) {
        dp[i][0] = max(dp[i-1][1] + a[i]*2, dp[i-2][1] + a[i]*2); // 分别对应选i-1和不选i-1
        dp[i][1] = max(dp[i-1][0] + a[i], dp[i-2][0] + a[i]); // 分别对应选i-1和不选i-1
    }
    // 第n位是必选的，前n-1位选与不选的状态递推过来，一定是没有疏漏的
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

DP思路二

解析直接看代码里的注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int n;
    cin >> n;
    vector<vector<ll>> dp(n+5, vector<ll>(2));
    // dp[i][0] 走到第i位为止，选了偶数个数时的最大收获（第i位不一定选）
    // dp[i][1] 走到第i位为止，选了奇数个数时的最大收获（第i位不一定选）
    // 最终选到的数的个数要么是奇数要么是偶数
    // 所以答案是max(dp[n][0], dp[n][1])
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    dp[1][1] = a[1];
    dp[1][0] = -2e18; // 选了第1位后就只能是奇数个数
    for(int i=2; i<=n; i++) {
        // 分别对应选与不选第i位
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + a[i]*2);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

D 穿越之我在《都市：天际线》里修路

【贪心】【优先队列】
前段时间看朋友在玩这个游戏，顺手想了个故事。
抛开题目背景，一句话题意其实就是：
有 nn 个点，每个点有一个权值 aia_i ，每个点的度为 did_i 。构造一颗树使得 $ \sum_{i=1}^N a_i\times{d_i}^2$ 的值最小。

不知道有没有同学看到这道题的时候，想到了最小生成树🤔
这道题的思想和最小生成树的prim算法很类似哈。
不过只能说学过prim有助于想到正解，其实完全不会prim也是能写的哈。prim算法虽然有名有姓的，但也就是个贪心而已，没那么厉害。

这道题怎么贪呢？
如果一上来就从整体（完全体的树）考虑，根本无从下手。
我们不妨不要那么聪明，别一上来就建模成 "构造一颗树使得 $ \sum_{i=1}^N a_i\times{d_i}^2$ 的值最小“这个问题哈。
不如顺着题目描述，路是一条一条修的，我们就一步步考虑。
我们考虑一个一个城市地扩张连通块，直到全部城市都连进来。
对于题给背景，每修一条路其实就对应着把一个新城市连到当前的连通块里。（一定是这样的，因为是树）
那么新增的城市 ii 当前只会连着一条公路，即加进来的代价为 $a_i × 1 $ ，是个固定值。
而与城市 ii 所连接的那个点 jj 所新增的代价是不固定的，这也就是我们要贪的对象。
原本 jj 的代价是 aj×dj2a_j × d_j^2 ，现在要变为 aj×(dj+1)2a_j × (d_j+1)^2。
我们要最小化总的代价，其实只需要最小化每一步的 aj×(dj+1)2−aj×dj2a_j × (d_j+1)^2 - a_j × d_j^2。
至于怎么维护每个 jj 对应的代价，可能需要用到优先队列 + 重载运算符。（不重载的话也能写，就是麻烦点）
关于重载运算符的方法，可以看一下我以前写过的这篇文章：优先队列的重载运算符 - octal_zhihao - 博客园
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
struct node{
    ll x;
    ll y;
    friend bool operator<(node a,node b) {
        ll ta = a.x * ((a.y+1)*(a.y+1) - a.y*a.y);
        ll tb = b.x * ((b.y+1)*(b.y+1) - b.y*b.y);
        return ta > tb;
    }
};
priority_queue<node> q;
inline void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    sort(a.begin()+1, a.end());
    q.push({a[1], 1});
    q.push({a[2], 1});
    ll res = 0;
    res += a[1] + a[2];
    for(int i=3; i<=n; i++) {
        auto [w, d] = q.top();
        q.pop();
        res += w * ((d+1)*(d+1) - d*d);
        res += a[i];
        q.push({a[i], 1});
        q.push({w, d+1});
    }
    cout << res << endl;
}
int main()
{
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

E 饥饿之墙

【贪心】
贪心策略：每次摧毁从最左边的尚未被破坏的墙的右端点 RiR_i 开始破坏，就能保证每次摧毁的D列尽可能得靠右，也就能尽可能多地覆盖右侧的墙。
换句话说，每次在未摧毁的 (L,R)(L, R) 对中找 RR 最小的来打。
那么只需要，最开始就按 RR 来排序，然后从前往后遍历就行。
代码如下，详细过程可看注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
inline void solve()
{
    int n, d;
    cin >> n >> d;
    vector<pii> a;
    for(int i=1; i<=n; i++) {
        int l, r;
        cin >> l >> r;
        a.push_back({l, r});
    }
    // 根据右边界从小到大排序
    sort(a.begin(), a.end(), [&](pii x, pii y) {
        return x.second < y.second;
    });
    int R = 0, res = 0;
    // R代表当前拳头已经覆盖区域的最右边的位置
    for(auto [l, r]: a) {
        if(l <= R) continue; // l<=R 意味着已经被打倒了
        // 否则就是没被打倒
        // 那么此时的r就是我们要选的未摧毁的墙里最小的r
        res ++; // 从r开始打一拳！
        R = r + d - 1; // 当前覆盖区域扩展到r后面d位 
    }
    cout << res << endl;
}
int main()
{
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

F Fire_Lime的*3 or /2问题

【思维】【数学】
这种题其实也算初阶的诈骗题，ICPC其实还有很多很智慧的诈骗题（也非常有意思）。

过程搞这么复杂，其实*3是不会增加因数分解后2的个数的。
所以我们只需要求出，这些数里一共有多少个因子2可以来除就ok了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int res = 0;
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        int a;
        cin >> a;
        while(a % 2 == 0) { // 还有因数2就除
            a /= 2;
            res ++;
        } 
    }
    cout << res << endl;
    return 0;
}

G Fire_Lime的打印机

【贪心】【模拟】
验题的时候目测G的做法应该是比较多的，但本质其实差不多。我也没考虑其他做法，这里就给一种好理解的做法吧：
首先，我们想尽可能地省时，那就要尽可能最大化每次右移所打印的数。

然后规则上，打印机打印了 aa ，那么下一次就只能打印 a+1a + 1，都没有其他方案可选。那其实最大化每次打印的方案是显然且固定的，就是每次遇到上一个数 +1+1 就打印，直到无数可印而返回。

这里有个误区就是考虑到DP，但其实每次转移只能到 a+1a+1 ，转移结果是固定的，没必要DP。
拓展：这题再加点难度可以改为：“每次打印能打印比上一个数字更大的数”，例如打印出数字 "1"之后，可以打印2,3,4…,n。
这样就是一道家喻户晓的经典DP模型了。

那么回过来，这个逻辑用代码要怎么实现呢？
对于一个数 aa 而言，只要 a−1a - 1 在前面出现过，我们在 打印 a−1a - 1 的那一轮就可以把 aa 打印了，不需要付出额外的代价。反之，就只能新开一轮，从 aa 开始打印。

怎么记录 a−1a-1 是否在 $ a $ 之前呢？一个简单的做法是用 STL 库的 set 容器（不用万能头的话，需要引入set头文件）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    cin >> n;
    set<int> st;
    int res = 0;
    for(int i=1; i<=n; i++) {
        int ai;
        cin >> ai;
        if(!st.count(ai-1)) res ++;
        st.insert(ai);
    }
    cout << res-1 << endl;
    return 0;
}

不用set其实也很简单，用一个bool类型的数组代替就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    int n;
    cin >> n;
    vector<bool> p(n+1, false);
    int res = 0;
    for(int i=1; i<=n; i++) {
        int ai;
        cin >> ai;
        if(!p[ai-1]) res ++;
        p[ai] = true;
    }
    cout << res-1 << endl;
    return 0;
}

H 我爱YNU-ICPC校队

【签到】【模拟】or【数学】
这道题的难点其实就在于有隔天的，如果要比大小，那应该统一参考系。
做法很多哈，为了保证正确性其实可以多写几个if来模拟一下时间。花点时间总能做出来的，所以定位是签到。
介绍一下我的做法：
首先需要明确一点，对一个时间+24是不会改变它本来的意义的。
我们不妨就把 bb 作为最早的时间，凡是比b小的都加24.
然后看看 aa 是否在 [b,c][b, c] 范围内即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(c < b) c += 24;
    if(a < b) a += 24;
    if(a >= b && a <= c) cout << "No" << endl;
    else cout << "I love YNU-ICPC team" << endl;
    return 0;
}

I 量子宇宙的迎新赛

【组合数学】【推式子】

考了考高中数学的知识，数竞生应该是能拿捏的
从高中课本上有的两个公式入手
性质1: $ C_{n}^{m} =\frac{n!}{m!(n-m)!} $

性质2: Cn1+Cn2+Cn3+...+Cnn=2nC_{n}^{1}+C_{n}^{2}+ C_{n}^{3}+ ... +C_{n}^{n}= 2^{n} ①

由性质1 可以推出：$m × C_{n}^{m} = n × C_{n-1}^{m-1} $ （展开了约分一下就行）

那么结合性质2可得：1Cn1+2Cn2+3Cn3+⋯+nCnn=n2n−11 C_{n}^{1}+2 C_{n}^{2}+3 C_{n}^{3}+\cdots+n C_{n}^{n}=n 2^{n-1} （不过这个式子本题用不到）

又因为 m2×Cnm=m×n×Cn−1m−1=n×Cn−1m−1+n×(m−1)×Cn−1m−1m^2 × C_{n}^{m} = m × n × C_{n-1}^{m-1} = n × C_{n-1}^{m-1} + n × (m-1) × C_{n-1}^{m-1}

12Cn1+22Cn2+32Cn3+⋯+n2Cnn=n2n−1+n×(n−1)×2n−2=n(n+1)2n−21^{2} C_{n}^{1}+2^{2} C_{n}^{2}+3^{2} C_{n}^{3}+\cdots+n^{2} C_{n}^{n}= n 2^{n-1} +n ×(n-1)×2^{n-2} =n(n+1) 2^{n-2} ②

以上是结论推导部分

这道题，我们实际需要求的是:

将①②式代入：简化答案为 (n+1)×n/4(n+1)×n / 4，O(1)O(1) 可求得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define debug(x) cerr << #x << ": " << x << '\n';
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    ll n;
    cin >> n;
    ll res = (n+1)*n / 4;
    cout << res << endl;
    return 0;
}