[ICPC 2024 Chengdu R] Recover Statistics

cjn1122334 · 2026-01-26 17:04:29 · 题解

简化题意

如此长的题目，读起来实在有些费解，我们来分析一下。

题目大致是这样的，有一个数列 a，它满足有 50\% 的数小于等于 p_{50}，满足有 95\% 的数小于等于 p_{95}，满足有 99\% 的数小于等于 p_{99}。

你现在知道 p_{50},p_{95},p_{99} 的值，要反推构造整个序列。

思路

题面里给出提示：有些数列不满足构造条件，是因为他们的数列长度无法整除 95 或者是 99。

解决这一点，我们可以观察到题目里面给出的都是百分比，所以我们就令答案为 100 项。

那么就是有 50 项小于等于 p_{50} 的，有 95 项小于等于 p_{95} 的，那么就是有 99 项小于等于 p_{99} 的。

:::info[如何构造？]{open} 我们可以观察题面中的“小于等于”四个字，我们不妨就让其变为等于，因为三个值满足 p_{50} < p_{95} < p_{99}，所以我们输出 50 个 p_{50}，45 个 p_{95}，4 个 p_{99} 就好了。

最后的第一百位，比 p_{99} 大即可。 :::

代码

#include<bits/stdc++.h>
#define int long long
#define N 1919810ll
#define Mod 998244353ll
#define pii pair<int,int>
#define qck ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int p50,p95,p99;
signed main(){
    qck;
    cin>>p50>>p95>>p99;
    cout<<"100\n";//不要忘记输出总个数
    for(int i=1;i<=50;i++) cout<<p50<<" ";
    for(int i=1;i<=45;i++) cout<<p95<<" ";
    for(int i=1;i<=4;i++) cout<<p99<<" ";
    cout<<p99+1<<"\n";
    return 0;
}