[CYJian的水题大赛] 题解

CYJian

2018-07-16 16:42:47

Personal

## 八百标兵奔北坡 #### $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; } ``` ~~(完结撒花)~~