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输入 #14 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输出 #1480 372 Use Luogu!输入输出样例 #2输入 #22 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输出 #2500 650 Forget it...说明/提示【样例解释 #1】使用传统方法的话装载4 44道题目需要4 × 50 200 4 \times 502004×502002 22号同学和7 77号同学使用教师机所需要的时间分别为30 × 3 90 30 \times 39030×390、30 × 4 120 30 \times 4 12030×4120但是明显自己装载 cena 只需要50 10 × 3 80 5010 \times 3805010×380、50 10 × 4 90 5010 \times 4905010×490更优。而3 , 5 3,53,5同学则使用教师机就好耗时60 , 30 60,3060,30。2 22号同学的前两次评测单调递增所以额外花费2 × 5 10 2 \times 5102×510时间记录3 33号同学太弱了都是0 00分所以没必要记录了5 55与7 77各耗费5 55时间。所以这种情况总时间耗时为200 80 90 60 30 10 5 5 480 200809060301055480200809060301055480。使用洛谷的话装载题目耗费200 20020010 1010次评测共耗费10 × 10 100 10 \times1010010×10100考虑稳定性时间为( 200 100 ) / 93 % 322 (200100) / 93\% 322(200100)/93%322所以最后总耗时为322 50 372 3225037232250372所以决定使用洛谷。【数据范围】其中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≤10001 ≤ 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≤100001 ≤ R 100000 1 \le R 1000001≤R1000000 ≤ S c i ≤ 100 0 \le \mathit{Sc}_i \le 1000≤Sci​≤1001 ≤ A ≤ 100 1 \le A \le 1001≤A≤100学号和题目号在10 8 {10}^8108之内。实际上根据超级监控颁发的证书洛谷 2015 年第一季度可靠性SLA为99.36 % 99.36 \%99.36%。同时观念也是可以改变的。洛谷的优点很多都是不能量化的其精华在于社区。和全国的 OIer 一起学习交流不很好吗最后插一句去年的【榨取 kkksc03】的布告依然有效详情。解题思路本题核心是模拟计算离散化映射最优策略选择精准计算两种训练模式的总耗时。由于题目号、学号数值极大无法直接用数组存储因此采用哈希表将其映射为连续下标简化数据统计。洛谷训练耗时按规则计算总基础耗时为题目装载时间加评测耗时除以可用度后叠加罚时。传统训练耗时分为三部分全局题目装载耗时、每个学生每题选择教师机/本地装载的最优耗时、Excel成绩更新耗时。遍历所有评测记录统计提交次数与最高成绩累加各项耗时最后对比两种耗时输出结论算法简洁高效完全适配题目数据约束。总结核心逻辑分别模拟传统训练与洛谷训练的耗时规则传统训练选择最优评测方式洛谷训练计算稳定性与罚时。关键操作哈希离散化处理超大编号、统计提交次数/最高成绩、分模块累加耗时、结果对比输出。效率保障离散化简化数据统计线性遍历评测记录高效完成全部计算逻辑。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;intsc[1010][1010],cnt[1010][1010];intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cinnm;mapint,intmp1,mp2;for(inti1,x;in;i){cinx;mp1[x]i;}for(inti1,x;im;i){cinx;mp2[x]i;}intta,tb,tc,td,a,h,e;cintatbtctdahe;intr;cinr;intlu(n*tar*tc)/(a/100.0)h;intctn*ta;for(inti1;ir;i){intx,y,z;cinxyz;intump2[y],vmp1[x];cnt[u][v];if(esc[u][v]z){sc[u][v]z;cttd;}}for(intp1;pm;p)for(inti1;in;i)ctmin(cnt[p][i]*tb,tacnt[p][i]*tc);coutct\nlu\n;if(luct)coutUse Luogu!\n;elsecoutForget it...\n;return0;}