[CYJian的水题大赛] 题解
CYJian
2018-07-16 16:42:47
## 八百标兵奔北坡
#### $Tag:$ DP
这道题最大的一个问题是"在北边"的定义。
自己可以作一下图,然后你就会发现这就是北偏东45°和北偏西45°这两条射线的上面的部分。
这个怎么做呢?
可以发现,对于$(i,j)$这一个点,$(i-1,j-1)$、$(i-1,j)$和$(i-1,j+1)$是在点$(i,j)$的"北边"。
所以我们可以设$f[i][j]$表示$(i,j)$这一个点到某一座山的最小切比雪夫距离。这样的话我们就可以得到下面这样的转移:
> 0.$f[i][j]$初值赋为无穷大。
>
> 1.点$(i,j)$是一座山时,$f[i][j]=0$
>
> 2.点$(i,j)$不是一座山时,$f[i][j] = min{f[i-1][j-1],f[i-1][j],f[i-1][j+1]}+1$
最后只需要每次读入点的坐标再愉快输出就好了。
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int s = 0, t = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') t = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + (ch ^ '0'); ch = getchar(); }
return s * t;
}
const int N = 1005;
int n;
int m;
int k;
int S[N][N];
int f[N][N];
bool Mountain[N][N];
inline int Min(int a, int b) { return a < b ? a : b; }
int main() {
n = read(), m = read(), k = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
S[i][j] = read();
memset(f, 63, sizeof(f));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(S[i][j] > S[i - 1][j] && S[i][j] > S[i][j - 1] && S[i][j] > S[i][j + 1] && S[i][j] > S[i + 1][j])
Mountain[i][j] = 1, f[i][j] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
f[i][j] = Min(Min(f[i][j], f[i - 1][j - 1] + 1), Min(f[i - 1][j] + 1, f[i - 1][j + 1] + 1));
for(int i = 1; i <= k; i++) {
int x = read();
int y = read();
if(f[x][y] == f[0][0]) puts("Pool Babingbaboom!");
else printf("%d\n", f[x][y]);
}
return 0;
}
```
## 灰化肥,会挥发
#### $Tag:$ 状压DP,BFS
这道题的话。
你会发现仓库的个数很少,可以状压。
我们设置状态$f[i][j]$表示已经走过的仓库集合为$i$且最后一个走到的仓库为$j$的时候最小走过的距离。
这样的话,状态转移方程也很显然了:
$$
f[i][j]=min(f[i][j],f[i\ xor\ (1 << j)][k] + dis[k][j])
$$
这里的$k$表示枚举$j$之前一个到的仓库是哪一个仓库,$dis[k][j]$表示从k到j的最短路。
$dis$数组只需要做$N$遍$BFS$就可以算出来了。
但是还要输出字典序最小的方案。
不过也好办,就是再设$g[i][j]$表示已经走过的仓库集合为$i$且最后一个走到的仓库为$j$的时候最小走过的距离的字典序最小的方案。
这个跟着转移一下就好了。
但是还需要在$f[i][j]$和转移值相等的情况下考虑$g[i][j]$转移的字典序大小。
维护好就行了。
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Node {
int x;
int y;
};
const int N = 16;
const int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n;
int m;
int s;
int jsq;
int f[1 << N][N];
string g[1 << N][N];
int To[N][N];
int Arrive[501][501];
char S[501][501];
Node F[N];
void BFS(Node F) {
memset(Arrive, 0, sizeof(Arrive));
queue<Node>q;
q.push(F);
Arrive[F.x][F.y] = 1;
while(!q.empty()) {
Node f = q.front(); q.pop();
for(int i = 0; i < 4; i++) {
int x = f.x + fx[i][0];
int y = f.y + fx[i][1];
if(x < 1 || y < 1 || x > n || y > m || S[x][y] == '*' || Arrive[x][y]) continue;
Arrive[x][y] = Arrive[f.x][f.y] + 1;
q.push((Node){x, y});
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= n; i++)
scanf("%s", S[i] + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(S[i][j] >= 'A' && S[i][j] <= 'Z')
F[S[i][j] - 'A' + 1] = (Node){i, j};
for(int i = 1; i <= s; i++) {
BFS(F[i]);
for(int j = 1; j <= s; j++) To[i][j] = Arrive[F[j].x][F[j].y] - 1;
}
memset(f, 63, sizeof(f));
f[1][1] = 0;
g[1][1] = "A";
for(int i = 2; i < (1 << s); i++) {
if(!(i & 1)) continue;
for(int j = 1; j <= s; j++) {
if(i & (1 << (j - 1)) == 0) continue;
for(int k = 2; k <= s; k++) {
if(i & (1 << (k - 1)) == 0 || j == k) continue;
if(f[i][k] > f[i ^ (1 << (k - 1))][j] + To[j][k]) {
f[i][k] = f[i ^ (1 << (k - 1))][j] + To[j][k];
g[i][k] = g[i ^ (1 << (k - 1))][j] + (char)(k + 'A' - 1);
}
else if(f[i][k] == f[i ^ (1 << (k - 1))][j] + To[j][k] && g[i][k] > (g[i ^ (1 << (k - 1))][j] + (char)(j + 'A' - 1)))
g[i][k] = (g[i ^ (1 << (k - 1))][j] + (char)(k + 'A' - 1));
}
}
}
int T = (1 << s) - 1;
int Min = f[T][2];
string res = g[T][2];
for(int i = 3; i <= s; i++) {
if(Min > f[T][i]) {
Min = f[T][i];
res = g[T][i];
}
else if(Min == f[T][i] && res > g[T][i])
res = g[T][i];
}
printf("%d\n", Min);
cout << res << endl;
return 0;
}
```
## 红鲤鱼与绿鲤鱼
#### $Tag:$ 数论,组合数
> 最最重要的一点:模数你看错了吗??正确的模数是998244853!!!
首先可以发现罚时的位置和最后一次$AC$对答案并没有影响。
这个我们可以直接加到答案里面去。
发现实际有影响的只有前$m$次$AC$的位置。
这些影响我们应该怎样计算呢??
首先发现不能分成每一种情况去计算,显然时间不允许我们这么做。
那么我们就应该把所有的情况一起计算。
可以想到的是所有情况中每一个位置上$AC$的总和都是一样的。
所以我们可以尝试只求出一个位置上$AC$的总和。
这就相当于我们把第一个位置上固定下来了,后面$(m+n-1)$个位置上有$(m-1)$个$AC$。组合数算一下方案数就好了。
然后对于每一个位置上答案的贡献不一样,但是是一个等差数列。因为每一个位置上都会有$C^{m-1}_{m+n-1}$个$AC$,所以可以求出每一个位置上单次贡献的和再乘上出现次数就好了。
完了吗??
并没有。。
上面我们只是分别求出了$WA$和所有方案的$AC$对答案的贡献,前者就直接是答案的一部分了,但是后者还需要除以所有的方案数,即$C^{m}_{n+m}$,但是由于要取模,所以需要算逆元。套用费马小定理就好了。
我们可以把式子写一下:
$ 5*(2*a+b+1)+5*C^{b-1}_{b+a-1}*(a+b+1)*(a+b)/2/C^{b}_{a+b} $
发现还可以化简:
$ 5*(2*a+b+1)+5*(a+b)!*(a+b+1)*b!*a!/(b-1)!/a!/(a+b)! $
$ 5*(2*a+b+1)+5*b*(a+b+1) $
这样就简单许多了。。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244853;
ll a;
ll b;
ll ksm(ll a, ll k) {
ll s = 1;
while(k) {
if(k & 1) s = (s * a) % mod;
k >>= 1;
a = (a * a) % mod;
}
return s;
}
int main() {
cin >> a >> b;//n就是a,m就是b
cout << 5 * (b * ((a + b + 1) % mod) % mod * ksm(2, mod - 2) % mod + 2 * a % mod + b + 1) % mod;
return 0;
}
```
~~(完结撒花)~~