noip2021 训练 3 做题记录

简介

一大堆毒瘤构造题中夹杂着几道其他题目……

题目

CF1348D Phoenix and Science

Description

Luogu传送门

Solution

考虑最快情况,即 \(1 \rightarrow 2 \rightarrow 4 \rightarrow 8 ····\)

但是我们发现如果前期分裂太多,后面可能会出现不可控的情况,即超出题目要求达到的数量,所以我们在前期合适的位置要控制一下。

那么是在哪里呢?

我们把 \(n\) 减去 2 的幂的前缀和之后的数放到 2 的幂数组中比它小的最大的数的位置后面即可。

只看文字不好理解,结合代码理解一下吧。

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int T, n;
int a[50], cnt;

int main(){
    scanf("%d", &T);
    while(T--){
        int tmp = 1;
        cnt = 0;
        scanf("%d", &n);
        while(n > 0){
            a[++cnt] = n > tmp ? tmp : n;
            n -= tmp;
            tmp <<= 1;
        }
        sort(a + 1, a + 1 + cnt);
        printf("%d\n", cnt - 1);
        for(int i = 2; i <= cnt; ++i)
            printf("%d ", a[i] - a[i - 1]);
        puts("");
    }
    return 0;
}

CF1348B Phoenix and Beauty

Description

Luogu传送门

Solution

emm……一开始没什么思路,去看样例。

发现第 4 组数据可以直接输出原数组的啊,为啥样例要输出这么多?

然后就发现样例输出在输出一个有循环节的数字串,那是不是可以推广一下?

确实是可以的。

不难发现,如果原数组中的不同数字的个数大于 \(k\),那显然是无解的,直接输出-1

接着我们尝试构造循环节,发现构造一个长度为 \(k\),只包含不同数字(每个数字只出现一次),且包含原数组中所有不同数字的数组,把它当作循环节,然后直接循环输出 \(n\) 遍即可。

\(n,k \leq 100\),所以 \(n \times k \leq 10000\),符合条件。

CF1304D Shortest and Longest LIS

Description

Luogu传送门

Solution

题目要求我们构造符合条件的最长和最短的 \(LIS\)。

既然要最长和最短的,我们就先构造出来。

  • 对于最长的:构造一个 \(1 \sim n\) 的序列。

  • 对于最短的:构造一个 \(n \sim 1\) 的序列

然后我们按照题意把不合法的段取个反即可。

CF1312E Array Shrinking

Description

Luogu传送门

Solution

题意比较迷,主要是刚开始把 两步操作 看成了 两种操作 QwQ。

那么题意大概就是你可以选择两个相邻的且相同的数合并,合并后的权值是原本权值 +1。

蒟蒻一开始想了半天都构造,结果没想出来/kk。

看了一眼题解之后,哦,原来是区间 \(dp\) 啊,那没事了(做构造做魔怔了属于是)。

设 \(dp_{i,j}\) 表示区间 \([i,j]\) 最少能合并成几个数,转移方程显然:

\[dp_{i, j} = dp_{i,k} + dp_{k + 1, j} \]

再记录一个数组 \(f_{i,j}\) 表示区间 \([i,j]\) 合并之后的数是多少。

如果 \(dp_{i,k}\) 和 \(dp_{k + 1, j}\) 都是 1,且 \(f_{i,k} = f_{k + 1, j}\),那么 \(dp_{i,j} = 1\),同时 \(f_{i,j} = f_{i,k} + 1\) 即可。

CF1110E Magic Stones

Description

Luogu传送门

Solution

神仙结论题,当然还是要推一下的。

我们对 \(c_i\) 做一个差分,\(a_i = c_{i + 1} - c_i\),\(a_{i + 1} = c_{i + 2} - c_{i + 1}\)。

那么对于 \(c_i\) 的一次操作之后:

\[c_i' = c_{i + 1} + c_{i - 1} - c_i \]

\(a_i\) 和 \(a_{i + 1}\) 就变成了:

\[a_i = c_{i + 1} - (c_{i + 1} + c_{i - 1} - c_i) \]

\[a_{i + 1} = c_{i + 2} - (c_{i + 2} + c_{i} - c_{i + 1}) \]

开一下括号,就变成了……

\[a_i = c_i - c_{i - 1} \]

\[a_{i + 1} = c_{i + 1} - c_i \]

惊不惊喜?意不意外?

没错,我们只要判断 \(c\) 数组和 \(t\) 数组的差分数组排完序之后是否一样就行了。

CF1110C Meaningless Operations

Description

Luogu传送门

Solution

神仙打表找结论题。

就是打表,暴力计算每一个数的答案。

打完表发现对于 \(2^{i - 1} < x < 2^i - 1\) 答案就是 \(2^i - 1\)。

对于 \(x = 2^i - 1\),提前把答案表打出来,询问的时候直接输出即可(似乎有个式子可以直接算出来,但我没去推)。

CF540C Ice Cave

Description

Luogu传送门

Solution

混在构造题里的搜索……

爆搜就完了,没什么好说的。

实在不会的话,详见博客CF540C Ice Cave 题解 - xixike - 博客园 (cnblogs.com)

CF989C A Mist of Florescence

Description

Luogu传送门

Solution

一开始想的是 \(A,B,C,D\) 交叉放,但是很难写……

然后发现可以直接构造一个 \(40 \times 50\) 的矩阵,每个字母 10 行。

然后把当前字母插入到上一个字母形成的矩阵中即可。

例如:

AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

假设 B需要 5 个联通块,那么就插成这样:

ABABABABAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

由于数据范围允许,我们可以插一行跳一行,还好写一点,具体来讲:

AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

假设B需要 7 个联通块,那么:

ABABABABAB
AAAAAAAAAA
ABAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

注意:第 3 行第 2 列变成了 B。

J - Beauty Of Unimodal Sequence

这题洛谷上没有,而且也还不会做,咕咕咕了。

上一篇:Flutter 打包发布


下一篇:基于frdia的安卓逆向工具hooker抓包soul app