A. 回文
\(20\) 多分的纯暴力搜索，\(A_{i,j} = A_{i-1,j+1}\) 可以判完回文直接递推出路径数，共 \(42 \text{pts}\)。
正解 \(DP\)。
回文可以转化一下思路，两个人分别从 \((1,1),(n,m)\) 出发，走的路径相同的方案数。
设计 \(dp[i][j][s][t]\) 为第一个人在 \((i,j)\) 位置，第二个人在 \((s,t)\) 位置的方案数。
转移要注意步数相同，即 \(i + j - 2 = n + m - s - t\)。
因为我们每走一步会使你的坐标 \(x + y\) 加上 \(1\)，又因为我们坐标都是从 \(1\) 开始的，所以第一个人路径长度就是 \(x + y - 2\)。
第二个人由于是从 \(n + m\) 开始，不太一样。
所以就可以压掉一维，\(t = n + m + 2 - s - i - j\)（好长）。
最后要考虑一下回文有两种情况，一种是长度为奇数，即最后两个人走到同一个位置；另一种长度为偶数，即二者相邻的状态，这种要考虑两种相邻的情况（上下和左右）。
这个思路来自sandom学长的博客，稍微解释地详细了一下。
这道题最坑的就是模数 \(993244853\)！！！！！！
注意，全开 \(long \ long\) 会 \(\text{MLE}\)，要中途计算时用 \(long \ long\) 的临时变量。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
const int N = 505;
const int Mod = 993244853;
int n,m;
char a[N][N];
int dp[N][N][N];
long long ans;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
cin >> a[i][j];
if(a[1][1] == a[n][m])
dp[1][1][n] = 1;
else {
cout << "0";
return 0;
}
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
for(int s = n;s >= 1; s--) {
int t = n + m + 2 - i - j - s;
if(t < 1 || t > m)
continue;
ans = dp[i][j][s];
if(a[i][j] == a[s][t])
ans = ans + dp[i - 1][j][s + 1] + dp[i - 1][j][s] + dp[i][j - 1][s + 1] + dp[i][j - 1][s];
dp[i][j][s] = ans % Mod;
}
}
}
ans = 0;
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
int s,t;
s = i,t = j;
if(i + j + s + t == n + m + 2)
ans += dp[i][j][s];
s = i + 1,t = j;
if(i + j + s + t == n + m + 2)
ans += dp[i][j][s];
s = i,t = j + 1;
if(i + j + s + t == n + m + 2)
ans += dp[i][j][s];
ans %= Mod;
}
}
cout << ans;
return 0;
}
B. 快速排序
指针看不懂寄
简单看一下题目里给的快速排序。
\(\text{namespace\_std}\) 的快排
标签：int,long,模拟,ans,include,CSP,dp,回文 From： https://www.cnblogs.com/baijian0212/p/csp-3.html