第一题
中文题意：求解 n! % m?
n：[1,1e9]，m：[1,2e4]，如果直接循环求解，显然会超时。
那么注意：
当 n >= m 时，n！% m? = 1 * 2 * 3 * ... * m * m + 1 * m + 2 * ... * n % m = 0，
当n < m时，直接循环求解即可，
注意循环的过程取模m。
核心代码如下：
void solve() {
?? ?cin >> n >> m;
?? ?if (n >= m) cout << 0;
?? ?else {
?? ??? ?int ans = 1;
?? ??? ?for (int i = 1; i <= n; i++)
?? ??? ??? ?ans = ans * i % m;
?? ??? ?cout << ans;
?? ?}
}第二题
?中文题意——
给你n个数，要求必须去掉其中一个数，然后对剩下的n-1个数求解gcd，使gcd最大。
解法——
我们先思考一下暴力解法：
枚举每个数，表示删除这个数，然后对于剩下的n-1个数进行gcd求解，不断保留或更新最大值，
很显然，枚举的时间复杂度是O(n)，循环遍历剩下的n-1个数，时间复杂度是O(n - 1)，求解gcd的时间复杂度是O(logx)，由于1 <= n <= 1e6，显然会超时。
那么尝试优化：
已知：对于n个数，求解其gcd，与这n个数的顺序无关，比如{1,2,3,4,5}求解gcd，和{5,4,3,2,1}求解gcd，最终结果一定是相同的。
那么，我们可以从前到后扫一遍数组，求一下前缀gcd，再从后到前扫一遍数组，求一下后缀gcd，然后再从前到后扫一遍数组，这时的循环是枚举删除的数字，根据上面预处理出来的前缀gcd和后缀gcd，即可求出来删除该数字后剩下n-1个数的gcd，并不断保留或更新最大值。
时间复杂度分析：
前缀gcd：O(nlogx)
后缀gcd：O(nlogx)
枚举删除： O(nlogx)
并不会超时，并且显然是这道题的最优解法。
核心代码——
int gcd(int x, int y) {?
? ? return y == 0 ? x : gcd(y, x % y);?
}
void solve() {
????cin >> n;
? ? for (int i = 1; i <= n; i++)
? ? ? ? cin >> a[i];
? ? for (int i = 1; i <= n; i++)
? ? ? ? head[i] = gcd(a[i], head[i - 1]);
? ? for (int i = n; i >= 1; i--)
? ? ? ? tail[i] = gcd(a[i], tail[i + 1]);
? ? int ans = 1;
? ? for (int i = 1; i <= n; i++)
? ? ? ? ans = max(ans, gcd(head[i - 1], tail[i + 1]));
? ? cout << ans;
}第三题
?中文题意——
给你一个棋盘，'.'表示空白区域，'*'表示黑棋，'#'表示白棋，执黑棋手要下一子，棋子只能放置到空白区域，求解”可行“的空白位置，按照”行最小优先，然后列最小优先”输出整个棋盘。
“可行”：棋手在该位置放置黑棋后，能够组成五子连线。
数据保证：初始局面下没有五子连线。
解法——
n：[1,20]，m：[1,20]，显然只需要暴力枚举每个空白区域即可，再检查该棋子左右，上下，左上右下，右上左下，四条线上，每条线上连续的黑棋数量是否为4即可，再储存起来，最终输出。
核心代码——
class Cmp {
public:
? ? bool operator() (pll tt, pll ttt) const {
? ? ? ? if (tt.first != ttt.first) return tt.first < ttt.first;
? ? ? ? return tt.second < ttt.second;
? ? }
};
char a[sz][sz];
int n, m;
set<pll, Cmp>st;
int dd[][2] = { 1,0,0,1,1,1,1,-1 };
bool check(int x, int y) {
? ? if (x < 1 || x > n || y < 1 || y > m) return false;
? ? if (a[x][y] != '*') return false;
? ? return true;
}
void search(int stx, int sty) {
? ? for (int i = 0; i <= 3; i++) {
? ? ? ? int cntz = 0, cntf = 0;
? ? ? ? for (int x = stx + dd[i][0], y = sty + dd[i][1]; check(x, y); x += dd[i][0], y += dd[i][1]) cntz++;
? ? ? ? for (int x = stx - dd[i][0],? y = sty - dd[i][1];?check(x, y); x -= dd[i][0], y -= dd[i][1]) cntf++;
? ? ? ? if (cntz + cntf >= 4) {?
? ? ? ? ? ? st.insert(pll(stx, sty));
? ? ? ? ? ? break;
? ? ? ? }
? ? }
}
void solve() {
? ? cin >> n >> m;
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = 1; j <= m; j++)
? ? ? ? ? ? cin >> a[i][j];
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = 1; j <= m; j++)
? ? ? ? ? ? if (a[i][j] == '.')
? ? ? ? ? ? ? ? search(i, j);
? ? if (st.size()) {
? ? ? ? for (auto tt : st) {
? ? ? ? ? ? for (int i = 1; i <= n; i++) {
? ? ? ? ? ? ? ? for (int j = 1; j <= m; j++) {
? ? ? ? ? ? ? ? ? ? if (i == tt.first && j == tt.second) cout << '*';
? ? ? ? ? ? ? ? ? ? else cout << a[i][j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? cout << '\n';
? ? ? ? ? ? }
? ? ? ? ? ? cout << '\n';
? ? ? ? }
? ? }
? ? else cout << "NO";
}第四题
中文题意——?
小河可以看作一列格子依次编号为?0?到?N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子?ii?时，她只移动到区间?[i+L,i+R][i+L,i+R]?中的任意一格。
每一个格子都有一个冰冻指数?Ai?，编号为?0?的格子冰冻指数为?0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数?Ai。琪露诺希望能够在到达对岸时，获取最大的冰冻指数。
开始时，琪露诺在编号?00?的格子上，只要她下一步的位置编号大于?NN?就算到达对岸。
解法——
n：[1,2e5]，1 <= L <= R
我们先考虑暴力解法：
首先，我们回顾一下Dijkstra算法：求解起点到某个点的最长路，先求出来起点到该点的所有入度的最长路，再求解起点到该点的最长路。
但是，这个题的数据有负数，考虑SPFA跑最长路，但是，L和R无法保证，导致建边的最坏时间复杂度为O(n^2)，还没建完边就TLE。
回归dp本质：
结合上述的最长路思想，我们只需要枚举每个点的所有出度，不断更新起点到这个点的出度的最大值，最后再求解即可。但是，很显然，由于L和R，最坏的时间复杂度为O(n^2)，TLE。
考虑优化：
定义：dp[i]表示，从0到第i个点，所能获得的最大值。
初始化：dp[0] = 0,dp[i] = -INF(1 <= i <= n)。
从当前点开始，能够移动到的下一个点的范围是固定不变的，考虑单调队列。
以第i个点为例，能够影响到他的只有[i - R,i - L]这些点，如果我们可以提前求出起点到这些点的最大值，就可以直接O(1)求解起点到第i个点的最大值。
两个变量：
i，用来求解dp[i]，
tmp，用来不断更新[i - R,i - L]的最大值。
由于需要的是最大值，因此，在更新的过程中，小于等于dp[tmp]都应该舍弃，且更有利于后面的更新。
我们使用双端队列来模拟单调队列。
部分代码——
deque<node> que;
ll tmp = 0;
for (int i = L; i <= n; i++) {
while (que.size() && dp[tmp] > que.back().val) que.pop_back();
que.push_back(node{ dp[tmp],tmp });
while (i - que.front().rec > R) que.pop_front();
dp[i] = max(dp[i], que.front().val + a[i]);
tmp++;
}坑点——
如果直接循环dp[i]求取最大值，那么考虑：
6 2 2
0 1 -1 1 -1 1 -1
正确结果是-3，但按照刚刚的做法，结果是-1
那么重新读题，要么走到第n个点，要么直接走过第n个点，考虑：
6 2 4
0 1 -1 1 -1 1 -1
当走到第2个点时，是可以走到第6个点，在求解dp[6]时考虑了这种情况，
当走到第3个点时，是可以走到第6个点，也可以直接走过，这时最终结果可能是dp[6]，也可能是dp[3]。
这个题最终结果的选取应该是这样的：
部分代码——
ll ans = dp[n];
for (int i = 1; i < n; i++)
if (i + R > n)?ans = max(ans, dp[i]);
cout << ans;第五题：
中文题意——
给你一个n * n的矩阵，A要从(1,1)走到(n,n)，B要从(n,n)走到(1,1)，矩阵的每个点都有若干个糖果，每个人走到相应点时，会取得该点上所有的糖果，求最终A和B所能获得的最大糖果。
糖果数有正有负。
解法——
考虑只有一个人时，有两种思路：
一，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
i表示横坐标，j表示纵坐标。
二，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]
i表示当前共走了i步，j表示纵坐标。
当有两个人时：
采用思路一，dp[i][j][k][l]，空间复杂度和时间复杂度都很高。
采用思路二，dp[k][i][j]，空间复杂度和时间复杂度相较于思路一，都很优秀。
这里采取思路二：
1.特殊点：
令初始状态：两人都不在(1，1)
k = 1：两人走了一步，走到(1,1)
2.预处理：
memset(dp，-0x3f3f3f3f，dp)，全部预处理为极限最小负数，这在处理边缘情况时，相当于忽略掉冗余转移。
dp[1][1][1] = a[1][1]，既符合题意，又符合dp含义，又避免了初始状态转移的可能错误，又保证了从此开始的后续状态转移正确。
3.边界：
令k = 2为循环开始。
循环的过程中，要保证每人走的总步数不超过k，且当两人走到边缘时，状态转移有冗余，这需要在预处理时注意。
4.最终结果：
两人行动轨迹：
未知初始点 —— (1，1)? 步数：1
(1，1) —— (n，n)? 步数：n - 1 + n - 1 = n + n - 2
总计步数：n + n - 1
最终纵坐标：i = n，j = n
最终结果：dp[n + n - 1][n][n]
核心代码——
for (int i = 0; i <= 210; i++)
for (int j = 0; j <= 210; j++)
for (int k = 0; k <= 410; k++)
dp[k][i][j] = -0x3f3f3f3f;
dp[1][1][1] = a[1][1];
for(int k = 2; k <= n + n - 1; k++)
for(int i = 1;i <= n && i <= k; i++)
for (int j = 1; j <= n && j <= k; j++) {
dp[k][i][j] = max(max(dp[k - 1][i - 1][j], dp[k - 1][i][j - 1]), max(dp[k - 1][i][j], dp[k - 1][i - 1][j - 1]));
dp[k][i][j] += i == j ? a[k - i + 1][i] : a[k - i + 1][i] + a[k - j + 1][j];
}
cout << dp[n + n - 1][n][n];