玖的数学&算法录
0%

第十一届图灵杯NEUQ-ACM程序设计竞赛

发表于 更新于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

评价：题面有点难评价，数据锅一堆，题面题意不清，读入数据错误，鉴于自己部分题不能1A因此还是简单写个补题。和两年前感觉差别太大。

A.古堡中的勇者

题意：

n 个宝箱，第 i 个宝物在宝箱 x_i ，现在勇者位于位置 a ,一部分守卫着宝箱 b(b < a)** ， 另一部分守卫者宝箱 **c (c > a) ，守卫者不会移动。每一秒钟，勇者可以选择取出当前宝箱中的宝物，或者移动到相邻的宝箱。然而，他不能在任何时候移动到被守卫的宝箱，否则可能会命丧黄泉。请确定勇者最多能够收集到的宝物的数量。

出锅锐评：

1、 读入数据并不满足 b < a < c，甚至出现了 a < b 或 a < c的数据。

2、 读入数据中 n 有没读满的情况，即8个宝箱有只有7个xi的情况。

数据范围

a,b,c : 勇者、第一部分守卫和第二部分守卫位置。

n : 宝物数量

x_i : 第 i 个宝物位于 x_i 个宝箱中，注意 x_i 不一定是唯一的。

$$1\leq a,b,c \leq 10^9, 1 \leq n \leq 10^5,1\leq x_i \leq 10^9$$

题解：结论

实在看不懂，我猜的在b到c区间 i 范围的 x_i 的个数即为正解。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish(){
    int a,b,c;
    std::cin >> a >> b >> c;
    int n;
    std::cin >> n;
    int res = 0;
    for(int i=1;i<=n;i++) {
        int x;
        std::cin >> x;
        if(x > b && x < c)res++;
    }
    std::cout << res << endl;
}

B.三星五费

题意：

只差一张五费卡升三星，并且现在有 n 个金币，每次刷新商店需要消费 2 金币，购买一张五费卡需要消费 5 金币，并且当前商店无五费卡。

在没有任何外界干扰因素下，每次刷新出至少一张五费卡的概率固定为 3% 。

获胜规则：出现并购买了五费卡，反之认定失败。

出锅锐评：

1、 就是玩云顶/铲铲的都知道刷新一次有五张，但是原题目好像没说刷新一次只有一张？

数据范围

n : 持有的金币数

$$0 \leq n \leq 200$$

题解：数学

算失败的概率有多少次，再用1 - 失败的概率即可。

（成功的概率有很多种情况，直接算失败的更简便）

代码：
1
2
3
4
5
6
7
8
9
10
11
12
void JiuCherish(){
    int n;
    std::cin >> n;
    double ans = 0.0000;
    double sup = 1.000;
    int cnt = 1;
    if(n < 5) {
        std::cout << std::fixed << std::setprecision(3) << std::min(ans,sup) << endl;
    } else {
        std::cout << std::fixed << std::setprecision(3) << 1 - pow(0.97,(n - 5) / 2) << endl;
    } 
}

C.我就要不协调

题意：

给你一个长度为 n 的序列，给定一个操作，选择一个[1,n]的一个位置 pos , 使得 [1,pos] 区间的数据加1，区间 [pos + 1,n] 区间的数据减1。至少需要多少次操作才能使得序列变成不单调序列。

数据范围

t : 测试用例组数。

n : 序列长度。

a_i 每个序列的大小。

$$1\leq t \leq 100, 2 \leq n \leq 500,1\leq a_i \leq 10^9$$

题解：结论

找到相邻序列之差最小的作差除2即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int res = MOD;
    bool ok = false;
    for(int i=1;i<=n-1;i++) {
        if(a[i] > a[i + 1]) ok = true;
    }
    if(ok) {
        std::cout << 0 << endl;
        return;
    }
    for(int i=2;i<=n;i++) {
        res = std::min(res,(a[i] - a[i - 1]) / 2 + 1);
    }
    std::cout << res << endl;
}

D. 古希腊掌管原神的神

E.字母匹配

题意：

长度为 n 的字符串，有 k 次同个字母大小写转换机会，问最多能有字符串里面同个字母的大小写配对。

数据范围

n : 字符串长度

k : 操作次数

$$1\leq n,k \leq 2 \cdot 10^5$$

题解：模拟，贪心

按照题意模拟即可，枚举a~z可以转换配对的字母。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char str[MAXN];
int cnt[26][2];
void JiuCherish(){
    int n,k;
    std::cin >> n >> k;
    std::cin >> str + 1;
    for(int i=1;i<=n;i++)
        if(str[i] >= 'a' && str[i] <= 'z') 
            cnt[str[i] - 'a'][0]++;
        else
            cnt[str[i] - 'A'][1]++;
    int ans = 0;
    int t = 0;
    for(int i=0;i<26;i++) 
        ans += std::min(cnt[i][0],cnt[i][1]),t += abs(cnt[i][0] - cnt[i][1]) / 2;
    std::cout << ans + std::min(t,k) << endl;
}

F 数学家的四不要

题意：

数学有四不要：偶数不要，质数不要，三角数不要，卡特兰数不要。请问 n 以内的正整数他能研究多少个。

数据范围

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

题解：模板

把四个不要的枚举掉即可。

代码：
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
int primes[MAXN], cnt;     // primes[]存储所有素数
bool st[MAXN];         // st[x]存储x是否被筛掉
bool sjs[MAXN];
bool ctls[MAXN];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
void cal_sjs(int n) {
    int x = 1;
    for(int i=1;i<=n;i+=x) {
        // std::cout << i << endl;
        sjs[i] = true;
        x += 1;
    }
}

void cal_ctls() {
    ctls[1] = true;
    ctls[2] = true;
    ctls[5] = true;
    ctls[14] = true;
    ctls[42] = true;
    ctls[132] = true;
    ctls[429] = true;
    ctls[1430] = true;
    ctls[4862] = true;
    ctls[16796] = true;
    ctls[58786] = true;
    ctls[208012] = true;
}
void JiuCherish(){
    get_primes(1e7);
    cal_sjs(MAXN);
    cal_ctls();
    int n;
    std::cin >> n;
    int res = 0;
    for(int i=1;i<=n;i++) {
        res += ((i % 2 != 0) && (st[i]) && (!ctls[i]) && (!sjs[i]));
    }
    std::cout << res << endl;
}

G.旗鼓相当的对手

题意：

给你 n 个数，请你把它分成两组，使得两组数之和的差值尽可能的小。

数据范围

$$1\leq n \leq 300,1 \leq a_i \leq 200000, \sum{a_i} < 200000$$

题解：模板

把四个不要的枚举掉即可。

代码：
1

H.卷王

I.字串比较

J. 小C的学习计划

K.同学聚会

L.删边游戏

M.网格谜题