藍橋杯第十一屆省賽C++B組真題解析
八、回文日期https://www.lanqiao.cn/problems/348/learning
方法一：暴力枚舉所有的日期，記錄有多少個回文日期。
#include <bits/stdc++.h>
using namespace std;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int s[9];
bool find(int year){if(year%400==0||(year%4==0&&year%100!=0)) return true;else return false;
}
bool tell(int s1[]){bool flag = true;for(int i=0; i<8; i++){if(s1[i] != s1[7-i]){flag = false;break;}}return flag;
}
void transform(int num, int kk){if(kk==1){s[0] = num/1000;s[1] = num/100%10;s[2] = num/10%10;s[3] = num%10;}else if(kk==2){if(num<10) s[4] = 0;else s[4] = num/10 ;s[5] = num%10 ;}else if(kk==3){if(num<10) s[6] = 0;else s[6] = num/10 ;s[7] = num%10;}
}int main()
{int ans=0;long long day1,day2;cin >> day1 >> day2;int y1 = day1/10000,y2=day2/10000;int m1 = day1%10000/100,m2=day2%10000/100;int d1 = day1%100,d2 = day2%100;if(y2>y1){
//特判第一年 transform(y1,1);if(find(y1)) month[2] = 29;for(int i=m1; i<13; i++){transform(i,2);int j=1;if(i==m1) j = d1;for(; j<=month[i]; j++){transform(j,3);if(tell(s)) ans++;}}
//特判最后一年transform(y2,1);if(find(y2)) month[2] = 29;for(int i=1; i<=m2; i++){transform(i,2);for(int j=1; j<=month[i]; j++){if(i == m2 && j>d2) break;transform(j,3);if(tell(s)) ans++;}}
}else{transform(y2,1);if(find(y2)) month[2] = 29;for(int i=m1; i<=m2; i++){transform(i,2);int j=1;if(i==m1) j = d1;for(; j<=month[i]; j++){if(i == m2 && j>d2) break;transform(j,3);if(tell(s)) ans++;}}
}for(int i=y1+1;i<y2;i++){if(find(i)) month[2] =29;else month[2] = 28;transform(i,1);for(int j=1; j<13; j++){transform(j,2);for(int k=1; k<=month[j]; k++){transform(k,3);if(tell(s)) ans++;}}}cout << ans;return 0;
}
方法二：用月份和日枚舉所有的回文日期，判斷是否在有效日期內。
??不用特判閏年，因為二月份反轉的年份為20，一定為閏年.
#include<bits/stdc++.h>
using namespace std;
//預處理月份對應天數
int a[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main(){int n,m;cin>>n>>m;int ans=0;
//根據月份和天數直接構造回文年份，看是是否在題目要求范圍內for(int i=1;i<=12;i++){for(int j=1;j<=a[i];j++){
//年份int y=j%10*1000+(j/10)*100+i%10*10+i/10;
//年份+月份+天數組成的回文串int sum=y*10000+i*100+j;if(sum>m||sum<n) continue;else ans++;}}cout<<ans;return 0;
}
九、子串分值和https://www.lanqiao.cn/problems/1037/learning/
方法一：遍歷+哈希表
#include <bits/stdc++.h>
using namespace std;
string s;int main()
{cin >> s;int cnt=0;for(int i=0; i<s.size(); i++){unordered_map<char,int> m;m[s[i]]++;for(int j=i; j<s.size(); j++){m[s[j]]++;cnt += m.size();}}cout << cnt;return 0;
}
方法二：
??核心觀察??：
每個字符 s[i] 在某個子字符串中第一次出現時，會為該子字符串的不同字符數 貢獻1。統計所有這樣的貢獻次數。
??實現方法??：
使用數組 last[26] 記錄每個字母上一次出現的位置。
對于每個字符 s[i]，計算它能在多少個子字符串中作為第一次出現的該字符。
#include <bits/stdc++.h>
using namespace std;
string s;
int o_last[26];//記錄26個字母上一次出現的位置int main()
{cin >> s;long long cnt=0;int l = s.size();memset(o_last, -1, sizeof(o_last)); for(int i=0; i<l; i++){int last = o_last[s[i]-'a'];cnt += (long long)(l-i)*(i-last);//前一段乘后一段o_last[s[i]-'a'] = i;//更新s[i]最新出現的位置}cout << cnt;return 0;
}
)
