2020 c/c++ 第二场蓝桥杯B组
2020 c/c++ 第二场蓝桥杯B组
回文日期
时间限制: 1Sec 内存限制: 128MB
题目描述
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202，
恰好是一个回文数。我们称这样的日期是回文日期。
有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202 即2021年12月2日。
也有人表示20200202 并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。
给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。
输入
输入包含一个八位整数N，表示日期。
输出
输出两行，每行1 个八位数。第一行表示下一个回文日期，第二行表示下
一个ABABBABA 型的回文日期。
样例输入复制
20200202
样例输出复制
20211202
21211212
提示
对于所有评测用例，10000101 ≤ N ≤ 89991231，保证N 是一个合法日期的8位数表示。
题解代码
#include
using namespace std;int A[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};//平年闰年表
char str[9];
int res[9]; int main(){cin>>str;//日期int year=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');//转年份int moth=(str[4]-'0')*10+(str[5]-'0');//转月份int day=(str[6]-'0')*10+(str[7]-'0');//转日期int k1=0,k2=0;//k1判定是否是回文日期，k2判定是否符合ABABBABA格式while(1){//循环查找day++;//日期格式判定if((year%4==0&&year%100!=0) || year%400==0){//闰年判定if(day>A[1][moth]) moth++,day=0;}else{if(day>A[0][moth]) moth++,day=0;//平年判定}if(moth>12) year++,moth=0;//月份判定//年份转格式res[0]=year/1000;res[1]=year%1000/100;res[2]=year%1000%100/10;res[3]=year%1000%100%10;//月份转格式res[4]=moth/10;res[5]=moth%10;//日期转格式res[6]=day/10;res[7]=day%10;//回文判定if(res[0]==res[7] && res[1]==res[6] &&res[2]==res[5]&& res[3]==res[4]){if(k1<1){//找到第一个回文日期k1++;for(int i=0;i<8;i++) cout< 子串分值和
时间限制: 1Sec 内存限制: 128MB
题目描述
对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 2，f (”abc”) = 3, f (”aaa”) = 1。
现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。
输入
输入一行包含一个由小写字母组成的字符串 S。
输出
输出一个整数表示答案。
样例输入复制
ababc
样例输出复制
28
提示
子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3b 1ba 2bab 2babc 3a 1ab 2abc 3b 1bc 2c 1
题解代码
第一版代码 暴力
#include
using namespace std;
const int N=1e3+10;
int str[N];
int len=0;
int res=0;//暴力解法
//时间复杂度为O(n*n*n) 只能过少部分样例
int main(){int c;int s[N];while((c=getchar())!='\n'){str[len]=c;len++;}
// cout< 第二版代码 dp+前缀和 O(n*n)
#include
using namespace std;const int N=1e7+10;
int dp[N];
string str;
int len=0;
long long res=0;
int s[26];//s代表每个字母出现次数//dp[i][j]代表从i到j区间内的字符串 存储数据为子串值
//void initdp(){
//二维dp 空间上只能支持1e3的数据 时间复杂度为O（n*n）
//定义左端点
// for(int j=0;j";
//调试代码**********}// res+=dp[j][m];
// }
//调试代码**********{
// cout<<" "<";res+=dp[m];}
// cout<<" "<>str;len=str.size();initdp2();cout< 第三版代码 全样例通过 O(n) 贡献度计算
这里的贡献度是一种与位置相关的函数
通过求每个字符对数列的贡献度来解决问题，比如对于字符串ababc，第一个字符a的贡献度为5，因为它在五个字符串中出现了；而对于第二个a它一共在6个字符串中出现，所以它的贡献度为6.每个字符的贡献度都是等于该字符距离上一个和它一样的字符之间的个数乘以它到字符串末尾的个数。
子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3b 1ba 2bab 2babc 3a 1ab 2abc 3b 1bc 2c 1
比如第二个a的贡献度=（2-0）*3=6；
这五个字符每个字符的贡献度分别为：
a: 5//因为它是第一个所以贡献度就是字符串的长度
b: 2*4=8//因为在它之前没有b
a:（2-0）*3=6
b: (3-1)*2=4;
c: 5*1=5;
所以正好加起来等于28；
#includeusing namespace std;
typedef long long ll;int main(){//贡献度算法 用公式计算 时间复杂度为O(n)//全样例通过 string s;cin>>s;ll res=0;int po[26];//存放上次字母出现位置fill(po,po+26,-1);//慎用memsetpo[s[0]-'a']=0;//把第一个元素出现位置初始化res+=int(s.size());//第一个元素的贡献的一定为字符串长度for(int i=0;i 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！