本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-14 17:36:34

A

暴力枚举就可以了。

B

注意到删除操作最多 $100$ 次操作，不会出现删除操作的时候没有可以删除的卡牌的情况。

先进先出，队列维护。

C

显然在已经确定选择的球的数量的情况下，优先选择大的。

首先将黑色白色分别降序排列。

然后，枚举白色球选择的数量 $x$，然后，黑色球最优贡献值就是 $\max\limits_{y=x}^n pre_y$，$pre_i$ 代表前 $i$ 个黑色球的价值总和。
把 $pre$ 的后缀最大值预处理一下就可以了。

D

这道题无法使用状压 dp，原因在于无法将所需要的所有状态加入。

但是注意到 $n\le 10$，可以暴力枚举所有可能的路径，判断是否合法即可。

一个简单的实现是 $O(n!)$ 枚举全排列作为路径顺序，检查合法的过程则仅截取到 $n$ 第一次出现的位置。

E

考虑在 $x_i,y_i$ 之间建一条权值为 $z_i$ 的边。

注意到每一位都是独立的，并且由于异或的性质，同一个连通块只要有一个点的某一位翻转，连通块内所有其他节点的这一位也都需要翻转。

找到所有的连通块，对于每个连通块，随便找一个起始节点将其赋值为 $0$，然后求出连通块内每一位的 $0,1$ 数量。

根据这个数量决定每一位是否翻转即可。

F

考虑任意一对数造成的贡献。

• 对于 $\forall i \lt j,a_i \lt a_j$：
  会对 $k \in [m-a_j,m-a_i)$ 造成 $+1$ 的贡献。
• 对于 $\forall i \lt j,a_i \gt a_j$： 会对 $k \in [0,m-a_i),[m-a_j,m]$ 造成 $1$ 的贡献。

把包含 $i$ 作为未知量的归类到 $i$ 的贡献，包含 $j$ 作为未知量的归类到 $j$ 的贡献，同时包含的那一项拆一下也可以分别归类。

归类完之后可以转化为若干个区间加，最后统一查询一遍就可以。

G

这里

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-16 15:20:11

看到很多人使用了一些数学上的拆式子技巧，实际上根本不需要。

暴力做法

从小到大枚举 $x$，双指针计算 $y$。

遗憾的是，对于 $n$ 较大的情况，这样会寄掉。

一些性质

注意到一件事，假设 $k$ 固定，随着 $n$ 增大， $n^3-(n-k)^3$ 也会越来越大，而且增长速度很快。

计算器算一下可以发现当 $n\ge 10^9$ 的时候，$n^3-(n-1)^3 \gt 10^{18}$。

$k$ 不可能超过 $10^6$，否则无论如何，差值都会大于 $10^{18}$。

枚举 $k$，然后二分 $x$ 就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-20 16:16:53

Training Link: https://codeforces.com/contests/596860

本场难度最高的是 E 题，除此以外思考时间不需要超过半分钟。

A

题意

给定两个数 $a,b$。
每次给定一个区间 $[l,r]$，求区间内 $a,b$ 的最大公因数 。

Solution

升序预处理 $a,b$ 的所有公因数，每次询问二分求出最大的。

B

题意

有两种计数方法。
一种以 $1,2,3,\cdots$ 的形式。

另一种以 A 开始，一直到 Z，然后再到 AA，AZ,BA,BZ，一直到 ZZ，然后到 AAA，以此类推。

要求写一个程序将编号从两种形式之间互相转化。

Solution

考虑数字形式转化为字母形式，当前数字是 $x$。

首先枚举长度，首先从 $x$ 中减去长度比自己小的数量。

然后，从高到低计算每一位的值，从 $x$ 中减去这一位小于自己的数量。

一直到 $x$ 减到 $0$。

反过来，字母形式转化为数字形式也差不多，不过简单很多。

C

题意

做一个汉堡需要 $3$ 种材料，分别 $a,b,c$ 个。
给定你已经有的材料，每种材料的价格，你的钱数，求最多做多少个汉堡。

Solution

二分，或者不嫌麻烦的话，$O(1)$ 分段函数也可以。

D

题意

你可以进行任意数量的操作，每次可以在 $[1,k]$ 选择一个整数加上去，且必须至少有一次操作加的值大于等于 $d$，求最后操作结果为 $n$ 的方案数。

Solution

$dp_{i,j,0/1}$ 代表前 $i$ 个，总和为 $j$，是否已经有一个位置的值大于等于 $d$ 的方案数。

E

题意

给定 $n$，要求选择 $3$ 个不一定不同的小于等于 $n$ 的数，要求 $lcm(1,2,3)$ 最大。

题解

考虑一些贪心的方案。

比如选择 $n,n-1,n-2$，分情况讨论的结果：

如果 $n$ 是奇数，那么就是 $n(n-1)(n-2)$。

但是如果 $n$ 是偶数，那么 $(n,n-2)=2$，此时结果是 $\frac{n(n-1)(n-2)}{2}$。

考虑转化一下，选择 $(n-1)(n-2)(n-3)$，那么答案就是 $(n-1)(n-2)(n-3)$。

这样成功获得了答案的一个较大的上界。

由此可得，只需要将 $3$ 个数在 $[n-3,n]$ 之间枚举，就可以保证不出错。

上述已经可以解决本题，想要更快的速度，只需要再分讨一种 $n,n-1,n-3$ 的情况就可以了，这样凑齐了全部的可能情况。

F

题意

给定一个 $n\times m$ 的网格图，由空单元和障碍组成，保证空单元是联通的。

要求将恰好 $k$ 个空单元变为障碍，使得所有的剩余空单元仍然联通，要求构造出一组方案。

Solution

将所有的空单元建立一颗 dfs 生成树，每次只删除叶子节点就可以了。

G

题意

有 $n$ 个箱子，每个箱子有 $a_i$ 个物品。

单次操作可以选择一个箱子 $x$，满足 $2x+1 \le n$，从箱子 $x,2x,2x+1$ 各取出一个物品，如果没有物品则不取出。

求最少操作次数清空所有箱子。

Solution

显然是一颗完全二叉树。

如果存在一个节点，使得仅有一颗子树，那么其必然无法完成操作，这是因为这种节点只能出现在倒数第二层。

$dp_{u,i}$ 代表 $u$ 为根的子树，$u$ 自己还剩 $i$ 个，子树全部清空的最小代价。

转移是显然的。

最后，$ans = min(dp_{1,i}+i)$，但是注意如果 $n=1$ 那么无解。

H

题意

给定一个文件路径，要求对其简化，简化方法是将多个连续的 \/ 转化为 $1$ 个 \/，最后一段 \/ 全部删除（但是需要保证不会删空）。

Solution

扫一遍，只将每一段第一个 \/ 加入答案，最后将最后一段 \/ 全部弹出。

然后输出。

I

题意

有 $n$ 个本质相同的步兵，$m$ 个本质相同的骑兵，要求对其进行排列，要求不能有超过 $k1$ 个连续步兵，超过 $k2$ 个连续骑兵，求方案数。

Solution

$f_{i,j,k,l}$ 分别代表已分配步兵数量，已分配骑兵数量，当前连续步兵数量，当前连续骑兵数量。

升序枚举 $4$ 个量，正常转移就没问题。

J

题意

给定一个字符串 $s$，求最长的子串，使得其既是 $s$ 的前缀，又是 $s$ 的后缀，又在 $s$ 中间出现过。

Solution

枚举前缀，通过哈希判定对应后缀是否与自己相同。

现在需要求出的是最长的中间字符串使得其等于某个前缀。

容易发现这就是第 $2$ 到 $n-2$ 个非空前缀的 border 最大值。

使用 kmp 计算出每个位置的 border 值取最大的，到这里其实可以发现前缀与后缀的相等判定也不再需要，只需要枚举整个字符串的每个 border 长度作为前后缀就可以了。

K

题意

给定一个长度为 $n$ 的可能存在负数的整数数组。

求将其划分为 $3$ 个和相等的子数组的方案数。

Solution

计算出单个数组的和 $avg$，定义一段子数组合法当且仅当其和等于 $avg$。

先枚举第一段，使得第一段合法。

然后，问题转化为对于每个后缀，求出其划分为两个合法数组的方案数。

注意到一个性质，只需要第一个子数组合法了，剩下的那个一定也合法。

一段区间 $[l,r]$ 合法判定条件为 $p_r-p_{l-1}=x$。
考虑从 $n$ 倒序枚举后缀的起点，记当前起点为 $l$，那么当前后缀的答案就是满足 $p_r=x+p_{l-1}$ 的 $r$ 的数量，开个 map 记一下每个 $p$ 值的数量就行了。

L

题意

原题意太烦人了，就写点核心操作要干的事：

给定 $x$，求 $floor(0.8x),ceil(0.8x),floor(\frac{x}{0.8}),ceil(\frac{x}{0.8})$。

Solution

不要使用 double 不然容易被 hackers 干死。

考虑乘法下取整，将其转化为乘 $8$ 再除以 $10$，此时，如果原本结果就是整数，那么不会有问题，否则显然结果就是下取整的。

考虑除法，可以转化为乘法。

M

题意

给定一个 $n$ 个点的树，每条边标记了一个方向，代表这条边的指向。

需要确定一个点作为首都，随后有一个任务，需要到达树的所有节点（到达之后跳回首都），但只能沿着指向的方向走。

求有多少个点作为首都时，需要改变指向的边最少。

Solution

先以 $1$ 作为根（不一定是首都）。

然后，假设 $x$ 点是首都，那么答案就是除了 $x$ 到根路径以外所有的向上边，以及 $x$ 到根路径上所有的向下边。

这些都可以一次预处理的出来。

N

题意

有 $n$ 个物品，每个物品有对应价值，给定背包容量，求最多选多少个。

Solution

$f_{i,j}$ 代表前 $i$ 个总共用了 $j$ 的容量，求最多选了多少个物品数量。

O

题意

有一个长度为 $2^n$ 的数列。
第一次操作将相邻两项变为其 OR 值然后合并。
第二部将相邻两项变为其 XOR 值然后合并。
第一次操作将相邻两项变为其 OR 值然后合并。
就这样 OR,XOR 交替，操作 $n$ 次。

每次询问修改一个位置的值，回答修改之后，这个数列最终剩余的数的值。

Solution

注意到本题单点修改，支持 $O(1)$ 合并两个子树的答案。

建立一颗线段树维护就可以了。

P

题意

有一个 $n\times m$ 的网格图。

单次跳跃可以横向或纵向跳恰好 $s$ 单位，求有多少个位置可以跳到最多的位置。

Solution

横纵分开考虑，以下仅考虑横向最多位置。

注意到前 $1+(n-1)\bmod s$ 个位置可以跳到尽可能多的位置。

然后，自然地，一个可行地位置加上 $s$ 仍然是可行的。

所以答案就是 $\lfloor \frac{n}{s}\rfloor (1+(n-1)\bmod s)$。

纵向同样方式计算，答案乘起来就行。

Q

题意

给定 $l,r$，求 $\forall l\le a\le b\le r$，最大的 $a\oplus b$。

Solution

首先，忽略掉 $l,r$ 的二进制表示下的公共前缀。

假设确定了答案的最高位为 $i$，那么两个数必然一个是 $2^i$，一个是 $2^i-1$。

R

题意

给定一张图，保证其为一条链，输出它。

Solution

随便选一个点，如果度数为 $1$，那么一直走下去就可以。

如果度数为 $2$，那么两个出点分别 dfs 就行。

S

题意

给定 $a,b$，满足 $a\ge b$，求 $\frac{a!}{b!}$ 的质因数个数。

Solution

注意到乘法过程中，质因数个数会相加，除法则相减。

线性筛预处理每个数的质因数个数，剩下的事就非常简单了。

T

题意

给定一个整数数组 $a$，值域 $[1,10^7]$。

令 $f(x)$ 代表 $a$ 中能整除 $x$ 的数的个数。

多次询问，每次给定一个区间 $[l,r]$，令 $S$ 代表 $[l,r]$ 的质数集合，求 $\sum\limits_{v\in S} f(v)$。

$1 \le l \le r \le 10^9$。

Solution

线性筛预处理出所有数的质因数，然后，预处理每个质数的贡献，前缀和计算答案。

U

题意

一个 01 串合法当且仅当可以通过【将连续 $k$ 个 $1$ 变为 $0$】 的操作将所有数变为 $0$。

多次询问，每次询问 $[l,r]$，求长度在 $[l,r]$ 之内的 01 串个数。

Solution

$f_{i,0/1}$ 代表长度为 $i$，最后一个数是 $0/1$ 的方案数，转移显然，前缀和预处理一下就可以 $O(1)$ 算答案。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-04-09 13:13:43

虽然我的做法比较唐，但好像没人用双端队列，就来交一个。

做法

假设现在考虑前 $i$ 个，且第 $i$ 个属于上升序列的。

那么，贪心的想一下，显然是此时下降序列的最后一个数的值越大越好。

设 $f_{i}$ 代表考虑前 $i$ 个数，第 $i$ 个数属于上升序列，此时下降序列的最后一个数的最大值是多少。

转移的话，考虑上升序列中 $i$ 的前一个位置 $j$，分类讨论 $j \lt i-1$ 和 $j = i-1$，不存在 $j$ 三种情况。

• 若 $j \lt i-1$。
  那么只要存在一个合法的这样的 $j$，那么 $f_i \leftarrow a_{i-1}$。而一个 $j$ 合法的条件是 $f_{j} \gt a_{j+1}$，并且 $[j+1,i-1]$ 是严格降序。现在问题是怎么快速判定符合条件的 $j$ 是否存在。注意到 $f_j \gt a_{j+1}$ 这个条件仅和 $j$ 有关，考虑每计算出一个 $f_k$，若 $f_k \gt a_{k+1}$，那么将其加入一个双端队列的末尾，若 $a_k$ 小于等于双端队列的末尾对应位置的值，那么就把队尾弹出。这样就形成了一个值递增的单调队列。另外，观察第二个条件，容易发现其对于 $j$ 的限制是单调不降的，所以每次可以从双端队列头部弹出不符合第二个条件要求的位置。由于队列的值递增，此时最优的位置一定是队列第一个位置。
• 若 $j=i-1$。
  只需要满足 $a_{i} \gt a_{i-1}$ 就行了，转移是 $f_{i} \leftarrow f_{i-1}$。
• 若 $j$ 不存在。
  此时需要满足 $[1,i-1]$ 是严格递减，$f_i \leftarrow a_{i-1}$。

一个细节：可以令 $a_0 = \infty$，代表不存在递减序列时，递减序列最后一个数是无穷大，后面接什么都可以。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=2e5+5;
int n;
int a[maxn];
int des[maxn];
int dp[maxn];
int lst[maxn];
deque<int> okids;
bool added[maxn];
bool ans[maxn];
bool wait[maxn];
void solve(int id_of_test){
	read(n);
    bool alldes=1;
    FOR(i,1,n){
        read(a[i]);
    }
    FOR(i,2,n)alldes&=(a[i]>a[i+1]);
    if(alldes){
        puts("YES");
        FOR(i,1,n)printf("%d ",1);
        pln
        return;
    }
    FOR(i,1,n){
        if(a[i]<a[i-1])des[i]=des[i-1];
        des[i]++;
    }
    a[0]=1e9;
    dp[0]=1e9;
    FOR(i,1,n){
        
        bool can_be_add=0;
        int lim=i-1-des[i-1];
        while(!okids.empty()&&okids.front()<lim){
            okids.pop_front();
        }
        if(!okids.empty()&&a[okids.front()]<a[i]){
            ckmx(dp[i],a[i-1]);
            lst[i]=okids.front();
            can_be_add=1;
        }
        if(a[i]>a[i-1]&&added[i-1]){
            ckmx(dp[i],dp[i-1]);
            if(dp[i]==dp[i-1])lst[i]=i-1;
            can_be_add=1;
        }
        \/\/ 还有一种情况，它是第一个节点
        if(des[i-1]==i-1){
            ckmx(dp[i],a[i-1]);
            if(dp[i]==a[i-1])lst[i]=0;
            can_be_add=1;
        }
        if(a[i+1]<dp[i]&&can_be_add){
            wait[i]=1;
        }
        added[i]=can_be_add;
       
        if(wait[i-1]){
            while(!okids.empty()&&a[i-1]<=a[okids.back()])okids.pop_back();
            okids.eb(i-1);
        }
       \/\/ printf("lst[%d] = %d\n",i,lst[i]);
    }
    FOR(i,1,n)ans[i]=1;
    REP(i,n,n-des[n]){
        if(added[i]&&(i==n||a[i+1]<dp[i])){
            puts("YES");
            int nw=i;
            while(nw>=1){
                ans[nw]=0;
                nw=lst[nw];
            }
            FOR(i,1,n){
                printf("%d ",int(ans[i]));
            }
            pln
            return;
        }
    }
    puts("NO");
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 16:10:13

本题仍然参照了其他题解，原因是最后一步没能转化为 dirichlet 卷积的形式。

假设 $n \le m$。

需要求解的：$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \mu(lcm(ij))$。

引理：$\mu(lcm(i,j))=\mu(i)\mu(j)\mu((i,j))$。
这个比较简单，我都能发现，较为显然不用证明。

原始转化为 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \mu(i)\mu(j)\mu((i,j))$
$= \sum\limits_{d=1}^n \mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \mu(id)\mu(jd)[(i,j)=1]$
$= \sum\limits_{d=1}^n \mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} (\mu(id)\mu(jd)\sum\limits_{k|(i,j)} \mu(k))$
$= \sum\limits_{d=1}^n\sum\limits_{k=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{i=1}^{\lfloor \frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{kd} \rfloor} \mu(d)\mu(k)\mu(ikd)\mu(jkd)$。

这是关键的一步，令 $T=kd$，此处的用意在于将前两个 sigma 转化为卷积的形式，并将后面的 $kd$ 合并为一个变量。

原式变为 $\sum\limits_{T=1}^n \sum\limits_{d|T}\mu(d)\mu(\frac{T}{d})\sum\limits_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{T}\rfloor}\mu(iT)\mu(jT)$。

对于每个 $T$，$\sum\limits_{d|T}\mu(d)\mu(\frac{T}{d})$ 可以 $O(n\log n)$ 预处理，而 $\sum\limits_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{T}\rfloor}\mu(iT)\mu(jT) = (\sum\limits_{i=1}^{\lfloor \frac{n}{T}\rfloor}\mu(iT))(\sum\limits_{j=1}^{\lfloor\frac{m}{T}\rfloor} \mu(jT))$，这个也可以暴力计算。

最后复杂度 $O(n \log n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 16:53:09

这场 vp 起飞了，Div.1,Div.2 选手都算，在现场也是二十几名的位置。

A

模拟就行。

B

$dp_i,j$ 以第 $i$ 个结尾，模 $4$ 等于 $j$ 的子串总数。

C

每次贪心的尽可能选距离远的，只要不超过 $k$。

D

差分一下，设 $f(i)$ 表示 $[0,i]$ 有多少个能被 $m$ 整除的魔法数字。

那么答案就是 $f(b)-f(a-1)$。

设 $f_{i,j,0/1}$ 代表仅考虑前 $i$ 位，当前数字取模 $m$ 的结果是 $j$，并且当前数字是否已经确定小于限制。

转移是显然的。

E

可以枚举 z 字形的左下角，假设是 $(x,y)$。

首先，预处理出 $(x,y)$ 右边最多延申多长，记为 $d$。

显然，向上延申的长度不能超过 $d$。

假设向上延申 $k$ 的长度，即 z 字形右上角为 $(x-k,y+k)$，那么有两个必须满足的条件：

1. $(x-k,y+k)$ 必须向左能延申至少 $k$ 的长度。
2. $(x,y)$ 到 $(x-k,y+k)$ 的对角线上必须全部是 z。

值得一提的是，我 vp 的时候因为没注意条件 2 吃了 4 发罚时。

现在，升序枚举 $(x,y)$，考虑枚举的时候需要怎样操作。

枚举之前先 $O(nm)$ 预处理每个点向右，向左最长连续多少个 z，设 $p_i$ 代表 $i$ 点开始向左最多连续 $p_i$ 个 z，$q_i$ 代表 $i$ 点开始向右最多连续 $q_i$ 个 z。

对于每个 $(x,y)$，我们主要关心的是其所在的正对角线上有多少个点能作为 z 字形的右上角。

一个点 $i$ 想要满足条件，那么要求是这个点与 $(x,y)$ 的行的差 $d_i$ 需要小于等于 $p_i$。

考虑对于每个正对角线，都维护一个这样的集合，记录这条线上每个点的 $d_i-p_i$，只有这个集合内部的点才是有可能符合要求的。

随着 $(x,y)$ 升序枚举，$d_i-p_i$ 单调不增，所以每次枚举 $(x,y)$ 都会导致其所在对角线上的一些点被删除。

但是，对于单个 $(x,y)$ 还有个额外限制，就是符合要求的点与 $(x,y)$ 的行差 $d_i$ 必须小于等于 $(x,y)$ 向右的最长连续 z 长度 $q_{x,y}$，这个使用树状数组就可以维护，每次更新集合，也需要更新树状数组。

F

这题最难的点在于想到网络流。

Limak 给的关于值域的前缀元素个数，本质上给出了每个值域区间的元素个数。

而每个值域区间，能给模 $5$ 同余 $0,1,2,3,4$ 的数字数量贡献多少也是可以计算出来。

最后，它也给出了模 $5$ 同余 $0,1,2,3,4$ 的数字数量应该是多少个。

现在建模已经很显然了。

复杂度证明

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 17:08:33

考虑逐步分解其每一位。

首先，考虑最后一位应该是什么样的。

先计算出 $n$ 取模 $R$ 的结果（非负）。

然后，把这一位从 $n$ 中去掉，继续分解，以此类推。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 17:12:42

首先明确一点：非平行的直线都一定会相交，每对相交的直线贡献一个交点。

设 $f_{x,s}$ 代表已经存在 $x$ 个直线，交点总数为 $s$ 是否可行。

爆搜就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 18:35:41

符合条件的 $x$ 肯定是 $b_1$ 的因数，暴力枚举并检查合法性就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 19:53:02

A

考虑倒推一开始的苹果总数，记为 $ans$。从最后一个顾客倒序枚举，如果没有赠送，那么 $ans \leftarrow 2ans$，如果赠送了，$ans \leftarrow 2ans+1$。

这样，计算出了一开始的苹果总数，然后再根据购买情况计算收益就可以了。

B

将原序列中原本属于 A 的设计为正值，原本属于 B 的值取反。

然后 Bob 显然会选择权值最大的前缀或后缀。

C

结论：字符串 $a,b$，$a$ 在 $b$ 前面当且仅当 $a+b$ 的字典序小于 $b+a$ 的字典序。

反证法易证。

D

设 $f_x$ 为数组中 $x$ 的因子个数。

答案显然是 $\max\limits_{x \in [1,l]}f(x)$。

E

本题正解为 FFT，但是暴力也可以通过，考虑暴力怎么写。

恰好 $k$ 个的限制很烦人，如果是小于等于 $k$ 个就简单多了。

实际上，只要有一个权值为 $0$ 的物品就可以满足这个要求。

没有怎么办？

那就将所有物品的权值减去最小值。

然后 dp 就非常简单了。

F

本题我被卡死，主要原因在于我对 MST 的性质不是很熟悉。

很像是一个邻接矩阵，考虑以此解题。

$a_{i,j} \le \max(a_{i,k},a_{k,j})$ 的限制，可以理解为一条边的权值不能是任意一个包含它的环的严格次大值。

刚好 MST 的树边也有这个性质，那么如何检测非树边？

假设存在一个不合法的非树边，考虑枚举这个非树边的其中一个端点作为树的根节点，若某个点与根的边权大于它通过树边到根的路径最大值，那么不合法。