【题解】吉林大学ACM集训队选拔赛（重现赛）

Problem A. 777

从高到低统计每 中 的个数
每个数位考虑小于7、等于7、大于7三类统计结果

Problem B. Subset of Five

DP：前 位中选取若干数字后模 为 的最大值
贪心：在模 为 四类中每类取最小的 个，暴力求子集和或分类讨论，找出最小子集使得模 等于

Problem C. Strange Bulbs

为每个点维护一个长度为 的bitset
一边拓扑排序，一边DP某个点被哪些点影响到了
时间复杂度

Problem D. Query Theory I

筛出每个数因子和后前缀和
埃式筛：
线性筛：

Problem E. Final Exam

将所有 换成二进制，统计每一位上有几个数为 ，这样问题就转换成有若干个物品，
每个物品花费 ，得到的价值形式为
每种物品有两个形态，
一个形态表示 这一位为 ，则价值乘上的数为 中这一位为 的数的个数，另一个形态表示 这一位为 ，价值乘上的数为 中这一位为 的数的个数
先贪心求出一个 使得 最小，这个贪心是显然的
之后我们从高位往低位贪心求最终答案

Problem E. Final Exam

如果这一位 已经为 ，则不用管直接继续下一位
如果这一位 为 ，那么贪心取
如果这一位 为 的价值加上已有价值小于等于 的话，那这一位一定为 ，否则k这一位一定为0（为1就不符合题意了）
最后输出得到的 就是答案
注意一下数据，这个数据很大，看似需要高精度，实际上只需要一个特判就可以判掉无解
时间复杂度

Problem F. EndA's GPA

减少浮点数计算
检查

Problem G. Pair Complex

方法1 ~ 暴力对每个式子进行前缀和加减计算
方法2 ~ 计算每个数字对答案的贡献

Problem H. Precision

展开 后为
树状数组或线段树维护

Problem I. Firework}

建立超级起点 连接到每个 ignited node
SPFA或Dijkstra求出离超级起点最远的两个点
两者相连则根据到达时间和两者间距解出燃烧尽时间
否则最后一个燃尽的点的时间就是答案

Problem J. Across the Firewall

拆点限制流量的无向图最大流送分题

Problem K. Dress as women

复杂度计算每个子集内的点是否共线
dp[0101010] 表示某个子集的必胜/必败态 枚举每个状态的子集进行转移