本期主要讲解模拟、枚举算法。
例题
T1
简单模拟题。
利用 scanf/cin 以 int 形式读入分和秒，并令秒循环累加，逢 \(60\) 归 \(0\) 并向分进 \(1\)，分则是逢 \(24\) 归 \(0\)。
在循环的过程中若分秒合起来是回文数字，则退出循环，按照题目格式输出当前时间。
注意开始时间不算。
#include<bits/stdc++.h>
using namespace std;
int main(){
int h,m; char c;
cin>>h>>c>>m;
while(1){
m++;
if(m==60) m=0,h++;
if(h==24) h=0;
if(h/10==m%10&&h%10==m/10) break;
}
if(h<10) cout<<0; cout<<h<<':';
if(m<10) cout<<0; cout<<m;
}
T2
将这个八位数按字符串读入，然后分离出年、月、日。
接着按照上一题的方法，将日期不断累加，这里可以打一个表记录每月天数，当日期大于此月天数就归 \(0\) 并向月份进 \(1\)，需要特判二月；月份是逢 \(12\) 归 \(0\) 并向年份进 \(1\)，年份则不用进位。
在循环过程中，若当前年月日为回文数，则输出当前年月日，此时不可 break；若当前年份 \(1,2\) 位和 \(3,4\) 位相同，且 \(1\)、\(2\) 位不同（即当前年月日为 ABABBABA 形式），则输出当前年月日并退出循环。输出时仍按上一题的格式来。
#include<bits/stdc++.h>
using namespace std;
int y,m,d;
int cnt;
int day[]={-1,31,-1,31,30,31,30,31,31,30,31,30,31};
string s;
int main(){
cin>>s;
y=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0');
m=(s[4]-'0')*10+(s[5]-'0');
d=(s[6]-'0')*10+(s[7]-'0');
while(1){
d++;
if(m==2){
if(y%4==0&&y%100!=0||y%400==0) day[2]=29;
else day[2]=28;
}
if(d>day[m]) m++,d=0;
if(m>12) m=0,y++;
if(y/1000==d%10&&y/100%10==d/10&&y/10%10==m%10&&y%10==m/10){
if(cnt==0){
cout<<y;
if(m<10) cout<<0; cout<<m;
if(d<10) cout<<0; cout<<d;
cout<<'\n';
cnt++;
}
if(cnt==1){
int a=y/100,b=y%100;
if(a==b&&a/10!=a%10){
cout<<y;
if(m<10) cout<<0; cout<<m;
if(d<10) cout<<0; cout<<d;
cout<<'\n';
break;
}
}
}
}
return 0;
}
另：我们老师的思路是按 int 整型读入 \(n\)，并不断累加 \(n\)，若它是合法日期且是回文数 / ABABBABA 形式，则输出。
T3
典题。
从 \(date_1\) 循环至 \(date_2\)，依次检查是否为合法日期且为回文日期，若是则输出。
#include<bits/stdc++.h>
using namespace std;
int d1,d2,ans;
int day[]={-1,31,-1,31,30,31,30,31,31,30,31,30,31};
bool isdate(int x){
int m=x/100%100,d=x%100;
if(m==2){
int y=x/10000;
if(y%4==0&&y%100!=0||y%400==0) day[m]=29;
else day[m]=28;
}
return m>=1&&m<=12&&d>=1&&d<=day[m];
}
bool check(int x){
int y=0,tmp=x;
while(tmp){
y=y*10+tmp%10;
tmp/=10;
}
return x==y;
}
int main(){
cin>>d1>>d2;
for(int i=d1;i<=d2;i++)
if(isdate(i)&&check(i)) ans++;
cout<<ans;
return 0;
}
T4
虽然上课没讲，但还是说一下。
其实只需要写一个进制转换函数，对 \([1,300]\) 的数依次进行转换，并判断它们是否为回文数即可。
#include<bits/stdc++.h>
using namespace std;
int b;
bool check(string s){
string x; int l=s.length();
for(int i=l-1;i>=0;i--) x+=s[i];
for(int i=0;i<l;i++)
if(s[i]!=x[i]) return false;
return true;
}
string trans(int x){
string s="",ss="";
while(x){
if(x%b>9) s+=(char)(x%b-10+'A');
else s+=(char)(x%b+'0');
x/=b;
}
int l=s.length();
for(int i=l-1;i>=0;i--) ss+=s[i];
return ss;
}
int main(){
cin>>b;
for(int i=1;i<=300;i++)
if(check(trans(i*i))) cout<<trans(i)<<' '<<trans(i*i)<<'\n';
return 0;
}
习题
T5
首先筛出 \(2 \sim n\) 中的所有质数，因为 \(n\) 范围很小，所以连试除法都可以过。我使用的是埃氏筛，老师说可以从 \(i \times i\) 开始标记。
接着 \(O(n^2)\) 地枚举一对质数 \(p_i\) 与 \(p_j\)，若 \(p_i = p_j + p_{j - 1} + 1\)，则令计数器 \(cnt \gets cnt + 1\)。需要注意，若你和我的判断式子一样，则 \(j\) 需要从 \(2\) 开始。
最后，若 \(cnt \ge k\)，则输出 YES，反之输出 NO。
#include<bits/stdc++.h>
using namespace std;
int n,k,tot,ans;
bool f[1031];
int p[1031];
void Esh(){
for(int i=2;i<=n;i++){
if(!f[i]){
p[++tot]=i;
for(int j=i*i;j<=n;j+=i) f[j]=true;
}
}
}
int main(){
cin>>n>>k;
Esh();
for(int i=1;i<=tot;i++)
for(int j=2;j<i;j++)
if(p[i]==p[j]+p[j-1]+1)
ans++;
cout<<(ans>=k?"YES":"NO");
return 0;
}
T6
字符串题。
读入四行字符串，统计每个字母出现的次数，存入 \(ch\) 数组，记次数最多的字母出现的次数为 \(x\)。
从 \(x\) 循环至 \(1\)，遍历 \(ch\) 数组，若当前字母的出现次数 \(\ge\) 行数，则输出 * \(+\) 一个空格，是最后一行则输出 *；若当前字母出现 \(0\) 次，则输出两个空格，是最后一行则输出一个空格。
在最后一行下方需要输出 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z。
#include<bits/stdc++.h>
using namespace std;
string t;
int ch[31],x;
int main(){
getline(cin,t); for(int i=0;t[i];i++) if(isupper(t[i])) ch[t[i]-'A'+1]++;
getline(cin,t); for(int i=0;t[i];i++) if(isupper(t[i])) ch[t[i]-'A'+1]++;
getline(cin,t); for(int i=0;t[i];i++) if(isupper(t[i])) ch[t[i]-'A'+1]++;
getline(cin,t); for(int i=0;t[i];i++) if(isupper(t[i])) ch[t[i]-'A'+1]++;
for(int i=1;i<=26;i++) x=max(x,ch[i]);
for(int i=x;i>=1;i--){
for(int j=1;j<=26;j++){
if(ch[j]>=i){
if(j<26) cout<<"* ";
else cout<<"*";
}
else{
if(j<26) cout<<" ";
else cout<<" ";
}
}
cout<<"\n";
}
cout<<"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z";
return 0;
}