Solution - P7204
2022/2/2 23:12:57
本文主要是介绍Solution - P7204,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目传送门
Solution.
我们首先发现答案是具有单调性的:砸的雪球越多构成「完美单词」的机率就越大。所有我们可以进行二分答案。
然后在 check
里面进行的操作有如下几种:
- 统计单词序列中每个单词出现的次数
- 删除位置在 \(1 \sim x\) 的字母( \(x\) 为二分的咋的雪球数量)
- 判断区间是否有重复字母,即判断区间每种字母的数量是否大于 \(1\)
我们可以发现以上的操作都可以用树状数组进行维护,于是就按以上思路进行二分即可。
复杂度: \(O(26×q\log^2n)\)
Code.
开 O2 能卡过
#include <bits/stdc++.h> #define int long long using namespace std; template <typename T> void read (T &x) { x = 0; T f = 1; char ch = getchar (); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar (); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar (); } x *= f; } char For_Print[25]; template <typename T> void write (T x) { if (x == 0) { putchar ('0'); return; } if (x < 0) { putchar ('-'); x = -x; } int poi = 0; while (x) { For_Print[++poi] = x % 10 + '0'; x /= 10; } while (poi) putchar (For_Print[poi--]); } template <typename T> void print (T x, char ch) { write (x); putchar (ch); } const int maxn = 1e5; int n, q; namespace T { int t[31][maxn + 5]; #define lowbit(x) x & -x void add(int l, int x, int k) { for (; x <= n; x += lowbit(x)) { t[l][x] += k; } } int ask(int l, int x) { int ans = 0; for (; x; x -= lowbit(x)) ans += t[l][x]; return ans; } } using namespace T; struct node { int l, r; } p[maxn + 5]; char c[maxn + 5]; int a[maxn + 5]; bool check(int x) { memset(t, 0, sizeof(t)); for (int i = 1; i <= n; i++) add(c[i] - 'a', i, 1); for (int i = 1; i <= x; i++) add(c[a[i]] - 'a', a[i], -1); for (int i = 1; i <= q; i++) { for (int j = 0; j < 26; j++) { if (ask(j, p[i].r) - ask(j, p[i].l - 1) > 1) return false; } } return true; } int half(int l, int r) { if (l == r) return l; if (l + 1 == r) { if (check(l)) return l; else return r; } int mid = (l + r) >> 1; if (check(mid)) return half(l, mid); else return half(mid, r); } signed main() { scanf("%s", c + 1); getchar(); n = strlen(c + 1); read(q); for (int i = 1; i <= q; i++) { read(p[i].l), read(p[i].r); } for (int i = 1; i <= n; i++) { read(a[i]); } write(half(0, n)); return 0; }
这篇关于Solution - P7204的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南