第一题：数字反转（number）

题目描述

题解部分

1. 字符串反转

解题思路：

可以将整个数字当做字符串输入，再倒序输出。

时间复杂度：

#include <bits/stdc++.h>using namespace std;string s;int main() { cin >> s;for (int i = s.size() - 1; i >= 0; i--) {  cout << s[i]; }return 0;}

2. 数位拆分

解题思路：

通过cin输入将整数部分和小数部分分隔，再使用数位拆分倒序输出整数部分。

时间复杂度：

#include <bits/stdc++.h>using namespace std;int a, b;char c;int main() { cin >> a >> c >> b; cout << b << c << a % 10 << a / 10 % 10 << a / 100;return 0;}

第二题：数的性质（char）

题目描述

题解部分

分支结构

解题思路：简单分支结构，按照题目的要求一个个判断即可。 不过可以在写法上进行优化，降低出错率。

时间复杂度：

#include <bits/stdc++.h>using namespace std;int x;int main() { cin >> x; int a = x % 2 == 0; int b = x > 4 && x <= 12; cout << (a && b) << " "; cout << (a || b) << " "; cout << (a + b == 1) << " "; cout << (a + b == 0);return 0;}

第三题：坚持锻炼（run）

题目描述

题解部分

模拟

解题思路：

根据题意，我们可以得到如下格式的数据：

1// 第1天获得1块钱22// 接下来2天每天获得2块钱333// 接下来3天每天获得3块钱4444// 接下来4天每天获得4块钱....i i ... i i  // 接下来i天每天获得i块钱  

我们可以用第一层循环表示第几行（可获得几块钱），第二层循环表示有几天（可以领几天  元钱），顺便更新天数并累加金额，一旦天数到达 ，则输出结果并结束程序即可。

时间复杂度：

#include <bits/stdc++.h>using namespace std;long long x, d, s;int main() { cin >> x;for (int i = 1; ;i++) {         // 表示当天可以领的钱 for (int j = 1; j <= i; j++) {  // i 元可以领 i 天    d++;              // 累加天数    s += i;           // 累加金额 if (d == x) {     // 到了第 x 天     cout << s;       // 输出结果 return 0;        // 结束程序    }  } }return 0;}

第四题：炮（zombie）

题目描述

题解部分

1. 找规律

解题思路：

直接手动打表找规律，如果僵尸左边的植物数量与右边植物数量在模  的情况下同余则结果为  ，否则结果为 。

时间复杂度：

#include<bits/stdc++.h>usingnamespacestd;longlong t, n, k;intmain(){cin >> t;while (t--) {cin >> n >> k;cout << (k % 3 == (n - k) % 3 ? 2 : 1) << '\n'; }return0;}

2. 贪心 - 最终状态

解题思路：

我们将僵尸左右两侧的植物数量看成一个状态，易得：

结论1：最终结果一定为  或 

最终状态要么是，表示僵尸左右两侧分别有  个植物；要么是，表示僵尸左侧有1个植物，右侧没有；要么是，表示僵尸右侧有  个植物，左侧没有。

盲猜：

结论2：对于任一状态，它只能走到1和2的其中一个状态。

在此基础上，除了所有的状态均能走到僵尸在所有植物的一侧左侧右侧效果等同且不能继续吃植物的状态，所以我们仅需分析

易得：对于能走到中  的状态一定会走到答案为  的状态，否则只能走到答案为  的状态。

最终状态是贪心中的常见题型，博弈论中的必败必胜态的分析方式与此题类似。

时间复杂度：

#include<bits/stdc++.h>using namespace std;using ll=long long;const int N=2e5+5;int t;ll x,y;bool Check(ll x,ll y){//僵尸左右各多少个植物 if(x==1&&y==1) return 1;//特判 if(x%2==0) return (y+x/2)%3==0;//如果一侧植物是偶数 if(y%2==0) return (x+y/2)%3==0; return (x+y-((x+1)/2+1))%3==0;//两侧植物都是奇数 }int main(){ cin>>t;while(t--){  cin>>x>>y;  cout<<(Check(y,x-y)?2:1)<<endl; }return 0;}

第五题：跳棋（checkers）

题目描述

题解部分

线性dp + 降维

算法流程：

考虑动态规划：设计状态表示走到第个格子，用完 张第  种卡片所得的最大分数，状态转移也很好想，一共四种转移方式。

但是，这样无论时间还是空间复杂度都是超的（均为  ）。即使通过滚动数组降维，也仅将空间复杂度降为  ，时间复杂度没有变化。

观察题目给出的额外信息，保证到达终点时刚好用光  张卡片，所以可以去掉第一个参数,实现降维。

相较于动态规划，用递推（扩散型转移）更好实现。

时间复杂度：

#include<bits/stdc++.h>using namespace std;const int N=45;int n,m;int a[N*100];int cnt[10];//第i种卡片的数量 int f[N][N][N][N];//f[i][j][k][l]表示使用了i,j,k,l张第1,2,3,4种卡片能拿到的最大分数 int count(int i,int j,int l,int r){return i+j*2+l*3+r*4+1;}int main(){ cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){  int x;  cin>>x;  cnt[x]++;//统计卡片数量  } f[0][0][0][0]=a[1];//已知问题 for(int i=0;i<=cnt[1];i++){for(int j=0;j<=cnt[2];j++){for(int k=0;k<=cnt[3];k++){for(int l=0;l<=cnt[4];l++){//从已知问题推出未知问题      f[i+1][j][k][l]=max(f[i+1][j][k][l],f[i][j][k][l]+a[count(i+1,j,k,l)]);     f[i][j+1][k][l]=max(f[i][j+1][k][l],f[i][j][k][l]+a[count(i,j+1,k,l)]);     f[i][j][k+1][l]=max(f[i][j][k+1][l],f[i][j][k][l]+a[count(i,j,k+1,l)]);     f[i][j][k][l+1]=max(f[i][j][k][l+1],f[i][j][k][l]+a[count(i,j,k,l+1)]);    }   }  } } cout<<f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];return 0;}

改题链接：

http://hu33.tech/contest/6a0c38494b52870861f44fd4