P8940 不见故人题解

E_huan · 2023-01-28 22:59:55 · 题解

前言，考场上写了一个和标算不同的贪心做法，但是少个对于全部相同的特判得分 95，考后加了特判就 AC 了。后来题目提供者 Cocoly1990 私信我问能不能证明正确性，我尝试证明了一下，我们都觉得挺对的，遂发题解。如果发现这个证明有问题请指出，感激不尽！

做法：

找出所有长度大于 k 的等于全局 gcd 的段，以它们为分界线得到若干个段。

若段内 gcd 超过全局 gcd，则多带上旁边的一个全局 gcd。但是发现连续两端带上旁边的 gcd 之后就可能会导致把这段全局 gcd 选了反而更优。

贪心地，从前往后看，若本来的 gcd 段是 k+1，且左右需要延申，就把左右两端连上，并且标记这两端都不需要延申了。

正确性说明：

不难发现最终结果肯定是所有数变成全局 gcd ，而每个位置最多被修改一次（如果修改两次则一定可以有办法不修改第一次，且答案不劣），所以当有一段的 gcd 不是全局 gcd 的时候，它们修改了也不是全局 gcd，一定不优，所以肯定会选择与旁边的若干个数合并使得 gcd 变成全局 gcd。

所以最终的策略肯定是操作若干个不交的段，且段与段之间必定间隔至少 k+1 个等于 gcd 的元素（否则两段合起来一次变化肯定不劣）。

称段内 gcd 不是全局 gcd 的被分隔出的段为“非法段”。

最开始以长度大于 k 的等于全局 gcd 的连续段作为分隔的构造，在假设所有段都不是非法段情况下肯定是最优的。而对于非法段，如果不吞掉完整的分割段，那在分割段上取 >1 个肯定没有取恰好 1 个优，且取恰好一个就可以使其合法了。

那么考虑什么时候会吞掉完整的分割段。非法段向旁边（左边或右边）的段取 1 个的时候，可以看作让这段长度 -1，由于分割段长度 >=k+1，只有长度恰好是 k+1 且左右都向它取的时候，它的长度变成 k-1，直接把它吞并更优。

全都不吞的情况下已经确定了一个答案，如果能满足吞的条件就可以使答案减小 1，所以尽可能使它满足吞的条件。贪心地确定每个非法段是向左使分割段长度 -1 还是向右，尽可能让更多的长度是 k+1 的段的左右都向它 -1。

如果对于非法段，满足“它左边的分割段长度是 k+1 且这个分割段的左边的段选择在这个分割段 -1” ，那么该段和分割段的前一段一定能消去这个分割段，而该段和后一段未必可以，所以该段选择向左 -1 ，消去这个分割段一定不劣。如果不满足这个条件，则它和前一段一定不能消去它左边的分隔段，与右边的可能可以，所以选择让右边的分割段 -1 一定不劣。

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
inline int read()
{
    int res=0; bool f=0;
    char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) res=res*10+(ch^'0'),ch=getchar();
    return f?-res:res;
}
const int N=4000010;
int n,k,a[N];
int l[N],r[N],tot;
int del_l[N],del_r[N];
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    int ed=a[1];
    for(int i=2;i<=n;i++) ed=gcd(ed,a[i]);
    for(int i=1;i<=n;i++)
        if(a[i]==ed)    
        {
            if(a[i-1]!=ed) l[++tot]=i;
            if(a[i+1]!=ed)
            {
                if((l[tot]!=1)&&(i!=n)&&i-l[tot]+1<=k) tot--;//长度不够(但是特判左右两端长度不够也是要的)
                else r[tot]=i;//长度够k+1
            } 
        }
    if(l[1]==1&&r[1]==n) {puts("0"); return 0;}//特判只有一段全是ed，否则最后“ans+(cnt+1)*k”会挂
    for(int t=1,L=1;t<=tot;t++)
    {
        if(l[t]==1) {L=r[t]+1; continue;}//开头就是全局gcd段就不用管了
        int g=a[L];
        for(int i=L+1;i<l[t];i++) g=gcd(g,a[i]);
        if(g!=ed)
        {
            if(del_l[t-1]&&(r[t-1]-l[t-1]+1==k+1))
            {
                del_r[t-1]=1;
                continue;
            }
            else del_l[t]=1;
        } 
        L=r[t]+1;   
    }
    if(r[tot]<n)
    {
        int g=a[r[tot]+1];
        for(int i=r[tot]+2;i<=n;i++) g=gcd(g,a[i]);
        if(g!=ed) del_r[tot]=1;
    }//后面一段
    int ans=n,cnt=0;
    for(int t=1;t<=tot;t++)
        if(!(del_l[t]&&del_r[t]))//没有被删除的段
        {
            for(int i=l[t]+del_l[t];i<=r[t]-del_r[t];i++)
                ans--;//ans是长度
            if(l[t]!=1&&r[t]!=n) cnt++;//有效间隔数
        }
    printf("%d\n",ans+(cnt+1)*k);
    return 0;
}

P8940 不见故人 题解

做法：

正确性说明：

代码实现：

P8940 不见故人题解