前言
今天是集训最后一天，也是最后一场比赛了！我也是给了自己这次比赛考得不错，315分，第13名，虽然没有上次好，但已经超出我的平均水平了。AC三题，有一道签到题。好的地方就是没有再出现提交错代码的错误了。应得：T1AC,T2AC,T3AC,T4AC，T4WA5。实得：T1AC,T2AC,T3AC,T4WA10，T5WA5。
T1 Daisy Chains
题目大意
有一个集合P，再P里面选一个子集，满足子集里有一个数等于那个子集的平均值。问有多少个这样的子集。
正解
签到题直接过。
赛时情况
要是不AC我早毕业了。
T2 Stuck in a Rut
题目大意
有n头奶牛在一个无穷大的棋盘上，它们可以一直想北走或向东走，知道碰到其他牛的路径。问一头牛最多可以走多少个格子。
正解
和昨天的题一模一样，只不过换了个问法。排序后枚举向东走的牛和向北走的牛，看看它们会不会阻拦对方。如果向东走的被向北走的阻拦了，则向东走的距离是。如果向北走的被向东走的阻拦了，则向北走的距离是。
赛时情况
我要是不AC我能rank13？
T3 交通换乘
题目大意
再数轴轴上标有两类点：1类点需要花费；2类点需要花费，不过如果再比它小45个单位长度之内有一个1类点满足，则不需要花费，但是每一个1类点只能让一个二类点免费。现在给你这个数轴上的所有点，问总花费是多少。
正解
模拟。不过会爆，我们用一个单调队列q维护所有时间再当前点45个单位长度以内的点。因为题目保证所有点的位置是升续的，所以我们就每个点更新。因为q是单调的，所以如果有一个元素不行，它之前的元素也都是不行的，我们这样去更新q。
更新后的q里都是位置允许的1类点，我们遍历一遍q，找出第一个费用允许的点，花了这张优惠券。如果没有，那就只能花钱了。
赛时情况
想了大概半个小时，想到了用单调队列优化，AC。
T4 纪念品
题目大意
你有n个物品，m个比特币，你可以买或卖物品，但是每天它的物品的价值不一样。问t天后你获得的最大比特币数量。ps：致敬xmring
正解
完全背包问题。物品的买卖只能再两天之间进行，即昨天买+今天卖，因为前天买今天卖=前天买+昨天卖+昨天买+今天卖。昨天的价格当作重量，今天的价格当做价值，做一遍完全背包。注意每天的初始化，以及答案的更新。
赛时情况
花了太多时间搞T5，没时间就打了个表骗了10分。
T5 加工零件
题目大意
有n个点，m条边，如果让一个点做等级为的零件，和他有边相连的点要做的零件。给你Q个任务，问你1要不要做0的零件。
正解
图论。因为两个有边相连的点可以来回跳，所以如果1做了零件，他也要做零件，所以我们可以分析奇偶性。我们先计算出1到每个点的奇数最短路和偶数最短路。如果是奇数并且,那么输出Yes；如果是偶数并且,那么输出Yes。否则输出No
赛时情况
我想到了正解，但实现错了WA5。
总结
这次比赛有两个问题：
1.不要因为题目复杂就放弃。
2.多手推几组数据测试。
写在最后
祝我们全体2021届纪中信息队队员，初一的生活++，RP++，信息学学得和文化课进步++，作业--。
@2021吴同春，@2021罗浚博，@2021刘宇翔，@2021凌梓亿天神，咱么开学见！
标签：
c++
本文转载自: https://blog.csdn.net/jz_2021_fengyue/article/details/119837792
版权归原作者 OIer_FY 所有， 如有侵权，请联系我们删除。
版权归原作者 OIer_FY 所有， 如有侵权，请联系我们删除。