竞赛讨论区 > 牛客IOI周赛28-提高组 题解

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

头像
八云蓝不是懒骨头
编辑于 2021-09-05 10:31:06 APP内打开
赞 3 | 收藏 0 | 回复2 | 浏览696

——by WdOI 出题组——

纯情活泼的拆分(written by 八云蓝)

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

Subtask 3&4&5
我们考虑只能分成 的情况,这时,显然最优的方法是从小到大依次加数,如果加到下一个大于要分解的数 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,初始时包含大于一的所有正整数,从小到大取出集合中的数并加上,在加一个数 后,将数 加入集合,如果加的数的和大于 a_i 了就直接输出加了多少数即可。容易证明对于数 a_i,进行 量级的加数操作后就能求出结果。对于 Extra1 和Extra2,暴力模拟即可。对于 Hard,预处理出 之内的所有答案即可单次询问 O(1) 回答。

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

标准程序
#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
通过打表,可以发现这部分只要直接输出 就行了。

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

超几何分布:一共 N 个物品,有 M 个被指定的物品。现在随机选择其中 n 个,记被指定的物品被选中的数量为 ,那么称 ,有:



对于 (1) 式,读者可以自证; (2) 式可以简要证明如下:

由于概率的性质,有:

取 M=M'-1,N=N'-1,n=n'-1 ,于是有:

代回我们之前的式子,就能得到 了。
接着再介绍一下关于概率的问题。
对于概率事件 A,B ,记 P(A|B) 表示“在 B 发生的条件下 A 发生的概率”。那么有:

读者可自行证明。

依次考虑第 i 条边 的贡献。
它是第 j 个被删除的概率为 )。如果把“它是第 j 个删除的”记为事件 A ,某种删除顺序发生的概率为 B ,那么 。由于 ,所以我们只要知道“在 A 发生的情况下这种情形存在的概率”的期望就行了。假设一共有 c 条边都是 ,那么这些重边中被删除的个数 ;假设在剩下来的边中,与 u 或者 v 相连的边有 s 个,那么这些边中被删除的个数 。于是,第 i 条边的贡献为:

对于第一部分,有:

对于第二部分,有:

对于第三部分,有:

于是,有:

事实上,我们只要计算选中的边的两端节点的度数和即可,而不需要特别区分某条边是否是重边(因为一条重边对度数的贡献为 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
枚举 中每个 i,以及 中的每个 j,判断是否符合条件然后更新答案即可。

Subtask 2
中的所有 a_j 放到一个数组 b 里,然后对 b 进行排序,对于每个 中的 a_i,二分找到最大的 的数,如果符合条件就更新答案 

Subtask 3
因为 是一个区间,所以可以用莫队来比较快速地解决这个问题
移动端点的过程中动态维护一颗权值线段树,表示当前这个 [l,r] 中所有数,每次加入一个新数的时候,去分别求出它作为 a_ia_j 的最大答案,然后再把新数插入就行了
貌似还要写回滚莫队,估计挺麻烦的

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

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

Subtask 6
考虑如何从 Subtask 4 的做法推广过来。
首先找到 中的最大值,设其为 x,然后在 中找有没有合法的配对,如果有,直接 return,否则说明 中没有值在 中的数。
然后去找到 中小于 的最大值,设其为 y,然后在 里找有没有合法的配对,如果有,return,否则说明 中没有值在 内的数。
然后再在 中找到小于 y + 1 的最大数,如此这样循环往复,仍然是 次枚举后排除所有值域。
在 [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;
}


2条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐