蓝桥打卡-Day15

酶和ATP 2022年03月23日 604次浏览

金币-2015NOIP普及组

https://www.lanqiao.cn/problems/357/learning/

题目描述

国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币......;这种工资发放模式会一直这样延续下去:当连续 N 天每天收到 N 枚金币后,骑士会在之后的连续 N+1 天里,每天收到 N+1 枚金币。

请计算在前 K 天里,骑士一共获得了多少金币。

输入描述

输入只有 1 行,包含一个正整数 K (1≤_K_≤10^4),表示发放金币的天数。

输出描述

输出只有 1 行,包含一个正整数,即骑士收到的金币数。

输入输出样例

示例 1

输入

6

输出

14

示例 2

输入

1000

输出

29820

暴力模拟即可,注意这个150,等差数列求和公式(1+n)*n/2 = 10000,解出来141。

#include <iostream>
using namespace std;
const int N = 1e5;
int money[N];

void get_money() {
    int cnt = 1;
    for (int i = 1; i < 150; i++)
        for (int j = 1; j <= i; j++) money[cnt++] = i;
}
int main() {
    get_money();
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) res += money[i];
    cout << res << endl;
    return 0;
}

优秀的拆分-2020CSP-J

https://www.lanqiao.cn/problems/801/learning/

题目描述

一般来说,一个正整数可以拆分成若干个正整数的和。

例如,1=1,10=1+2+3+4 等。对于正整数 n 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,n 被分解为了若干个不同的 2 的正整数次幂。注意,一个数 x 能被表示成 2 的正整数次幂,当且仅当 x 能通过正整数个 2 相乘在一起得到。

例如,10=8+2=2

3+2

1是一个优秀的拆分。但是,7=4+2+1=2

2+2

1+2

0 就不是一个优秀的拆分,因为 1 不是 2 的正整数次幂。

现在,给定正整数 n,你需要判断这个数的所有拆分中,是否存在优秀的拆分。若存在,请你给出具体的拆分方案。

输入描述

输入只有一行,一个整数 n (1≤_n_≤10

7),代表需要判断的数。

输出描述

如果这个数的所有拆分中,存在优秀的拆分。那么,你需要从大到小输出这个拆分中的每一个数,相邻两个数之间用一个空格隔开。可以证明,在规定了拆分数字的顺序后,该拆分方案是唯一的。

若不存在优秀的拆分,输出 -1

输入输出样例

示例 1

输入

6

输出

4 2

示例 2

输入

7

输出

-1
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int cnt = 1;
int pow2[30];
int rescnt = 1;
int res[30];

void get2() {
    for (int i = 1; pow2[cnt - 1] < 1e7 + 10; i++) pow2[cnt++] = pow(2, i);
}

int main() {
    int n;
    cin >> n;
    get2();

    int rest = n;

    for (int i = cnt; i > 0; i--)
        if (pow2[i] <= rest) rest -= pow2[i], res[rescnt++] = pow2[i];

    if (rest == 0)
        for (int i = 2; i < rescnt; i++) cout << res[i] << ' ';
    else
        cout << -1 << endl;

    return 0;
}

穿越雷区

http://lx.lanqiao.cn/problem.page?gpid=T2818

蓝肽子序列-2020国赛

https://www.lanqiao.cn/problems/1030/learning/

题目描述

L 星球上的生物由蛋蓝质组成,每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。

生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列,想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。

具体的,一个蓝肽可以使用 1 至 5 个英文字母表示,其中第一个字母大写,后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。

在一条蓝肽序列中,如果选取其中的一些位置,把这些位置的蓝肽取出,并按照它们在原序列中的位置摆放,则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的,中间可能间隔着一些未被取出的蓝肽。

如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等,则称为一个公共蓝肽子序列。

给定两条蓝肽序列,找出他们最长的那个公共蓝肽子序列的长度。

输入描述

输入两行,每行包含一个字符串,表示一个蓝肽序列。字符串中间没有空格等分隔字符。

其中有 ,两个字符串的长度均不超过 1000。

输出描述

输出一个整数,表示最长的那个公共蓝肽子序列的长度。

输入输出样例

示例

输入

LanQiaoBei
LanTaiXiaoQiao

输出

2