质因数分解
已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。
题解
分解质因数模板题。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, ans;
cin >> n;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
n /= i;
ans = i;
}
}
if (n > 1) {
ans = n;
}
cout << ans << endl;
}
寻宝
题面
传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：
藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有N层，每层M个房间，这M个房间围成一圈并按逆时针方向依次编号为0，…，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的k号房间。比如当前房间的指示牌上写着2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。
请帮助小明算出这个打开宝箱的密钥。
输入
第一行2个整数N和M，之间用一个空格隔开。N表示除了顶层外藏宝楼共N层楼，M表示除顶层外每层楼有M个房间。
接下来N*M行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第(i-1)*M+j行表示第i层j-1号房间的情况（i=1, 2, …, N；j=1, 2, … ,M）。第一个整数表示该房间是否有楼梯通往上一层（0表示没有，1表示有），第二个整数表示指示牌上的数字。注意，从j号房间的楼梯爬到上一层到达的房间一定也是j号房间。
最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从0开始）。
输出
输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对20123取模的结果即可。
输入样例 1
2 3
1 2
0 3
1 4
0 1
1 5
1 2
1
输出样例 1
5
提示
【输入输出样例说明】 第一层：
0号房间，有楼梯通往上层，指示牌上的数字是2；
1号房间，无楼梯通往上层，指示牌上的数字是3；
2号房间，有楼梯通往上层，指示牌上的数字是4；
第二层：
0号房间，无楼梯通往上层，指示牌上的数字是1；
1号房间，有楼梯通往上层，指示牌上的数字是5；
2号房间，有楼梯通往上层，指示牌上的数字是2；
小明首先进入第一层（底层）的1号房间，记下指示牌上的数字为3，然后从这个房间开始，沿逆时针方向选择第3个有楼梯的房间2号房间进入，上楼后到达第二层的2号房间，记下指示牌上的数字为2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第2个有楼梯的房间即为1号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即3+2=5，所以打开宝箱的密钥就是5。
题解
大模拟。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 105;
int n, m;
vector<int> a[N], b[N];
int c[N][M];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int s;
scanf("%d%d", &s, &c[i][j]);
if (s == 0) {
a[i].push_back(j);
} else {
b[i].push_back(j);
}
}
}
int cur, ans = 0;
cin >> cur;
for(int i = 1;i <= n; i++) {
auto it = lower_bound(a[i].begin(), a[i].end(), cur);
int x = -1;
if (it != a[i].end() && *it == cur) {
x = c[i][*it];
}
it = lower_bound(b[i].begin(), b[i].end(), cur);
if (it == b[i].end()) {
it = b[i].begin();
}
if (x < 0) {
x = c[i][*it];
}
int k = (it - b[i].begin() + x - 1) % b[i].size();
(ans += x) %= 20123;
cur = b[i][k];
}
cout << ans << endl;
}
摆花
已知$n$，$m$，$a_i$，求$\sum_{i=1}^{n}{x_i}=m (0<=x_i<=a_i)$的正整数解方案数。
题解
递推，令$f[i][j]$表示前$i$个未知数的和为$j$的方案数。 $$f[i][j] = \sum_{k=max(0, j-a[i])}^{j}{f[i-1][k]}$$ 时间复杂度$O(nm^2)$
优化1
利用前缀和。 令 $$ s[i][j]=\sum_{k=0}^{j}{f[i][k]} \newline =\sum_{k=0}^{j-1}{f[i][k]}+f[i][j] = s[i][j-1]+f[i][j] $$ 于是 $$ f[i][j] = \begin{cases} s[i-1][j] &\text{if } j<=a[i] \newline s[i-1][j] - s[i-1][j-a[i]-1] &\text{otherwise} \end{cases} $$ 时间复杂度$O(nm)$
拓展
当$n$较小时有用容斥原理+组合数的跟m无关的指数级算法。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1000007;
int n, m, f[N][N], a[N], s[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
f[0][0] = 1;
for (int i = 0; i <= m; i++) {
s[0][i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j <= a[i]) {
f[i][j] = s[i-1][j];
} else {
f[i][j] = (s[i-1][j] - s[i-1][j-a[i]-1] + M) % M;
}
s[i][j] = (s[i][j-1] + f[i][j]) % M;
}
}
cout << f[n][m] << endl;
}
文化之旅
题面
有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。
输入
第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为1到N），文化种数（文化编号为1到K），道路的条数，以及起点和终点的编号（保证S不等于T）；
第二行为N个整数，每两个整数之间用一个空格隔开，其中第$i$个数$C_i$，表示国家$i$的文化为$C_i$。
接下来的K行，每行K个整数，每两个整数之间用一个空格隔开，记第$i$行的第$j$个数为$a_{i,j}$，$a_{i,j}=1$表示文化$i$排斥外来文化$j$（$i$等于$j$时表示排斥相同文化的外来人），$a_{i,j}=0表示不排斥（注意$i$排斥$j$并不保证$j$一定也排斥$i$）。
接下来的M行，每行三个整数$u,v,d$，每两个整数之间用一个空格隔开，表示国家$u$与国家$v$有一条距离为$d$的可双向通行的道路（保证$u$不等于$v$，两个国家之间可能有多条道路）
输出
输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。
输入样例 1
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输出样例 1
-1
输入样例 2
2 2 1 1 2
1 2
0 1
0 0
1 2 10
输出样例 2
10
提示
【输入输出样例说明1】
由于到国家2必须要经过国家1，而国家2的文明却排斥国家1的文明，所以不可能到达国家2。
【输入输出样例说明2】
路线为1 -> 2。
【数据范围】
对于20%的数据，有2≤N≤8，K≤5；
对于30%的数据，有2≤N≤10，K≤5；
对于50%的数据，有2≤N≤20，K≤8；
对于70%的数据，有2≤N≤100，K≤10；
对于100%的数据，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u, v≤N，1≤d≤1000，S≠T，1 ≤S, T≤N。
题解
二分答案然后A*爆搜判断。
估价函数为：当前走过的距离+当前国家到终点的不经过与已经走过的国家文化排斥的国家的最短路。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, m, s, t, a[N][N], c[N], d[N][N], v[N], q[N * N], g[N];
int check(int y) {
for (int x = 1; x <= n; x++) {
if (v[x] && a[c[y]][c[x]]) {
return 0;
}
}
return 1;
}
int cal(int x) {
memset(g, 0x3f, sizeof(g));
q[1] = x;
g[x] = 0;
for (int l = 1, r = 1; l <= r; l++) {
int x = q[l];
for (int y = 1; y <= n; y++) {
if (g[x] + d[x][y] < g[y] && check(y)) {
g[y] = g[x] + d[x][y];
q[++r] = y;
}
}
}
return g[t];
}
int dfs(int x, int dis, int lim) {
if (dis + cal(x) > lim) {
return 0;
}
if (x == t) {
return 1;
}
v[x] = 1;
for (int y = 1; y <= n; y++) {
if (check(y) && dfs(y, dis + d[x][y], lim)) {
v[x] = 0;
return 1;
}
}
v[x] = 0;
return 0;
}
int main() {
cin >> n >> k >> m >> s >> t;
for (int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
}
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= k; j++) {
scanf("%d", &a[i][j]);
}
a[i][i] = 1;
}
memset(d, 0x3f, sizeof(d));
for (int i = 1; i <= m; i++) {
int u, v, x;
scanf("%d%d%d", &u, &v, &x);
d[u][v] = d[v][u] = min(d[u][v], x);
}
int ans = -1;
for (int l = 1, r = 1e5; l <= r;) {
int m = (l + r) / 2;
if (dfs(s, 0, m)) {
r = m - 1;
ans = m;
} else {
l = m + 1;
}
}
cout << ans << endl;
}