天天滚动:4.14训练解题报告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

天天滚动:4.14训练解题报告

2023-04-14 22:59:51 来源：博客园

比赛传送门 \(\color{white}20230413Tainrnig\)

A. Ice Cave

题意：考虑糖豆人的蜂窝迷图中的一层，走过一个正常格子就会变成洞。给定当前地板局面（抽象成 \(n\times m\) 矩阵），以及起点和终点，求是否能在终点位置掉到下一层。特殊地，本题不允许停留。起点终点可以相同。\(n,m\le 500\)

【资料图】

判断是否能到达是容易的，dfs 即可。

如果终点本来有洞，到达终点即可。如果没有洞，到达终点后要向旁边走一格再回来。这也就要求旁边某个非洞的格子不能走。枚举邻居钦定成洞，判断是否可达即可。

对于起点等于终点的情况，只要将起点设成没有洞即可，避免了特殊处理。

By KrK

#include #include #pragma comment(linker, "/STACK:16000000")using namespace std;const int Maxn = 505;const int Maxd = 4;const int dy[Maxd] = {-1, 0, 1, 0};const int dx[Maxd] = {0, -1, 0, 1};int n, m;char B[Maxn][Maxn];int sr, sc;int fr, fc;bool tk[Maxn][Maxn];void Fill(int r, int c){if (B[r][c] == "X" || tk[r][c]) return;tk[r][c] = true;for (int i = 0; i < Maxd; i++)Fill(r + dy[i], c + dx[i]);}bool findPath(){fill((bool*)tk, (bool*)tk + Maxn * Maxn, false);Fill(sr, sc);return tk[fr][fc];}int main(){scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%s", B[i] + 1);B[i][0] = B[i][m + 1] = "X";}for (int j = 0; j <= m + 1; j++)B[0][j] = B[n + 1][j] = "X";scanf("%d %d", &sr, &sc); B[sr][sc] = ".";scanf("%d %d", &fr, &fc);if (B[fr][fc] == "X") { B[fr][fc] = "."; printf("%s\n", findPath()? "YES": "NO"); return 0; }for (int i = 0; i < Maxd; i++) {int nr = fr + dy[i], nc = fc + dx[i];if (B[nr][nc] == ".") {B[nr][nc] = "X";if (findPath()) { printf("YES\n"); return 0; }B[nr][nc] = ".";}}printf("NO\n");return 0;}

B. Bad Luck Island

有三个种族，分别出剪刀石头布，每一时刻随机两个人相遇，输者会被吃掉（平局则无事）。问每个种族活到最后的概率。\(n\le 100\)

显然可以 DP。设 \(f[x][y][z]\) 为一个三元组，表示在当前人数局面下，三个种族活到最后的概率。由于相同的无效，所以可钦定不同，人数一定会减少。简单算一下概率即可转移。

个人觉得此题中写记忆化搜索比较方便。

By cxm1024

#include using namespace std;#define ld long doublearray f[110][110][110];bool vis[110][110][110];array dfs(int x, int y, int z) {if (vis[x][y][z]) return f[x][y][z];vis[x][y][z] = 0;if (x == 0 || y == 0 || z == 0) {if (x && !z) return {1, 0, 0};else if (y && !x) return {0, 1, 0};else if (z && !y) return {0, 0, 1};else assert(0);}ld all = x * y + y * z + x * z;array res{0, 0, 0};auto solve = [&](array x, ld tmp) {for (int i = 0; i < 3; i++)res[i] += x[i] * tmp;};solve(dfs(x - 1, y, z), (ld)x * z / all);solve(dfs(x, y - 1, z), (ld)x * y / all);solve(dfs(x, y, z - 1), (ld)y * z / all);return f[x][y][z] = res;}signed main() {int x, y, z;scanf("%d%d%d", &x, &y, &z);auto res = dfs(x, y, z);printf("%.10Lf %.10Lf %.10Lf\n", res[0], res[1], res[2]);return 0;}

C. Woodcutters

题意：数轴上有 \(n\) 棵树，坐标为 \(x_i\)，高度为 \(h_i\)。砍倒时可以选择往左还是往右，但树之间不能重叠（点重叠也不行）。问最多砍多少棵树。

显然可以贪心。从左往右考虑每一棵树。如果可以往左倒则往左，否则如果可以往右就往右，否则不倒。过程中维护当前的右端点即可。正确性显然。

By cxm1024

#include using namespace std;int n;pair a[100010];signed main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].first, &a[i].second);a[n + 1].first = 2e9 + 7;int lst = -2e9, ans = 0;for (int i = 1; i <= n; i++) {if (a[i].first - a[i].second > lst)ans++, lst = a[i].first;else if (a[i].first + a[i].second < a[i + 1].first)ans++, lst = a[i].first + a[i].second;else lst = a[i].first;}printf("%d\n", ans);return 0;}

D. Queue

题意：有 \(n\) 个人，第 \(i\) 个人需要 \(t_i\) 时间服务，每个人希望等待时间不能超过他的服务时间。问最多能让多少人满意。\(n,t\le 10^5\)

首先贪心地找性质。

首先发现不满意的人一定可以扔到最后，不会对其他人产生影响，所以只需要考虑选一部分人满意即可。
满意的人中一定是从小往大排，因为如果前面的时间大于后面的时间，后面的人一定不满意（等待时间过长），于是先从小到大排序。

进一步地，我们可以发现，每加入一个人，当前的时间都会至少 \(\times 2\)，所以人数是 \(\log\) 级别的。

至此，有一个显然的 DP，\(f[i][j]\) 表示考虑了前 \(i\) 个人，选了 \(j\) 个的最小时间，则 \(f[i][j]=a[i]+\min f[k][j-1]\)，其中 \(\min\) 式可以简单地维护。复杂度 \(O(n\log n)\)。

By cxm1024

#include using namespace std;#define int long longint a[100010], f[100010][35], g[35];signed main() {memset(g, 0x3f, sizeof(g));g[0] = 0;int n;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++)for (int j = 34; j >= 1; j--) {if (g[j - 1] <= a[i]) {f[i][j] = g[j - 1] + a[i];g[j] = min(g[j], f[i][j]);}}int ans = 0;for (int i = 1; i <= 34; i++)if (g[i] < 1e18) ans = i;printf("%d\n", ans);return 0;}

继续观察可以发现，一定是每一步的人权值越小越好。即，如果某一次选择的人值为 \(x\)，存在一个值为 \(y(

据此，我们有一个更强的贪心的做法：排序后，从左到右考虑，如果能选则直接选中即可。

By KrK

#include #include using namespace std;typedef long long ll;const int Maxn = 100005;int n;int t[Maxn];ll cur;int res;int main(){scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &t[i]);sort(t, t + n);for (int i = 0; i < n; i++)if (cur <= t[i]) { res++; cur += t[i]; }printf("%d\n", res);return 0;}

E. Soldier and Cards

题意：有两堆牌总共组成 \(1\sim n\) 的排列，每次取顶上的比较，大的可以获取到对方的牌：先把对方的那张放到自己堆底，再把自己的那张放到堆底。没有牌的人输。问结束的步数以及输赢情况，或输出永远不会结束。\(n\le 10\)。

注意到 \(10!<4\times 10^6\)，所以可以暴力模拟，如果出现环则永远不会结束，否则一定会在 \(10!\) 步内结束。

判定环看起来需要用 set 之类的东西，而且不方便记录状态（比如我就通过一个排列和一个分界点来表示状态）。事实上，只要暴力模拟，超过了 \(10!\) 步就可以认定为环。

By KrK

#include #include using namespace std;const int lim = 4000000;int n;deque  Q1, Q2;int res;int main(){scanf("%d", &n);int n;scanf("%d", &n);for (int i = 0; i < n; i++) {int a; scanf("%d", &a);Q1.push_back(a);}scanf("%d", &n);for (int i = 0; i < n; i++) {int a; scanf("%d", &a);Q2.push_back(a);}while (res <= lim && !Q1.empty() && !Q2.empty()) {res++;if (Q1.front() > Q2.front()) { Q1.push_back(Q2.front()); Q1.push_back(Q1.front()); }else { Q2.push_back(Q1.front()); Q2.push_back(Q2.front()); }Q1.pop_front(); Q2.pop_front();}if (res <= lim)printf("%d %d\n", res, Q1.empty()? 2: 1);else printf("-1\n");return 0;}

F. Soldier and Number Game

题意：多次询问，每次给定一个 \(a,b\)，求 \(\frac{a!}{b!}\) 的质因数个数（\(p^c\) 算 \(c\) 次）。\(T\le 10^6,a,b\le 5e6\)。

显然可以把分子分母分别求出来相减。由于 \(n!\) 的质因子个数即为 \(1\sim n\) 的质因子个数之和，所以只需要求出每个值的质因子个数即可。可以通过线性筛/埃氏筛求出来。

By cxm1024

#include using namespace std;const int MAXN = 5e6;int prime[MAXN + 10], cnt[MAXN + 10], tot = 0;bool isprime[MAXN + 10];void getprime() {memset(isprime, 1, sizeof(isprime));isprime[0] = isprime[1] = 0;for (int i = 2; i <= MAXN; i++) {if (isprime[i]) {prime[++tot] = i;cnt[i] = 1;}for (int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {isprime[i * prime[j]] = 0;cnt[i * prime[j]] = cnt[i] + 1;if (i % prime[j] == 0) break;}}for (int i = 2; i <= MAXN; i++)cnt[i] += cnt[i - 1];}void Solve(int test) {int x, y;scanf("%d%d", &x, &y);printf("%d\n", cnt[x] - cnt[y]);}signed main() {getprime();int T;scanf("%d", &T);for (int i = 1; i <= T; i++) Solve(i);return 0;}

G. Divisibility by Eight

题意：有一个数字串，找出一个子序列能被 \(8\) 整除，或判断无解。\(n\le 100\)

我们知道，一个数能被 \(8\) 整除，当且仅当后三位是 \(8\) 的倍数。于是可以枚举选哪三位，复杂度 \(O(n^3)\)。注意不一定真的选三位，所以可以添加两个前导零（添加三个则可能选三个前导零，不合法）。

By cxm1024

#include using namespace std;signed main() {string s;cin >> s;s = "00" + s;for (int i = 0; i < s.size(); i++)for (int j = i + 1; j < s.size(); j++)for (int k = j + 1; k < s.size(); k++) {int x = (s[i] - "0") * 100 + (s[j] - "0") * 10 + (s[k] - "0");if (x % 8 == 0) {printf("YES\n%d\n", x);return 0;}}puts("NO");return 0;}

同样可以数位 DP，记录当前选的位数，以及目前对 \(8\) 取模的结果。

By KrK

#include #include #include using namespace std;string s;bool found;void Print(int num){    printf("YES\n");    printf("%d\n", num);}void Gen(int lvl, int from, int has){    if (lvl && has % 8 == 0) { Print(has); found = true; }    if (lvl < 3)        for (int i = from; i < s.length() && !found; i++)            Gen(lvl + 1, i + 1, has * 10 + s[i] - "0");}int main(){    cin >> s;    Gen(0, 0, 0);    if (!found) printf("NO\n");    return 0;}

H. Regular Bridge

题意：给定一个参数 \(k\)，构造一个简单无向图，使得每个点的度数均为 \(k\)，且图中存在割边。\(k\le 100\)。

容易发现，\(k\) 为奇数时可如下构造：

\(k\) 为偶数时一定无解

证明 1（ysl）：每个点的度数均为偶数，则一定存在欧拉回路，故存在环。
证明 2（cxm）：若存在，一定能构造只有一条割边的哑铃状图（如上面奇数）。此时，考虑其中一侧，设有 \(x\) 个点，则总度数为 \(xk\)，去掉割边后的子图度数和为 \(xk-1\)。而图的度数之和一定为偶数（边数等于度数之和的一半），所以不合法。

By cxm1024

#include using namespace std;signed main() {int k;scanf("%d", &k);if (k % 2 == 0) {puts("NO");return 0;}puts("YES");printf("%d %d\n", (k - 1) * 4 + 2, (k - 1) * (k - 1) * 2 + (k - 1) * 2 + 1 + k - 1);auto add = [](int x, int y, int z) {printf("%d %d\n", x * 2 - z, y * 2 - z);};auto solve = [&](int x) {for (int i = 2; i <= k; i++)add(1, i, x);for (int i = k + 1; i <= k + k - 1; i += 2)add(i, i + 1, x);for (int i = 2; i <= k; i++)for (int j = k + 1; j <= k + k - 1; j++)add(i, j, x);};solve(0), solve(1);puts("1 2");return 0;}

I. Vanya and Scales

题意：有 \(1,w,w^2,...\) 的砝码每种一个，问能否在天平上称出重量为 \(m\) 的物品（注意砝码可以放在物品同侧）。

容易发现，转化成类似 \(w\) 进制的形式，每一位可以是 \(-1,0,1\) 三种取值，即“平衡 \(k\) 进制”。类似平衡三进制的构造方式，从低往高考虑，如果为 \(0,1\) 则可以直接放；如果为 \(w-1\) 则可以在同侧放一个，使其变为 \(w\) 并往上进位；否则无解。

By cxm1024

#include using namespace std;signed main() {int w, m;scanf("%d%d", &w, &m);while (m > 0) {int tmp = m % w;if (tmp == 0 || tmp == 1);else if (tmp == w - 1) m++;else {puts("NO");return 0;}m /= w;}puts("YES");return 0;}

J. Vanya and Triangles

题意：给定平面上 \(n\) 个点，问有多少个三元组形成非退化三角形。\(n\le 2000,V\le 100\)

\(n^3\)

有 \(n^3\) 大暴力，我也不知道为什么可以过。

\(n^2V\)

转化一下，即为问有多少个三点共线。

有一个显然的 \(O(n^2V)\) 的算法，枚举两个点，然后枚举线上的所有坐标即可。

By cxm1024

#include using namespace std;int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}int n, x[2010], y[2010];bool vis[210][210];signed main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d%d", &x[i], &y[i]);x[i] += 101, y[i] += 101;vis[x[i]][y[i]] = 1;}long long ans = 0;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {int d = gcd(abs(x[i] - x[j]), abs(y[i] - y[j]));int dx = (x[i] - x[j]) / d, dy = (y[i] - y[j]) / d;int nowx = x[i], nowy = y[i];while (1) {nowx += dx, nowy += dy;if (nowx > 201 || nowy > 201 || nowx < 0 || nowy < 0)break;ans += vis[nowx][nowy];}nowx = x[i], nowy = y[i];while (1) {nowx -= dx, nowy -= dy;if (nowx > 201 || nowy > 201 || nowx < 0 || nowy < 0)break;ans += vis[nowx][nowy];}ans--;}ans /= 3;printf("%lld\n", (long long)n * (n - 1) * (n - 2) / 6 - ans);return 0;}

\(n^2\log n\)

可以将枚举两个端点，\(map\) 统计直线的出现次数，如果某个直线上有 \(k\) 个点，则 map 里将出现 \(\frac{k(k-1)}{2}\) 次。通过出现次数反推出点数，进而得出三点共线数即可。

\(n^2\)

可以将斜率和截距哈希后使用 unordered_map 储存。

K. Amr and Chemistry

题意：有 \(n\) 个数，每次操作可以选一个数左移/右移一位（二进制），问最少多少次能将他们变得相同。

考虑显然要找到他们二进制下的最长公共前缀，后面全部变成 \(0\)。假设前缀有 \(x\) 位，则找到 \(x\) 位后的第一个 \(1\)，必然要通过右移将其消掉。每个数都这样操作后，变为公共前缀+若干个 \(0\)。将其剩余 \(0\) 的个数排序后，根据初中数学经典贪心，应该选中位数作为最终 \(0\) 的个数。

最长公共前缀使用可以先整体扫描做到 \(n\log n\)，但这里我为了好写暴力枚举的长度，本质没有区别。

By cxm1024

#include using namespace std;int n, a[100010];string s[100010];signed main() {scanf("%d", &n);int len = 1e5, ans = 1e9;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);while (a[i] > 0) s[i] += a[i] % 2 + "0", a[i] /= 2;len = min(len, (int)s[i].size());}for (int i = 1; i <= len; i++) {string t;for (int j = s[1].size() - i; j < s[1].size(); j++)t += s[1][j];bool flag = 1;for (int j = 2; j <= n; j++) {for (int k = 1; k <= i; k++)if (s[j][s[j].size() - k] != t[t.size() - k])flag = 0;if (flag == 0) break;}if (flag == 0) break;int res = 0;vector v;for (int j = 1; j <= n; j++) {res += s[j].size() - i;int k = s[j].size() - i - 1, tmp = 0;for (; k >= 0; k--) {if (s[j][k] == "0") res--, tmp++;else break;}v.push_back(i + tmp);}sort(v.begin(), v.end());for (int j = 0; j < (v.size() - 1) / 2; j++)res += v[(v.size() - 1) / 2] - v[j];for (int j = (v.size() - 1) / 2; j < v.size(); j++)res += v[j] - v[(v.size() - 1) / 2];ans = min(ans, res);}printf("%d\n", ans);return 0;}

L. Guess Your Way Out! II

题意：有一棵 \(n\) 层的满线段树，节点按照左儿子 \(\times 2\)、右儿子 \(\times 2 + 1\) 的顺序标号。有一个叶子为特殊点。给定 \(q\) 个信息，每个形如 \(k,l,r,0/1\)，表示特殊点的第 \(k\) 层的祖先（即 \(n-k\) 次祖先）编号是否在 \([l,r]\) 内。保证 \(l,r\) 都是第 \(k\) 层的合法标号。你需要回答信息有冲突/有不止一个合法标号/输出特殊点标号。

做法一

\(k\) 次祖先在 \([l,r]\) 内，可以映射到特殊点在 \([l+000...,r+111...]\) 内（加号表示二进制后面添加若干位）。在 \([l,r]\) 外同理。于是现在有若干个限制，每个为在某区间内/在某区间外。于是可以离散化，每次将区间内/区间外+1，最后依次单点查询，如果被 \(q\) 个区间覆盖则全部满足。

实现上，可以用单点修改差分数组，最后求前缀和来简单地维护。最后查询答案时统计合法的个数以及任意一个合法解即可。个数为 \(0\) 则无解。

By cxm1024

#include using namespace std;#define int long longint v[100010], l[100010], r[100010], t[100010];int b[200010], cnt = 0, s[200010];signed main() {int h, q;scanf("%lld%lld", &h, &q);int ll = 1ll << (h - 1), rr = 1ll << h;b[++cnt] = ll, b[++cnt] = rr;vector > p;for (int i = 1; i <= q; i++) {scanf("%lld%lld%lld%lld", &v[i], &l[i], &r[i], &t[i]);l[i] <<= h - v[i], r[i] <<= h - v[i], r[i] += 1ll << (h - v[i]);if (t[i]) p.push_back({l[i], r[i]});else p.push_back({ll, l[i]}), p.push_back({r[i], rr});}for (auto [x, y] : p) b[++cnt] = x, b[++cnt] = y;sort(b + 1, b + cnt + 1);cnt = unique(b + 1, b + cnt + 1) - b - 1;for (auto [x, y] : p) {x = lower_bound(b + 1, b + cnt + 1, x) - b;y = lower_bound(b + 1, b + cnt + 1, y) - b;s[x]++, s[y]--;}for (int i = 1; i <= cnt; i++)s[i] += s[i - 1];int num = 0, ans = 0;for (int i = 1; i < cnt; i++)if (s[i] == q) {num += b[i + 1] - b[i];ans = b[i];}if (num == 0) puts("Game cheated!");else if (num >= 2) puts("Data not sufficient!");else printf("%lld\n", ans);return 0;}

做法二

同样是映射到叶子区间。考虑先处理在区间内的限制，再处理区间外的限制。

对于区间内，显然可以简单地区间求交来实现，最后得出答案的必要范围。

对于区间外，我们不能简单的直接实现，因为可能会打断区间的连续性，如下图：

此时合法区间分成了两段。这也是我赛时没有继续思考此思路的原因。

然而事实上，只需要将区间外的限制按左端点排序，从左往右考虑每个限制，即可保证区间的连续性。考虑使用归纳的思路，假设考虑完了前若干个限制，得到的合法区间为 \([l,r]\)，现在考虑下一个限制 \([x,y]\)（外），则只有如上图，被严格包含的情况下才会分裂，否则直接缩短即可。

如果遇到了上图的情况，意味着什么呢？由于是按照左端点从左到右排序的，这就意味着 \([l,x)\) 这段区间永远不会被后面的限制变为不合法！于是可以直接将 \([l,x)\) 这段区间统计答案，并把 \(l\) 右移到 \(y+1\) 的位置即可。

By zerokugi

int h, q;main(){ios::sync_with_stdio(0);cin.tie(0);scanf("%d%d", &h, &q);ll l = 1ll << (h-1), r = (1ll << h);vector rej;REP(itr, q){int i, t;ll x, y;scanf("%d%I64d%I64d%d", &i, &x, &y, &t);x = x << (h-i);y = (y+1) << (h-i);if(t == 1){l = max(l, x);r = min(r, y);}else{rej.eb(x, y);}}rej.eb(r, r);sort(ALL(rej));ll ans = -1;for(auto it : rej){ll x, y; tie(x, y) = it;if(r <= l) break;if(l < x){if(ans != -1 || l + 1 < x){cout << "Data not sufficient!" << endl;return 0;}ans = l;}l = max(l, y);}if(ans == -1) cout << "Game cheated!" << endl;else cout << ans << endl;return 0;}

这启示我们，当遇到看起来无法维护的信息时，不妨尝试将其排一下序，可能会有非常显著的效果。

关键词：