CVBB ACM Team

题意:钻石铲要$2$个木棍$1$个钻石，钻石剑要$2$个钻石$1$个木棍，现在有$a$个钻石和$b$个木棍，问最多能做多少把武器。

题解:这题叫Shovels and Swords，第一反应就是MC，还真是。不妨设$a \le b$，如果$2a>b$，答案为$\frac{a+b}{3}$，否则答案为$a$。

题意:一开始只有一个位置是$1$，其它都是$0$，按照顺序可以将一个区间内任意两个数字交换，问有多少个下标最后可能是$1$。

题解:按顺序求有重叠的区间的并集即可。

题意:$n \times m$的方格图，每个格子为$0$或$1$，要求每条从左上角到右下角（只能走右下）的路线所组成的字符串都是回文串，需要最少改变多少格子的数字。

题解:每个格子只会出现在固定的位置，统计一下每个位置$1$和$0$的数量取最小值即可。

题意:给定数字$x$，求满足条件$a|x,b|x,gcd(a+b,x)=1$的一组$a,b$，或判断无解。

题解:如果$x$只有一种质因子，那显然无解。否则将$x$分为$a,b$两部分即$ab=x$且$gcd(a,b)=1$，有$gcd(a+b,x)=gcd(a+b,ab)=1$。证明如下，首先需要两个前置芝士，$gcd(a,b)=gcd(a+b,b),gcd(a,b)=1 \rightarrow gcd(a,bc)=gcd(a,c)$。利用这两个结论，我们可以得到$gcd(a,b)=gcd(a+b,b)=1 \rightarrow gcd(a+b,ab)=gcd(a+b,a)=gcd(a,b)=1$。

题意:给出$a,b$两个数组，长度分别为$n,m$，保证$b$严格单增，现在要将$a$分为连续的$m$段，使得第$i$段的最小值等于$b_i$，求分段方案数，模$998244353$。$(1 \le n, m \le 2 \cdot 10^5)$

题解:可以发现如果$a$中一个数很小，那么即使它很靠后，也只能被分到前面的组。因此我们从小到大考虑$a$中的每个值最靠右的位置，和去和$b$中的值一一对应。对于不属于$b$数组的值$a_x$，设$b_i<a_x<b_{i+1}$，显然它必须归属于$b_i$对应的组。因此我们可以算出$b_i$每个值在$a$中分组的左右边界，如果出现边界重叠或者某个值在$a$中没出现自然无解，否则从左到右扫一遍乘以边界差值即可。

题意:给出一个$n$个点$m$条边的无向连通图，每条边有权值$w_i$，不保证没有重边自环，设$f(i)$为从$1$号点出发的经过$i$条边的所有路径中最长路的长度，求$\sum_{i=1}^{q}{f(i)} \mod 10^9+7$。$(2 \le n \le 2000, n - 1 \le m \le 2000, m \le q \le 10^9, 1 \le w \le 10^6)$

题解:可以发现对于任意一个$f(i)$对应的最长路一定可以分解成从$1$走到某个点，然后在某条边两边反复横跳。那么我们可以先暴力$O(n^2)$求出走$m$次的情况，求出停留在每个点对应的最长路长度$b_i$，以及连接每个点的最长边长度$k_i$，题目转变为$n$个形如一次函数$y=k_i \times (x-m) + b_i$，求横坐标$m$到$q$这个区间内位于最上面的直线是哪些。可以直接上半平面交，不过由于$n$比较小，所以我们可以$O(n^2)$求出每个交点，然后套等差数列求和公式即可。

题意:

题解: