🌼深夜伤感网抑云 - 南辰Music/御小兮 - 单曲 - 网易云音乐
🌼多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐
50题才停更，课业繁忙，有时间就更，2023/3/14/15:06写下
目录
👊填空题
🌼一,[蓝桥杯2020初赛] 门牌制作
🌼二,[蓝桥杯2020初赛] 既约分数
🌼三,[蓝桥杯2020初赛] 蛇形填数
🌼四,[蓝桥杯2020初赛] 七段码
🌼五,[蓝桥杯2020初赛] 约数个数
🌼六,[蓝桥杯2021初赛] 卡片
🌼七，[蓝桥杯2021初赛] 直线
🌼八,[蓝桥杯2021初赛] 货物摆放
🌼九,[蓝桥杯2021初赛] 路径
🌳Floyd-Warshall
🌳Dijkstra AC
🌼十, [蓝桥杯2021初赛] 空间
🌼十一,[蓝桥杯2022初赛] 裁纸刀
🌼十二,[蓝桥杯2022初赛] 灭鼠先锋
🌼十三, [蓝桥杯2022初赛] 九进制转十进制
🌼十四, [蓝桥杯2022初赛] 顺子日期
🌼十五，[蓝桥杯2022初赛] 排列字母
🌼十六，[蓝桥杯2019初赛]平方和
🌼十七，[蓝桥杯2019初赛]数列求值
🌼十八，[蓝桥杯2019初赛]最大降雨量
👊填空题总结
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
👊编程题
🌼一，[蓝桥杯2022初赛] 刷题统计
🌼二，1518: [蓝桥杯2020初赛] 回文日期
🌳暴力 AC 20% Time Lmit
🌳AC 100%
骗分过样例,暴力出奇迹;暴搜挂着机,打表出省一 (过去式了,看22年A组就知道)
2018，2019，2020，2021，2022年蓝桥杯C++／C组省赛A，B，G组真题
题目链接，题目， 解析，代码
要参加2023年C++组A组省赛了！希望可以省一，没有也不要紧，还有大二
当然，如果题目不对胃口，有些ACM银牌的大佬也才省二．．．对头的话，打铁选手也给你来个国一国二
和我一起刷进蓝桥杯C++A组省一（小声）
👊填空题
咱先从20年开始
🌼一,[蓝桥杯2020初赛] 门牌制作
P1508 - [蓝桥杯2020初赛] 门牌制作 - New Online Judge (ecustacm.cn)
考虑到蓝桥杯OI赛制(没有反馈),最好自己多试几组例子,比如我,将代码第6行 i <= 2020分别改成23, 1, 19, 32测试了下,如果和草稿本算的一样,就算过了
否则真到比赛时信心满满,感觉自己AC了七八道题,最后连个省二都没就笑了
#include<iostream>
using namespace std;
int main()
{
int sum = 0, j;
for(int i = 1; i <= 2020; ++i) {
j = i;
while(j / 10) {
if(j % 10 == 2)
sum += 1;
j /= 10;
}
if(j % 10 == 2) sum += 1;
}
cout<<sum;
return 0;
}
624🌼二,[蓝桥杯2020初赛] 既约分数
P1509 - [蓝桥杯2020初赛] 既约分数 - New Online Judge (ecustacm.cn)
用辗转相除法求最大公约数
原理: 原来的除数(➗右边的) / 余数
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1#include<iostream>
using namespace std;
int com(int x, int y)
{
while(x % y) { //辗转相除法
int z = x % y;
x = y;
y = z;
}
return y;
}
int main()
{
int sum = 0;
for(int i = 1; i <= 2020; ++i)
for(int j = 1; j <= 2020; ++j)
if(com(i, j) == 1) sum++;
cout<<sum;
return 0;
}
2481215🌼三,[蓝桥杯2020初赛] 蛇形填数
P1510 - [蓝桥杯2020初赛] 蛇形填数 - New Online Judge (ecustacm.cn)
容易发现,数字按照 右-->左下-->下-->右上 的规律递增
加个判断边界的条件即可
先画到45,可知,找第n行n列, i, j 需要遍历到2 * n - 1
#include<iostream>
using namespace std;
int a[1000][1000];
int main()
{
a[1][1] = 1;
int m = 1;
for(int i = 1, j = 1; i <= 40 && j <= 40;) {
//右
a[i][++j] = ++m;
//左下
while(1) {
a[++i][--j] = ++m;
if(j == 1) break;
}
//下
a[++i][j] = ++m;
//右上
while(1) {
a[--i][++j] = ++m;
if(i == 1) break;
}
}
cout<<a[20][20];
return 0;
}
761🌼四,[蓝桥杯2020初赛] 七段码
P1511 - [蓝桥杯2020初赛] 七段码 - New Online Judge (ecustacm.cn)
第一次做,猜了63种,错了,7 + 10 + 14 + 14 + 10 + 7 + 1 = 63
错在哪里呢,错在3,4,5段发光
而且由于不发光部分不需要连通,所以 3段 != 4段, 2段 != 5段
这道题单靠猜,90%的人都做不对,很容易就漏掉几种或者想当然
当然代码我也不会😂
来个别人的AC代码把
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
// 请在此输入您的代码
int sum = 0;
//有一段二极管发光; a,b,c,d,e,f,g
int l1 = 7;
//有两段二极管发光; ab,af,bc,bg,cg,cd,de,eg,ef,fg
int l2 = 10;
//有三段二极管发光; abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,cdg,deg,def,efg
int l3 = 16;//
//有四段二极管发光; abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defa
int l4 = 20;
//有五段二极管发光即有两端不发光; ab,ac,ad,ae,af,ag,bc,bd,be,bg,cd,cf,cg,de,df,dg,ef,eg,fg
int l5 = 19;//
//有六段二极管发光即有一端不发光; a,b,c,d,e,f,g
int l6 = 7;//(找一段二极管不发光的：)
//第七种情况，全部发光
int l7 = 1;
sum = l1 + l2 + l3 + l4 + l5 + l6 + l7;
printf("%d\n", sum);
return 0;
}🌼五,[蓝桥杯2020初赛] 约数个数
P1514 - [蓝桥杯2020初赛] 约数个数 - New Online Judge (ecustacm.cn)
#include<iostream>
using namespace std;
int main()
{
int sum = 0;
for(int i = 1; i <= 1200000; ++i)
if(1200000 % i == 0) sum++;
cout<<sum;
return 0;
}
96到21年
🌼六,[蓝桥杯2021初赛] 卡片
P1550 - [蓝桥杯2021初赛] 卡片 - New Online Judge (ecustacm.cn)
初始化a[10]为2021，对应着0~9，int k = i; a[k % 10]--即可
但是有个问题，代码虽然输出了正确答案，但是提交时显示编译错误，原来是语言选了C
#include<iostream>
using namespace std;
int a[10];
int main()
{
for(int i = 0; i <= 9; ++i)
a[i] = 2021; //初始化
int flag = 0;
for(int i = 1;; ++i) { //从1开始遍历
int k = i;
while(k) {
a[k % 10]--;
k /= 10;
}
for(int j = 0; j <= 9; ++j)
if(a[j] < 0) {
cout<<i - 1;
flag = 1; //到头了
break;
}
if(flag) break;
}
return 0;
}3181🌼七，[蓝桥杯2021初赛] 直线
P1551 - [蓝桥杯2021初赛] 直线 - New Online Judge (ecustacm.cn)
注意,除了下标和计数的now,其他都声明为double
而且第一次看成斜率相同算同一条直线了...
如果只是判断多少种斜率,最简单的set即可
但这里斜率 + 截距才能确定一条直线
一开始...犯了个重名的小错误, 找了半小时 + 百度 才找出来...
set<pair<double, double>>b; //斜率k, 截距b
for(int i = 0; i < 420; ++i)
for(int j = 0; j < 420; ++j) {
if(a[i].x != a[j].x && a[i].y != a[j].y) {
double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
double b = a[i].y - k * a[i].x;
b.insert({k, b});
}
}报错error: request for member 'insert' in 'b', which is of non-class type 'double'
意思是, set变量名b和循环里面的double b重复了
修改后,第一次提交, 错了....(原因会在后面分析)
错误代码
#include<iostream>
#include<set> //set<>b;
using namespace std;
struct place
{
double x, y; //横纵坐标
};
int main()
{
struct place a[430];
int now = 0;
//读入420个点
for(double i = 0; i <= 19; ++i)
for(double j = 0; j <= 20; ++j) {
a[now].x = i;
a[now++].y = j;
}
//判断不同的直线
set<pair<double, double>>line; //斜率k, 截距b
for(int i = 0; i < 420; ++i)
for(int j = 0; j < 420; ++j) {
if(a[i].x != a[j].x && a[i].y != a[j].y) {
double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
double b = a[i].y - k * a[i].x;
line.insert({k, b});
}
}
cout<<line.size() + 20 + 21; //加上竖和横
return 0;
}48953而正确答案是40257
错误原因是double精度丢失
k那里没问题, 问题是b那里,解决方案是
b = y1 - (y2 - y1) / (x2 - x1) * x1 ----> b = (y1 * (x2 - x1) - (y2 - y1) * x1) / (x2 - x1)
猜测是先除再减,会丢失更多精度....
AC代码
当然,我用结构体写的有点乱了,意思就是这么个意思, y = kx + b, k = (y2 - y1) / (x2 - x1)
核心思路就是斜率和截距确定一条直线 + set排除重合元素 + pair
#include<iostream>
#include<set> //set<>b;
using namespace std;
struct place
{
double x, y; //横纵坐标
};
int main()
{
struct place a[430];
int now = 0;
//读入420个点
for(double i = 0; i <= 19; ++i)
for(double j = 0; j <= 20; ++j) {
a[now].x = i;
a[now++].y = j;
}
//判断不同的直线
set<pair<double, double>>line; //斜率k, 截距b
for(int i = 0; i < 420; ++i)
for(int j = 0; j < 420; ++j) {
if(a[i].x != a[j].x && a[i].y != a[j].y) { //排除横竖直线
double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
double b = (a[i].y * (a[i].x - a[j].x) -
(a[i].y - a[j].y) * a[i].x) / (a[i].x - a[j].x);
line.insert({k, b});
}
}
cout<<line.size() + 20 + 21; //加上竖和横
return 0;
}
40257🌼八,[蓝桥杯2021初赛] 货物摆放
P1552 - [蓝桥杯2021初赛] 货物摆放 - New Online Judge (ecustacm.cn)
虽然填空题不看复杂度,但是这么大的数,直接O(n^3)暴力肯定不行
容易发现,虽然是三个数,还是能用找因子的方法,用一个数组保存因子即可
因子用取余 == 0的方式判断
第一次敲完, 输出0.....然后一看int a[10000]里,单个数不能超过int,所以改long long就好了
#include<iostream>
#include<cmath> //sqrt()
using namespace std;
long long a[10010];
int main()
{
long long n = 2021041820210418, sum = 0, now = 0;
for(long long i = 1; i < sqrt(n); ++i)
if(n % i == 0) { //找出因子
a[now++] = i;
if(i * i != n) //判断另一个因子
a[now++] = n / i;
}
for(int i = 0; i < now; ++i)
for(int j = 0; j < now; ++j)
for(int k = 0; k < now; ++k)
if(a[i] * a[j] * a[k] == n) sum++;
cout<<sum;
return 0;
}
2430🌼九,[蓝桥杯2021初赛] 路径
P1553 - [蓝桥杯2021初赛] 路径 - New Online Judge (ecustacm.cn)
看到最短路, 正好前天刚学了Floyd-Warshall和Dijkstra , 盘它
不会的可以看看这个博客
(5条消息) 最短路之Floyd-Warshall（10张图解）_码龄11天的博客-CSDN博客
(2条消息) 最短路之Dijkstra（15张图解）_迪杰斯特拉算法求最短路径图解_码龄?天的博客-CSDN博客
1,floyd是求多源最短路的
而且Floyd和Dijkstra都适用于稠密图(本题显然是稠密图)
假设n个顶点, m条边
看到没,这个才是稠密图(m >= n^2)
而一般的10个顶点,20条边这种,都是稀疏图(m << n^2)
Floyd核心思路还是中转
2,将"路"读入二维数组e;
3,第三个我们借辗转相除法间接求出最小公倍数
第一次敲完,无论是顶点1到2021还是顶点1到100,输出都是1e8,肯定哪里错了
然后我对每一部分进行验算
1,求公倍数函数com()没问题
2,Floyd那里有问题
//利用中转求最短路
for(int k = 1; k <= 2021; ++k) //通过所有点中转
if(e[1][k] + e[k][2021] < e[1][2021])为什么这段代码会让每次都输出无穷值呢?
因为你误以为Floyd可以求单源最短路. 它必须先通过求出多源最短路,才能找到单源的答案
只能用n^3先算出所有点的最短路,才能求1到2021的最短路
🌳Floyd-Warshall
(本地AC, OJ上时间超限)
#include<iostream>
#include<cmath> //abs()
using namespace std;
int e[2050][2050];
int inf = 1e9; //infinity无穷
int com(int x, int y)
{
int a = x, b = y;
while(y) {
int z = x % y;
x = y;
y = z; //最后的x为公因数
}
return a * b / x; //最小公倍数
}
int main()
{
//初始化
for(int i = 1; i <= 2021; ++i)
for(int j = 1; j <= 2021; ++j) {
if(i == j) e[i][j] = 0; //自己到自己距离为0
else e[i][j] = inf;
}
//读入边的长度
for(int i = 1; i <= 2021; ++i)
for(int j = 1; j <= 2021; ++j) {
if(abs(i - j) <= 21 && i != j) {
e[i][j] = com(i, j);
e[j][i] = e[i][j]; //无向边
}
}
//利用中转求最短路(Floyd核心)
for(int k = 1; k <= 2021; ++k) //通过所有点中转
for(int i = 1; i <= 2021; ++i)
for(int j = 1; j <= 2021; ++j)
if(e[i][k] + e[k][j] < e[i][j])
e[i][j] = e[i][k] + e[k][j];
cout<<e[1][2021];
return 0;
}
等了10秒才出结果(不要提交这个,这个在本地算出答案,只提交答案即可)
10266837提交时,怕超时,所以直接printf()
AC代码
#include<iostream>
using namespace std;
int main()
{
cout<<10266837;
return 0;
}尽管时间复杂度达O(n^3), 大约是(2*10^3)^3 = 8e9, 也不是很大,毕竟顶点个数才2021个
所以填空题,一般建议暴力解决 + printf()
------------------------------------------------------------------
下面,我再用Dijkstra做下这题
Dijkstra的科普博客(6条消息) 最短路之Dijkstra（15张图解）_码龄11天的博客-CSDN博客
Dijkstra原理是贪心,而Floyd是动态规划
1,初始化数组
2,循环
(1)确定源点到最近点的最短路径
(2)从刚被确定的点"出边"
🌳Dijkstra AC
#include<iostream>
#include<cmath> //abs()
using namespace std;
int e[2050][2050], dis[2050], book[2050];
int inf = 1e9; //infinity无穷
int com(int x, int y)
{
int a = x, b = y;
while(y) {
int z = x % y;
x = y;
y = z; //最后的x为公因数
}
return a * b / x; //最小公倍数
}
int main()
{
//初始化
for(int i = 1; i <= 2021; ++i)
for(int j = 1; j <= 2021; ++j) {
if(i == j) e[i][j] = 0; //自己到自己距离为0
else e[i][j] = inf;
}
//读入边的长度
for(int i = 1; i <= 2021; ++i)
for(int j = 1; j <= 2021; ++j) {
if(abs(i - j) <= 21 && i != j) {
e[i][j] = com(i, j);
e[j][i] = e[i][j]; //无向边
}
}
//初始化book和dis数组
for(int i = 1; i <= 2021; ++i) {
book[i] = 0;
dis[i] = e[1][i];
}
//Dijkstra
for(int i = 1; i <= 2020; ++i) { //n - 1次确定最短路
int Min = inf;
int u;
//找确定值
for(int j = 2; j <= 2021; ++j) { //1为源点，从下一个开始
if(book[j] == 0 && dis[j] < Min) {
Min = dis[j];
u = j;
}
}
book[u] = 1; //源点1号到u号的距离确定为最短路程
//从刚确定的点出边
for(int k = 2; k <= 2021; ++k) {
//两点连通且可更新
if(e[u][k] < inf && dis[k] > dis[u] + e[u][k])
dis[k] = dis[u] + e[u][k];
}
}
cout<<dis[2021];
return 0;
}
10266837时间复杂度O(n^2),2021个点的数据量,直接提交也能过了
🌼十, [蓝桥杯2021初赛] 空间
P1555 - [蓝桥杯2021初赛] 空间 - New Online Judge (ecustacm.cn)
一个32位二进制整数 = 4B, 1KB = 1024B, 1MB = 1024KB
所以 256MB = 256 * 1024 * 1024 / 4 个32位二进制整数
#include<iostream>
using namespace std;
int main()
{
cout<<256 * 256 * 1024;
return 0;
}
到22年了
🌼十一,[蓝桥杯2022初赛] 裁纸刀
P2021 - [蓝桥杯2022初赛] 裁纸刀 - New Online Judge (ecustacm.cn)
🌼十二,[蓝桥杯2022初赛] 灭鼠先锋
P2022 - [蓝桥杯2022初赛] 灭鼠先锋 - New Online Judge (ecustacm.cn)
22年A组前两道填空题,放个以前的博客👇
(8条消息) 2022蓝桥杯省赛C++A组初尝试_码龄11天的博客-CSDN博客
🌼十三, [蓝桥杯2022初赛] 九进制转十进制
P2031 - [蓝桥杯2022初赛] 九进制转十进制 - New Online Judge (ecustacm.cn)
先让我们回忆下,十六进制转10怎么转的?
首先作为字符串输入 ,如果由0~9组成的十六进制数, 只需
if(s[i] >= '0' && s[i] <= '9')
sum += s[i] - '0';
......
sum *= 16;接下来有样学样就行,关键别人还给了确定的数
2022(9) = 2 * 9^0 + 2 * 9^1 + 0 * 9^2 + 2 * 9^3
#include<iostream>
using namespace std;
int main()
{
int sum = 2 * 1 + 2 * 9 + 0 + 2 * 9*9*9;
cout<<sum;
return 0;
}
粗心就会败北,第一次提交还写错个1,,,,真到蓝桥杯,一定要细心细心再细心
在草稿纸列清楚条条框框和细节,想尽可能多的, 特殊的样例
🌼十四, [蓝桥杯2022初赛] 顺子日期
P2032 - [蓝桥杯2022初赛] 顺子日期 - New Online Judge (ecustacm.cn)
一开始我以为是任意年份，，，写了一堆字符串验证
然后看到了2022
先梳理思路，2022肯定构不成顺子，如果最后一个2开始构成顺子，2，3，4，需要第34月
也不可能
细心细心再细心，不要想当然，老老实实列出所有情况
所以只能从月，日入手：
1，01月 + 20~29日（10种）
2，10月 + 12日（1种）
3，11月 + 23日（1种）
4，12月 + 30~31日 （2种）
10 + 1 + 1 + 2 = 14
#include<iostream>
using namespace std;
int main()
{
cout<<14;
return 0;
}
细心的人，高考能拿多50分；而粗心，足以使一个国二变成省二
🌼十五，[蓝桥杯2022初赛] 排列字母
P2041 - [蓝桥杯2022初赛] 排列字母 - New Online Judge (ecustacm.cn)
标签：入门题，模拟
按字符数组输入字符串，strlen()求字符数组字符串长度，sort()排序
#include<iostream>
#include<algorithm> //sort()
#include<cstring> //strlen()
using namespace std;
int main()
{
char s[20200] = "WHERETHEREISAWILLTHEREISAWAY";
sort(s, s + strlen(s));
cout<<s;
return 0;
}
AAAEEEEEEHHHIIILLRRRSSTTWWWY当然，这种填空题，自己直接排序，敲上去printf()也可
🌼十六，[蓝桥杯2019初赛]平方和
P1452 - [蓝桥杯2019初赛]平方和 - New Online Judge (ecustacm.cn)
#include<iostream>
typedef long long LL;
using namespace std;
bool check(LL n)
{
while(n) {
LL m = n % 10;
if(m == 0 || m == 1 || m == 2 || m == 9)
return true;
n /= 10;
}
return false;
}
int main()
{
LL sum = 0;
for(LL i = 1; i <= 2019; ++i) {
if(check(i))
sum += i * i;
}
cout<<sum;
return 0;
}
2658417853当然，最后提交时，我是这样提交的
#include <iostream>
using namespace std;
int main()
{
cout<<2658417853;
return 0;
}
🌼十七，[蓝桥杯2019初赛]数列求值
P1453 - [蓝桥杯2019初赛]数列求值 - New Online Judge (ecustacm.cn)
第一次，求出0115，做错了。。
错误代码
#include<iostream>
typedef long long LL;
using namespace std;
LL a[20200000];
int main()
{
a[1] = 1; a[2] = 1; a[3] = 1;
for(int i = 4; i <= 20190324; ++i) {
a[i] = a[i - 1] + a[i - 2] + a[i - 3];
}
cout<<a[20190324];
return 0;
}
5268603393216230115难道是超限了？应该是，考虑到题目说只需要最后四项，因为边取余边加不影响取余结果
所以我们在每一步加上取余10000
所以以后遇到，累乘或累加求最后几位数字的，每算一步取余一次
因为边加边取余，或者边乘边取余，结果不变
#include<iostream>
typedef long long LL;
using namespace std;
LL a[20200000];
int main()
{
a[1] = 1; a[2] = 1; a[3] = 1;
for(int i = 4; i <= 20190324; ++i) {
a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 10000; //注意这里
}
cout<<a[20190324];
return 0;
}
4659AC代码
#include <iostream>
using namespace std;
int main()
{
cout<<4659;
return 0;
}
🌼十八，[蓝桥杯2019初赛]最大降雨量
P1454 - [蓝桥杯2019初赛]最大降雨量 - New Online Judge (ecustacm.cn)
👊填空题总结
1，做了那么多2018，2019，2020，2021，2022的填空题，2023蓝桥杯省赛的填空题是什么呢，让我们猜猜看？和2023有关的前缀和或者字符串或者模拟？
2，显而易见，我从22年做到18年，基本上一年比一年简单。。。
如果说18，19，20年难度为6，21年难度为7，22年难度就为10（特指A组）
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
👊编程题
1，大题和填空题一样，最好自己弄多几组测试数据，否则大失所望就不好了
2，勿忘return 0;
🌼一，[蓝桥杯2022初赛] 刷题统计
P2033 - [蓝桥杯2022初赛] 刷题统计 - New Online Judge (ecustacm.cn)
标签：基础题，数学
为防止爆long long，我们采用减的方式
同时，为了避免粗心，我准备了8组数据来测试我的代码
10 20 99 --> 8 3 1 16 --> 6 3 1 19 --> 8 100 1 1 --> 1 1 100 6 --> 6 1 100 5 --> 5
8 10 99 --> 12 3 6 1200 --> 312
测试后没问题，提交。。。时间超限，AC 80%
时间超限 AC 80%
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int main()
{
long long n, a, b, i = 1;
scanf("%lld%lld%lld", &a, &b, &n);
while(n > 0) {
if(i % 7 > 0 && i % 7 < 6)
n -= a;
if(i % 7 == 0 || i % 7 == 6)
n -= b;
i++;
}
cout<<i - 1;
return 0;
}
显然，我们得化简代码
先得到刷题的周数
#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int main()
{
long long n, a, b, i = 1;
scanf("%lld%lld%lld", &a, &b, &n);
long long k = 5 * a + 2 * b; //一周刷题量
long long t = n / k; //多少周
n -= t * k;
while(n > 0) {
if(i % 7 > 0 && i % 7 < 6)
n -= a;
if(i % 7 == 0 || i % 7 == 6)
n -= b;
i++;
}
cout<<i - 1 + t * 7;
return 0;
}注意，最后的 * 7不要忘了，，记得测试
🌼二，1518: [蓝桥杯2020初赛] 回文日期
👂 形容 - 沈以诚 - 单曲 - 网易云音乐
P1518 - [蓝桥杯2020初赛] 回文日期 - New Online Judge (ecustacm.cn)
这题的难点在于，如何优化遍历过程，你从10000101遍历到89991231肯定超时
🌳暴力 AC 20% Time Lmit
对10000000~89991231遍历一次，考虑到两个check函数里的循环，运行次数 > 10^8
不知道是算力不够还是什么原因，2121年后的“ABABBABA”型日期输出不了
#include<iostream>
using namespace std;
int m[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int x) //判断日期合法 + 回文
{
m[1] = 28;
int yy = x/10000, mm = x/100%100, dd = x%100; //年月日
int y = x, s = 0;
while(y) {
s *= 10;
s += y % 10;
y /= 10;
}
if(s == x) //回文
if(mm >= 1 && mm <= 12 && dd >= 1 && dd <= m[mm - 1]) //合法
return true;
return false;
}
bool check2(int x) //判断ABABBABA
{
int yy = x/10000, mm = x/100%100, dd = x%100; //年月日
int aa = dd % 10, bb = dd / 10;
if(aa && bb && yy == aa*1010+bb*101 && mm == bb*10+aa) //ABABBABA
return true;
return false;
}
int main()
{
int t, test;
cin>>t;
while(t) {
t--;
cin>>test;
int yy = test / 10000, mm = test/100%100, dd = test%100;
for(int i = test + 1; i <= 89991231; ++i)
if(check(i)) {//输出回文串
cout<<i<<endl;
break;
}
for(int i = test + 1; i <= 89991231; ++i)
if(check(i) && check2(i)) {
cout<<i<<endl;
break; //先注释,输出所有千年两遇的情况,再降低复杂度
}
}
return 0;
}🌳AC 100%
遍历的优化方法
我也是从网上学来的哈（自己真的好弱）
回文串：
咱只需遍历1000~8999(年份)，然后a = 年份, b = 年份
接着for(int j = 0; j < 4; ++j) a = a * 10 + b % 10, b /= 10;
a 最后的结果就是4位数年份开头的回文日期（妙啊）
ABABBABA：
考虑到ABABBABA的形式，我们可以用两层for循环遍历 a和b 从1到9，最大也就81次
令 date = a*10100101 + b*1011010; （符合ABABBABA形式）
然而！！！
不得不说，我的问题很多
总结下通过率10%的原因
1，读题目不细心
题目说评测用例达89991231，但是输入这个数据的话，会输出：
90011009
90900909所以你得遍历到9091年
2，小bug
可能是OJ网测试数据的小Bug，如果允许AAAAAAAA的情况，才能AC100%
也就是不要加 if(a != b)的判断
AC 代码
这里是多组输入，和蓝桥杯官网不一样
#include<iostream>
using namespace std;
int m[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
int date;
bool check(int x) //判断日期合法
{
int yy = x/10000, mm = x/100%100, dd = x%100; //年月日
m[1] = 28;
if(yy % 400 == 0 || (yy % 100 != 0 && yy % 4 == 0))
m[1] = 29;
if(mm >= 1 && mm <= 12 && dd >= 1 && dd <= m[mm - 1]) //合法
return true;
return false;
}
int main()
{
int t, test;
cin>>t;
while(t) {
t--;
cin>>test;
int date;
//输出回文
for(int i = test/1e4; i <= 9999; ++i) { //年份
int ii = i, jj = i;
for(int j = 0; j < 4; ++j) {
ii = ii * 10 + jj % 10;
jj /= 10;
} //ii为某个年份开头唯一确定的回文串
if(check(ii) && ii > test) {
cout<<ii<<endl;
break;
}
}
//输出ABABBABA
int flag = 0;
for(int a = test/1e7; a <= 9; ++a) { //a为最高位
for(int b = 0; b <= 9; ++b) {//b从0开始
date = a*10100101 + b*1011010; //ABABBABA
if(date > test && check(date)) { //还要判断合法
cout<<date<<endl;
flag = 1;
break;
}
}
if(flag) break;
}
}
return 0;
}
