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
33 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
318 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] 回文数组
(考虑贪心算法)