试题 A: 数青蛙（模拟）
>答案：353
个位数一位;11~19以及10的倍数两位;其余情况三位
#include <iostream>
using namespace std;
int get(int x)
{
if(x >= 1 && x <= 10) return 1;
else if((x >= 11 && x <= 20) || x == 30 || x == 40 || x == 50 || x == 60 || x == 70 || x == 80 ) return 2;
else return 3;
}
int main()
{
int res = 0;
res += 10 * 20;
for(int i = 1;i <= 20;i ++ ) res += get(i); // 第一个数字
for(int i = 1;i <= 20;i ++ ) res += get(i); // 第二个数字
for(int i = 2;i <= 40;i += 2 ) res += get(i); // 第一个数字
for(int i = 4;i <= 80;i += 4 ) res += get(i); // 第一个数字
cout << res << endl;
return 0;
}
试题 B: 互质（最大公约数）
>答案：1008
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
return b ? gcd(b,a % b) : a;
}
int main()
{
int res = 0;
for(int i = 1;i <= 2020;i ++ )
if(gcd(i,1018) == 1) res ++;
cout << res << endl;
return 0;
}
试题 C: 车牌（爆搜）
>答案：4002750
#include <iostream>
using namespace std;
int res;
void dfs(int u,int l1,int l2) // u表示搜到第几位，
// 从0开始，l1表示上一位是多少，l2表示上2位是多少
{
if(u == 6) {
res ++;
return;
}
if(u < 3)
{
for(int i = 0;i <= 15;i ++ ){
if(i == l1 && i == l2 && l1 == l2) continue;
dfs(u + 1,i,l1);
}
}else{
for(int i = 0;i <= 9;i ++ ){
if(i == l1 && i == l2 && l1 == l2) continue;
dfs(u + 1,i,l1);
}
}
}
int main()
{
dfs(0,-1,-1);
cout << res << endl;
return 0;
}
试题 D: Fibonacci 集合（多路归并）
>答案：41269
类似题 – 62. 丑数
#include <iostream>
#include <vector>
using namespace std;
vector<long long> q;
int main()
{
q.push_back(1);
q.push_back(2);
q.push_back(3);
int i =0,j = 0,k = 0;
while(q.size() < 2020)
{
long long t = min(3 * q[i] + 2,min(5 * q[j] + 3,8 * q[k] + 5));
q.push_back(t);
if(3 * q[i] + 2 == t) i ++ ;
if(5 * q[j] + 3 == t) j ++ ;
if(8 * q[k] + 5 == t) k ++ ;
}
cout << q.back() << endl;
return 0;
}
试题 E: 上升子串（动态规划 | 记忆化搜索）
>答案：无（无数据）
类似题 – 滑雪
#include <iostream>
#include <vector>
using namespace std;
const int N = 110;
vector<string> g;
int f[N][N]; // f[i][j]: 表示以[i,j]开头的上升子序列
int n,m;
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
int dfs(int x,int y) // dfs返回以[x,y]开头的上升子序列
{
if(f[x][y]) return f[x][y];
f[x][y] = 1;
for(int i = 0;i < 4;i ++ )
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] > g[x][y])
{
f[x][y] += dfs(a,b);
}
}
return f[x][y];
}
int main()
{
freopen("inc.txt","r",stdin);
string s;
while(getline(cin, s)) g.push_back(s);
n = g.size(), m = g[0].size();
int res = 0;
for(int i = 0;i < n;i ++ )
for(int j = 0;j < m;j ++ )
{
res += dfs(i,j);
}
cout << res << endl;
return 0;
}
试题 F: 日期识别（模拟）
#include <iostream>
using namespace std;
int main()
{
string months[13] = {"","Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
string s;
cin >> s;
string month,day;
month = s.substr(0,3);
day += s.substr(3);
for(int i = 1;i < 13;i ++)
if(month == months[i]) cout << i << ' ';
// int d = (day[0] - '0') * 10 + (day[1] - '0');
// cout <<d;
cout << stoi(day);
return 0;
}
试题 G: 乘法表（进制转换）
进制转换
#include <iostream>
#include <algorithm>
using namespace std;
int n;
char get(int x)
{
if(x <= 9) return x + '0';
else return x - 10 + 'A';
}
string base(int x) // 十进制转 P进制
{
string num;
while(x){
num += get(x % n), x /= n;
}
reverse(num.begin(),num.end());
return num;
}
int main()
{
cin >> n;
for(int i = 1;i < n;i ++ ){
for(int j = 1;j <= i;j ++ )
{
cout << get(i) << "*" << get(j) << "=" << base(i * j) << ' ';
}
printf("\n");
}
return 0;
}
试题 H: 限高杆（改进spfa()算法）
spfa算法模板
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
struct Node //每个点指向的下一个节点
{
int node;
int w;
int no; //是否有限高杆
};
const int N = 10010;
int n, m;
vector<Node> g[N];
int d[N][3];
bool st[N][3];
void spfa()
{
memset(d, 0x3f, sizeof d);
d[1][0] = d[1][1] = d[1][2] = 0;
queue<PII> q;
q.push({1, 0}); //三种状态都加入队列
// q.push({1, 1});
// q.push({1, 2});
while (q.size())
{
auto tt = q.front();
q.pop();
int t = tt.first; //当前节点
int cnt = tt.second; //当前经过的限高杆数量
st[t][cnt] = false;
int num = g[t].size();
for (int i = 0; i < num; i ++ )
{
int j = g[t][i].node;
int w = g[t][i].w;
int no = g[t][i].no;
if (cnt + no < 3 && d[j][cnt + no] > d[t][cnt] + w) //不能超过三个限高杆
{
d[j][cnt + no] = d[t][cnt] + w;
if (!st[j][cnt + no])
{
q.push({j, cnt + no});
st[j][cnt + no] = true;
}
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++ )
{
int a, b, c, f;
scanf("%d%d%d%d", &a, &b, &c, &f);
g[a].push_back({b, c, f});
g[b].push_back({a, c, f});
}
spfa();
cout << d[n][0] - min(min(d[n][0], d[n][1]), d[n][2]);
return 0;
}
试题 I: 画中漂流（动态规划）
关键点：距离可以通过 时间和剩余体力计算出来!
题解
#include <iostream>
using namespace std;
const int N = 3010, mod = 1e9 + 7;
int d,t,m;
int f[N][N]; // f[i,j] : 花费时间为i，且剩余体力为j的方案数 答案：f[t][0]，初始化f[0][m] = 1;
// 不滑f[i - 1][j] ， 滑f[i - 1][j + 1];
// 关键点：距离可以通过 时间和剩余体力计算出来!
// 初始距离：d， 向上游距离：m - j ，向下流距离 i - (m - j)
int main()
{
cin >> d >> t >> m;
f[0][m] = 1;
for(int i = 1;i <= t;i ++ )
for(int j = 0;j <= m;j ++)
{
int dist = d + (m - j) -(i - (m - j));
if(dist > 0){
// 不滑
f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
// 滑
f[i][j] = (f[i][j] + f[i - 1][j + 1]) % mod;
}
}
cout << f[t][0] << endl;
return 0;
}
试题 J: 旅行家
70分代码，时间复杂度$O(n ^ 2)$，像spfa()
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
LL T[N],F[N];
LL rp[N];
bool st[N];
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++ ) scanf("%lld",&T[i]);
for(int i = 1;i <= n;i ++ ) scanf("%lld",&F[i]);
memset(rp,-0x3f,sizeof rp);
rp[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = t + 1;i <= n;i ++)
{
if(rp[t] / 2 - F[t] + T[t] * T[i] > rp[i])
{
rp[i] = rp[t] / 2 - F[t] + T[t] * T[i];
if(!st[i])
{
q.push(i);
st[i] = true;
}
}
}
}
LL res = -1e18;
for(int i = 1;i <= n; i ++) res = max(res,rp[i]);
printf("%lld\n",res);
return 0;
}
