玖的数学&算法录
0%

河南萌新联赛2024第（五）场：信息工程大学

发表于
本文字数： 9.7k 阅读时长 ≈ 9 分钟

评价：题简单，适合萌新，部分题面理解有点绕，基本上都是板子应用题。

A.日历游戏

题意：

给定一个日期，在 2000.1.1 到 2024.8.1 之间（不包括 2024.8.1），现在有以下两种操作：

1：把日期天数加1，如1月1日加一天变成1月2日（1月31日天数加一变成2.1）。

2：把月份加1，如1月1日变到2月1日（但是不允许1月31日变成2月31日）。

所有的操作均要考虑历法和闰年的规定。

谁先变到2024.8.1日谁就赢了，超过指定日期不算胜利。

Alice先手，问是否能胜利？

题解：博弈、SG函数

正着可能不太好想，因此反过来想，从2024年8月1日出发，打表6月份与7月份的每一天观察情况，不难发现7月奇数天先手是必胜的，而6月与7月的情况相反，从而一年内的情况基本上可以确定胜负了，那么可以断定Alice先手跟月和日奇偶性有关。

Q1：为什么结论和年没关？只和日月有关？

从任意一年算起，最简单的操作就是从1月1日到第二年的1月1日，是12次操作，因此谁操作都不会影响结果。

Q2：9月30为什么必胜？

解释这个问题可以转换成为什么11.30必胜，首先Alice先操作有两种方法第一个是变月份变成12月30，Bob也有两种操作：加一天变31日或者变成1月30日，接下来的操作都可以从最开始的分析得到。

代码：
1
2
3
4
5
6
7
8
9
void JiuCherish(){
    int x,y,z;
    std::cin >> x >> y >> z;
    if((y + z) % 2 == 0 or (y == 9 and z == 30) or (y == 11 and z == 30)) {
        std::cout << "YES" << endl;
    } else {
        std::cout << "NO" << endl;
    }
}

B.学生分组

题意：

有一个含有 n 个元素的随机序列，如果一个序列中所有元素均在 [L,R] 区间内，则称其为一个好的序列，现在每次你可以在使其中一个数+1，另一个数-1，问最少要多少次才可以使随机序列成为一个好的序列。如果都不能满足的话输出-1。

数据范围：

$$n < 10^6 , L < R < 2\times 10^9$$

题解：模拟

考虑数组的每个学生数，如果小于下界说明需要进行 l - a[i] 次+1操作，用sL（small left）存起来。

考虑数组的每个学生数，如果大于下界说明可以进行 a[i] - l 次-1操作，用bL（big left）存起来。

考虑数组的每个学生数，如果小于上界说明可以进行 r - a[i] 次+1操作，用sR（small right）存起来。

考虑数组的每个学生数，如果大于上界说明需要进行 a[i] - r 次-1操作，用bR（big right）存起来。

对于上界来说如果需要-1的操作多过可以+1的操作，那么不成立。

同样考虑下界如果需要+1的操作多过可以+1的操作，那么不成立。

最后结合成立的操作，取需要进行操作的最大值就是答案。

代码：
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
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    i64 l,r;
    std::cin >> l >> r;
    i64 sL = 0,sR = 0;
    i64 bL = 0,bR = 0;
    for(int i=1;i<=n;i++) {
        if(a[i] < l) {
            sL += l - a[i];
        }
        if(a[i] < r) {
            sR += r - a[i];
        }
        if(a[i] > r) {
            bR += a[i] - r;
        }
        if(a[i] > l) {
            bL += a[i] - l;
        }
    }
    if(bR > sR || sL > bL) {
        std::cout << -1 << endl;
    } else {
        std::cout << std::max(sL,bR) << endl;
    }
}

C.小美想收集

吐槽： 原题洛谷P1525 [NOIP2010 提高组] 关押罪犯，好理解太多了。

题意：

题面魔改的有点一般般，不好懂

有好记忆和坏记忆，但是一个回忆和其他回忆会产生一个冲突，值为c，只要会产生冲突的两个回忆同时被划分到好回忆或者坏回忆中，小美的波动值就可能发生变化。小美想要自己的暑假尽可能的美好，所以她想请你帮她来划分回忆，使得最后的冲突值最小。

数据范围：

$$1 \leq n \leq 2\times10^4 , 1 \leq m \leq 10^5$$

$$1 \leq c \leq 10^6$$

n 表示回忆数，m表示冲突的回忆对数。

下面 m 行，每行三个数 a, b, c, 表示回忆 a 会和回忆 b 产生冲突，冲突值为 c 。

题解：并查集，二分图匹配

看洛谷P1525，理解起来会好很多。

代码：
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
49
50
51
52
53
54
55
const int N = 2e6 + 10;
int h[N], e[N], ne[N], w[N], idx;
int clr[N], u, v, c, n, m;

void add(int a, int b, int c) 
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

bool dfs(int cur, int c, int mid) 
{
    clr[cur] = c;
    for (int i = h[cur]; ~i; i = ne[i]) 
    {
        int j = e[i];
        if (w[i] <= mid) continue ;
        if (clr[j] && clr[j] == c) return false;
        if (!clr[j] && !dfs(j, 3 - c, mid)) return false;
    }
    return true ;
}

bool check(int mid) 
{
    memset(clr, 0, sizeof clr);
    for (int i = 1; i <= n; i ++ ) 
        if (!clr[i]) if (!dfs(i, 1, mid))
            return false;
    return true ;
}

int main() 
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- ) 
    {
        scanf("%d%d%d", &u, &v, &c);
        add(u, v, c), add(v, u, c);
    }

    int l = 0, r = 1e9;
    while (l < r) 
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

D. 区间问题1

题意：

Alice 有 n 个数，她可以对这 n 个数执行 q 次以下两种操作：

  1. 将区间 [L,R] 上的所有数加上 d

  2. 查询第 x 个数的值

数据范围：

$$1 \leq n \leq 10^5$$

$$1 \leq q \leq 10^5$$

保证 n 个数的数据范围在 long long之内

题解：线段树，树状数组

裸板子运用。

代码：
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
long long tree[500005];
int n, m;
void add(int x, long long num) {
    while (x <= n) {
        tree[x] += num;
        x += lowbit(x);
    }
}
long long query(int x) {
    long long ans = 0;
    while (x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
void JiuCherish() {
    scanf("%d", &n);
    long long last = 0, now;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &now);
        add(i, now - last);
        last = now;
    }
    int flg;
    scanf("%d",&m);
    while (m--) {
        scanf("%d", &flg);
        if (flg == 1) {
            int x, y;
            long long k;
            scanf("%d%d%lld", &x, &y, &k);
            add(x, k);
            add(y + 1, -k);
        } else if (flg == 2) {
            int x;
            scanf("%d", &x);
            printf("%lld\n", query(x));
        }
    }
}

E. 哥德巴赫猜想

题意：

给你一个正奇数，请你分解成三个质数之和，优先让第一个质数尽可能的小，其次第二个质数也尽可能的小，并输出这三个质数。如果无法分解成三个质数之和，输出-1。

数据范围：

$$t < 200,1 < n \leq 10^5并且n为奇数$$

题解：数学、线性筛

板子运用，筛完之后从第一个质数去跑，枚举第二个质数，如果正奇数减去这两个质数也是质数的话即为答案。

代码：
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
void init(){
    for(int i=0;i<5005;i++) {
        y[primes[i]] = true;
    }
}
void get_eulers(int n)  // 线性筛法求1~n的欧拉函数
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

 
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=0;i<cnt;i++) {
        for(int j=0;j<cnt;j++) {
            if(primes[i] + primes[j] >= n) break;
            if(y[n - primes[i] - primes[j]]) {
                std::cout << primes[i] << ' ' << primes[j] << ' ' << n - primes[i] - primes[j] << endl;
                return;
            }
        }
    }
    std::cout << -1 << endl;
}

F. 小美想跑步

题意：

小美跑步，希望跑完除起始点的 n - 1个打卡点，跑完最后一个打卡点后想喝水，但是小美想再跑一次 n - 1个打卡点回家喝水，使得跑步路径最短。

数据范围：

$$1 \leq n,m \leq 10^6, x,y,z表示x到y的路，长度为z,1\leq z \leq10^6$$

题解：最短路

板子应用题，因为路长为正数，因此跑两次dijkstra即可。

代码：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
const int MaxN = 100010, MaxM = 500010;
 
struct edge
{
    int to, dis, next;
};
 
edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;
 
inline void add_edge( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
 
struct node
{
    int dis;
    int pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
 
std::priority_queue<node> q;
 
 
inline void dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    dis[1] = 0;
    q.push( ( node ){0, 1} );
    while( !q.empty() )
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for( int i = head[x]; i; i = e[i].next )
        {
            int y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}
 
void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;  
    std::vector<std::tuple<int, int, int>> e;  
    for(int i = 0; i < m; ++i) {
        int u,v,d;
        std::cin >> u >> v >> d;
        add_edge(u,v,d);
        e.emplace_back(u,v,d);
    }
    i64 ans = 0;
    dijkstra();
    for(int i=2;i<=n;i++) {
        ans += dis[i];
    }
    memset(head,-1,sizeof(head));
    cnt = 0;
    for(auto [v,u,d] : e) {
        add_edge(u,v,d);
    }
    dijkstra();
    for(int i=2;i<=n;i++) {
        ans += dis[i];
    }
    std::cout << ans << endl;
}

G.爬楼梯

题意：

需要爬 n 阶楼梯到楼顶，每次只能爬 1 - 3 个台阶，你有多少种不同方法到顶楼。对答案取模 1e9 + 7。

数据范围：

$$n < 10^6$$

题解：dp

斐波那契题了, 上到当前楼是受前面三层楼层的影响。

其中三层楼上法为：111, 12, 21, 3。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
void JiuCherish(){
    int n;
    std::cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i=4;i<=n;i++) {
        dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        dp[i] %= MOD;
    }
    std::cout << dp[n] % MOD << endl;
}

H. 区间问题2

题意：

Bob 有 n 个数，他有 q 次想知道任意一个区间内的最大值是多少。

数据范围：

$$n \leq 10^6, q\leq 10^6$$

题解：st表

裸板子

代码：
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
int Max[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return std::max(Max[l][k],Max[r-(1<<k)+1][k]);
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
 
void JiuCherish(){
    int N=read();
    for(int i=1;i<=N;i++) Max[i][0]=read();
    for(int j=1;j<=21;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            Max[i][j]=std::max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
    int M=read();
    for(int i=1;i<=M;i++)
    {
        int l=read(),r=read();
        printf("%d\n",Query(l,r));
    }
}

I.小美想打音游

想复杂了。。。

题意：

有 n 首歌，每首歌的分数是 c_i,但是都没达到满分。小美有魔法可以把所有歌分数都变成一个分数 a , 但是需要消耗 |c_i - a|的魔力值。在变成同一分数后，再把所有歌变成满分只需要一个魔力值。问小美最少花费的魔力值是多少？

数据范围：

$$1 \leq n \leq 10^6,1 \leq c_i \leq 10^6$$

题解：贪心

画一条数轴，实际上不难发现，把所有的数变成中间值即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void JiuCherish(){
    int n;
    std::cin >> n;
    int t = (n + 1) / 2;
    i64 sum = 0;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
    }
    std::sort(a + 1,a + n + 1);
    int now = a[t];
    for(int i=1;i<=n;i++) {
        sum += std::abs(now - a[i]);
    }
    std::cout << sum + 1 << endl;
}

J.平方根

题意：

给一个正整数 n, 输出 下取整 根号 n。

数据范围：

$$n < 2 \times 10^{18}$$

题解：?

签到，注意C++直接输出sqrtl(n)会变成字符串。

代码：
1
2
3
4
5
6
7
import math
t = int(input())
for i in range(0,t):
    x = int(input())
    x = math.sqrt(x)
    x = math.floor(x)
    print(x)

K.小美想游泳

题意：

小美家的旁边共有 m 条河和 n 个岛屿，这 m 条河将这 n 个岛屿相连。小美想选择一条路线，能够从 s 岛游到 t 岛。但是小美家旁边的河可不是普通的河，因为受到了大海的影响，所以每条河都会有波浪，波浪很厉害。而一条河当中的波浪的厉害程度 a 是固定的，小美作为一个初学者，希望不要遇到太厉害的波浪。所以小美想请你帮她找到一条路线，使这条路线上最厉害的波浪的厉害程度值 a 最小。

数据范围：

$$1 \leq n \leq 10^4,1 \leq m \leq 2\times 10^4$$

$$u,v,a表示u到v的路,长度为a,1\leq a \leq10^6,1 \leq s,t \leq n$$

题解：并查集，最短路

还是正边，跑一次dijkstra就好。

代码：
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
49
50
51
52
53
54
55
56
57
58
59
const int INF = 0x3f3f3f3f3f3f3f3fLL;
struct edge
{
    int v,w;
};

struct node {
    int id, dis;
    bool operator < (const node & t) const {
        return dis > t.dis;
    }
};
 
int dis[MAXN];
bool vis[MAXN];
int n, m;
std::vector<edge> a[MAXN];

inline void dijkstra(int s)
{
    std::priority_queue<node> q;
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[s] = 0;
    q.push({s, 0} );
    while (!q.empty()) {
            auto [u, _] = q.top();
            q.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            for (auto [v, w] : a[u]) {
                if (vis[v])
                    continue;
                if (dis[v] > std::max(dis[u], w)) {
                    dis[v] = std::max(dis[u], w);
                    q.push({v, dis[v]});
                }
            }
        }
}


void JiuCherish(){
    std::cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        std::cin >> u >> v >> w;
        a[u].pb({v,w});
        a[v].pb({u,w});
    }
    int s,t;
    std::cin >> s >> t;
    dijkstra(s);
    std::cout << dis[t] << endl;
}