A 成绩
时间复杂度：
#include <iostream>
using namespace std;
int main()
{
int a,b,c;
cin >> a >> b >> c;
cout << a * 0.2 + b * 0.3 + c * 0.5 << endl;
return 0;
}B 输出’Z’
时间复杂度：
#include<iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cout << "->"[i == n];
cout << endl;
for(int i = 2; i <= n - 1; i++)
{
for(int j = n; j >= 1; j--)
cout << ".//"[i == j];
cout << endl;
}
for(int i = 1; i <= n; i++) cout << "-<"[i == 1];
cout << endl;
}
return 0;
}
C 买金币
时间复杂度：
#include <iostream>
using namespace std;
int main()
{
int n, day = 0, res = 0;
cin >> n;
for(int i = 1, j = 1; i <= n; )
{
res += j;
day++;
if(day == j)
day = 0, j++;
if(i == n)
break;
i++;
}
cout << res << endl;
return 0;
}E 街道的树
区间问题, 将区间的树拔掉, 求剩下的树数量。
数组 代表中每棵树是否被拔, 初始为0代表未被拔, 若为正数则说明被拔过至少一次（重合区间会拔多次）
采用差分来记录区间变动即可。 时间复杂度：
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N];
int main()
{
int n,m;
cin >> n >> m;
n++;
while(m--)
{
int l, r;
cin >> l >> r;
a[l]++, a[r+1]--;
}
int res = 0;
for(int i = 0; i < n; i++)
{
a[i] += a[i - 1];
if(a[i] == 0) res++;
}
cout << res << endl;
return 0;
}
F 倍数问题
三的倍数判断除了直接取模, 还有一个方法是把每位数组加起来看是否为3的倍数。
例如 , 为 3 的倍数。 证明：
abc \\ =a * 100+b * 10+c \\ =a * 99+b * 9+a+b+c \end{array}$$ 显然， $a * 99+b * 9$ 是3的倍数，那么只需要判断 $a+b+c$ 是否是 3 的倍数即可 即: $\sum_{i=1}^{n} 10^{i-1} * x_{i} \equiv \sum_{i=1}^{n} x_{i}(\bmod 3)$ 而题目是将$[l,r]$之间的数**连接**，等价于将它们的数字求和，等价于检测把L到R所有数求和后检测其是否被3整除。 证明： 设将它们数字求和为$f$, 所有数求和为$sum$\begin{array}{l} l=10,r=15 \ sum(l,r) = 10+11+12+13+14+15= 75\ f(l,r) = f(101112131415)\=1+0+1+1+1+2+1+3+1+4+1+5 = 21\ f(75) = 7 + 5 = 12 = 3\ f(21) = 2 + 1 = 3 \end{array}
因此成立。 这里并不能直接求和, 其结果会溢出, 可以利用等差数列来判断： $S_{i,j}= \frac{(a_i+a_j)*(j-i+1)}{2}$ 显然, 只要 $a_i+a_j$ 或 $(j-i+1)$ 有一个是三的倍数, 那么整个式子就是3的倍数。 时间复杂度：$O(1)$ ``` c++ #include<iostream> using namespace std; int main() { int T; cin >> T; while(T--) { long long l,r; cin >>l >>r; if((l + r) % 3 == 0 || (r - l + 1) % 3 == 0) cout << "YES\n"; else cout << "NO\n"; } return 0; } ``` # G 下棋 最大是 $10\times10$ , 直接暴力枚举即可。 共有4种胜利情况： - 横 - 竖 - 正对角线 - 逆对角线 时间复杂度：$O(n^2)$ ``` c++ #include <iostream> #include <cstring> using namespace std; const int N = 20 + 5; int g[N][N]; int n; bool check(int i, int j) { int op = g[i][j]; // 横 if(g[i+1][j] == op && g[i+2][j] == op && g[i+3][j] == op && g[i+4][j] == op) return true; // 竖 if(g[i][j+1] == op && g[i][j+2] == op && g[i][j+3] == op && g[i][j+4] == op) return true; // 正对角线 if(g[i+1][j+1] == op && g[i+2][j+2] == op && g[i+3][j+3] == op && g[i+4][j+4] == op) return true; // 副对角线 if(j >= 5 && g[i+1][j-1] == op && g[i+2][j-2] == op && g[i+3][j-3] == op && g[i+4][j-4] == op) return true; return false; } int main() { int T; cin >> T; while(T--) { int n ; cin >> n; memset(g, 0, sizeof g); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { char c; cin >> c; if(c == 'w') g[i][j] = 1; else if(c == 'b') g[i][j] = 2; else g[i][j] = 0; } } int res = 0; for(int i = 1; i <= n; i++) { bool flag = false; for(int j = 1; j <= n; j++) { if(g[i][j] && check(i,j)) { res = g[i][j]; flag = true; break; } } if(flag) break; } if(res == 1) cout << "FYMNB\n"; else if(res == 2) cout << "DDNB\n"; else cout << "PINGJU\n"; } return 0; } ``` # H 密码问题 根据题目可知, 加密运算为： $M_{i} ® S_{i} = M_{i} + S_{i}相对'a'的位置$ 故其逆运算为： $C_{i}-S_i相对'a'的位置=M_i$ , 因为有可能$C_i$ 比 $S_i$ 小, 此时其结果有可能为负数, 需要转化一下： $(C_{i} + 26 - S_i相对'a'的位置)\mod26 = M_i$ 之后枚举求一遍就行 时间复杂度：$O(n)$ ```c++ #include <iostream> #include <cstring> using namespace std; const int N = 1e3 + 10; char a[N],b[N]; bool st[N]; int main() { cin >> a >> b; int n = strlen(b), m = strlen(a); for(int i = 0; i < n; i++) { if('A'<= b[i] && b[i] <= 'Z') b[i] += 32, st[i] = true; if('A'<= a[i] && a[i] <= 'Z') a[i] += 32; b[i] = (b[i] + 26 - a[i % m]) % 26; } for(int i = 0; i < n; i++) if(st[i]) cout << (char)(b[i] + 'A'); else cout << (char)(b[i] + 'a'); return 0; } ``` # I Feb 斐波那契模板题, 注意别用递归写, 会栈溢出, 得用递推写法。 时间复杂度：$O(n)$ DP（递推）写法： ```c++ #include <iostream> using namespace std; const int N = 10000+10, MOD = 998244353; int f[N]; int main() { int n = 10000; f[0] = 0, f[1] = 1; for(int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD; cout << f[n] << endl; return 0; } ``` 节省空间写法, 但是会慢一点（多了赋值操作）： ```c++ #include <iostream> using namespace std; const int MOD = 998244353; int main() { int n = 10000; int a = 0,b = 1, c; for(int i = 2; i <= n; i++) { c = (a + b) % MOD; a = b, b = c; } cout << c << endl; return 0; } ``` # J 进行划分 参考：[算法笔记——整数划分1 - DwyaneTalk - 博客园 (cnblogs.com)](https://www.cnblogs.com/DwyaneTalk/p/4617057.html) 对于整数划分，相当于把正整数n写成下面形式： $n=n_1+n_2+…+n_k$（$其中n≥n_1≥n_2≥…≥n_k≥1，k≥1$）， 则${n_1, n_2, ……,n_k}$为$n$的一个划分。 现假设$n_1 <= m$，即：$\{n_1, n_2, ……,n_k\}$中最大的数不超过$m$，则称$\{n_1, n_2, ……,n_k\}$是$n$的一个$m$上限划分。记$n$的$m$上限划分为$f(n,m)$。因此，此题的解便是$f(n,n)$。对于$f(n,m)$，分析可得下面的递推关系式： 1. 当$n = 1$时，$f(n,m)=1$。即$1$只有$\{1\}$这一种划分。 2. 当$m = 1$时，$f(n,m)=1$。即此时只有$\{1, 1,……,1\}$（共n个1）这一种划分。 3. 当$m = n$时，$f(n,m) = f(n,n) = f(n, n-1) + 1$。其中"$+1$"对应的就是$\{n\}$这种划分，其他的划分中，必定所有数都小于$n$。 4. 当$m > n$时， $f(n,m)= f(n,n)$，因为$n$的划分中不可能存在大于$n$的数。 5. 当$m < n$时， $f(n,m) = f(n-m, m) + f(n, m-1)$。其中$f(n-m,m)$表示包含$m$的划分，$f(n,m-1)$表示不包含$m$的划分。 显然可以有递归DFS写法和动态规划DP写法： 采用DFS深度优先搜索。 `dfs(int n, int sum, int k)` n 为当前剩余可分的数, sum为上一步分的数量, k为当前分了几部分。为了保证答案唯一, 只需要枚举时以特定顺序枚举即可, 这里则是递增顺序。 ``` c++ #include <iostream> using namespace std; long long res; int n,k; void dfs(int n, int sum , int k) { if(n == 0 && k == 0) { res++; return; } else if(n == 0 || k == 0) return; for(int i = sum; i <= n; i++) dfs(n - i,i, k - 1); } int main() { cin >> n >> k; dfs(n,1,k); cout << res << endl; return 0; } ``` 动态规划写法： ```c++ #include<iostream> using namespace std; const int N = 2e2 + 10, M = 6; int f[N][M]; int main() { int n, k; cin >> n >> k; for(int i = 0 ; i <= n; i++) { for(int j = 0; j <= k; j++) { if(i == j) f[i][j] = 1; else if (i < j) f[i][j] = 0; else f[i][j] = f[i -1][j-1] + f[i-j][j]; } } cout << f[n][k] << endl; return 0; } ```