自动搬运

查看原文

来自洛谷，原作者为

	untrigintillion Withered

搬运于2025-08-24 22:44:01，当前版本为作者最后更新于2023-01-16 20:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[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 篇题解。