1.天干地支
古代中国使用天干地支来记录当前的年份。
天干一共有十个，分别为：
甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。
地支一共有十二个，分别为：
子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、 亥（hài）。
将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。
20202020 年是庚子年。
每过一年，天干和地支都会移动到下一个。例如 20212021 年是辛丑年。
每过 6060 年，天干会循环 66 轮，地支会循环 55 轮，所以天干地支纪年每 6060 年轮回一次。例如 19001900 年，19601960 年，20202020 年都是庚子年。给定一个公元纪年的年份，请输出这一年的天干地支年份。
输入描述
输入一行包含一个正整数，表示公元年份。
其中有 ，输入的公元年份为不超过 99999999 的正整数。
输出描述
输入一行包含一个正整数，表示公元年份。
#include <iostream>
using namespace std;
string tg[10]={"jia","yi","bing","ding","wu","ji","geng","xin","ren","gui"};
string dz[12]={"zi","chou","yin","mao","chen","si","wu","wei","shen","you","xu","hai"};
int main()
{
int year;
cin>>year;
int start=2020;
while(year<start){
start-=60;
}
int dis=year-start;
cout<<tg[(dis+6)%10]<<dz[dis%12];
return 0;
}
2.包子凑数
#include <iostream>
using namespace std;
const int N=110;
const int M=1e5+10;
int a[N];
//最大公约数>1时，有无穷个不能组合出来的数
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool dp[N][M];//
int main(){
int n,ans=0;
//long long maxnum=1;//最大不能组合出来的数字 可以用来限定范围，但三位数及以上的裴蜀定理公式不知
int gc;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i==1)gc=a[1];
else gc=gcd(gc,a[i]);
}
if(gc>1){
printf("INF");
}else{
for(int i=0;i<=n;i++){
dp[i][0]=true;
}
//完全背包
// for(int i=1;i<=n;i++){
// for(int j=0;j<maxnum;j++){
// for(int k=0;k*a[i]<=j;k++){
// if(dp[i-1][j-k*a[i]])dp[i][j]=true;
// //printf("dp%d,%d=%d\n",i,j,dp[i][j]);
// }
// }
// }
//前面的写法超时了，进行优化
for(int i=1;i<=n;i++){
for(int j=0;j<M;j++){
if(dp[i-1][j]||(j>=a[i]&&dp[i][j-a[i]]))dp[i][j]=true;
//printf("dp%d,%d=%d\n",i,j,dp[i][j]);
}
}
for(int i=1;i<M;i++){
if(!dp[n][i])ans++;
}
printf("%d",ans);
}
return 0;
}
3.求值
#include <iostream>
using namespace std;
// bool check(int num){
// int w=0;
// for(int i=1;i<=num;i++){
// if(num%i==0)w++;
// }
// return w==100;
// }
int main()
{
// long long ans;
// for(long long i=1000;;i++){
// if(check(i)){
// ans=i;
// break;
// }
// }
//printf("%lld",ans);
cout<<45360;
return 0;
}
4.青蛙跳杯子
类似的题有：八数码问题 卡牌换位
最少跳数->bfs
涉及
- 状态表示
- 状态处理（出队，入队） （广搜过程记得恢复状态）
- 对遍历过的状态进行标记（防止死循环）
蓝桥unordered_map用map替代
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
int f[6]={-3,-2,-1,1,2,3};
string s1,s2;
int n;
queue<string>q;
map<string,int>dis;
int bfs(){
q.push(s1);
dis[s1]=0;
while(q.size()){
string t=q.front();
q.pop();
int d=dis[t];
int index=t.find("*");
for(int i=0;i<6;i++){
int next=f[i]+index;
if(next>=0&&next<n){
swap(t[next],t[index]);
if(!dis.count(t)){
dis[t]=d+1;
if(t==s2)return dis[t];
q.push(t);
}
swap(t[next],t[index]);
}
}
}
return -1;
}
int main(){
cin>>s1;
cin>>s2;
n=s1.size();
cout<<bfs();
return 0;
}