大二非acm选手第一次参加蓝桥，PB组意外进决赛_蜂巢 动态规划

pythonB组赛后总结

没参加过或者参加过成绩不理想的，记住考试的时候一定要敢写，就算打暴力只有20%的分数，有些题打表，打暴力也要写上，万一恰巧蒙对几个样例，多得几分就能拉开差距了。

考试前一个其他省的群友（编程群认识的），我们两个实力差不多，我考试的时候有一题暴力的思路还写错了，但因为我多骗了一些分，导致侥幸拿了省一（中上排名），实际也就完全ac了三道题。那个群友不太敢写，一直在想能ac的正解，可能有的题目都不敢写，最后得了省三（省三里面的第一）约等于省二吧，也有可能和不同省份有关

0. 考试心态

线下考试，监场的老师不让提前进场，直到50多才让进，没时间敲准备好的板子了，呜呜~~ 进场之后，默写了一手bfs的模板，一个树状数组的模板，表示后来考试过程中也没有用到…考试过程中一个小时左右已经有半数同学离场，感觉心里面有点安慰（好多分母^_）。最恶心的是机房电脑时间与标准时间不符，导致我以为右下角55的时候，提交最后一题，结果提示考试结束。。又少骗了几分…

1. 排列字母

难度系数：⭐

签到题，据说我们省，做出这题加上尺寸的那个题，就可以省三了，暂且称之为蓝桥铜牌题hh…

观察一下题目，字符串排列后，是按照字典序排列的，先加入一个列表中（字符串没有排序的api），字典序排序一下即可

解释一下：字典序排序

0 < 00 < 001 < 01 < 1 （根据从左到右第一位比较大小）

同理: a < b < c

s = "WHERETHEREISAWILLTHEREISAWAY"
nums = []
for i in range(len(s)):
    nums.append(s[i])
nums.sort()
for i in range(len(nums)):
    print(nums[i],end="") 
    # 输出不换行
1
2
3
4
5
6
7
8

2. 寻找整数

难度系数：⭐⭐⭐

考试的时候以为是一道枚举的题目，用dev挂了几个小时也没跑出来，而且把步长调到1w多的（答案是16位数），

预估一手运算量

2e16 / 1e5 * 50 ≈ 1e13

勉强按照1秒1e8的计算量，实际机房电脑最多跑1e7（太卡了，1e5的数据 nlogn的做法都要卡一下才能出结果~~）

至少要跑1e5秒，考试4个小时，4 * 60 * 60 = 14440 ，如果考试刚开始的时候就挂上，也有几率跑出来的，我反正没跑出来，也没填这个空…

实际考察：数论 <中国剩余定理> 或者一种搜素算法

第一种搜素做法，考试的时候不太容易想出来，每次加前n个数的最小公倍数

例如：一组数据 2 3 5

​ 余数为 1 1 3

​ 第一个满足的数： 13

​ 下一个满足的数： 43

由此得出规律： 13 + lcm（2，3，5）=> 由此演化为下方的算法

def gcd(a,b):
    return b  if a % b == 0 else gcd(b,a % b)
nums = [0, 0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46]

lcm,ans = 1,1
i = 2
while i < 50:
    if ans % i == nums[i]:
        lcm = lcm // gcd(lcm,i) * i
        i += 1
    else:
        ans += lcm
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

第二种标准做法 中国剩余定理

菜鸡表示不会求逆元，扩欧这些数论，如果不打acm的话，数论的要求还挺少的

简单总结一下：

蓝桥杯可能出现的数论知识：

（以出现频率总结）

1. 素数筛（学一个欧拉筛即可）
2. 素数判定（试除法）
3. gcd/lcm （最大公约数和最小公倍数）
4. 分解质因数求约数相关的**（算术基本定理）** 比较重要
5. 快速幂，矩阵快速幂，快速幂（py可以不学，因为pow库函数比手写快速幂要快一点）
6. 求组合数 （如果不学卢卡斯定理，可以用math库里面的factorial 求阶乘的公式）

算数基本定理基本思想：
如果 N=p1c1∗p2c2∗…∗pkckN=p1c1∗p2c2∗…∗pkck
约数个数：(c1+1)∗(c2+1)∗…∗(ck+1)(c1+1)∗(c2+1)∗…∗(ck+1)
约数之和： (p10+p11+…+p1c1)∗…∗(pk0+pk1+…+pkck)

这些常用板子的总结（Python语言）后续会慢慢补充上

3. 纸张尺寸

不多解释，手算打表都行，入门题

难度系数：⭐

index=int(input()[-1])
h,w=1189,841
i=0
while i<index:
    h=int(h/2)
    h, w = max(h, w), min(h, w)
    i+=1
print(h)
print(w)
1
2
3
4
5
6
7
8
9

4. 数位排序

难度系数：⭐⭐

做出这题，在我们省大概省二了

关键字排序，根据数位和

n=int(input())
m=int(input())
arr=list(range(1,n+1))
def f(i):
    val=0
    x=i
    while x>0:
        val+=x%10
        x//=10
    return val
arr.sort(key=lambda i:f(i))
print(arr[m-1],end='')
1
2
3
4
5
6
7
8
9
10
11
12

5. 蜂巢

难度系数：⭐⭐⭐⭐

数学 推理

2021河南icpc省赛(B题）思路一样，后悔当时大一没补这题（按照当年现场赛的学长说，这题应该算夺冠难度了，大于金牌题）

原题链接：Honeycomb

题解目前正在努力中

6. 消除游戏

---

难度系数：⭐⭐⭐⭐

链表 并查集

目前只会暴力模拟的做法，能拿75%的分

s = input()
for i in range(2<<64):
    exit = 1
    vis = [0] * len(s)
    a = []
    for i in range(1,len(s)-1):
        if s[i] == s[i-1] and s[i]!=s[i+1]:
            vis[i] = 1
            vis[i+1] = 1
            exit = 0
        elif s[i] == s[i + 1] and s[i] != s[i-1]:
            vis[i] = 1
            vis[i-1] = 1
            exit = 0
    ss = ''
    for i in range(len(s)):
        if not vis[i]:
            ss += s[i]
    s = ss
    if exit:
        print(s,end="")
        break
    if not s:
        print("EMPTY",end="")
        break
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

7. 全排列的价值

难度系数：⭐⭐⭐⭐

考试的时候没推出规律，用C++的next_permutation 打了前12项数据，特判输出样例，其他输出1.

如果没找到变化的规律，可以推出dp状态转移方程，下面是ac代码

n=int(input())
mod=998244353
f=[0]*(n+10)
f[2]=1
ways=2
for i in range(3,n+1):
    f[i]=(f[i-1]*i%mod+ways*(i-1)*i//2%mod)%mod
    ways=ways*i%mod
print(f[n]%mod)
1
2
3
4
5
6
7
8
9

简化版

n=int(input())
mod=998244353
 
ans=1
for i in range(1, n+1):
    ans=(ans*i)%mod
 
ans=(ans*n*(n-1)//4)%mod
print(ans)
1
2
3
4
5
6
7
8
9

8. 技能升级

难度系数：⭐⭐⭐⭐

当时用排序打了一个暴力做法，估计能过50%数据

正解是二分 + 贪心 或者优先队列

思路二分最后一次升级技能提升了多少攻击力

我们升级技能的过程，肯定是贪心的思路，找到所有技能中攻击力最高的，升级后它的点数发生改变。可以发现，当我们知道了最后一次升级技能提升了多少攻击力，由于之前升级技能的贪心过程，之前升级技能提升的攻击力都不少于最后一次，而升级技能点数减少的过程是一个等差数列，我们显然能 通过O(1) 的时间知道每个技能升级了几次。最后根据升级技能的次数和 M 对比，check函数的就可以推出来了

O（1）复杂度推导每个技能升级几次 解释说明：

例如 ai = 5 , bi = 2

5 3 1 0 0 0 …

如果要算 从ai改变到x，需要的升级次数：

cnt = (a[i] - x) // b[i]

但是统计第n项大于等于x的时候，需要算上初始的那一次，应该再加1

res += （cnt + 1）

贴一下newoj创始人fzl大佬的代码：

大佬博客链接：傅志凌

（py这么大数据量，相同时间复杂度的做法在其他oj提交可能还是会tle）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
int n, m;
int a[maxn], b[maxn];
ll ans;
 
 
///每个技能相当于一个数列：a[i], a[i]-b[i], a[i]-2b[i] ,..., 0 0 0 0
///求第m大是多少
///假设第m大为x，求存在多少个数字>=x
bool check(ll x)
{
    ll cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        ///a[i] - k * b[i] >= x
        if(a[i] < x)continue;
        int k = (a[i] - x) / b[i];
        cnt += k + 1;
    }
    return cnt >= m;
}
 
int main()
{
    read(n);read(m);
    for(int i = 1; i <= n; i++)
        read(a[i]), read(b[i]);
    int left = 0, right = 1000000, x = 0;
    while(left <= right)
    {
        int mid = (left + right) >> 1;
        if(check(mid))
            x = mid, left = mid + 1;
        else
            right = mid - 1;
    }
    for(int i = 1; i <= n; i++)
    {
        ///找一个最大的满足k：a[i] - k * b[i] > x
        if(a[i] < x)continue;
        int k = (a[i] - x) / b[i];
 
        if(k * b[i] != (a[i] - x))k += 1;
        m -= k;
        ///a[i] ... a[i]-(k-1)*b[i]
        ans += (ll)(a[i] + a[i] - (k - 1) * b[i]) * k / 2;
    }
    ans += m * x;
    cout<<ans<<endl;
    return 0;
}
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

9. 最长不下降子序列

难度系数：⭐⭐⭐⭐

动态规划 + 权值线段树 （只会线段树的模板题，还没听说过这种）

好像还有二分 + 两个辅助数组的做法，看不懂

至于最长上升子序列有两种模板

dp模板O（n ^ 2）:

res = 0
f = [0]*1010
# 正向求解LIS 问题
for i in range(n):
    f[i] = 1
    for j in range(i):
        if a[i] > a[j]:
            f[i] = max(f[i],f[j] + 1)
    res = max(res,f[i])
1
2
3
4
5
6
7
8
9

贪心 + 二分O（nlogn）

d = []
for n in nums:
    if not d or n > d[-1]:
        d.append(n)
    else:
        l, r = 0, len(d) - 1
        loc = r
        while l <= r:
            mid = (l + r) // 2
            if d[mid] >= n:
                loc = mid
                r = mid - 1
            else:
                l = mid + 1
       d[loc] = n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

贴一下大佬的代码，

原博客链接：A组题解

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int a[maxn], b[maxn];
int dp[maxn];
///dp[i]表示以i结尾的最长上升子序列
 
///权值线段树，维护dp数组
int tree[maxn << 2];
void build(int o, int l, int r)
{
    tree[o] = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
}
void update(int o, int l, int r, int x, int val)
{
    if(l == r)
    {
        tree[o] = max(tree[o], val);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
        return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}
 
int main()
{
    int n, k, tot = 0;
    read(n); read(k);
    for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];
    if(n == k)
    {
        cout<<n<<endl;
        return 0;
    }
    ///离散化
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - (b + 1);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
     
    build(1, 1, tot);
    int ans = 0;
    for(int i = 1; i <= n; i++)///从前往后遍历a，放入权值线段树中
    {
        ///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]
        dp[i] = query(1, 1, tot, 1, a[i]) + 1;
        update(1, 1, tot, a[i], dp[i]);
    }
    ///重新清空
    build(1, 1, tot);
    for(int i = n; i > k; i--)///从后往前遍历a，放入权值线段树中
    {
        ///a[i-k+1] ... a[i]相等 均等于a[i-k]
        ///最后一段要注意：查询的是[a[i-k],tot]中的最大值
        ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);
        int tmp = query(1, 1, tot, a[i], tot) + 1; ///以a[i]开始的最长上升子序列长度
        ans = max(ans, tmp + k);
        ///插入的是a[i]
        update(1, 1, tot, a[i], tmp);
    }
    cout<<ans<<endl;
    return 0;
}
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
91
92
93
94

10. 最优清零方案

难度系数：⭐⭐⭐⭐⭐

贪心 + 暴力写了一份代码，可惜55的时候机房电脑有误差，导致实际时间已经结束了，没有交上，哭辽┭┮﹏┭┮…

正解是贪心 + 线段树

贴一份fzl大佬的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int maxn = 2000000 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
int a[maxn], n, k;
struct Node
{
    int mi, add;
}tree[maxn << 2];
 
void push_up(int o)
{
    tree[o].mi = min(tree[o << 1].mi, tree[o << 1 | 1].mi);
}
void push_down(int o)
{
    if(tree[o].add != 0)
    {
        tree[o << 1].add += tree[o].add;
        tree[o << 1].mi += tree[o].add;
        tree[o << 1 | 1].add += tree[o].add;
        tree[o << 1 | 1].mi += tree[o].add;
        tree[o].add = 0;
    }
}
void build(int o, int l, int r)
{
    if(l == r)
    {
        tree[o].mi = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    push_up(o);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
        return tree[o].mi;
    push_down(o);
    int mid = l + r >> 1;
    int ans = 1e9 + 10;
    if(L <= mid)ans = min(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = min(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}
void update(int o, int l, int r, int L, int R, int val)
{
    if(L <= l && r <= R)
    {
        tree[o].mi += val;
        tree[o].add += val;
        return;
    }
    push_down(o);
    int mid = (l + r) >> 1;
    if(L <= mid)update(o << 1, l, mid, L, R, val);
    if(R > mid)update(o << 1 | 1, mid + 1, r, L, R, val);
    push_up(o);
}
int main()
{
    ///freopen("test.in", "r", stdin);
    read(n);read(k);
    ll sum = 0;
    for(int i = 1; i <= n; i++)
        read(a[i]), sum += a[i];
    if(k > n)
    {
        cout<<sum<<endl;
        return 0;
    }
    build(1, 1, n);
    ll ans = 0;
    for(int i = 1; i <= n - k + 1; i++)
    {
        int mi = query(1, 1, n, i, i + k - 1);
        ///cout<<mi<<endl;
        if(mi == 0)
        {
            int res = query(1, 1, n, i, i);
            update(1, 1, n, i, i, -res);
            ans += res;
        }
        else
        {
            ans += mi;
            update(1, 1, n, i, i + k - 1, -mi);
            int res = query(1, 1, n, i, i);
            if(res)
            {
                ans += res;
                update(1, 1, n, i, i, -(res));
            }
        }
    }
    ///cout<<ans<<endl;
    for(int i = n - k + 2; i <= n; i++)
        ans += query(1, 1, n, i, i);
    cout<<ans<<endl;
    return 0;
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

11. 准备国赛

根据去年和今年题目的知识点总结：

线段树应该是必考的了，但是如果不是冲国一的话，也可以不学

去年考过一道数位dp的裸题，今年dp有可能换一个高阶dp知识点考：

例如 下列类型的动态规划

1. 树形dp
2. 区间dp
3. 状压dp
4. 单调队列优化dp
5. 斜率优化dp
6. 状态机模型

除此之外，各种类型的背包问题也是复习的重点哦^__ ^****

去年省赛 到 国赛压轴 题目的变化

异或数列 => 异或 三角形

括号序列 => 翻转括号序列

那么大胆预测一手今年的国赛压轴题目

（线段树）
最长不下降子序列 -> 不下降子序列~~
最优清零方案 -> 最优~~~~

希望同学们都好好复习，能在六月份国赛取得一个满意的成绩！！！