Loading... ## A - QQ solver 略 ## B - Caesar Cipher 判断字符串$S$能否循环移位成为$T$. 判断每一位差是否相等就行了, 如果是负数那么要+26. ## C - Graph Isomorphism 给定两个图判断是否同构. 好像是个NP-hard问题, 注意到$N$的范围很小, 所以枚举所有排列然后看能否对应就行了. 数组开小了WA了好久, 呆逼. ### 错误做法 比较点的度是否相同. 反例(感谢群聚): 化学里的邻间对结构, 同分异构体. ## D - Weak Takahashi 有障碍四连通平面里能够到达的最远点曼哈顿距离是多少. ### 做法 BFS模板题 ## E - Rook Path ### 题意 棋盘, 给定骑士坐标$(x_1,y_1)$和目标点$(x_2,y_2)$, 求$k$步后恰好移动到目标点的方案数. 在每一步中, 骑士可以移动到同行或同列任意点. ### 做法(吐槽?) 我是傻逼 我是傻逼 我是傻逼!!! 读错题读错了一天, 以为骑士移动是四连通的, 口胡了一个区间和有界的差分模型搞排列组合(OS: abc的E什么时候这么难了), 然后群友说DP, 当时想了半天,这咋DP啊??? 然后今天突然意识到, 诶?骑士是不是可以移动到行列任意位置来着... 然后就会了. 艹. 水题. DP状态就只包含$dp[x==x2?1:0][y==y2?1:0]$, 然后按$k$阶段DP就行了. ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define K 1000006 #define MOD 998244353 int h, w, k; int x_1, y_1, x_2, y_2; int dx, dy; ll dp[2][2]; int main() { cin >> h >> w >> k; cin >> x_1 >> y_1 >> x_2 >> y_2; if (x_1 == x_2 && y_1 == y_2) dp[1][1] = 1; else if (x_1 == x_2) dp[1][0] = 1; else if (y_1 == y_2) dp[0][1] = 1; else dp[0][0] = 1; for (int i = 1; i <= k; i++) { ll tmp[2][2]; tmp[1][1] = (dp[1][0] + dp[0][1]) % MOD; tmp[1][0] = ((w - 2) * dp[1][0] + dp[0][0] + (w - 1) * dp[1][1]) % MOD; tmp[0][1] = ((h - 2) * dp[0][1] + dp[0][0] + (h - 1) * dp[1][1]) % MOD; tmp[0][0] = (dp[0][0] * (w - 2 + h - 2) + dp[1][0] * (h - 1) + dp[0][1] * (w - 1)) % MOD; memcpy(dp, tmp, sizeof(dp)); } cout << dp[1][1] << endl; return 0; } ``` ## F - Simple Operations on Sequence ### 题意 给定序列$A$和$B$, 支持对$A$进行以下两种操作: 1. 将某个数+1或者-1, 代价为$x$ 2. 交换$A$中某两个相邻数字, 代价为$Y$ 求将$A$变为$Y$的最小开销 ### 分析 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏