来自FallDream的博客，未经允许，请勿转载

---

奇怪的O(n)大赛，三道题数据都是几百万，真吓人。

-------------------------------------------------

A.交易♂

一个坐标轴上有n个商人，分别在坐标x1.x2..xn(保证递增且都是正整数)，你和商人在同一位置的时候你可以和他交易，他在t秒后会丢下一个货物，你和货物在同一位置的时候可以拿走那个货物。移动一个单位花费时间1，捡起货物和交易不消耗时间，你一开始在0号点求拿走所有商人的货物并且走到点m(m>x)的最小时间。

n<=3000000 x,m,t<=10^9

题解：显然最优解是我们走很多段，每一段中，我们都是在走过去的时候先交易一下，然后往回走，再往前走，拿走所有货物。

用f[i]表示拿到前i个货物并且到达第i个点的最小时间，n^2dp很好列出:$$f[i]=max(f[j]+s[i]-s[j]+max(2*s[i]-2*s[j+1],t)$$

考虑优化，但是这个max怎么办呢？我们可以把它拆成两部分，一部分等待时间都是t，只需要求一个最小的坐标更新答案，另一部分我们记一下f[j]-s[j]-2*s[j+1]的最小值就行了，复杂度O(n)

我比较傻还上了一个单调队列

#include
     
      #include
      
       #define MN 3000000#define INF 10000000000000000LL#define ll long long#define getchar() (*S++)using namespace std;char B[1<<26],*S=B;inline int read(){    int x = 0;  char ch = getchar();    while(ch < '0' || ch > '9') ch = getchar();    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x;}int n,q[MN+5],top,tail;ll m,t,f[MN+5],mn=INF,s[MN+5];inline ll get1(int x,int y){    while(top>=tail&&q[tail]
       
        =tail&&f[x]-s[x]
        
         =t)mn=min(mn,f[j]-2*s[j+1]-s[j]),++j;        ll res1,res2;        res1=j
        
       
      
     

B.字符串

给定两个长度都是n的字符串，你要通过一种变换使得第一个字符串变成第二个字符串，求最小变换次数。

所谓的变换是指，对于一个区间[l,r]，从前往后，每个字符都可以变成上一个变成的字符，或者不变。

如果无法完成，输出-1   n<=3000000

题解：考虑贪心。我们定义一个k，初始k=n,然后从后往前对于第二个字符串中的第i位，从第一个字符串的第k位之前找一个和它相同的字符，从那个字符更新它肯定最优。

那么我们用f[i]表示第i个字符在多久之前被占用，也就是有多少个操作覆盖了它。那么每次k前移，f[i]都会+1，而每个$k\leqslant j<i$的j都要用它来更新下一个，也就是说f[j]=max(f[j],f[j+1])+1.

很显然f[j]一定不会比f[j+1]大,所以f[j]=f[j+1]+1,也就是整个数组的前半部分被我们后移了一位，然后+1  最后答案就是f的最大值.

考虑实现，后移直接用一个变量统计，+1操作通过差分实现，时间复杂度都是O(n)

#include
     
      #include
      
       #define MN 3000000using namespace std;inline int read(){    int x = 0;; char ch = getchar();    while(ch < '0' || ch > '9')  ch = getchar();    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x;}int n;int x[MN+5],now=0,move=0,ans=0;char s[MN+5],s2[MN+5];int main(){    freopen("string.in","r",stdin);    freopen("string.out","w",stdout);    n=read();scanf("%s",s+1);scanf("%s",s2+1);    for(register int i=n,k=n;i;i--)    {        if(k>i&&s2[i]!=s[i]) k=i;        now+=x[i+move],x[i+move]=0;        if(k<=i&&s2[i]!=s[k])        {            while(k&&s[k]!=s2[i]) --k;            if(!k) return 0*puts("-1");            move++,x[k+move-1]-=1,++now;            ans=max(ans,now);         }    }    printf("%d\n",ans);    return 0;}
      
     

C.矩阵

有一个n*n的矩阵，其中有m个黑块。如果有两个块(x,y)(y,z)都是黑块，那么你可以把(z,x)涂黑。求你最多能涂黑多少块。n,m<=1000000

题解：很容易想到转化成图论模型，黑块(x,y)表示第x个点向第y个点连边。那么考虑暴力染色，将i能到的所有点染色成(col[i]+1)%3

如果存在一种合法的染色方案，且颜色012都有出现，那么此时所有点0向所有点1都有连边，1->2,2->0同理

这个很容易证明，假设你有一个图，所有0->1,1->2,2->0都有连边，那么你随意加入一个点，假设是一个0->1,那么因为所有2都向0连边，所以新加的点向所有2都有连边，那么又因为2到所有0都有连边，所以所有0到他都有连边，所以新图同样满足这个结论。而012都出现的图可以看作一个简单的0->1->2->0三个点组成的环，你把其他所有点塞进去，一定还是满足的。

如果存在一种合法的染色方案，且颜色012没有全部出现，那么此时肯定没有新增的边，这个很好理解。

如果没有合法的染色方案呢？这时候所有点向所有其他点,包括自己，肯定都有边。这个结论同样可以证明，当然也可以 打表/画图 观察发现。

严格证明我不会，但是你可以随意选出一个长度不是3的倍数的环，你会发现边都是满的。

大概就是这样，每个联通块跑一跑就没了，复杂度O(n+m)吧。

#include
     
      #include
      
       #define ll long longusing namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}struct edge{
   int to,next,kind;}e[2000005];int head[1000005],cnt=0,n,num,m,sum,col[1000005],cou[5];ll ans=0;bool mark[1000005],flag;inline void ins(int f,int t){e[++cnt]=(edge){t,head[f]};head[f]=cnt;}void dfs(int x){    mark[x]=1;num++;cou[col[x]]++;    for(int i=head[x];i;i=e[i].next,++sum)        if(!mark[e[i].to]) col[e[i].to]=(col[x]+((i&1)?1:-1)+3)%3,dfs(e[i].to);        else if(col[e[i].to]!=(col[x]+((i&1)?1:-1)+3)%3) flag=false;}void solve(int i){    cou[0]=cou[1]=cou[2]=0;    flag=true;num=0;sum=0;dfs(i);sum/=2;    if(flag)     {        if(cou[0]&&cou[1]&&cou[2])             ans+=1LL*cou[0]*cou[1]+1LL*cou[2]*cou[0]+1LL*cou[1]*cou[2]-sum;     }    else        ans+=1LL*num*num-sum;}int main(){    freopen("matrix.in","r",stdin);    freopen("matrix.out","w",stdout);    n=read();m=read();    for(register int i=1;i<=m;i++){
   int u=read(),v=read();ins(u,v);ins(v,u);}    for(register int i=1;i<=n;i++)        if(!mark[i]&&head[i])            solve(i);    printf("%lld\n",ans+m);    return 0;}