第一种做法（暴力） 思路： 暴力求解，从j = p开始枚举到21252，因为21252是最大得数，将23 * 28 * 33 = 21252，所以最大的情况就是所有的都可以整除他们对应的除数，这样答案就是21252了，然后枚举的数如果符合样例，那么这个数就是答案，但是需要注意的是，答案要是正整数，如果是负数的话要转换成正数。 #include #include using namespace std; const int maxn = 21252; int main() { int p, e, i, d, Case = 0; while (scanf("%d %d %d %d", &p...

思路：有题目可以得出(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，我们可以将之看成ax + by = c，从而使用扩展欧几里德定理。由扩展欧几里德定理可以得出x, y, gcd(a, b)的值，由于欧几里德的公式是ax + by = gcd(a, b)，但是本题需要求的是ax + by = c, 所以就有了 (ax + by) * c / gcd = gcd * c ...

思路：本题是一道有限队列的题目，简单的说，乳液的spf要在奶牛的最大的spf和最小的spf之间，首先排序，将奶牛按照最小的spf从小到大排序，乳液按照spf从小到大，然后开始循环，因为之前将奶牛最小的spf从小到大排序了，那么假如奶牛的最小的spf会小于乳液的spf那么，无论后面那种乳液的spf都会符合大于最小spf这个条件，因此就可以将这只奶牛存进优先队列，然后优先队列根据奶牛的 最大的spf从小到大排序，因为小的若是符合，那么大的一定符合，但是小的不符合的情况，那么大的可能可以符合，所以为了是数量最大，那么肯定小的优先，先把难符合条件的先用了，需要注意的是乳液是有数量的，每次用完一瓶，数量...

思路： 本题用了贪心+优先队列，本题要用尽量少的摊位让更多的奶牛生产，所以尽量能够让一个结束后，另一个能够接上，所以先排序将开始时间早的排前面，然后开始用优先队列，把结束时间早的排在前面，（把最早开始时间的放在前面，最早结束时间放在前面，如果这都接不上，那么肯定要开个摊位了），如果能接上的话，就将最早结束时间刷新，也就是说，这个摊位的最早结束时间变成了接上的那个奶牛的结束时间，需要注意的是加入1 4 和4 7必须要两个摊位，因为在4这个时间点，是两个奶牛都要在摊位里面，题目不允许，本题的摊位会发生没有奶牛生产，所以无需考虑队列为空这种情况。 优先队列： 优先队列是用堆实现的，但是用法上相当于队...

1003 我要通过！ (20 point(s)) “答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。 得到“答案正确”的条件是： 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符； 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串； 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。 现在就请你为 PAT 写一个...

Strange Way to Express Integers Time Limit: 1000MS Memory Limit: 131072K Description Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following: Choose k different positive integers a1, a2, …, ak. For some non-nega...

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

既然要循环的话，那么肯定前缀和后缀要相等，所以先求next数组，而想要知道有多少个循环，那么比如ababab，Next[len] = 4，也就是说前缀abab = 后缀abab，则前缀中的重合的ab = 后缀中的后面的ab而后缀中重合的ab等于前缀中的前面的ab，所以就可以知道循环节为len / (len - Next[len])（整除的情况）,否则为1。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e+6 + ...

Biorhythms Time Limit: 1000MS Memory Limit: 10000K Description Some people believe that there are three cycles in a person’s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respe...

A/B Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。 Input 数据的第一行是一个T，表示有T组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 109)。 Output 对应每组数据输出(A/B)%9973。 Sample Input 2 100...

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。 输出描述: 一个整数，表示a^b mod p的值。 示例1 输入 2 3 9 输出 8 解题思路： 首先看这题是让我们求a的b次方并对结果去余，如果是按照循环去做的话那么肯定时间复杂度O(b)太大了（b最大到1e+9），所以这里就要想办法把时间缩少，既然一个个循环着相乘不行，我们是否可以一次乘多个呢，这里就用到了快速幂的...

C Looooops Time Limit: 1000MS Memory Limit: 65536K Description A Compiler Mystery: We are given a C-language style for loop of type for (variable = A; variable != B; variable += C) statement; I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats state...

Romantic Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description The Sky is Sprite. The Birds is Fly in the Sky. The Wind is Wonderful. Blew Throw the Trees Trees are Shaking, Leaves are Falling. Lovers Walk passing, and so are You. …Write in English clas...

青蛙的约会 Time Limit: 1000MS Memory Limit: 10000K Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具***置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青...