玄不救非，氪不改命

题解

HDU(22) POJ(90) PTA(60) UVa(2) 未归档(111) 百练(1)

/ 注册

全部文章 / 题解（共8篇）

信息学奥赛一本通在线题库 C Looooops

题意：问什么A加上C取模2k等于B，其中经历了几次循环，还是永远无法使等式成立。思路：有题意知(A + x * C) mod 2^k = B mod 2^k可以推导出x * C + y * 2^k = B - A所以就有 a = C, b = 2^k， c = B - A, 然后就是扩展欧几里得得...

2019-09-10

0 473

信息学奥赛一本通在线题库 Biorhythms题解

第一种做法（暴力）思路：暴力求解，从j = p开始枚举到21252，因为21252是最大得数，将23 * 28 * 33 = 21252，所以最大的情况就是所有的都可以整除他们对应的除数，这样答案就是21252了，然后枚举的数如果符合样例，那么这个数就是答案，但是需要注意的是，答案要是正整数，如...

2019-08-19

0 620

信息学奥赛一本通在线题库青蛙的约会

思路：有题目可以得出(mt + x) mod L = (nt + y) mod L，这样才可以相遇，因为比如1 mod 2 = (1 + 2 * n) mod 2，所以就有了(mt + x) + k * L = (nt + y)转之后就有了(m - n) * t + k * L = y - x，我们...

2019-08-18

1 630

《算法竞赛进阶指南》Sunscreen题解

思路：本题是一道有限队列的题目，简单的说，乳液的spf要在奶牛的最大的spf和最小的spf之间，首先排序，将奶牛按照最小的spf从小到大排序，乳液按照spf从小到大，然后开始循环，因为之前将奶牛最小的spf从小到大排序了，那么假如奶牛的最小的spf会小于乳液的spf那么，无论后面那种乳液的spf都会...

2019-08-18

0 810

《算法竞赛进阶指南》Stall Reservations题解

思路：本题用了贪心+优先队列，本题要用尽量少的摊位让更多的奶牛生产，所以尽量能够让一个结束后，另一个能够接上，所以先排序将开始时间早的排前面，然后开始用优先队列，把结束时间早的排在前面，（把最早开始时间的放在前面，最早结束时间放在前面，如果这都接不上，那么肯定要开个摊位了），如果能接上的话，就将最...

2019-08-18

0 538

信息学奥赛一本通在线题库农场派对题解

题目需要求求出来去的路径中的最短路径的最大值，那就写一个Dijkstra算法，然后每到一个点求出起点到终点的最短路径距离加上终点到起点的最短路径的距离，然后找到最大的就是答案了。（在写Dijkstra的时候用了堆优化的优先队列，没有的话可能会TLE）时间复杂度：没有堆优化的情况下使O（n ^ 2），...

2019-08-17

1 460

信息学奥赛一本通在线题库 Power Strings题解

既然要循环的话，那么肯定前缀和后缀要相等，所以先求next数组，而想要知道有多少个循环，那么比如ababab，Next[len] = 4，也就是说前缀abab = 后缀abab，则前缀中的重合的ab = 后缀中的后面的ab而后缀中重合的ab等于前缀中的前面的ab，所以就可以知道循环节为len / (...

2019-08-17

0 461

《算法竞赛进阶指南》a^b题解

a^b 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K64bit IO Format: %lld 题目描述求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤10^9 输入描述: 三个用空格隔开的整数a,b和p。输出描述: 一个整数，...

2019-08-15

4 859