第十四届蓝桥杯模拟赛第二期部分题答案（C++代码）

A题

题面

请找到一个大于 2022 的最小数，这个数转换成二进制之后，最低的 6 个二进制为全为 0 。
请将这个数的十进制形式作为答案提交。

思路

由于最低6位都是0，且(11111000000)₂<(2048)₁₀,所以选要选取(100000000000)₂=2048

答案：2048

B题

题面

我们计从 1949 年 10 月 1 日至 1949 年 10 月 2 日为经过了 1 天。请问从 1949 年 10 月 1 日至 2022 年 1 月 1 日经过了多少天？

算法

模拟，枚举。可以用excel，直接for然后判定一下该日期是否合法，如是就cnt++;

答案：26390

C题

题面

8518 是一个非常特殊的数，如果把这个数看成 16 进制数，它的值为 (8518)16=8161616+51616+116+8=34072，而 34072 正好是 8518 的整数倍。9558 也是这样一个数，当看成 16 进制时是 38232。其实长度为 1 的数 0 到 9 都满足看成 16 进制后是自己的整数倍（1倍）。请问，除开长度为 1 的数，最小的满足这样条件的数是多少？

算法

模拟。直接for到底然后check一下即可

答案：1038

D题

题面

小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 到 9 之间的数字。现在小蓝想从这个矩阵的第一行第一列画一条折线到第 30 行 60 列，线只能沿水平向右走或竖直向下走，只能在有数字的地方拐弯。小蓝想知道，这样一条线经过的数字的和最大是多少。

算法

线性DP，状态转移方程：$f[i][j]=f[i-1][j]+f[i][j-1]$

答案：592

E题

题面

将 2022 拆分成不同的质数的和，请问最多拆分成几个？

算法

01背包，先求质数，再通过状态转移方程来求出$f[i][j]=max(f[i-1][j],f[i-1][j-prime[i]]+prime[i])$，f[i][j]表示前i个数恰好凑成j.

答案：32

J题

题面

小蓝有一个序列 a[1], a[2], …, a[n]，每次可以交换相邻的两个元素，代价为两个元素中较大的那个。请问，要通过交换将序列变为从小到大递增的序列，总代价最少为多少？

输入格式

输入一行包含一个整数 n ，表示序列长度。
第二行包含 n 个整数，表示给定的序列。

输出格式

输出一行包含一个整数，表示最少代价的值。

数据范围

对于 30% 的评测用例，1 <= n <= 1000, 1 <= a[i] <= 1000。
对于 60% 的评测用例，1 <= n <= 50000, 1 <= a[i] <= 50000。
对于所有评测用例，1 <= n <= 1000000, 1 <= a[i] <= 1000000。

算法(贪心,逆序对,树状数组)

给定一个序列x₁到x_n，假如x_i是目标元素，x_j是排完序后的位置(且x_j＞x_i)(x_j＜x_i是同理的)，然后目标元素移动到对应位置需要移动x_j ~ x_i次，若存在x≥目标元素，将目标从x_i移到x_j后，x则会向前一个位置，后续需要再次移动，即至少计算两次x，此时不是最优解。

当目标移到x_j时，x_i到x_j序列变成x_i+1到x_j、x_i序列，原序列x_i到x_j中， x_i+1到x_j上的元素对于目标来说都是1（目标对后续那段序列造成的逆序对是1）,移动完后，x_i+1到x_j都向前移动了一个位置，即对于x_j来说当前位置是x_j-1，因此需要代入逆序对。

逆序对的求法有归并排序、树状数组、线段树的方法，这里用树状数组来求逆序对，求的是该数前面有几个比它大的。

经过一番思考后可以得出式子：(新坐标-(原坐标-该数的逆序对))

代码

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 1e6+10;
LL res;
int n,ni[N];
int tr[N];

struct Node
{
    int data,id;
    bool operator < (const Node &W)
    {
    	//排序关键字
        if(data == W.data) return id<W.id;
        return data<W.data;
    }
}node[N];

int lowbit(int x)
{
    return x&-x;
}

int query(int x)
{
    int res=0;
    for(int i=x; i; i-=lowbit(i)) res+=tr[i];
    return res;
}

void add(int x,int v)
{
    for(int i=x; i<N; i+=lowbit(i)) tr[i]+=v;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&node[i].data);
        node[i].id=i;
    }
    //求当前数前面比它大的个数
    for(int i=1; i<=n; i++)
    {
    	//线段树求逆序对
        ni[node[i].id]=query(N-1)-query(node[i].data);
        add(node[i].data,1);
    }
    sort(node+1,node+n+1);
    for(int i=1; i<=n; i++)
    {
    	//(新坐标-(原坐标-逆序对))
        res+=(LL)(i-(node[i].id-ni[node[i].id]))*node[i].data;
    }
    printf("%lld",res);
    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

---

个人观点，非官方答案。

---

一直审核不过说“版权投诉”
以上纯手码（除了题面是复制），并未涉及任何版权问题。
如果说涉及到蓝桥杯模拟赛的版权，那么审核是否应该将所有蓝桥杯模拟赛的题解都下架？