建网站需要哪些步骤,开元棋牌网站怎么做,深圳营销网站建设模板,求好用的seo软件别忘了请点个赞收藏关注支持一下博主喵#xff01;#xff01;#xff01;
关注博主#xff0c;更多蓝桥杯nice题目静待更新:)
枚举与模拟 一、卡片#xff1a; 【问题描述】 小蓝有很多数字卡片#xff0c;每张卡片上都是一个数字#xff08;0到9#xff09;。 小蓝…别忘了请点个赞收藏关注支持一下博主喵
关注博主更多蓝桥杯nice题目静待更新:)
枚举与模拟 一、卡片 【问题描述】 小蓝有很多数字卡片每张卡片上都是一个数字0到9。 小蓝准备用这些卡片来拼一些数他想从1开始拼出正整数每拼一个就保存起来卡片就 不能用来拼其他数。 想知道自己能从1拼到多少。 例如当小蓝有30张卡片其中0到9各3张则小蓝可以拼出1到10但是拼 11时卡片1已经只有一张了不够拼出11。 现在小蓝手里有0到9的卡片各2021张共20210张请问小蓝可以从1拼到 多少? 提示建议使用计算机编程解决问题。
【答案提交】 这是一道结果填空题你只需要算出结果后提交即可。本题的结果作为一个整数在 提交答案时只填写这个整数填写多余的内容将无法得分
解析 本题思路较为简单可直接从数字1开始往后枚举枚举的同时检查剩下的卡片能不能拼出当前枚举到的数字即可。 定义cnt[i] 表示刻有数字i的卡片张数。那么按照题目的意思初始化cnt[0∼9]2021 参考代码如下。
int cnt[10];
for(int i 0 ; i 9 ; i) cnt[i] 2021;
若我们将步骤拆分为两步则可分为枚举、检查。枚举没什么问题写个循环即可但 该怎么检查呢? 首先就需要把一个数在十进制下的每一位数字求出来。怎么求呢? 可以将该数对 10 取 模这样就得到了个位上的数字再除以10这样原本十位上的数字就跑到了个位上然后 再对10取模……反复这个过程就可以得到这个数在十进制下所有数位上的数字了。 得到数位上的所有数字后再看看这些数字对应的卡片够不够不够的话就说明这个数拼 不了就停止枚举这样答案就为上一个枚举的数。
bool check(int x) { // x 表示当前枚举的数while (x) {int b x % 10; // 获取十进制下的每个数位if (cnt[b] 0) cnt[b]--; // 这个数位对应的卡片个数 -1else return false; // 如果卡片不够了则无法拼凑出该数x / 10; // 将十位变为个位}return true;
}
至此检查的模块就完成了。不过我们还可以进行一点小小的优化。 我们的枚举是从1开始的如果分别看枚举数的个位、十位……上的数字那么会得到 如下的内容。 显然个、十、百、千、万……每一数位的变化都是有周期性的。每个周期中各个数字出 现的次数都是相同的且每一数位都是从1开始变化的。因此刻有数字1的卡片一定会被 最早使用完我们只需要对该卡片的张数作判断就好具体代码可见参考代码第4∼14行。
#include bits/stdc.h
using namespace std;int cnt[10];bool check(int x) { // x 表示当前枚举的数while (x) {int b x % 10; // 获取十进制下的每个数位if (b 1) {if (cnt[1] 0) return false;cnt[1]--;}x / 10; // 将十位变为个位}return true;
}signed main() {for (int i 0; i 9; i) cnt[i] 2021;for (int i 1;; i) {if (!check(i)) return cout i - 1 \n, 0;}return 0;
}
最终答案为3181。
二、回文日期 【问题描述】 2020年春节期间有一个特殊的日期引起了大家的注意2020年2月2日。因为 如果将这个日期按“yyyymmdd”的格式写成一个8位数是20200202恰好是一个回文数。我们称这样的日期是回文日期。 有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同因为不到2年 之后就是下一个回文日期20211202即2021年12月2日。 也有人表示20200202并不仅仅是一个回文日期还是一个ABABBABA型的回文 日期。对此小明也不认同因为大约100年后就能遇到下一个ABABBABA型的回文日 期21211212即2121年12月12日。算不上“千年一遇”顶多算“千年两遇”。 给定一个8位数的日期请你计算该日期之后下一个回文日期和下一个ABAB BABA型的回文日期各是哪一天。
【输入格式】 输入包含一个八位整数N表示日期。 对于所有评测用例10000101⩽N⩽89991231保证N是一个合法日期的8位数表示。
【输出格式】 输出两行每行1个八位数。第一行表示下一个回文日期第二行表示下一个ABAB BABA型的回文日期。
【样例输入】 20200202
【样例输出】 20211202 21211212
【答案提交】 这是一道结果填空题你只需要算出结果后提交即可。本题的结果作为一个整数在 提交答案时只填写这个整数填写多余的内容将无法得分。
解析 根据题意我们可以将题目拆解为如何判断回文和如何枚举日期两个部分来解决。 1. 如何判断回文 对于一个8位数的整型日期可以通过除法和取余运算来获取它的每一位数字。比如
若整数date 的值为20050511它从高到低的每一数位上的数可以通过下列方法得到。
• data / 10000000 2
• data / 1000000 % 10 0
• data / 100000 % 10 0
• data / 10000 % 10 5
• data / 1000 % 10 0
• data / 100 % 10 5
• data / 10 % 10 1
• data % 10 1。
对于本题若用a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]、a[8] 分别存储每一位则一个 回文日期须满足: 一个ABABBABA 型回文日期须满足以下条件。
a[1] a[3] a[6] a[8]a[2] a[4] a[5] a[7]. 对于一个日期字符串可以直接通过下标来获取它的每一位数字。例如string date “20050511”它从高到低的每一位分别可以通过data[0],data[1],...,data[7] 得到。判断回文日期及ABABBABA型回文日期的方式和上述方法类似。 不难看出字符串获取日期的每一位数字是要比整型简单的所以在判断回文日期及 ABABBABA 型回文日期时可以将整型转换为字符串来操作如参考代码所示。
#include bits/stdc.h
using namespace std;int date 20050511;
string s to_string(date); // 将整型转换为字符串, s 20050511// 判断回文日期
bool check1(int date) {string s to_string(date);if (s[0] s[7] s[1] s[6] s[2] s[5] s[3] s[4])return true;return false;
}// 判断 ABABBABA 型回文日期
bool check2(int date) {string s to_string(date);if (s[0] s[2] s[0] s[5] s[0] s[7] s[1] s[3] s[1] s[4] s[1] s[6])return true;return false;
} 2. 如何枚举日期 对于一个整型日期可以用最简单的方式枚举即令该日期不断1直到出现满足ABAB BABA 型的回文日期。 但这样存在一个问题会枚举出许多不合法的日期如20209999。为此我们需要对 日期进行合法性判断设y,m,d分别表示年、月、日month[i]表示第i个月的天数那么当m12或dmonth[m]时日期不合法反之日期合法如参考代码所示。
#include iostream
#include string
using namespace std;int month[13] {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check(int date) {string s to_string(date);//stoi-将字符串转为整型int y stoi(s.substr(0, 4)), m stoi(s.substr(4, 2)), d stoi(s.substr(6, 2));if (y % 400 0 || (y % 4 0 y % 100 ! 0)) month[2] 29;else month[2] 28;if (m 1 || m 12 || d 1 || d month[m]) return false;return true;
}int main() {int date 20050511;for (int i date 1;; i) {if (!check(i)) continue;// 找到下一个有效日期后可以在这里进行进一步处理// 例如检查是否是回文日期或 ABABBABA 型回文日期cout Next valid date: i endl;break;}return 0;
}
不过这样的枚举量是相当大的要在比赛中完成本题要求的所有测试数据不太现实。 那么还有什么枚举方法呢? 可以直接枚举合法日期。枚举合法日期只需模拟日期的变化规律即可对应参考代码如 下所示。
#include iostream
using namespace std;int month[13] {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main() {int date 20050511;int y date / 10000, m date / 100 % 100, d date % 100;for (int i y;; i) {if (i % 400 0 || (i % 100 ! 0 i % 4 0)) month[2] 29; // 闰年2月有29天else month[2] 28;int j (i y) ? m : 1; // 如果是i y则月份从m开始枚举否则从1开始枚举for (; j 12; j) {int k (i y j m) ? d : 1; // 如果i y并且j m则日从d开始枚举否则从1开始枚举for (; k month[j]; k) {int new_date i * 10000 j * 100 k;// 在这里可以进行进一步处理例如检查是否是回文日期或ABABBABA型回文日期cout Next valid date: new_date endl;return 0; // 找到第一个有效日期后退出程序}}}return 0;
} 综上
枚举合法日期 #include bits/stdc.h
using namespace std;int month[13] {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int date, ans1, ans2;// 判断日期是否为回文
bool check1(int date) {string s to_string(date);if (s[0] s[7] s[1] s[6] s[2] s[5] s[3] s[4])return true;return false;
}// 判断日期是否满足 ABABBABA 型回文
bool check2(int date) {string s to_string(date);if (s[0] s[2] s[0] s[5] s[0] s[7] s[1] s[3] s[1] s[4] s[1] s[6])return true;return false;
}signed main() {cin date;int y date / 10000, m date / 100 % 100, d date % 100;for (int i y;; i) {if (i % 400 0 || (i % 100 ! 0 i % 4 0))month[2] 29;elsemonth[2] 28;int j (i y) ? m : 1;for (; j 12; j) {int k (i y j m) ? d 1 : 1;for (; k month[j]; k) {int new_date i * 10000 j * 100 k;if (check1(new_date) ans1 0)ans1 new_date;if (check2(new_date)) {cout ans1 \n new_date \n;return 0; // 当找到了 ABABBABA 型回文日期时结束程序}}}}return 0;
}
枚举年份
#include bits/stdc.h
using namespace std;// month[1~12]分别记录1~12月每月的天数
int date, month[13] {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 判断日期是否合法
string check(int date) {string s to_string(date), t to_string(date); // 将整型转换为字符串reverse(t.begin(), t.end()); // 翻转s t; // 将s翻转后再与s拼接拼接后的字符串一定会是个回文串int y stoi(s.substr(0, 4)), m stoi(s.substr(4, 2)), d stoi(s.substr(6, 2));if (y % 400 0 || (y % 4 0 y % 100 ! 0)) month[2] 29;else month[2] 28;if (m 1 || m 12 || d 1 || d month[m]) return -1;return s;
}// 判断日期是否是ABABBABA型回文
string check2(int date) {string s to_string(date), t to_string(date);reverse(t.begin(), t.end()); // 翻转s t;if (s[0] s[2] s[0] s[5] s[0] s[7] s[1] s[3] s[1] s[4] s[1] s[6]) return s;return -1;
}signed main() {cin date;string ans1 ;for (int i date / 10000;; i) {// 注意date输入的日期不能作为答案if (check(i) -1 || check(i) to_string(date)) continue;if (ans1 ) ans1 check(i);if (check2(i) ! -1) {cout ans1 \n check2(i) \n;return 0;}}return 0;
}
以上就是这次博客的内容了
别忘了请点个赞收藏关注支持一下博主喵
关注博主更多蓝桥杯nice题目静待更新:)
