gdfzoj 比赛题解
2022/8/26 6:23:42
本文主要是介绍gdfzoj 比赛题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
本次比赛:初一训练5.21 / 编号531
题目难度中等偏上,有几题比较简单,有两三题较难。
T1
题目:gdfzoj1441
思路:
算是一道暴力题。
由于 \(h_{i, j}\) 范围很小,考虑二分答案。
二分答案的范围应该是 \([0, 110]\)。
对于 chk()
函数,可以暴力枚举所有差为 \(\texttt{mid}\) 的数对,并使用 bfs
强行搜索检验。
bfs
比较容易实现,重点在于 chk()
的枚举。
我们明显可以枚举所有数对的较小值,较大值自然就是 \(\text{较小值} + \texttt{mid}\)。
但是直接这样枚举太过鲁莽,可以剪枝。
注意到 \(h_{1, 1}\) 与 \(h_{n, n}\) 是必定会经过的。
数对较大值 的 最小值
应该是 \(\max(h_{1, 1}, h_{n, n})\)。
因此可得,数对较小值 的 最小值
应该是 \(\max(h_{1, 1}, h_{n, n}) - \texttt{mid}\)。
再来看 数对较小值 的 最大值
,它是 \(\min(h_{1, 1}, h_{n, n})\)。这个稍微有点难想。
思路总结:
- 读入数据。
- 写一份
bfs
,参数有 \(\texttt{最高点}\) 与 \(\texttt{最低点}\),用于检验这种情况是否可行。 - 写二分答案必须用到的
chk()
函数,实现如上所述,思考上略有困难。 - 写二分,然后输出。
代码:
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #define N 105 using namespace std; int n, a[N][N]; int Max, Min; void Input() { scanf("%d", &n); if (n == 1) //特判 { printf("0"); exit(0); } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); Max = max(a[1][1], a[n][n]); Min = min(a[1][1], a[n][n]); } struct Node { int x, y; }; int dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool vis[N][N]; bool bfs(int minn, int maxn) //非常模板的 bfs 只是要判一下数的范围。 { memset(vis, false, sizeof(vis)); //切记清空数组 queue <Node> Q; Q.push( (Node){1,1} ); vis[1][1] = true; while (!Q.empty()) { int x = Q.front().x, y = Q.front().y; Q.pop(); if (x == n && y == n) return true; for (int i = 0; i < 4; i++) { int dx = x + dict[i][0], dy = y + dict[i][1]; if (!(1 <= dx && dx <= n && 1 <= dy && dy <= n)) continue; if (vis[dx][dy]) continue; if (minn <= a[dx][dy] && a[dx][dy] <= maxn) //唯一和板子不一样的地方。 { vis[dx][dy] = true; Q.push( (Node){dx, dy} ); } } } return false; } bool chk(int ans) //较难理解。 { int l = Max - ans, r = Min; for (int i = l; i <= r; i++) if (bfs(i, i + ans)) return true; return false; } int FIND() { int pos = -1, L = 0, R = 110; while (L < R) { int mid = (L + R) >> 1; if (chk(mid)) R = mid, pos = R; //答案求最大值,pos 应该在 R 这一边更新。 else L = mid + 1; } return pos; } int main() { Input(); printf("%d", FIND()); return 0; }
T2
题目:gdfzoj1942
思路:
个人觉得这题最难。
重要的前置知识:分数取模。
由于篇幅原因,不详细证明,使用到了 费马小定理 与 逆元。
这里只给出结论:\(\dfrac{x}{y}\equiv x \cdot y^{p-2} \pmod{p}\)
通过样例得知,先手赢一场比赛的概率为 \(\dfrac{2}{3}\)。
进一步地,我们设先手赢第 \(n\) 场比赛的概率为 \(p_n\),则先手输掉第 \(n\) 场比赛的概率为 \((1 - p_n)\)。
容易写出状态转移方程(假设『我』代表先手,『他』代表后手):
\[\text{我赢的概率} = \text{上一场我赢的概率} \times \text{这一场他输的概率} +\text{上一场我输的概率} \times \text{这一场我赢的概率} \]转换成数学语言:
\[\begin{aligned}p_i & = p_{i-1} \times \dfrac{1}{3} + (1 - p_{i-1}) \times \dfrac{2}{3}\\ & = p_{i-1} \times \dfrac{1}{3} + \dfrac{2}{3} - p_{i-1} \times \dfrac{2}{3}\\ & = \dfrac{2}{3} - \dfrac{1}{3} \times p_{i-1}\end{aligned} \]整合一下,标准的状态转移方程就是:
\[p_i = \begin{cases}\dfrac{2}{3} & i = 1\\\\\dfrac{2}{3} - \dfrac{1}{3} \times p_{i-1} & i \ge 2\end{cases} \]但是这样的效率是 \(O(n)\) 的,还需要优化。
最快的办法是找规律,如下。
场数 | 先手获胜的概率 | 后手获胜的概率 |
---|---|---|
\(1\) | \(\dfrac{2}{3}\) | \(\dfrac{1}{3}\) |
\(2\) | \(\dfrac{4}{9}\) | \(\dfrac{5}{9}\) |
\(3\) | \(\dfrac{14}{27}\) | \(\dfrac{13}{27}\) |
\(4\) | \(\dfrac{40}{81}\) | \(\dfrac{41}{81}\) |
规律如下,其实还是比较容易找的。
若当前是第 \(n\) 场比赛,则:
- \(分母 = 3^{场数}\);
- 先手获胜与后手获胜的概率的分子总是相差 \(1\)。
进一步地,可以得到下面这条式子:
\[p_n = \begin{cases} \dfrac{(3^n + 1)}{2 \times 3^n} & n\equiv1\pmod{2}\\ \\ \dfrac{(3^n - 1)}{2 \times 3^n} & n\equiv0\pmod{2}\end{cases} \]然后对着它打代码就完事了,照着 $$\dfrac{x}{y}\equiv x \cdot y^{p-2} \pmod{p}$$ 这条结论模即可。
需要注意,此处需要使用快速幂来达到 \(O(\log n)\) 的速度求 \(3^n\)。
代码:
#include <iostream> #include <cstdio> #define LL long long using namespace std; LL ksm(LL x, int y, int p) //x^y mod p { if (y == 1) return x % p; LL t = ksm(x, y >> 1, p); t = (t * t) % p; if (y & 1) t = (t * x) % p; return t; } int main() { int n, p = 998244353; scanf("%d", &n); if (n & 1) { LL POW = ksm(3, n, p); LL x = (POW + 1) % p, y = (2 * POW) % p; y = ksm(y, p-2, p); printf("%lld", (x * y) % p); } else { LL POW = ksm(3, n, p); LL x = (POW - 1) % p, y = (2 * POW) % p; y = ksm(y, p-2, p); printf("%lld", (x * y) % p); } return 0; }
T3
题目:gdfzoj2232
思路:
T2 有点难啊,T3 轻松多了。
我们都知道,合法的括号序列有一个特征:
- 假设
(
代表 \(1\),)
代表 \(-1\); - 统计转换为数字的序列的前缀和。
- 如果前缀和中出现了负数,表明括号序列不成立。
对于本题,我们可以先确认更改的字符是 (
还是 )
。
假设需要更改左括号(如果是右括号,只需要倒着扫)。
统计前缀和,如果某个前缀和出现了负数,说明可以更改从开头至当前位置所有左括号。
代码实现上,如果需要更改右括号,可以将左括号改成右括号,并将字符串翻转。
这样,代码就具有良好的扩展性了。
代码:
#include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; string s; int len, lcnt, rcnt; void Input() { cin >> s; len = s.length(), lcnt = 0, rcnt = 0; for (int i = 0; i < len; i++) { if (s[i] == '(') lcnt++; else rcnt++; } } void Reverse() { //每个字符翻转+整串翻转 for (int i = 0; i < len; i++) { if (s[i] == '(') s[i] = ')'; else s[i] = '('; } reverse(s.begin(), s.end()); } void solve() { int sum = 0, cnt = 0; for (int i = 0; i < len; i++) { if (s[i] == '(') sum++; else sum--, cnt++; if (sum < 0) { printf("%d", cnt); return; } } printf("0"); } int main() { Input(); if (lcnt > rcnt) Reverse(); solve(); return 0; }
T4
题目:gdfzoj2233
思路:
没有思路,这是一道暴力题。
由于规模较小,采用 dfs
更优。
一遍深搜,一遍记录当前走过的字符串。
写一个 chk()
函数判断字符串是否为完美字符串即可。
代码:
#include <iostream> #include <cstdio> using namespace std; char a[7][7]; bool vis[7][7]; int maxn, dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool chk(string s) { int len = s.length(); if (len & 1) return false; int tlen = len >> 1; for (int i = 0; i < tlen; i++) if (s[i] == ')') return false; for (int i = tlen; i < len; i++) if (s[i] == '(') return false; return true; } int n; void dfs(int x, int y, string s) { if (chk(s)) { int len = s.length(); maxn = max(maxn, len); return; } for (int i = 0; i < 4; i++) { int dx = x + dict[i][0], dy = y + dict[i][1]; if (!(1 <= dx && dx <= n && 1 <= dy && dy <= n)) continue; if (vis[dx][dy]) continue; vis[dx][dy] = true; dfs(dx, dy, s + a[dx][dy]); vis[dx][dy] = false; } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j]; vis[1][1] = true; string tql = ""; tql += a[1][1]; dfs(1, 1, tql); printf("%d", maxn); return 0; }
T5
题目:gdfzoj2234
本题名声过大,了解过括号序列的人肯定做过这题。
故,不细述。
T6
题目:gdfzoj2235
思路:
此题明显是最短路。
我们需要求任意两点的最短路的最大值,即全源最短路。
本题共有 \(n^2\) 个点,如果跑 Floyd 时间复杂度是 \(O(n^6)\),非常极限,不是本题正解。
但是,我又不会写 Johnson 全源最短路,怎么办呢?
每个点朝四周建边,容易发现,边的数量不超过 \(4 \times n^2\)。
想到这里,明显可以跑 \(n^2\) 次 dijkstra 实现,因为当边数较小时,跑多次 dijkstra 会比 Floyd 快。
此处 dijkstra 是使用优先队列实现。
那么就很容易写出代码了。
思路总结:
- 读入数据。
- 每个点朝四周建边。
- 写一个 dijkstra 的模版。
- 统计最大值,输出。
代码:
#include <iostream> #include <cstdio> #include <queue> #define N 905 #define M 7205 //905 * 4 * 2 = 7200 using namespace std; int n, nn, A, B; int dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool a[35][35]; struct Node { int now, nxt, w; }e[M]; int head[N], cur; void add(int x, int y, int k) { e[++cur].now = y; e[cur].nxt = head[x]; e[cur].w = k; head[x] = cur; } struct Dis { int pos, len; bool operator <(const Dis &t) const { return len > t.len; } }dis[N]; bool vis[N]; int dijkstra(int first) { priority_queue <Dis> Q; for (int i = 1; i <= nn; i++) dis[i].pos = i, dis[i].len = 2147483647, vis[i] = false; dis[first].len = 0; Q.push(dis[first]); while (!Q.empty()) { int topi = Q.top().pos; Q.pop(); if (vis[topi]) continue; vis[topi] = true; for (int i = head[topi]; i; i = e[i].nxt) if (dis[topi].len + e[i].w < dis[e[i].now].len) { dis[e[i].now].len = dis[topi].len + e[i].w; Q.push(dis[e[i].now]); } } //此处有是惟一与普通模版不同的地方,需要找出最大值。 int maxn = 0; for (int i = 1; i <= nn; i++) maxn = max(maxn, dis[i].len); return maxn; } void Input() { scanf("%d%d%d", &n, &A, &B); nn = n * n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { char x; cin >> x; if (x == '(') a[i][j] = true; } } void get_edge() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 0; k < 4; k++) { int x = i + dict[k][0], y = j + dict[k][1]; if (!(1 <= x && x <= n && 1 <= y && y <= n)) continue; int t1 = n * (i-1) + j, t2 = n * (x-1) + y; if (a[i][j] == a[x][y]) add(t1, t2, A); else add(t1, t2, B); } } void solve() { int maxn = 0; for (int i = 1; i <= nn; i++) maxn = max(maxn, dijkstra(i)); printf("%d", maxn); } int main() { Input(); get_edge(); solve(); return 0; }
T7
题目:gdfzoj2958
思路:
dp 题,较简单。
注意到数据范围 \(n \le 1000\),容易想到时间复杂度大约是 \(O(n^2)\) 左右的级别。
设 \(dp_i\) 表示:第 \(i\) 个蒟蒻留下的最多人数。
容易想到转移方程(表达式可能不太规范):
\[dp_i = \huge[\small\max\limits_{j=1}^{i-1} dp_j \space(\text{满足} |a_i-a_j| \ne 1) \huge] \small + 1 \]貌似代码比这东西容易理解多了。
代码:
#include <iostream> #include <cstdio> #include <cmath> #define N 1005 using namespace std; int a[N], dp[N]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i] = 1; //注意初始化。 for (int i = 1; i <= n; i++) for (int j = 1; j < i; j++) if (abs(a[i] - a[j]) != 1) dp[i] = max(dp[i], dp[j] + 1); printf("%d", dp[n]); return 0; }
结语
感觉这次比赛比较综合。
搜索、二分、dp、最短路、数学题、括号序列,这几种常考题型及算法都出了。
还要继续加油!
首发:2022-05-27 13:23:18
这篇关于gdfzoj 比赛题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-22[开源]10.3K+ Star!轻量强大的开源运维平台,超赞!
- 2024-11-21Flutter基础教程:新手入门指南
- 2024-11-21Flutter跨平台教程:新手入门详解
- 2024-11-21Flutter跨平台教程:新手入门与实践指南
- 2024-11-21Flutter列表组件教程:初学者指南
- 2024-11-21Flutter列表组件教程:新手入门指南
- 2024-11-21Flutter入门教程:初学者必看指南
- 2024-11-21Flutter入门教程:从零开始的Flutter开发指南
- 2024-11-21Flutter升级教程:新手必读的升级指南
- 2024-11-21Flutter升级教程:轻松掌握Flutter版本更新