今天只过了3个题目前先给出有难度的题目的分析和代码。A体测队列唐克老师的学校要进行体测了现在学校安排了 n 位老师来给同学们体测由于学校人手不够派出的老师有的是体育老师有的是数学老师每个人的专业能力不同比如体育老师可以同时给十几个人同时测试而数学老师可能同时只能关注两三个同学同时测试毕竟专业不同嘛现在唐克老师已经统计好了每位老师的测试能力第 i 位老师可以同时给 a_i 位同学进行测试并且每位同学的测试需要花费 b_i 分钟现在有 m 位同学需要测试唐克老师需要给他们安排队伍唐克老师安排的思路非常简单每位同学依次安排到现在排队等待时间最短的老师处排队如果有两位老师处的等待时间一样则选择编号小的老师现在唐克老师想知道分配完所有同学以后每位老师处的排队人数分别是多少这里我们认为 m 位同学全部都是同时到达的分配完队伍后才会统一开始体测显然对于m过大a1优先队列直接分配法是不行的那么我们观察这个题对时间答案上具有单调性可以想到二分答案但是题目中的分配只考虑等待时间到当前并不是对于t最小所以我们对这个二分需要创新性判断对于t如果在时间t内所有学生都能排上队那么可以最终得到的对应left由于一次不一定是一个同学进入排队同时t时刻如果没有新同学排队那么t-1时刻肯定也是行的但是如果我们在计算最终的每个老师的人数只left/u[i].b*u[i].au[i].a(这里多加一个是因为0时刻)显然是有问题的可以先对left-1内的当前老师进行排序 left-1之前的肯定是排满的最终从小序号到大序号对剩下未排队的同学进行处理代码如下#include bits/stdc.h using namespace std; int n; long long m; bool yes(vectorpairlong long, long long u, long long mid) { __int128 res 0; for (int i 0; i u.size(); i) { res (mid / u[i].second 1) * u[i].first; } return res m; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin n m; vectorpairlong long, long long u(n); for (int i 0; i n; i) cin u[i].first u[i].second; long long left 0, right LLONG_MAX; while (left right) { long long mid left (right - left) / 2; if (yes(u, mid)) right mid; else left mid 1; } vectorlong long cnt(n); long long tleft; __int128 had0; for(int i0;in;i) { if(t0) { cnt[i]0; } else { cnt[i]((t-1)/u[i].second1)*u[i].first; } hadcnt[i]; } long long restm-had; for(int i0;inrest0;i) { if(t%u[i].second0) { cnt[i]min(u[i].first,rest); rest-min(u[i].first,rest); } } for(int i0;in;i)coutcnt[i] ; }C背书计划自举办完最强大脑比拼以后唐克老师受到了打击怎么大家都这么厉害于是唐克老师决定发愤图强他要把新华字典背下来他买了一本《超级豪华无敌加强plus版新华字典》一共有 n 页唐克老师决定用 m 天时间把它全部背下来作为一个规划性超强的人唐克老师决定规划一个学习计划他决定规划两个数字 a,b第一天背 a 页第二天背 ab 页第三天背 a2 * b 页 ...... 第 m 天背 a (m - 1) * b 页唐克老师想知道有多少种学习计划可以让他在第 m 天刚好背完整本书不多也不少直接进行公式推导得到2n/m(m-1)b2a.变型之后需满足一下需求1.2n%m02.(2n/m-(m-1)b)%203.a为整数4.m为整数5.m1特判通过计算b可能的数值以及b的奇偶性判断即可代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin t; while (t--) { long long n, m; cin n m; long long T 2 * n / m; if (2 * n % m ! 0) { cout 0 \n; continue; } long long cnt 0; if(m1) { cout1\n; continue; } long long b T / (m - 1); if (T % 2 0) { if ((m - 1) % 2 0) cnt b 1; else cnt b / 2 1; } else { if ((m - 1) % 2 0) { cnt 0; } else { if (b % 2 0) cnt b / 2; else cnt b / 2 1; } } cout cnt \n; } }D题签到题不过多赘述之后准备更改策略看过的题干进行补题没看过时间紧张将不准备补题(第一场和第二场训练赛已更新完毕第二场的H暂未解决)
