代码编织梦想

在我的博客内阅读。

A,B 略。

C 考虑将 K K K 二进制表示下的每个 1 1 1 换成 2 2 2 即可。

D 维护一个小根堆在线维护前 K K K 大元素即可。

E 发现首项只可能是 a 1 a_1 a1 a 1 + 1 a_1 + 1 a1+1,随后枚举公差判断是否可行即可,细节略多。

ABC234F - Reordering

题意:给定一个字符串 S S S,问选出里面的部分字母并重排后能得到多少种不同字符串。 ∣ S ∣ ≤ 5000 |S|\le 5000 S5000,模 998244353 998244353 998244353

考虑能构成的字符串只与字符集合有关。我们不妨从 a \texttt a a 开始,一个个的加字符。设 f i , j f_{i, j} fi,j 表示前 i i i 种字符中,填满了 j j j 个格子的方案数。转移的时候考虑第 i i i 个字符我们填 k k k 个进去,就相当于是 j − k + 1 j - k + 1 jk+1 个不同的桶里面放 k k k 个相同球,可以有空桶,所以转移如下:
f i , j = ∑ k = 0 min ⁡ ( j , g ( i ) ) ( k j ) f i − 1 , j − k f_{i,j} = \sum_{k = 0}^{\min(j, g(i))}\binom k jf_{i- 1, j - k} fi,j=k=0min(j,g(i))(jk)fi1,jk
g ( i ) g(i) g(i) 为第 i i i 种字符在原串中的出现次数。

那么 ∑ f 26 , i \sum f_{26, i} f26,i 就是答案。

const int maxn = 5005;
char s[maxn];
modint f[26][maxn], fac[maxn], ifac[maxn];
int buc[27];

modint binom(int n, int m) {return fac[n] * ifac[m] * ifac[n - m];}

int main() {
    read(s + 1);
    int n = strlen(s + 1);
    FOR(i, 1, n) ++buc[s[i] - 'a'];
    fac[0] = 1;
    FOR(i, 1, n) fac[i] = i * fac[i - 1];
    ifac[n] = qPow(fac[n], mod - 2);
    DEC(i, n - 1, 0) ifac[i] = (i + 1) * ifac[i + 1];
    FOR(j, 0, buc[0]) f[0][j] = 1;
    FOR(i, 1, 25) {
        FOR(j, 0, n) {
            FOR(k, 0, min(buc[i], j)) {
                f[i][j] += binom(j, k) * f[i - 1][j - k];
            }
        }
    }
    modint ans = 0;
    FOR(j, 1, n) ans += f[25][j];
    print(ans);
    return output(), 0;
}

ABC234G - Divide a Sequence

给定长为 N N N 的数列 A A A,有 2 N − 1 2^{N - 1} 2N1 种方法将其划分为若干个非空序列 B 1 , ⋯   , B k B_1,\cdots, B_k B1,,Bk,求出对于每种划分方式,下面这个式子的和,对 998244353 998244353 998244353 取模, N ≤ 3 × 1 0 5 N\le 3\times 10^5 N3×105
∏ i = 1 k ( max ⁡ { B i } − min ⁡ { B i } ) \prod_{i = 1}^k(\max\{B_i\} - \min\{B_i\}) i=1k(max{Bi}min{Bi})
考虑一个 dp: f i f_i fi A 1 , ⋯   , A i A_1, \cdots, A_i A1,,Ai 的答案,边界为 f 0 = 1 f_0 = 1 f0=1。则我们可以知道:
f i = ∑ j = 0 i − 1 f j ( max ⁡ k = j + 1 i { A i } − min ⁡ k = j + 1 i { A i } ) f_i = \sum_{j = 0}^{i - 1}f_j(\max_{k = j + 1}^i\{A_i\} - \min_{k = j + 1}^i\{A_i\}) fi=j=0i1fj(k=j+1maxi{Ai}k=j+1mini{Ai})
这个式子看似是 O ( n 2 ) O(n^2) O(n2) 的,拆开来:
f i = ∑ j = 0 i − 1 f j max ⁡ k = j + 1 i { A i } − ∑ j = 0 i − 1 f j min ⁡ k = j + 1 i { A i } f_i = \sum_{j = 0}^{i - 1}f_j\max_{k = j + 1}^i\{A_i\} - \sum_{j = 0}^{i - 1}f_j\min_{k = j + 1}^i\{A_i\} fi=j=0i1fjk=j+1maxi{Ai}j=0i1fjk=j+1mini{Ai}
然后我们维护一下 max ⁡ k = j + 1 i { A k } \max_{k = j + 1}^i\{A_k\} maxk=j+1i{Ak},以及对应的 dp 值之和,使用单调栈就可以完成这题了。答案即为 f n f_n fn,实现细节见代码。

const int maxn = 3e5 + 5;
modint f[maxn];
int a[maxn], n;

struct node {
    int a;
    modint v;
} st1[maxn], st2[maxn];
int top1, top2;

int main() {
    read(n);
    FOR(i, 1, n) read(a[i]);
    f[1] = 1;
    modint maxsum = 0, minsum = 0;
    FOR(i, 1, n) {
        modint sumv = f[i];
        while (top1 && st1[top1].a < a[i]) {
            maxsum -= st1[top1].a * st1[top1].v;
            sumv += st1[top1].v;
            --top1;
        }
        maxsum += sumv * a[i];
        ++top1, st1[top1] = {a[i], sumv};
        sumv = f[i];
        while (top2 && st2[top2].a > a[i]) {
            minsum -= st2[top2].a * st2[top2].v;
            sumv += st2[top2].v;
            --top2;
        }
        minsum += sumv * a[i];
        ++top2, st2[top2] = {a[i], sumv};
        f[i + 1] = maxsum - minsum;
    }
    print(f[n + 1]);
    return output(), 0;
}

ABC234Ex - Enumerate Pairs

给定二维平面上的 N N N 个点 ( x i , y i ) (x_i, y_i) (xi,yi) 和一个正整数 K K K。请列出所有欧几里得距离小于等于 K K K 的点对。 1 ≤ N ≤ 2 × 1 0 5 1\le N\le 2\times 10^5 1N2×105 1 ≤ K ≤ 1.5 × 1 0 9 1\le K\le 1.5\times 10^9 1K1.5×109。保证最多 4 × 1 0 5 4\times 10^5 4×105 对点对将被枚举。

以下题解参考了 AtCoder 官方题解传送门。神仙结论题,先给出结论:

  • 对于每个点 ( x i , y i ) (x_i, y_i) (xi,yi),将其分配到集合 ( ⌊ x i / K ⌋ , ⌊ y i / K ⌋ ) (\lfloor x_i/K\rfloor, \lfloor y_i/K\rfloor) (xi/K,yi/K) 中。
  • 然后对于任意一个点,若其被分配到了 ( X , Y ) (X, Y) (X,Y) 集合中,则能与其配对的点一定在 ( X + m , Y + l ) (X + m, Y + l) (X+m,Y+l) 集合中,其中 − 1 ≤ m , l ≤ 1 -1\le m,l\le 1 1m,l1。直接枚举即可得到答案。

然后,其时间复杂度为 O ( N + M ) O(N + M) O(N+M),其中 M M M 为输出的答案个数(忽略了使用数据结构产生的 log ⁡ \log log)。

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 5;
const ll big = 2000000000;
int n; ll K;
pll p[maxn];
map<ll, vector<int> > mp;
vector<ll> delta = {-big - 1, -big, -big + 1, -1, 0, 1, big - 1, big, big + 1};

int main() {
    read(n, K);
    FOR(i, 1, n) {
        read(p[i].first, p[i].second);
        ll id = (p[i].first / K) * big + (p[i].second / K);
        mp[id].push_back(i);
    }
    vector<pii> ans;
    FOR(i, 1, n) {
        ll id = (p[i].first / K) * big + (p[i].second / K);
        for (auto &d : delta) {
            ll curid = id + d;
            for (auto &j : mp[curid]) {
                if (j >= i) continue;
                ll dis = (p[i].first - p[j].first) * (p[i].first - p[j].first) + (p[i].second - p[j].second) * (p[i].second - p[j].second);
                if (dis <= K * K) ans.push_back(pii(j, i));
            }
        }
    }
    sort(ans.begin(), ans.end());
    print(ans.size());
    for (auto &p : ans) print(p.first, p.second);
    return output(), 0;
}

上述做法得解的正确性较为显然,这里不说明。下面对时间复杂度给出证明。

B X , Y B_{X, Y} BX,Y 为集合 ( X , Y ) (X,Y) (X,Y) 中的点的数量, f ( x ) f(x) f(x) 为“含 x x x 个点的集合内最少的距离小于等于 K K K 的点对数”。 f ( x ) f(x) f(x) 的上界显然为 O ( n 2 ) O(n^2) O(n2),下面证明其下界为 Ω ( n 2 ) \Omega(n^2) Ω(n2)

在一个边长小于 K 2 \dfrac{K}{\sqrt 2} 2 K 的子正方形区域中,每一对点对的距离都小于 K K K。而一个 K × K K\times K K×K 的正方形区域能由 4 4 4 个小的边长为 K 2 \dfrac{K}{\sqrt 2} 2 K 的小正方形覆盖。考虑往大区域中放 4 n 4n 4n 个点,则至少一个小区域包含至少 n n n 个点。该小区域有 n ( n − 1 ) 2 \dfrac{n(n - 1)}{2} 2n(n1) 个点对,所以 f ( x ) f(x) f(x) 的下界为 Ω ( n 2 ) \Omega(n^2) Ω(n2)

∑ X , Y f ( B X , Y ) ≤ M \sum_{X,Y}f(B_{X,Y}) \le M X,Yf(BX,Y)M,故 ∑ X , Y B X , Y 2 \sum_{X,Y}B^2_{X,Y} X,YBX,Y2 的上界为 O ( N + M ) O(N + M) O(N+M)

然后我们的算法里面,要枚举的点对数为 ∑ X , Y ∑ m = − 1 1 ∑ l = − 1 1 B X , Y B X + m , Y + l \sum_{X,Y}\sum_{m = -1}^1\sum_{l = -1}^1B_{X,Y}B_{X+m,Y+l} X,Ym=11l=11BX,YBX+m,Y+l。因为 ∑ X , Y B X , Y 2 \sum_{X,Y}B^2_{X,Y} X,YBX,Y2 的上界为 O ( N + M ) O(N + M) O(N+M),然后,根据均值不等式, B X , Y B X + m , Y + l ≤ 1 2 ( B X , Y 2 + B X + m , Y + l 2 ) B_{X,Y}B_{X + m,Y+l}\le \dfrac12(B_{X,Y}^2 + B_{X + m, Y + l}^2) BX,YBX+m,Y+l21(BX,Y2+BX+m,Y+l2),所以整体的上界也是 O ( N + M ) O(N + M) O(N+M)

证毕。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44950190/article/details/122418685

AtCoder Beginner Contest 187 A~D题解-爱代码爱编程

ABC187 A~D [A - Large Digits](https://atcoder.jp/contests/abc187/tasks/abc187_a)题目大意输入格式输出格式样例分析代码[B - Gentle Pairs](https://atcoder.jp/contests/abc187/tasks/abc187_b)题目大意输入格式

AtCoder题解 —— AtCoder Beginner Contest 187 —— A - Large Digits-爱代码爱编程

题目相关 题目链接 AtCoder Beginner Contest 187 A 题,https://atcoder.jp/contests/abc187/tasks/abc187_a。 Problem Statement For an integer n

AtCoder Beginner Contest 200 题解-爱代码爱编程

A.B比较简单,题解就不放了,主要想说下C的几种做法 C-Ringo’s Favorite Numbers 2 题目链接 本题我在比赛中用的是类似埃氏筛的思想,用一个vis[]数组来标记。但是赛后看队友的做法和editorial提供的做法时,感觉有所启发,故记录一下,感觉还蛮有意思的,主要想分享一下一步步优化的过程。具体做法见我的代码。 #inclu

Atcoder Beginner Contest 202 题解-爱代码爱编程

A.B比较简单,主要想说下C.D的做法 C-Made Up 题目链接 有三个数组 A A A=( A

AtCoder Beginner Contest 233D-爱代码爱编程

链接:D - Count Interval 题意: 给定n个数及k的值,问这个序列中,能找到多少段闭区间,使得闭区间内所有数字求和是k。 思路: 数据比较大(n是2e5,|k|是1e15),处理一段区间的和,我们首先会想到用前后缀和来加加减减,这里我们具体用后缀和处理,通过求出下标 id 的后缀和 last[id](不含id本身),我们可以知道一段

AtCoder Beginner Contest 234 题解-爱代码爱编程

A、 题意明了不用思考直接模拟 #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; LL cul(LL x) { return x*x+2*x+3; } int mai

AtCoder Beginner Contest 234 F - Reordering-爱代码爱编程

期末考试考完了…开始补题了 最近几场ATC的ABC都很简单,前五题都是普及组左右,因此目前的目标就是能够稳出F 这次F的读题没读明白,读错了,实际上是可以乱序,因此就是一个数学组合题: #define int LL const int N = 5010,mod=998244353; int n,m,k; int f[N][N],fac[N],inv[N

AtCoder Beginner Contest 234 (D-F)-爱代码爱编程

D、Prefix K-th Max 题目大意:给定一个长度为n的数组和一个k,对于每一个i(i >= k&&i <= n), 求前i个数字中第k大的数字是什么。 题解: 此题可以用优先队列来解决, 我们可以维护一个小根堆,然后维护其里面的size,一旦大于k则进行pop,这样的话每次输出答案时列头就是我们所需的答案

AtCoder Beginner Contest 234-爱代码爱编程

A - Weird FunctionB - Longest SegmentC - Happy New Year!D - Prefix K-th MaxE - Arithmetic NumberF - ReorderingG - Divide a Sequence  写个函数 int f(int x){return x*x+2*x+3;} int

AtCoder Beginner Contest 234 A~D-爱代码爱编程

A - Weird Function 题意:给一个方程,求值 #include<bits/stdc++.h> #define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); typedef long long ll; typedef unsigned long long ull

AtCoder Beginner Contest 237题解(A-E)-爱代码爱编程

AtCoder Beginner Contest 237题解 文章目录 AtCoder Beginner Contest 237题解A - Not OverflowB - Matrix TranspositionC - kasakaD - LR insertionE - Skiing A - Not Overflow 【题目链接】A - N

AtCoder Beginner Contest 234题解(A~D)-爱代码爱编程

AtCoder Beginner Contest 234题解 文章目录 AtCoder Beginner Contest 234题解A - Weird FunctionB - Longest SegmentC - Happy New Year!D - Prefix K-th MaxE - Arithmetic NumberF - Reorderi

AtCoder Beginner Contest 233(A~D)题解-爱代码爱编程

AtCoder Beginner Contest 233题解 文章目录 AtCoder Beginner Contest 233题解A - 10yen StampB - A ReversC - ProductD - Count Interval A - 10yen Stamp 【题目链接】A - 10yen Stamp (atcoder.j

leetcode-45. 跳跃游戏 II-使用最少的跳跃次数到达数组的最后一个位置。-爱代码爱编程

一、题目 二、思路 思想就一句话:每次在上次能跳到的范围(end)内选择一个能跳的最远的位置(也就是能跳到max_far位置的点)作为下次的起跳点 ! 三、代码 class Solution { public: int jump(vector<int>& nums) { int size=nums.s

【leetcode】202. 快乐数-爱代码爱编程

目录标题 算法汇总题目思路 - 关键点代码1.解体方法,如二分法思路代码时间和空间复杂度2.快慢指针 - 未掌握思路代码时间和空间复杂度 算法汇总 以下是所有算法汇总,包括GitHub源码地址链接:力扣算法练习汇总(持续更新…) 题目 202. 快乐数 思路 - 关键点 为啥一定不会出现死循环,因为int类型最大值为为‭‭2 147

Leetcode1598. 文件夹操作日志搜集器-爱代码爱编程

Every day a leetcode 题目来源:1598. 文件夹操作日志搜集器 解法1:模拟 设置一个计数器count,记录返回主文件夹所需的最小步数,初始化为0。 分三种情况讨论: “. . /” :移动到当前文件夹的父文件夹。如果已经在主文件夹下,则 继续停留在当前文件夹 。count=max(count-1,0)“. /” :继续停留

LeetCode常见题型——回溯法-爱代码爱编程

1. 算法思想 回溯法(backtracking)是优先搜索的一种特殊情况,又称为试探法,常用于需要记录节点状态的深度优先搜索。 排列、组合、选择类问题使用回溯法比较方便。 回溯步骤:修改当前节点状态-》递归子节点-》回改当前节点状态。 注意点:按引用或全局记录状态,所有状态修改在递归完成后需回退,才能继续进行下一节点的访问。 修改有两种情况:一