2021-09-05 10:31 已编辑 C++

关注

牛客IOI周赛28-提高组题解

$\textbf{Windy W Round 1 题解}$
——by WdOI 出题组——

纯情活泼的拆分（written by 八云蓝）

Subtask 1&2
暴力枚举什么的，或者手算打表。
关于 Normal：是给一些实现时失误的解法的分，可以忽略。

Subtask 3&4&5
我们考虑只能分成 $p_i=0$ 的情况，这时，显然最优的方法是从小到大依次加数，如果加到下一个大于要分解的数 $a_i$ 了则退出并输出已经分解了多少个数，例如分解36：
2+3+4+5+6+7+8+9 > 36 > 2+3+4+5+6+7+8
于是答案是7（2+3+4+5+6+7+9）。如果加上了指数呢？我们可以发现一个数指数加1，等价于新增加了一个数，于是仍可考虑从小到大加数。我们可以维护一个集合 S，初始时包含大于一的所有正整数，从小到大取出集合中的数并加上，在加一个数 ${p_i}^{q_i}$ 后，将数 ${p_i}^{q_i+1}-{p_i}^{q_i}$ 加入集合，如果加的数的和大于 $a_i$ 了就直接输出加了多少数即可。容易证明对于数 $a_i$ ，进行 $\sqrt{a_i}$ 量级的加数操作后就能求出结果。对于 Extra1 和Extra2，暴力模拟即可。对于 Hard，预处理出 $10^6$ 之内的所有答案即可单次询问 O(1) 回答。

Subtask 6
容易发现对于 $10^{12}$ 级别的数，出现的答案数量在 $10^6$ 量级并且对于更大的数答案一定不会更小。我们考虑模拟加数过程，并在过程中求出相同答案的数区间与它们对应的答案，最后在回答询问的时候利用二分求出 $a_i$ 所在的区间就可以了。时间复杂度 $O(10^6+t\times\log 10^6)$ ，预处理（也就是模拟加数过程）时如果实现不当可能会变成 $10^6\times\log 10^6$ ，会被卡掉。

标准程序

#include<bits/stdc++.h>
#define Mashu cout << "UUZ ate it." << endl
#define RE register int
#define ll long long
#define mp make_pair
const long long MXN = 1000000000000;
using namespace std;
vector < pair < int, int > > v[2000100];
int sz = 0;
long long a[2000010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long sum = 4;
v[4].push_back(mp(2, 8));
a[++sz] = 2;
a[++sz] = 4;
for (long long i = 3; sum <= MXN; i++){
for (int j = 0; j < v[i].size(); j++){
sum += i;
if (sum > MXN) break;
else{
a[++sz] = sum;
if ((v[i][j].first - 1) * v[i][j].second <= 2000000) v[(v[i][j].first - 1) * v[i][j].second].push_back(mp(v[i][j].first, v[i][j].first * v[i][j].second));
}
}
sum += i;
if (sum > MXN) break;
else{
a[++sz] = sum;
if (i * (i - 1) <= 2000000) v[i * (i - 1)].push_back(mp(i, i * i));
}
}
a[++sz] = 10 * MXN;
int t;
cin >> t;
while (t--){
long long n;
cin >> n;
cout << upper_bound(a + 1, a + 1 + sz, n) - a - 1 << endl;
}
return 0;
Mashu;
}

黑暗洞窟丶明亮之网（written by 离散小波变换°）
Subtask 1
直接暴力计算即可，没有什么技术含量。

Subtask 4
通过打表，可以发现这部分只要直接输出 $m\times 2$ 就行了。

Subtask 2&3&5
本题涉及到一些概率问题，高二及以上选手可以直接跳过。首先介绍超几何分布。

超几何分布：一共 N 个物品，有 M 个被指定的物品。现在随机选择其中 n 个，记被指定的物品被选中的数量为 $\zeta$ ，那么称 $\zeta \sim H(n,M,N)$ ，有：
$P(\zeta=r)=\frac{\binom{M}{r}\binom{N-M}{n-r}}{\binom{N}{M}}$
$E(\zeta)=n\times \frac{M}{N}$

对于 (1) 式，读者可以自证； (2) 式可以简要证明如下：
$\begin{aligned}E(\zeta)&=\sum_{i=0}^ni\times P(\zeta=i)\cr &=\sum_{i=0}^n\frac{\binom{M}{i}\binom{N-M}{n-i}\times i}{\binom{N}{M}} \cr &=\frac{M}{\binom{N}{M}}\sum_{i=1}^n\binom{M-1}{i-1}\binom{N-M}{n-i} \cr &=\frac{M}{\binom{N}{M}}\sum_{i=0}^{n-1}\binom{M-1}{i}\binom{N-M}{n-1-i} \cr \end{aligned}$
由于概率的性质，有：
$\sum_{i=0}^n P(\zeta=i)=\sum_{i=0}^n\frac{\binom{M}{i}\binom{N-M}{n-i}}{\binom{N}{M}}=1$
取 M=M'-1,N=N'-1,n=n'-1 ，于是有：
$\sum_{i=0}^{n-1}\frac{\binom{M-1}{i}\binom{N-M}{n-1-i}}{\binom{N-1}{M-1}}=1$
代回我们之前的式子，就能得到 $E(\zeta)=n\times \frac{M}{N}$ 了。
接着再介绍一下关于概率的问题。
对于概率事件 A,B ，记 P(A|B) 表示“在 B 发生的条件下 A 发生的概率”。那么有：
$P(A|B)=\frac{P(AB)}{P(B)} \iff P(AB)=P(A|B)\times P(B)$
读者可自行证明。

依次考虑第 i 条边 $u\to v$ 的贡献。
它是第 j 个被删除的概率为 $\frac{1}{m}$ （ $j=1,2,\cdots$ ）。如果把“它是第 j 个删除的”记为事件 A ，某种删除顺序发生的概率为 B ，那么 $P(AB)=P(B|A)\times P(A)$ 。由于 $P(A)=\frac{1}{m}$ ，所以我们只要知道“在 A 发生的情况下这种情形存在的概率”的期望就行了。假设一共有 c 条边都是 $u\to v$ ，那么这些重边中被删除的个数 $X\sim H(j-1,c-1,m-1)$ ；假设在剩下来的边中，与 u 或者 v 相连的边有 s 个，那么这些边中被删除的个数 $Y\sim H(j-1,s,m-1)$ 。于是，第 i 条边的贡献为：
$\frac{1}{m}\sum_{i=1}^m\left(\underbrace{(s+2\times c)}_{\text{第一部分}}-\underbrace{(i-1)\times \frac{c-1}{m-1}\times 2}_{\text{第二部分}}-\underbrace{(i-1)\times \frac{s}{m-1}}_{\text{第三部分}}\right)$
对于第一部分，有：
$\frac{1}{m} \sum_{i=1}^m(s+2\times c)=s+2\times c$
对于第二部分，有：
$\begin{aligned}\frac{1}{m} \sum_{i=1}^m\left((i-1)\times \frac{c-1}{m-1}\times 2\right)&=\frac{(c-1)\times 2}{m\times(m-1)}\sum_{i=1}^m(i-1) \cr &=\frac{(c-1)\times 2}{m\times(m-1)}\times\frac{(m-1)\times m}{2}\cr &=c-1 \end{aligned}$
对于第三部分，有：
$\begin{aligned}\frac{1}{m} \sum_{i=1}^m\left((i-1)\times \frac{s}{m-1}\right)&=\frac{s}{m\times(m-1)}\sum_{i=1}^m(i-1) \cr &=\frac{s}{m\times(m-1)}\times\frac{(m-1)\times m}{2} \cr &=\frac{s}{2} \end{aligned}$
于是，有：
$\text{原式}=s+2\times c-c+1-\frac{s}{2}=\frac{s}{2}+c+1$
事实上，我们只要计算选中的边的两端节点的度数和即可，而不需要特别区分某条边是否是重边（因为一条重边对度数的贡献为 2 ，恰好分摊到了两个端点上；一条普通边只会分摊到其中一个节点上）。最后累加答案即可得到结果。

标准程序

#include<bits stdc="">
#define Mashu cout << "UUZ has eaten it." << endl
#define ll long long
using namespace std;
ll qpow(ll a, ll b, ll p){
ll ans = 1;
while (b){
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int a[1000010], u[2000010], v[2000010];
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m ,&k);
for (int i = 1; i <= m; i++){
scanf("%d%d", &u[i], &v[i]);
a[u[i]]++;
a[v[i]]++;
}
long long sum = 0;
for (int i = 1; i <= k; i++){
int t;
scanf("%d", &t);
sum += a[u[t]] + a[v[t]] + 2;
}
cout << (sum % 998244353) * qpow(2, 998244351, 998244353) % 998244353;
return 0;
Mashu;
}

下克上の天邪鬼（written by chenxinyang2006）
Subtask 1
枚举 $[l_1,r_1]$ 中每个 i，以及 $[l_2,r_2]$ 中的每个 j，判断是否符合条件然后更新答案即可。

Subtask 2

把 $[l_2,r_2]$ 中的所有 $a_j$ 放到一个数组 b 里，然后对 b 进行排序，对于每个 $[l_1,r_1]$ 中的 $a_i$ ，二分找到最大的 $< a_i$ 的数，如果符合条件就更新答案

Subtask 3

因为 $[l_1,r_1]$ 和 $[l_2,r_2]$ 是一个区间，所以可以用莫队来比较快速地解决这个问题
移动端点的过程中动态维护一颗权值线段树，表示当前这个 [l,r] 中所有数，每次加入一个新数的时候，去分别求出它作为 $a_i$ 和 $a_j$ 的最大答案，然后再把新数插入就行了

貌似还要写回滚莫队，估计挺麻烦的

Subtask 4

首先有一个显然的结论：最大的 $a_i + a_j$ 一定是一个最大的有配对的 $a_i$ 以及它的最大配对。
观察到 $a_j$ 的下界是 $\left \lfloor \frac{a_i}{2} \right \rfloor$ ，所以这题多半和折半有关系。考虑先取出 [l,r] 中的最大值 x，然后看能不能去更新答案。如果区间内有 $\ge \left \lfloor \frac{x}{2} \right \rfloor$ 且 < x 的数，那么直接求出了答案。如果没有的话，实际上我们排除了 $\frac{x}{2}$ 的值域，接下来的数必定 $< \frac{x}{2}$ 了，可以再拿出下一个 x 。
那么显然进行 $\log v$ 次枚举后就排除了所有值域，也就是结束了。
实际上数据结构部分就是要支持求一个区间 [l,r] 的前 $\log v$ 小，可以通过各种各样的方法求出来。

Subtask 5
留给一些乱搞，比如依次从大到小枚举 $[l_1,r_1]$ 中每个 $a_i$ ，看有没有配对啥的。

Subtask 6
考虑如何从 Subtask 4 的做法推广过来。
首先找到 $[l_1,r_1]$ 中的最大值，设其为 x，然后在 $[l_2,r_2]$ 中找有没有合法的配对，如果有，直接 return，否则说明 $[l_2,r_2]$ 中没有值在 $[\left\lfloor \frac{x}{2} \right \rfloor,x - 1]$ 中的数。
然后去找到 $[l_2,r_2]$ 中小于 $\left\lfloor \frac{x}{2}\right \rfloor$ 的最大值，设其为 y，然后在 $[l_1,r_1]$ 里找有没有合法的配对，如果有，return，否则说明 $[l_1,r_1]$ 中没有值在 $[y + 1,2 \times y - 1]$ 内的数。
然后再在 $[l_1,r_1]$ 中找到小于 y + 1 的最大数，如此这样循环往复，仍然是 $\log v$ 次枚举后排除所有值域。
在 [l,r] 中找值域在 [L,R] 的数中的最大值可以用主席树求解。

标准程序

#include <bits/stdc++.h>
int n,m;
int a[200005];
int cnt;
int T[200005];
struct node{
int val,l,r;
}tree[6400005];
#define ls(rt) tree[rt].l
#define rs(rt) tree[rt].r
int upload(int Q,int l,int r,int id,int C){
int rt = ++cnt;
tree[rt] = tree[Q];
tree[rt].val += C;
if(l == r) return rt;
int mid = l + r >> 1;
if(id <= mid){
ls(rt) = upload(ls(Q),l,mid,id,C);
}else{
rs(rt) = upload(rs(Q),mid+1,r,id,C);
}
return rt;
}
int query(int rt,int l,int r,int L,int R){
if(l == L && r == R) return tree[rt].val;
int mid = l + r >> 1;
if(R <= mid){
return query(ls(rt),l,mid,L,R);
}else if(L > mid){
return query(rs(rt),mid+1,r,L,R);
}else{
return query(ls(rt),l,mid,L,mid) + query(rs(rt),mid+1,r,mid+1,R);
}
}
int kth(int x,int y,int l,int r,int k){
if(l == r) return l;
int mid = l + r >> 1;
if(tree[ls(x)].val - tree[ls(y)].val < k) return kth(rs(x),rs(y),mid+1,r,k - tree[ls(x)].val + tree[ls(y)].val);
else return kth(ls(x),ls(y),l,mid,k);
}
#define mn 1
#define mx 1000000001
int pre(int l,int r,int x){//[l,r] 中 x 的前驱
int rk = query(T[r],mn,mx,mn,x - 1) - query(T[l - 1],mn,mx,mn,x - 1);
if(rk == 0) return 0;
return kth(T[r],T[l - 1],mn,mx,rk);
}
int solve(int l1,int r1,int l2,int r2){
int i = pre(l1,r1,mx),j;
while(i){
j = pre(l2,r2,i);
if(j >= i / 2) return i + j;
if(j == 0) return 0;
i = pre(l1,r1,2 * j);
if(i >= j + 1) return i + j;
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
T[i] = upload(T[i - 1],mn,mx,a[i],1);
}
int l1,r1,l2,r2;
for(int i = 1;i <= m;i++){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
printf("%d\n",solve(l1,r1,l2,r2));
}
return 0;
}