P10898 [蓝桥杯 2024 省 C] 拼正方形

题目描述

小蓝正在玩拼图游戏，他有 7385137888721个 2×2的方块和 10470245 个 1×1 的方块，他需要从中挑出一些来拼出一个正方形，比如用 3 个 2×2 和 4 个 1×1 的方块可以拼出一个 4×4 的正方形，用 9 个 2×2 的方块可以拼出一个 6×6 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。

输入格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例

无

#include <iostream>
#include <cmath>
using namespace std;
int main()
{long long a = 7385137888721;int b = 10470245;int c = sqrt(a);c *= 2;a -= c;int len = c;while (true) {if (b >= c * 2 + 1) {len++;b -= (c * 2 + 1);}else {break;}}cout << len << endl;return 0;
}

思路：

        要想得到最大的正方形，就要把2×2的先尽可能的拼成正方形。

        有一个点需要注意，a的数据类型是long long，我一开始用了int，我说用计算器算的开方和sqrt不一样，找了好一会的原因才发现数据类型错了。

P10899 [蓝桥杯 2024 省 C] 劲舞团

题目描述

小蓝最近迷上了一款名为“劲舞团”的游戏，具体来说，只要按照游戏中给出的键位提示依次按出对应的键位，游戏人物便可以跟随节奏跳舞。对于连续的 K 次正确敲击，如果任意连续的两次敲击间间隔时间都小于等于 1s，那么 我们称这是一次 K 连击。现在给出一局小蓝的游戏记录文件，log.txt 中记录了 N 条记录，每条记录有三个字段，依次为正确的敲击字符、小蓝打出的字符、打出字符的时间对应的毫秒时间戳。现在请你计算下最长的 KK 连击是多少，你 只需要输出 K 的值。

输入格式

为了方便评测，输入数据已替换为 log.txt。在洛谷评测时，你可以从标准输入读取 log.txt，也可以从下发文件中下载。

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例

无

#include <iostream>
using namespace std;
int main()
{//freopen("log.txt", "r", stdin);char true_Str, s;long long time;cin >> true_Str >> s >> time;long long last = time;int count = 1, ans = -1;while (cin >> true_Str >> s >> time) {if (true_Str!=s) {count = 1;continue;}if (time - last <= 1000) {count++;last = time;}else {count = 1;last = time;}ans = max(ans, count);}cout << ans << endl;return 0;
}

思路：

        有一个点需要注意：//freopen("log.txt", "r", stdin);这一行我后来注释掉了，因为题目会逐行输入，不需要我去打开文件，不注释掉反而错了

P10900 [蓝桥杯 2024 省 C] 数字诗意

题目描述

在诗人的眼中，数字是生活的韵律，也是诗意的表达。

小蓝，当代顶级诗人与数学家，被赋予了“数学诗人” 的美誉。他擅长将冰冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。

某日，小蓝静坐书桌前，目光所及，展现着 n 个数字，它们依次为 a1,a2,⋯ ,an​，熠熠生辉。小蓝悟到，如果一个数能够以若干个（至少两个）连续的正整数相加表示，那么它就蕴含诗意。例如，数字 6 就蕴含诗意，因为 它可以表示为 1+2+3。而 88 则缺乏诗意，因为它无法用连续的正整数相加表示。

小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 n 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？

输入格式

输入的第一行包含一个整数 n，表示展示的数字个数。

第二行包含 nn 个整数 a1,a2,⋯ ,an，相邻整数之间使用一个空格分隔，表示展示的数字。

输出格式

输出一行包含一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。

输入输出样例

输入 #1

3
3 6 8

输出 #1

1

说明/提示

【样例说明】

在样例中，数字 3 可以表示为 1+2，数字 66 可以表示为 1+2+3，数字 8 无法表示为连续的正整数相加，因此，需要删除的数字个数为 1。

【评测用例规模与约定】

对于 30% 的评测用例，1≤n≤10^3，1≤ai​≤10^3。
对于所有评测用例，1≤n≤2×10^5，1≤ai​≤10^16。

#include <iostream>
using namespace std;
int main()
{int n, count = 0;cin >> n;ios::sync_with_stdio(false);cin.tie();cout.tie();for (int i = 0; i < n; i++) {long long a;cin >> a;if (a && !(a & (a - 1))) {count++;}}cout << count << endl;return 0;
}

思路：

        2的幂次就不“诗意”

P10901 [蓝桥杯 2024 省 C] 封闭图形个数

题目描述

在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字1、2、3、5、7 都没有形成封闭图形，而数字 0、4、6、9 分别形成了 1 个封闭图形，数字 8 则形成了 2 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 68，由于 6 形成了 1 个封闭图形，而 8 形成了 2 个，所以 68 形成的封闭图形的个数总共为 3。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 41 和数字 18，它们对应的封闭图形的个数分别为 1 和 2，因此数字 41 小于数组 18。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 14 和数字 41，它们的封闭图形的个数都是 1，但 14<41，所以14 小于数字 41。如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 n 个数 a1​,a2​,⋯,an​，请你按照蓝桥王国的数字大小规则，将这 n 数从小到大排序，并输出排序后结果。

输入格式

输入的第一行包含一个整数 n，表示给定的数字个数。

第二行包含 n 个整数 a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔，表示待排序的数字。

输出格式

输出一行包含 n 个整数，相邻整数之间使用一个空格分隔，表示按照蓝桥王国的数字大小规则从小到大排序后的结果。

输入输出样例

输入 #1

3
18 29 6

输出 #1

6 29 18

说明/提示

【样例说明】

对于给定的数字序列 [18,29,[18,29,6]，数字 18 的封闭图形个数为 2，数字 29 的封闭图形个数为 1，数字 6 的封闭图形个数为 1。按照封闭图形个数从小到大排序后， [29,6,18][29,6,18]。

由于数字 29 和数字 6 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 [6,29,18]。

【评测用例规模与约定】

对于 50% 的评测用例，1≤n≤2×103，1≤ai​≤105。
对于所有评测1≤n≤2×105，1≤ai​≤109。

#include <iostream>
#include <algorithm>
using namespace std;const long long N = 2e5 + 5;
int n;
pair<int, long long>a[N];
int cnt[] = { 1,0,0,0,1,0,1,0,2,1 };int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i].second;int x = a[i].second;while (x) {a[i].first += cnt[x % 10];x /= 10;}}sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++)cout << a[i].second << " ";return 0;
}

思路：

        1）选择用pair，我一开始用的是两个vector，一个记录封闭数字个数，一个记录数字本身，这样有一个坏处，就是在比较的时候很容易出错，而且代码有点累赘

        2）选择直接用一个cnt数字记录每个数字（10以内）所对应的封闭数字个数，不需要用if else（其实也可以用，只是这样貌似更加简洁？）

        3）sort函数内部记得+1，因为是从1下标开始的。

P10902 [蓝桥杯 2024 省 C] 回文数组

（考虑贪心算法）