P8948 题解

· · 题解

[YsOI2022]NOIp和省选！

先把题目和样例说一下，方便解释（

题目描述

其中一场考试有四道题目，满分 400；另一场考试有六道题目，满分 600。每个人每场考试得分都是一个 0 到满分间的一个非负整数（可以为 0 或者满分）。

有 n 名同学参加了这两场考试，其中第 i 名同学第一场得分 a_i，第二场得分 b_i，Ysuperman 通过以下规则计算第 i 名同学的标准得分 c_i：

  1. 分别统计两场比赛的最高分 A,B，有 A\ne 0，B\ne 0。
  2. 令 c_i=1000(\frac{a_i}{A}+\frac{b_i}{B})，其中 c_i 四舍五入保留到整数。

在算出了每位同学的标准得分后，Ysuperman 粗心地弄丢了每位同学的原始分，你能帮 TA 找到任意一组可能的原始分吗？

简单来说，已知 n 和每位同学的标准得分 c_{1\sim n}，Ysuperman 希望你找到一组合法的 a_{1\sim n}，b_{1\sim n} 满足上述要求。

特别的，有个十分强的小朋友 Qiu 在两场考试中都拿到了最高分，也就是保证 c_1=2000。另外其他小朋友水平都差不多，所以保证有 \forall i>1,c_i\in [10,1990]。

样例

样例输入 #1

4
2000
1319
1476
996

样例输出 #1

233 525
147 361
200 324
0 523

解法

显然，样例里给的输出构造，需要大量的四舍五入计算，太复杂了，所以我们希望能给出一个不需要四舍五入的构造方式。

显然，每一场比赛的 “标准得分” 都为 1000, 所以我们希望这场比赛的最高分能被 1000 整除

由于两场比赛的满分分别为 400 和 600, 我们自然就想到了让 Qiu 小朋友分别得 200 和 500 分，则每一位小朋友的标准得分为

c_i = 5 \cdot a_i + 2 \cdot b_i

（ \frac{1000}{2} 和 \frac{1000}{5} 互质，所以可以保证对于 [10,1990] 的分数均有解。 ）

于是：

cout<<"200 500\n";

然后对于每一个小朋友的分数，我们希望用不多于 200 个 5 和不多于 500 个 2 “处理“ 掉小朋友的标准得分。

因为 2 小于 5, 所以我们就想到先用 5 处理奇数分数，再用偶数个 5 尽可能处理掉剩余的分数。所以我们就能得到下面的代码：

if(a%2==1)a-=5,one++;
if(a<=990){one+=2*(a/10);a%=10;}
else one+=198,a-=990;

这里 one 指的是 NOIp 的分数 第一场考试的分数，a 指的是某个小朋友的标准分数。

然后只需要处理剩余的分数即可。从代码可以轻易看出，此时剩余未处理的分数一定是偶数。

two+=a/2;

这里 two 指的是 省选的分数 第二场考试的分数。

到这里这道题就做完了。

上大家喜闻乐见的代码片段：

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int t,n;
    cin>>t>>n;
    t--;
    cout<<"200 500\n";
    while(t--){
        int a;
        cin>>a;
        int one=0,two=0;
        if(a%2==1)a-=5,one++;
        if(a<=990){one+=2*(a/10);a%=10;}
        else one+=198,a-=990;
        two=a/2;
        cout<<one<<" "<<two<<endl;
    }
}

后记

我说怎么这么少人打比赛呢，原来是 Unrated...

这题也可以使用不定方程构造解的方法，但是还是要考虑个数上限的问题。

可以通过枚举证明这题不四舍五入得分的做法是唯一的，这里不再赘述。

至于用到四舍五入的做法，我太菜了，不会做，这里我姑且理解为出题人在秀自己的数据构造（

这是本蒟蒻提交的第 6 篇题解。