最近几天都没写博客，真是没什么时间写了，专题卡着，一周四场比赛，场场爆零，补题都补傻了。第一场还差两题可能今天补掉吧，昨天的杭电也是完全没动，感觉...很烦

第二场牛客断断续续也是补了几天...大概一天也就两题这样，然后补了六题感觉差不多了，就先放上来好了。

以下题解包括：\(A \ \ \ D \ \ \ E \ \ \ F \ \ \ H \ \ \ J\)

比赛地址： https://ac.nowcoder.com/acm/contest/882#question

【A】 Eddy Walker 数学

题目极长，赛中看了几眼读不下去了，然后就放掉了。问别人通过的全是暴力找规律...

给定圆上有 n 个点，初始点 0，每次会向左或向右移动一步（等可能），如果某一时刻所有点均被至少访问过一次则停止移动，问最终停留在 m 点的概率。

若 \(m \neq 0\) 且 \(n \neq 1\)，则 \(ans = \frac{1}{n-1}\)。emmm公式咋得到的建议去博客 DeaphetS 看，我懒得敲了....然后答案就是再求个逆元就完事了。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; ll q_pow(ll a, ll b) { ll res = 1; while(b) { if(b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; } int main() { int t; scanf("%d", &t); ll ans = 1; while(t--) { int n, m; scanf("%d%d", &n, &m); if(n == 1) { printf("%lld\n", ans); continue; } if(m == 0){ ans = 0; } else { ans = ans * q_pow((long long)n-1, (long long)mod-2) % mod; } printf("%lld\n", ans); } return 0; }

【D】 Kth Minimum Clique 优先队列BFS+状压

给定一个有 n 个顶点的无向图，求它的第 K 小完全子图（团）。

反着推，最小团就是空集，不断向空集里加点，从而找到第 K 小团。

采用优先队列，把权值小的团出队，拿去拓展其他状态。为了不重复加点，需要每次在当前状态的已选中的点中下标最大的点后面拓展，这样就可以把所有点都遍历一次了。

用 bitset 来保存点连接状态可以直接判断该点是否与团的每个点相连。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 100+5; ll w[maxn]; char a[maxn][maxn]; bitset<maxn> mp[maxn]; struct G { bitset<maxn> st; ll sum; bool operator < (const G &x) const { return sum > x.sum; } }; ll bfs(int n, int k) { priority_queue<G> q; G temp; temp.st.reset(); // clear temp.sum = 0; q.push(temp); while(!q.empty()) { G u = q.top(); q.pop(); k --; // cout << u.st << endl; // cout << u.sum <<endl; if(k == 0) { return u.sum; } int pos = 0; for(int i = 0; i < n; i++) { if(u.st[i]) pos = i+1; } for(int i = pos; i < n; i++) { if(u.st[i] == 0) { if((u.st & mp[i]) == u.st) { u.st[i] = 1; u.sum += w[i]; q.push(u); u.st[i] = 0; u.sum -= w[i]; } } } } return -1; } int main() { int n, k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) { scanf("%lld", &w[i]); } for(int i = 0; i < n; i++) { scanf("%s", a[i]); } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(a[i][j] == '1') { mp[i].set(j); // mp[i][j] = 1 } } } printf("%lld\n", bfs(n, k)); return 0; }

【E】 MAZE 线段树+矩阵乘法

给定一个 n*m 的迷宫，0表示能走的路，1表示不能。每次可以向左、向右、向下移动一格且不能回头。有 q 次操作，1表示把 [x, y] 位置进行翻转（0变1、1变0），2表示查询 “从 [1, x] 到 [n, y]的方案数”。【\(n \leq 5e4、m \leq 10\)】

首先，看到这个取值范围就知道这题肯定怪怪的对吧。然后?我也不会，以下题解来自 [https://www.cnblogs.com/DeaphetS/p/11222740.html] 。(https://www.cnblogs.com/DeaphetS/p/11222740.html)

设 \(f(i,j)\) 为走到 \((i,j)\) 的方案数，且第 \(i\) 行里包含点 \((i,j)\) 的区间为 \([l,r]\)，则有 \(f(i,j)=\sum^{r}_{k=l} f(i−1,k)\)，这里的 \(k\) 就代表着从前一行的第 \(k\) 列走下来。可以发现这个转移方程可以转换成一个矩阵形式： \[(f(i,1),f(i,2),...,f(i,m))=(f(i−1,1),f(i−1,2),...,f(i−1,m))*A\]

其中 \(A\) 为状态转移矩阵。求从第 \(i−1\) 行到第 \(i\) 行的转移矩阵可以用 \(o(m^2)\) 的时间复杂度来实现的。而最后一行的答案就是第一行的状态矩阵乘上这 \(n\) 行转移矩阵的乘积。在本题中，由于给出了起点和终点，所以若设这 \(n\) 行转移矩阵的乘积为\(A\)，则答案就是 \(A(a,b)\)。用线段树维护每行的矩阵以及区间的矩阵乘积即可。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 5e4+5; const int maxm = 10+5; int n, m, q; int a[maxn][maxm]; struct mat { ll a[maxm][maxm]; inline mat operator * (const mat &x) const { mat temp; memset(temp.a, 0, sizeof(temp.a)); for(int i = 1; i <= m; i++) { for(int j = 1; j <= m; j++) { for(int k = 1; k <= m; k++) { temp.a[i][j] += 1ll * a[i][k] * x.a[k][j] % mod; temp.a[i][j] = temp.a[i][j] % mod; } } } return temp; } }T[maxn << 2]; void build(int l, int r, int rt) { if(l == r) { memset(T[rt].a, 0, sizeof(T[rt].a)); for(int i = 1; i <= m; i++) { int k = i; while(k >= 1 && a[l][k] == 0) { T[rt].a[i][k] = 1; k--; } k = i; while(k <= m && a[l][k] == 0) { T[rt].a[i][k] = 1; k++; } } return ; } int mid = (l+r) >> 1; build(l, mid, 2*rt); build(mid+1, r, 2*rt+1); T[rt] = T[2*rt] * T[2*rt+1]; } void update(int l, int r, int rt, int x) { if(l == r) { memset(T[rt].a, 0, sizeof(T[rt].a)); for(int i = 1; i <= m; i++) { int k = i; while(k >= 1 && a[l][k] == 0) { T[rt].a[i][k] = 1; k--; } k = i; while(k <= m && a[l][k] == 0) { T[rt].a[i][k] = 1; k++; } } return ; } int mid = (l+r) >> 1; if(x <= mid) { update(l, mid, 2*rt, x); } else { update(mid+1, r, 2*rt+1, x); } T[rt] = T[2*rt] * T[2*rt+1]; } int main() { scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i++) { char s[15]; scanf("%s", s+1); for(int j = 1; j <= m; j++) { a[i][j] = s[j]-'0'; } } build(1, n, 1); while(q--) { int f, x, y; scanf("%d%d%d", &f, &x, &y); if(f == 1) { if(a[x][y] == 0) { a[x][y] = 1; } else { a[x][y] = 0; } update(1, n, 1, x); } else { printf("%lld\n", T[1].a[x][y]); } } return 0; }

【F】 Partition problem 暴力搜索

三个人在那边互相否定，结果没一个复杂度算对的 ······

有 2*n 个人要平均分成两队，给定 \(v[i, j]\) 表示 \(i\) 和 \(j\) 在不同队伍的“竞争值”。问最大的竞争值是多少。

爆搜，\(C^{14}_{28}*28 = 1123264800\) （应该没算错）。当然加了一点点的剪枝，不过好像真的很暴力就是了。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 35; int n; int a[maxn][maxn]; ll sum[maxn] = {0}; int choose[maxn] = {0}; ll ans = 0; void dfs(int now, int cnt, ll temp) { if(cnt*2 == n) { ans = max(ans, temp); return ; } for(int i = now+1; i <= n; i++) { if(choose[i]) { continue; } choose[cnt+1] = i; ll x = temp; for(int j = 1; j <= cnt; j++) { x = x - 2ll*a[i][choose[j]]; } x = x + sum[i]; dfs(i, cnt+1, x); choose[cnt+1] = 0; } } int main() { scanf("%d", &n); n *= 2; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); sum[i] += 1ll*a[i][j]; } } choose[1] = 1; dfs(1, 1, sum[1]); printf("%lld\n", ans); return 0; }

【H】 Second Large Rectangle 单调栈

我也不知道为何比赛中就死机了，对着一个假算法debug到死 ······

得定一个由 01 构成的矩阵，求这个矩阵里完全由 1 构成的 第二大矩形。

其实就是维护每一点上方的连续 1 的数量，然后和之前一列的高度进行比较，之前的大就不能用之前的（出队），然后计算 3 次可能的矩形面积。然后...就没有然后了。之前自己的假算法卡死在了去重...我也不知道脑子为啥抽了。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e3+5; char a[maxn][maxn]; int num[maxn][maxn]; struct node { int h, w; }; int main() { // fopen("in.txt", "r", stdin); // fopen("out.txt", "w", stdout); int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", a[i]+1); } int MAX = 0, ans = 0; for(int i = 1; i <= n; i++) { stack<node> s; for(int j = 1; j <= m; j++) { if(a[i][j] == '0') { num[i][j] = 0; } else { num[i][j] = num[i-1][j]+1; } } for(int j = 1; j <= m+1; j++) { int w = 0; while(!s.empty() && s.top().h > num[i][j]) { int h = s.top().h; w += s.top().w; s.pop(); if(h*w >= MAX) { ans = MAX; MAX = h*w; } else if(h*w > ans) { ans = h*w; } if((h-1)*w >= MAX) { ans = MAX; MAX = (h-1)*w; } else if((h-1)*w > ans) { ans = (h-1)*w; } if(h*(w-1) >= MAX) { ans = MAX; MAX = h*(w-1); } else if(h*(w-1) > ans) { ans = h*(w-1); } } s.push(node{num[i][j], w+1}); } } printf("%d\n", ans); return 0; }

【J】 Subarray 贪心

固定长度为 1e9 的字符串只包含 1 和 -1 ，其中有 \(n (\leq 1e6)\) 段由 1 构成且 1 的数量小于 1e7，其余都是 -1。问存在多少个区间 \([l,r]\)，使得区间和大于0。

贪心。先预处理对于每个 1 区间左端和右端分别可以延伸到哪里。之后需要从头到尾依次枚举，注意需要用 pos 标记以防重复。由于存在负值所以数组需要翻倍。由于不存在重复跑一个点，因此复杂度最多也是 1e7 级别。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 1e9; const int mod = 1e9 + 7; const int maxn = 1e6+5; int l[maxn], r[maxn]; int lmore[maxn], rmore[maxn]; int f[20000005]; int main() { int n, s; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d%d", &l[i], &r[i]); } l[0] = r[0] = -1; l[n+1] = r[n+1] = inf; s = r[1] - l[1] + 1; for(int i = 1; i <= n; i++) { rmore[i] = min(s, l[i+1]-r[i]-1); // 多减 1 保证大于 0 s = s - (l[i+1]-r[i]-1); if(s < 0) { s = 0; } s = s + (r[i+1]-l[i+1]+1); } s = r[n] - l[n] + 1; for(int i = n; i >= 1; i--) { lmore[i] = min(s, l[i]-r[i-1]-1); s = s - (l[i]-r[i-1]-1); if(s < 0) { s = 0; } s = s + (r[i-1]-l[i-1]+1); } s = 10000000; f[s] = 1; ll ans = 0, temp = 1; int pos = 0; for(int i = 1; i <= n; i++) { for(int j = max(pos, l[i]-lmore[i]); j <= r[i]+rmore[i]; j++) { if(j >= l[i] && j <= r[i]) { s ++; ++f[s]; temp = temp + f[s]; } else { s --; ++f[s]; temp = temp - (f[s+1] - 1); } ans = ans + (temp - f[s]); } pos = r[i] + rmore[i] + 1; } printf("%lld\n", ans); return 0; }

转载于:https://www.cnblogs.com/Decray/p/11232973.html