P1193 洛谷团队训练 VS 传统团队训练【洛谷算法习题】

P1193 洛谷团队训练 VS 传统团队训练

网页链接

P1193 洛谷团队训练 VS 传统团队训练

题目背景

“在中学的信息学教育领域，洛谷无疑是一个相当受欢迎的辅助网站。同时有百余所学校正在通过洛谷进行信息学竞赛（以后简称 OI）的教育。洛谷之所以如此受欢迎，是因为洛谷创新的将 OI 教育的几乎每一个环节都搬到了线上，无论是学校的竞赛教练还是学生，均可以仅仅使用这一个网站来进行练习，提升自己的能力。”

——摘自《厦门中小学教育科学研究》，2015 年 2 月号。

题目描述

XX 中学的两位信息组的教练正在为学校信息组是否应当将洛谷作为主要的训练工具而争论不休，最后决定采取一个量化的办法来决定是否迁移。

该中学的原来训练方法是，在机房的教师机里面用 cena 装载好测试数据，装载数据所需要T a T_aTa​时间，每一道题目都要装载。学生写好代码后，可以跑到教师机上收取程序并进行评测。但由于需要往返的路程，因此每跑一次就要浪费T b T_bTb​时间。所以也允许学生在自己的机子上装载好测试数据，可以根据自己的需要选择装载的题目，这需要花费和在教师机装载数据一样的时间T a T_aTa​，但是每次评测花费的时间就减少为T c T_cTc​。此外，该中学可能会用 Excel 记录各位同学的训练情况，如果某位同学的某道题的得分高于表格里的记录，那就会花费T d T_dTd​时间将这个成绩更新，否则就不必费那个事了，如果之前没有提交过这道题视为表格记录的程序为0 00分。

而在洛谷中，只需要将题目和测试数据上传到洛谷，花费T a T_aTa​时间。每次评测学生只需花费T c T_cTc​时间即可。记录成绩？那是洛谷的事儿，一提交完就帮你整理好了表格根本不费时间。

看起来可以省下不少时间吧。然而，支持传统训练方法的教练认为，洛谷并非100 % 100 \%100%的稳定，在有的情况会无法提供服务，因此首先要将洛谷的耗时除以它的可用度（一个小于100 % 100\%100%的数字A % A\%A%）并去掉小数点。又因为传统观念不易纠正，总是有不信任将题目数据交给洛谷这样的想法（kkksc03：怪我咯？），因此使用洛谷的耗时还要再加上一个罚时H HH以做公平比较。

现在给出该中学的训练情况，希望你帮两位教练分析一下到底该如何选择。

输入格式

第一行，两个整数N , M N, MN,M，代表题目数量与学生数量。

第二行，N NN个整数P 1 , P 2 , … , P N P_1, P_2, \ldots, P_NP1​,P2​,…,PN​，为涉及的题目编号。

第三行，M MM个整数S 1 , S 2 , … , S M S_1, S_2, \ldots, S_MS1​,S2​,…,SM​，为学生的学号。

第四行，七个整数T a , T b , T c , T d , A , H , E T_a, T_b, T_c, T_d, A, H, ETa​,Tb​,Tc​,Td​,A,H,E，前六个数字的意义见题目描述，E EE如果是1 11那么在 Excel 中记录成绩，如果是0 00则不记录。

第五行，一个整数R RR，代表评测数量。

接下来R RR行，评测记录，每行是P r i , S r i , S c i \mathit{Pr}_i, \mathit{Sr}_i, \mathit{Sc}_iPri​,Sri​,Sci​，分别为该次评测的题目号、学号以及成绩。

输出格式

三行。

第一行为传统方法的的耗时。

第二行为使用洛谷包括罚时在内的耗时。

第三行是结论，如果使用洛谷的时间小于传统方法的时间，那么输出Use Luogu!。否则输出Forget it...。

输入输出样例 #1

输入 #1

4 4 501 502 503 504 2 3 5 7 50 30 10 5 93 50 1 10 501 2 10 501 2 80 501 2 70 502 3 0 502 3 0 504 5 100 503 7 0 503 7 0 503 7 0 503 7 10

输出 #1

480 372 Use Luogu!

输入输出样例 #2

输入 #2

2 3 101 102 1 2 3 70 60 50 1 80 100 0 6 101 1 100 101 2 100 101 3 100 102 1 100 102 2 100 102 3 100

输出 #2

500 650 Forget it...

说明/提示

【样例解释 #1】

使用传统方法的话，装载4 44道题目需要4 × 50 = 200 4 \times 50=2004×50=200，2 22号同学和7 77号同学使用教师机所需要的时间分别为30 × 3 = 90 30 \times 3=9030×3=90、30 × 4 = 120 30 \times 4 = 12030×4=120，但是明显自己装载 cena 只需要50 + 10 × 3 = 80 50+10 \times 3=8050+10×3=80、50 + 10 × 4 = 90 50+10 \times 4=9050+10×4=90更优。而3 , 5 3,53,5同学则使用教师机就好，耗时60 , 30 60,3060,30。2 22号同学的前两次评测单调递增，所以额外花费2 × 5 = 10 2 \times 5=102×5=10时间记录，3 33号同学太弱了都是0 00分所以没必要记录了，5 55与7 77各耗费5 55时间。所以这种情况总时间耗时为200 + 80 + 90 + 60 + 30 + 10 + 5 + 5 = 480 200+80+90+60+30+10+5+5=480200+80+90+60+30+10+5+5=480。

使用洛谷的话，装载题目耗费200 200200，10 1010次评测共耗费10 × 10 = 100 10 \times10=10010×10=100，考虑稳定性时间为( 200 + 100 ) / 93 % = 322 (200+100) / 93\% = 322(200+100)/93%=322，所以最后总耗时为322 + 50 = 372 322+50=372322+50=372，所以决定使用洛谷。

【数据范围】

其中50 % 50\%50%数据中，不需要进行成绩的 Excel 记录。

其中50 % 50\%50%数据中，题目编号和学号均大于等于0 00，小于等于1000 10001000。

（这两种情况，可能会重叠）

对于100 % 100\%100%的数据，保证1 ≤ n , m ≤ 1000 1 \le n,m \le 10001≤n,m≤1000，1 ≤ T a , T b , T c , T d , H ≤ 10000 1 \le T_a, T_b, T_c,T_d,H \le 100001≤Ta​,Tb​,Tc​,Td​,H≤10000，1 ≤ R < 100000 1 \le R < 1000001≤R<100000，0 ≤ S c i ≤ 100 0 \le \mathit{Sc}_i \le 1000≤Sci​≤100，1 ≤ A ≤ 100 1 \le A \le 1001≤A≤100，学号和题目号在10 8 {10}^8108之内。

实际上，根据超级监控颁发的证书，洛谷 2015 年第一季度可靠性（SLA）为99.36 % 99.36 \%99.36%。同时观念也是可以改变的。

洛谷的优点很多都是不能量化的，其精华在于社区。和全国的 OIer 一起学习交流，不很好吗？

最后插一句，去年的【榨取 kkksc03】的布告依然有效，详情。

解题思路

本题核心是模拟计算+离散化映射+最优策略选择，精准计算两种训练模式的总耗时。由于题目号、学号数值极大，无法直接用数组存储，因此采用哈希表将其映射为连续下标，简化数据统计。洛谷训练耗时按规则计算：总基础耗时为题目装载时间加评测耗时，除以可用度后叠加罚时。传统训练耗时分为三部分：全局题目装载耗时、每个学生每题选择教师机/本地装载的最优耗时、Excel成绩更新耗时。遍历所有评测记录，统计提交次数与最高成绩，累加各项耗时，最后对比两种耗时输出结论，算法简洁高效，完全适配题目数据约束。

总结

核心逻辑：分别模拟传统训练与洛谷训练的耗时规则，传统训练选择最优评测方式，洛谷训练计算稳定性与罚时。
关键操作：哈希离散化处理超大编号、统计提交次数/最高成绩、分模块累加耗时、结果对比输出。
效率保障：离散化简化数据统计，线性遍历评测记录，高效完成全部计算逻辑。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intsc[1010][1010],cnt[1010][1010];intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;map<int,int>mp1,mp2;for(inti=1,x;i<=n;++i){cin>>x;mp1[x]=i;}for(inti=1,x;i<=m;++i){cin>>x;mp2[x]=i;}intta,tb,tc,td,a,h,e;cin>>ta>>tb>>tc>>td>>a>>h>>e;intr;cin>>r;intlu=(n*ta+r*tc)/(a/100.0)+h;intct=n*ta;for(inti=1;i<=r;++i){intx,y,z;cin>>x>>y>>z;intu=mp2[y],v=mp1[x];cnt[u][v]++;if(e&&sc[u][v]<z){sc[u][v]=z;ct+=td;}}for(intp=1;p<=m;++p)for(inti=1;i<=n;++i)ct+=min(cnt[p][i]*tb,ta+cnt[p][i]*tc);cout<<ct<<'\n'<<lu<<'\n';if(lu<ct)cout<<"Use Luogu!\n";elsecout<<"Forget it...\n";return0;}