目录
数学
买不到的数目
这道题的意思就是给定两个正整数p和q，求xp+yq这一个组合不能凑出来的最大正整数是多少
首先我们要知道，当p和q的最大公约数大于1时，是一定无解的。例如2和6，最大公约数是2，也就是说这两个数都是2的倍数，那么大部分2的倍数都是能够被凑出来的，所以无解。但是这道题并不需要考虑这种情况，因为题目中已经明确说明一定有解
当我们分析不出来的时候，我们可以考虑打表找规律
#include<iostream>
using namespace std;
bool dfs(int m, int p, int q)
{
if(!m) return true;
if(m >= p && dfs(m - p, p, q)) return true;
if(m >= q && dfs(m - q, p, q)) return true;
return false;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int p, q; cin >> p >> q;
int res = 0;
for(int i = 1;i <= 1000;i ++)
{
if(!dfs(i, p, q)) res = i;
}
cout << res << '\n';
return 0;
}然后可以验证几个数，从而得到数学规律
接下来我们看这道题中使用到的数学方法
引理：给定a，b，若d = gcd(a, b) > 1，则一定不能凑出最大数
结论：若a，b均为正整数且互质，那么ax + by，x>=0，y>=0，不能凑出的最大数是
(a - 1)(b - 1) - 1
#include<iostream>
using namespace std;
int n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
cout << (n - 1) * (m - 1) - 1 << '\n';
return 0;
}蚂蚁感冒
这道题我们会有一个疑问，就是最终所有蚂蚁都会离开杆子吗？
我们可以运用等价的思想来解决，当两只蚂蚁相遇时，正常来说是要调头，我们可以等价为是穿过，所以，最多100秒之后，所有蚂蚁都会穿过。所以，最终所有蚂蚁都会离开杆子。
我们可以分两种情况来讨论：
第一个蚂蚁向右走的情况：
1.右边向左走的，必然被感染
2.右边向右走必然不会被感染
3.左边向左走必然不会被感染
4.左边向右走：
(1)右边存在向左走，则必然被感染
(2)右边不存在向左走，则必然不会被感染
第一个蚂蚁向左走的情况：
1.左边向右走的，必然被感染
2.右边向右走的，必然不会被感染
3.左边向左走的，必然不会被感染
4.右边向左走：
(1)左边存在向右走的，则必然被感染
(2)左边不存在向右走的，则必然不会被感染
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int x[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> x[i];
int left = 0, right = 0; // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量
for (int i = 1; i < n; i ++ )
if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ; // 当前遍历到的蚂蚁初始在第一只蚂蚁的左边，并且当前蚂蚁向右走
else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ; // 当前遍历到的蚂蚁初始在第一只蚂蚁的右边，并且当前蚂蚁向左走
if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
else cout << left + right + 1 << endl;
return 0;
}饮料换购
#include<iostream>
using namespace std;
int n, sum;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
sum += n;
while(n >= 3)
{
int t = n / 3;
int p = n % 3;
sum += t;
n = t + p;
}
cout << sum << '\n';
return 0;
}DP
01背包问题
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N], v, w, n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i ++)
{
cin >> v >> w;
for(int j = m;j >= 1;j --)
if(j >= v) f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}摘花生
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int T, r, c, g[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
while(T --)
{
cin >> r >> c;
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
{
cin >> g[i][j];
g[i][j] += max(g[i - 1][j], g[i][j - 1]);
}
cout << g[r][c] << '\n';
}
return 0;
}最长上升子序列
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, a[N], f[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
int res = 1;
for(int i = 1;i <= n;i ++)
{
f[i]= 1;
for(int j = 1;j < i;j ++)
if(a[j] < a[i])
{
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
}
cout << res << '\n';
return 0;
}地宫取宝
这道题可以用dfs和DP做，但是dfs会爆时间，我们先看dfs
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
const int MOD = 1000000007;
int n, m, k, ans, g[N][N];
void dfs(int u, int i, int j, int t) // u表示当前拿了几件宝贝, t表示当前价值最大是多少
{
// 越界了或u>k了直接返回
if(i > n || j > m || u > k) return ;
if(i == n && j == m) // 到达终点计算是否合法
{
if(u == k || u == k - 1 && g[i][j] > t)
{
ans ++;
ans %= MOD;
}
return ;
}
// 不选
dfs(u, i + 1, j, t);
dfs(u, i, j + 1, t);
// 选
if(g[i][j] > t)
{
dfs(u + 1, i + 1, j, g[i][j]);
dfs(u + 1, i, j + 1, g[i][j]);
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> g[i][j];
dfs(0, 1, 1, -1);
cout << ans << '\n';
return 0;
}然后看DP的做法
状态表示需要用到4维数组，刚好与我们dfs中的函数4个参数对应
初始时，我们在左上角，此时需要对数组进行初始化
选取左上角这个位置的宝贝时， f[1][1][1][w[1][1]] = 1
不选取左上角这个位置的宝贝时，f[1][1][0][-1] = 1
因为C++中坐标没有负数，所以我们对每个宝贝的价值都增加1，这样宝贝的价值就变成了1到13，就可以使用0来表示没有选取任何一个宝贝了
然后看状态计算。
对于当前状态f[i, j, k, c]，可以由前一个状态向下走，也可以由前一个状态向右走，此时就有两个分支了。对于每一个分支，又可以分成是否拿当前这个位置[i, j]的宝贝。对于取的这一个分支，又可以分成前一个最大价值是多少。注意：不取没有什么限制，但是如果要取，则必须满足当前状态的宝物数量不为0，并且当前状态的宝贝最大值等于w[i][j]
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55, MOD = 1000000007;
int n, m, k;
int w[N][N];
int f[N][N][13][14];
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
cin >> w[i][j];
w[i][j] ++ ;
}
f[1][1][1][w[1][1]] = 1;
f[1][1][0][0] = 1;
// 首先，枚举四个维度
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if (i == 1 && j == 1) continue;
for (int u = 0; u <= k; u ++ )
for (int v = 0; v <= 13; v ++ )
{
int &val = f[i][j][u][v];
// 不取
val = (val + f[i - 1][j][u][v]) % MOD;
val = (val + f[i][j - 1][u][v]) % MOD;
// 取
if (u > 0 && v == w[i][j])
{
for (int c = 0; c < v; c ++ )
{
val = (val + f[i - 1][j][u - 1][c]) % MOD;
val = (val + f[i][j - 1][u - 1][c]) % MOD;
}
}
}
}
int res = 0;
for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;
cout << res << endl;
return 0;
}波动数列
设满足题意的一个数列的第一项为x，设di∈{a, -b}，则长度为n的数列为：
由这个数列的和为s，可得：
进一步传化可得：
因为x是整数，所以分子一定是n的倍数，也就是说s 和 (n - 1)d1 + (n - 2)d2 + ... + dn - 1，两者模n的余数是相等的。所以，问题就转化成了有多少种不同的选法，使得
(n - 1)d1 + (n - 2)d2 + ... + dn - 1与s模n的结果相同。这是一个组合问题
我们来看看状态计算的两个状态是怎么推出来的。我们要根据最后一项不同来推，很明显，最后一项不同就是从第i - 1项到第 i 项选+a，还是选-b
假设前i-1项的和为C，则有(以+a为例)：
移项可得：
所以最后一项是+a的所有方案的状态是f[i - 1, (j - (n - i)a) % n]
最后一项是+a的所有方案的状态是f[i - 1, (j + (n - i)b) % n]
最终结果就是f[n - 1, s % n]
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 100000007;
int f[N][N];
int get_mod(int a, int b) // 求a除以b的正余数
{
return (a % b + b) % b;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, s, a, b;
cin >> n >> s >> a >> b;
f[0][0] = 1;
for (int i = 1; i < n; i ++ )
for (int j = 0; j < n; j ++ )
f[i][j] = (f[i - 1][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;
cout << f[n - 1][get_mod(s, n)] << endl;
return 0;
}注意：取模操作需要我们自己实现，因为C++中负数取模是负数，而数列的项中是含有负数项的，所以需要自己实现求正余数