爬

首先，可以确定的是，对于同一边的蚂蚁来说，因为蚂蚁的速度和背负的米粒数量都是相同的，所以假如蚂蚁a回去路上碰见了蚂蚁b，那么蚂蚁b背上了蚂蚁a的物品，掉头返回， 相当于蚂蚁a、b都以原速度和原方向继续前进，但是a变成了b、b变成了a， 这是一个比较经典的弹性碰撞。

为了防止炸ll等事情，数据范围开得不是很大，这样转换后可以使用模拟的写法，感谢lyh提供的优先队列写法，主要可以将两边蚂蚁到达米粒堆时间同时乘上便可以转为整数进行模拟。

要是数据范围比较大的话，我们可以使用二分时间的方法来计算，通过二分时间check米粒堆有没有被分光，我们可以得到米粒堆被分光的时刻，通过这个时间点，我们可以计算计算每边蚂蚁取到的米粒数量。

但是浮点二分可能出现精度问题（我被卡了，zcy过去了），所以我们可以考虑整数二分速度快的一边的走过的距离（因为给出的距离都是整数），然后通过快的一边来计算慢的一边走过的路程，来check结果，注意时间的开闭取法。

花园

因为保证不超过50种花，所以可以枚举s到t的每一种花的愉悦值，然后取最大值。

这就变成了简单的前缀和问题，只需要打个前缀sum[i][j]，代表1到i这段路，只取第j种花的价值。

由于的取值范围是1e9，所以需要离散化映射到50的大小。

如果某个数字经历了偶数次删去和写上，最终肯定还在纸上，但是如果经历的次数是奇数，最终肯定不在纸上。现在问题转化为我们只需要知道多少个会使得被删去或写上，记这个次数为，更准确来说，我们关心的是的奇偶性。

• 对于所有的，不可能是的倍数，我们直接不考虑
• 对于所有的，必须满足，即中的因子的个数

那么什么时候会满足呢？我们知道可以表示为的形式
因此，只要不是一个完全平方数，必然找不到一个满足，其的值必然是偶数。反之假如是完全平方数，必然是奇数，将被删去。即最终能留下来的数字为所有的非完全平方数。记其花费时间为，则：

现在问题是求，大部分同学可能直接取m=(long long)sqrt(n)，然而这样在C语言内部是存在精度误差的，考虑到新生赛大家对这个可能不明确，我在样例中给出了999999999999999999 998244353。这组数据就是会被卡sqrt的，为了保证精度，可以先取一个m=(long long)sqrt(n)，然后检验是否满足题意，适当调整的值。

jyq跳格子

可以跳2格、也可以跳4格，跳4格是就2次跳2格，所以相当于只能跳无限次2格。

问能否恰好跳到终点，初始位置是1，所以只能跳到奇数序号的格子。

判断n是不是奇数即可。

欢迎来到CCNU

最签到的题，可以用map，也可以用if判断。

<big>你猜我是签到吗---题解</big>

这道题要从两点分析：

1.价值奇偶分类讨论：

1.1当价值为奇数时，头尾必须有且只有一个1.

1.2当价值为偶数时，头尾必须同时为0或同时为1.

2.题目要求二进制值最小：让1尽可能在右边。

那么这道题的做法就出来了：当价值为奇数时，如果可以在最右的那一位置1则置1，否则在最左边置1，如果两个位置都不可以置1，则QAQ！。如果没有强制置0和二进制最小，偶数的部分有两种情况，比如价值为4时有10101和01010，所以剩余的偶数价值，则可以生成这两种模板序列，将序列从右到左用双指针法“贴”到答案序列上

如果两个指针指向的是：

1.模板序列的字符0和答案序列的字符0，则continue，两个指针均指向下一位置

2.模板序列的字符1和答案序列的字符0，则指向答案序列的指针++，继续判断答案序列的下一个位置。

3.模板序列的字符和答案序列的空字符（未被填入的位置），则直接写入，两指针均指向下一位置。

因此，我们可以得到两个答案序列，但是还要判断，这两个序列是否满足价值。因为奇数的预先置1操作可能会和“10101"冲突，也可能置0位置过多导致价值不正确。

若两种答案序列都满足，则判断二进制值大小，输出小的那个。

这样这道题就完成了，希望小朋友们满意XAX.

zyf的塔防游戏

做法：排序，然后滑动窗口。
把所有炮塔的左右端点，所有路径点塞到一起排序，同时标记它原来是什么。
然后，遍历这个数组，维护一个当前的dps（每1距离所能造成的伤害），和当前路径段的输出。对于这个数组的每一段区间，处理如下：
首先，这个路径段的输出加上dps*这个区间的长度。
路径点：结束这个路径段的计算，存入数组。
炮塔左端点：当前dps加上这个炮塔的dps。
炮塔右端点：当前dps减去这个炮塔的dps。

之后，排序并对前k大的输出翻倍，之后求和。

七日狂想曲

（灵感来源：牛客某次加入假日团队赛，然后自己加大了数据范围）

观察数据可以发现，不到1e6，所以我们每个药材分开考虑。

假设在第个位置的一单位药材所需要花费的价值为，考虑的计算方法。

• 则需要搬药材到这里或者从其他地方要一个，因为从其他地方要一个过来时还要减去要过来的这个药材本身的贡献，所以
• 与上面同理，则

接下来考虑优化，拆开后分别用两个小顶堆维护即可，具体实现细节可以查看代码实现。

时间复杂度：

(可以发现其并不是一般的贪心，因为带有状态更改贪心，我们称其为后悔型贪心)

战斗力只有一的蒟蒻

首先进行两种预处理：

1. 预处理出以内每个数的所有因数，复杂度。
2. 用和埃式筛类似的操作，预处理出以内每个数的素因数分解式，时间复杂度在和之间。（出题人比较菜，不会算严格的时间复杂度）

我们将满足条件的最小的称作对模的指数，接下来介绍一个引理：设是互素的正整数，。是一个与互素的整数。设模及模的指数分别为，则模的指数为。根据引理可知，我们只需要得到原题中对每个素数幂次的原根，就可以应用引理得到对的原根。而题目中限制了，则对于的每个素数幂次，都满足，可以说不会很大。

下面对的每个素数幂次进行分析。由欧拉定理可知，，则对的指数一定能整除，我们来计算的因数个数，我们考虑能不能逐一判断这些因数（第一种预处理使我们很容易从小到大遍历这些因数），将满足条件的最小因数作为原根。

可以估算出总的需要判断的因数个数并不是很大，用程序算出来在左右（而且不可能把3e5跑满），每次可以用快速幂判断是否满足条件，总时间复杂度为，注意到会超过int型变量的表示范围，在乘法的过程中注意不要爆long long，最好使用时间复杂度的乘法代替慢速乘，慢速乘的时间复杂度可能会TLE。

由于我们开始进行了第二种预处理，将读入数字处理成素因数分解式的形式、以及将询问数字处理成素因数分解式的形式的时间复杂度都不会超过。

哒哒哒~

数据范围保证 ，很容易想到可以使用的暴力+贪心来解决。

从低到高枚举表示七七身高的字符串 的每一位，对于第 位我们在字符串 里寻找第一个比它大的字符串是哪一个，记录此时的答案，再记录在 里刚好找到和第 位字符 相等的字符最小的位置，如果这个位置比第一个大于 的字符位置下标小，就继续计算下去，否则算法终止。

详细的讨论请见代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 5 * 1e3 + 10;
char s1[N], s2[N];
int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%s%s", s2, s1);
        int len1 = strlen(s1), len2 = strlen(s2);
        int ans = (1 << 30), tot = 0;

        int maxn = max(len1, len2);
        for (int i = 0; i < maxn; i++) {
            int flag = 0;
            int p = tot;
            for (int j = i; j < maxn; j++) {
                if (s2[j] > s1[i]) {   //找到第一个大于的位置
                    ans = min(ans, p + j - i);
                    flag = max(1, flag);
                    break;
                }
                else if (s2[j] == s1[i] && flag == 0) {  //第一个等于的位置
                    for (int k = j; k > i; k--)
                        s2[k] = s2[k - 1];
                    s2[i] = s1[i];
                    tot += j - i;
                    flag = 2;
                }
            }
            if (flag == 0)   //如果不存在一个字符大于或者等于s[i]
                break;
            else if (flag == 1) //如果第一个大于s[i]的字符下标更小一些，直接退出
                break;
        }
        if (ans == (1 << 30))
            puts("sorry");
        else
            printf("%d\n", ans);
        for (int i = 0; i <= maxn; i++)
            s1[i] = s2[i] = 0;
    }
    return 0;
}

梦中的鬼魂

此题完全可以把S串和T串等价为两个01串。等价成为01串之后：第一种操作等价于将S串中某一位取反，第二种操作等价于任意交换S串中两位的字母。显然当S[i]=T[i]时，我们不需要进行任何操作。当S[i]!=T[i]时，我们直接统计S串待修改的字母的个数，最后直接比较待修改的'G'与待修改的'H'的个数，输出两者之中的较小值即可。

LCY的QQ

这是一道结构体+sort的裸题，我们只需要定义结构体存储消息的各个属性，再按题目给定的优先级排序即可。

具体排序优先级为：是否特别关心是否置顶消息数编号。

输出时注意大于99条的消息转化为99+输出即可。