命题精神

A

出一套 CSP-J 的题目，不仅仅只是挑出四个难度和正赛相仿的题目，更在于让刚刚涉足 OI 的同学们看到一些好的思想，好的角度。

A 是一道找规律的题目，本身定位就是意在让选手猜出答案。实际上，在后续的 OI 各种比赛中，学会不加证明地运用某些实际正确的结论是很重要的。

手玩几组小数据，答案明显是 $n^2$。

实际上 $f(x)$ 就是我们常说的 $\text{lowbit}(x)$。

【结论】

$$\sum\limits_{i=k+1}^{2k}\dfrac i{\text{lowbit}(i)}=k^2$$

【证明 1】

令 $f(x)=\dfrac x{\text{lowbit}(x)}$，上面的和为 $s(k)$。

• 【引理 1】 $f(x)=f(2\cdot x)$
• 【引理 2】 $\forall a\in\{x\mid x=2\cdot k+1,k\in\textbf{Z}^+\},f(a)=a$

证明显然。

设命题在 $k=k_0$ 时成立，则 $s(k_0)=k_0^2$。

则有

$$s(k_0+1)=s(k_0)-f(k_0+1)+f(2\cdot k_0+1)+f(2\cdot k_0+2)$$

显然有 $f(k_0+1)=f(2\cdot k_0+2),f(2\cdot k_0+1)=2\cdot k_0+1$（直接运用引理得到）。

所以有

$$\begin{matrix} s(k_0+1)&=&s(k_0)+2\cdot k_0+1\\ &=&k_0^2+2\cdot k_0+1\\ &=& (k_0+1)^2 \end{matrix}$$

即命题对 $k=k_0+1$ 成立。

命题对 $k=1$ 显然成立，数学归纳，得到结论成立。

---

【证明 2】

发现可以把 $(k,2\cdot k]$ 里的所有数映射到 $1\sim 2\cdot k-1$ 的所有奇数，然后相加即可。需要证明如下结论：

【结论】 $(k,2\cdot k]$（下称 A 集）里的所有数的 $f$ 值恰好构成 $[1,2\cdot k-1]$ 中的所有奇数（下称 B 集）。

【证明】

设命题对 $k=k_0$ 成立，对于 $k=k_0+1$：

• A 集中少了 $k_0+1$，多了 $2\cdot k_0+1,2\cdot k_0+2$。
• B 集中多了 $2\cdot k_0+1$。

注意到由于引理，上述易证等价。

即命题对 $k=k_0+1$ 成立。

命题对 $k=1$ 显然成立，数学归纳，得到结论成立。

代码略。

B

首先，我们考虑：数列 $b$ 一定严格单调递减。

为什么呢？模了一个数 $C$ 后，所得的 $A'$ 一定小于 $C$，接下来再用一个 $D>C$，发现 $A'\bmod D=A'$，没有任何意义。

因此，先将 $a$ 从大到小排序。

而 $n\le20$，我们可以用二进制枚举。

即，用一个 $n$ 位的二进制数，若第 $i$ 位为 $1$，则表示选中 $a_i$；否则表示不选中。

时间复杂度 $O(n\log n+n\cdot 2^n)$。

当然 dfs 也是可行的。

以下代码均为单测。

// 二进制枚举
#include<cstdio>
#include<algorithm>
using namespace std;

int a[30],n,m,ans;

void dfs(int step,int x)
{
    if(step>=ans)return;
    for(int i=1;i<=n;i++)
    {
        if(x%a[i]==0){ans=step;return;}
        if(x>a[i])dfs(step+1,x%a[i]);
    }
}

int main()
{
    int j;
    scanf("%d%d",&n,&m);
    for(j=1;j<=n;j++)scanf("%d",&a[j]);
    ans=30,dfs(1,m);
    if(ans==30)printf("%d\n",-1);
    else printf("%d\n",ans);
    return 0;
}

// dfs
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

const int N = 50;
const int INF = 50;
typedef long long ll;

int n, a, cnt;
int num[N];
int vis[N], ans;
void DFS(int x, int dis) {
    if (dis >= ans) return;
    if (x == 0) {
        if (ans > dis) ans = dis;   
        return;
    }
    for (int i = 0; i < cnt; i++) {
        if (num[i] > x) break;
        if (!vis[i]) {
            vis[i] = 1;
            DFS(x % num[i], dis + 1);
            vis[i] = 0;
        }
    }
}
int main() {
    ans = INF;
    scanf("%d %d", &n, &a); 
    int temp, flag = 0;
    cnt = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp); 
        if (temp == a || temp == 1) {
            flag = 1;
            break;
        } else if (temp < a) {
            num[cnt++] = temp;
        }
    }
    if (flag) {
        printf("1\n");
        continue;
    }
    sort(num, num + cnt);
    DFS(a, 0);
    if (ans == INF) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}

C

处理前缀和然后对所有前缀和 $sum$ 模 $p$，于是原题的合并 $[l，r]$ 使得最后剩下的元素可以被 $p$ 整除，就等价为了判断 $sum[l-1]$ 是否等于 $sum[r]$。

接着考虑 dp。

设 $f[i]$ 表示序列 $1\sim i$ 的答案为多少。

显然如果要合并第 $i$ 个元素的话那么直到合出符合条件的元素才停（不然没必要合）。

那么就有 $f[i]=\max(f[i-1],f[pre[i]]+1)$。

其中 $pre[i]$ 表示与第 $i$ 个前缀和相等的前一个的前缀和的位置，当然如果没有 $pre[i]$ 的话 $f[i]=f[i-1]$ 即可。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e6+5;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,p,a[N];
int pre[N],f[N],lst[N];
void init(){
    for(int i=0;i<p;i++)lst[i]=-1;
}
int main(){
    n=read(),p=read();
    init();
    for(int i=1;i<=n;i++)a[i]=(a[i-1]+read())%p;
    for(int i=0;i<=n;i++){
        pre[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(pre[i]!=-1)
            f[i]=max(f[i-1],f[pre[i]]+1);
        else f[i]=f[i-1];
    }
    printf("%d\n",f[n]);
    return 0;
}

D

令 $f[i][j]$ 表示从字符串的 $i$ 位置和 $j$ 位置开始，能够满足 $k$ 相似的最长长度。

可以用尺取法在 $O(n^2)$ 的复杂度中求出来。

具体做法是：

• 枚举两个位置的间隔距离 $d$；
• 枚举 $i$ 和 $j$，$i$ 从 $1$ 开始，$j$ 从 $i+d$ 开始；
• 若 $f[i][j]=L$，那么 $f[i+1][j+1]$ 就是 $L$ 减去位置 $i$ 和位置 $j$ 的距离，再继续往后匹配；
• 对于每个 $d$，匹配的最后位置单调不减。

设 $ans[i]$ 表示在 $i$ 后面分割，能找出的 $k$ 相似字符串对数。

枚举位置 $i$ 和位置 $j$，考虑以 $i$ 和 $j$ 为起始位置的字符串的贡献。

设 $f[i][j]=x$。

也就是说 $s[i]=s[j],s[i+1]=s[j+1]$，……，$s[i+x-1]=s[j+x-1]$。

所以如果分割位置在 $i$，以 $i$ 和 $j$ 为起始位置的字符串会有 $1$ 的贡献，即 $s[i]$ 与 $s[j]$。

• 如果分割位置在 $i+1$，有 $2$ 的贡献，即 $s[i]$ 与 $s[j]$，$s[i]s[i+1]$ 与 $s[j]s[j+1]$；
• 如果分割位置在 $i+2$，有 $3$ 的贡献。
• ……
• 直到分割位置在 $i+f[i][j]-1$，有 $f[i][j]$ 的贡献。

当分割位置在 $i+f[i][j]-1$ 后面且在 $j$ 前面，都是有 $f[i][j]$ 的贡献。

当分割位置在 $j$ 后面，因为要求分割位置左右各选一个子串，所以无贡献。

另外，$j$ 不能超过分割位置，所以 $f[i][j]$ 与 $j-i$ 取小。

我们看以 $i$ 和 $j$ 为起始位置的字符串对不同的分割位置产生的贡献：

$0,0,0,1,2,3,\ldots,f[i][j]-2,f[i][j]-1,f[i][j],f[i][j],f[i][j],0,0,0$。

最前面的 $1$ 是从分割位置 $i$ 开始的，到分割位置 $i+f[i][j]-1$ 贡献依次加 $1$，然后从分割位置 $i+f[i][j]$ 开始贡献都是 $f[i][j]$ 不变，再从分割位置 $j$ 后贡献都是 $0$。

对这个贡献做一次差分得到 $0,0,0,1,1,1$ …… $1,1,1,0,0,-f[i][j],0,0$。

再做一次差分得到二阶差分 $0,0,0,1,0,0$ …… $0,0,0,-1,0,-f[i][j],f[i][j],0$。

对于每一对 $i$ 和 $j$，在答案的二阶差分里只修改 $4$ 个位置。

$i$ 位置 $+1$，$i+f[i][j]$ 位置 $-1$，$j$ 位置 $-f[i][j]$，$j+1$ 位置 $+f[i][j]$。

最后求两次前缀和还原答案序列。

小细节：在求 $f[i][j]$ 时，匹配位置可能超过 $n$。

在字符串的最后加一个特殊字符，然后限定匹配到 $n+1$，因为程序写法是到不合法位置停止。

#include<bits/stdc++.h>

using namespace std;

#define N 3002

char s[N];
int f[N][N];

long long ans[N];

int main()
{
    int n,m,dis,len,k;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            f[i][j]=0;
    for(int i=1;i<n;++i) ans[i]=0;
    s[n+1]='#';
    for(int d=1;d<n;++d)
    {
        dis=0;
        len=0;
        for(int i=1,j=i+d;j<=n;++i,++j)
        {
            while(dis<=m && j+len<=n+1)
            {
                dis+=s[i+len]!=s[j+len];
                ++len;
            }
            f[i][j]=len-1;
            dis-=s[i]!=s[j];
            len--;
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            ans[i]++;
            k=min(j-i,f[i][j]);
            ans[i+k]--;
            ans[j]-=k;
            ans[j+1]+=k;
        }
    for(int i=2;i<n;++i) ans[i]+=ans[i-1];
    for(int i=2;i<n;++i) ans[i]+=ans[i-1];
    for(int i=1;i<n;++i) printf("%lld\n",ans[i]);
    return 0;
}