实际上的难度排序：ABCEDGF

为什么有点乱序，因为CD同一个题所以放一起了，然后我特别喜欢F题这个题号，然后F题又是这场我最喜欢的题，所以就放F了。

std发布在题解评论区一楼中

A、炸鸡块哥哥的粉丝题

按照题意模拟即可

B、智乃想考一道鸽巢原理

经典hack数据

2
3
1 2 3
6
1 1 1 1 1 1

有个叫摩尔投票的经典算法

摩尔投票是一种用来解决绝对众数问题的算法。

在一个集合中，如果一个元素的出现次数比其他所有元素的出现次数之和还多，那么就称它为这个集合的绝对众数。等价地说，绝对众数的出现次数大于总元素数的一半。

然后这道题题意每次去两个不同的数相消，就是摩尔投票的过程。

根据摩尔投票，有以下两点重要结论：

1. 如果存在绝对众数，则无论过程，最终只会出现绝对众数。
2. 如果不存在绝对众数，且元素总数为偶数，则必定存在一种方案使得所有元素凉凉相消。

由这两点重要结论，尝试从结果入手

1. 如果存在绝对众数，则绝对众数的答案为1，其他0。
2. 否则因为奇数最后至少会剩下一个，偶数至少剩下两个，所以奇数就先枚举每个元素，一开始就偷偷拿走一个/两个，然后再判是否存在绝对众数，以及绝对众数是不是它。

C/D、智乃想考一道完全背包

背包问题有一种虚拟物品的技巧，是指将某些限制条件也当成物品的一部分，或者将某个物品拆分成多个物品。

easy

如果你觉得easy卡常，你可以使用解法。

先说一下经典错解，考虑从中间切开，这样要么多放，要么限制条件无法保证被满足。

hack数据：

3 8 2
1 3
5 10
2 8

显然对于一个限制为的条件，利用前缀和/差分数组的思想就相当于所有包含位置的子区间，区间所有物品的和虚拟成一个物品放入背包。这样一定能满足限制条件，因为对于前缀和来说，这表示a[l]++,a[r]--。这样左边都是正的，右边都是负的，相当于中间高，两端低。

看上去时间复杂度为但是实际上，因为到后面超大物品根本就放不下，所以实际上是，复杂度为。顺带一提，使用hard中的贪心技巧，可以将其优化到。

hard

hard版本有三种解法，我觉得都很有价值，其中背包解法的常数很小，可以卡到半秒以内。

背包DP

考虑从easy版本中暴力枚举每个位置优化过去。第个位置的物品实际上和第,个位置绝大部分都是重叠的。如果能安排一个合理的求解顺序，在不影响答案的前提下尽可能多的将已经放置的物品转移到多个背包中，就能快速求解。

考虑状态转移的后效性，发现真的能安排一个合理的求解顺序在互不影响的前提下全求了。

存在转移方程：其中表示限制，表示背包的容量。

代码相当简洁漂亮，但是确实不是很好想。复杂度，下面那个循环不是的，因为超过就放不下了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005, MAXM = 505;
long long w[MAXN], v[MAXN], dp[MAXN][MAXM], ans[MAXN][2];
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld %lld", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        w[i] += w[i - 1];
        v[i] += v[i - 1];
        ans[i][1] = 1;
    }
    for (auto i = 1; i <= n; ++i)
    {
        for (auto j = n; j >= i; --j)
        {
            long long W = w[j] - w[i - 1];
            long long V = v[j] - v[i - 1];
            for (auto k = W; k <= m; ++k)
            {
                dp[j][k] = max({dp[j][k], dp[j + 1][k], dp[j][k - W] + V});
            }
        }
        for (auto j = 0; j <= m; ++j)
        {
            if (dp[i][j] > ans[j][0])
            {
                ans[j][0] = dp[i][j];
                ans[j][1] = i;
            }
        }
    }
    for (auto i = 1; i <= m; ++i)
    {
        printf("%lld%c", ans[i][0], " \n"[i == m]);
    }
    for (auto i = 1; i <= m; ++i)
    {
        printf("%lld%c", ans[i][1], " \n"[i == m]);
    }
    return 0;
}

区间dp

考虑限制条件，把它扩一下变成。

即中间某一段相等，两边递降，我们将这个限制条件称之为，我们发现，当满足的限制条件后，再往里面多放一个虚拟物品，它就可以自然转移到，反之如果往里面多放一个的虚拟物品，就可以转移到。

所以可以设计一个区间DP的算法，满足限制条件。

但是编码上可能不太好实现，需要滚动数组优化，不过稍加优化，就可以优化到上一种背包dp的方法。

贪心解法

因为是完全背包，所以可以直接按照体积贪心，每种体积只用保留价值最大的物品，其他都没用。

所以先贪一波，将物品降低到个，然后发现可以直接暴力了。

E、智乃想考一道莫比乌斯反演杜教筛求因子和的前缀和

这个题是诈骗，因为根本不需要反演，不要看见就走不动路。

不要上来写个这个东西，然后真的尝试凑反演

设

则原式为

右侧整除分块处理，左侧直接求和。

F、智乃想考一道模拟题

这道题是假的spj，答案是唯一解，可能大部分人都不知道考点是啥。

首先，如果你没读懂题，请运行以下代码

int f(int a,int b)
{
	return b==0?a:f(a^b,(a&b)<<1);
}

这个就是为什么“异或”又被称为半加运算，因为它真的是一半的加法，相当于加法不进位。

而给他补上进位的部分，就实现了加法，又被称为全加器。

所以这道题实际上就是给你两个二进制高精度数的和，然后告诉你和的某些位，但是保证不存在问号导致进位的情况。

问你的值，以及进位次数最大的进了几次位。

所以先利用高精度减法求，然后再反过来高精度加法求，求进位次数，验证正确性即可。

G、智乃想考一道平衡树

这个题实际上很无聊的套路，就是双端队列整体打lzay标记。

因为太无聊了，所以加了一个乘以的坑点。

怎么处理呢，考虑经典加乘懒标记，在计算答案时，类似这种形式。

假设其中的某个的值为零比如，发现里面的值全部失效，并且相当于从开始令重新计算。

这样只需要找到一个最近的的位置开始计算就可以了。代码实现上，我们对入队的每个打上时间戳，当存在乘以时，就令队列内的时间戳小于当前时间戳的全部失效，计算值时将其直接等于进行计算。