CF446 (Div. 1)简单题解

A .DZY Loves Sequences

pro：给定长度为N的序列，你最多可以改变一个数的值，问最长严格上升子序列长度。 N<1e5.

sol：分几种情况，一种的不改变；一种是改变，然后接上一个；一个是改变中间一个，接上两段，而且满足a[mid-1]<a[mid]<a[mid+1]

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=100010;
int a[maxn],L[maxn],R[maxn];
int main()
{
    int N,ans=0; scanf("%d",&N);
    rep(i,1,N) scanf("%d",&a[i]);
    rep(i,1,N) {
        L[i]=1;
        if(i>1&&a[i]>a[i-1]) L[i]=L[i-1]+1;
    }
    for(int i=N;i>=1;i--){
        R[i]=1;
        if(i<N&&a[i]<a[i+1]) R[i]=R[i+1]+1;
    }
    rep(i,1,N) ans=max(ans,L[i]);
    rep(i,1,N) ans=max(ans,R[i]);
    rep(i,1,N-2) {
        if(a[i]<a[i+2]-1) ans=max(ans,L[i]+R[i+2]+1);
    }
    rep(i,1,N-1) ans=max(ans,L[i]+1);
    rep(i,2,N) ans=max(ans,R[i]+1);
    printf("%d
",ans);
    return 0;
}

B .DZY Loves Modification

pro：给定N*M有数字的矩阵，现在你可以进行K次操作，每次操作，你会选择一行或者一列，把其对应的数字和加到sum里，然后对应的每个数字减少P，问K次操作后最大的sum是多少。 N,M<1e3, K<1e6, p<1e2;

sol：关键在于想到，如果取的行数和列数次数确定了，那么他们相互影响的值是固定的。然后就可以行列分开考虑了，我们考虑行，我们要取前K大，那么就是单调队列贪心取最大即可搞定。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=1010;
ll N,M,K,P,a[maxn][maxn],X[maxn],Y[maxn],t;
priority_queue<ll>A,B;
ll sumA[maxn*maxn],sumB[maxn*maxn],ans;
int main()
{
    scanf("%lld%lld%lld%lld",&N,&M,&K,&P);
    rep(i,1,N) rep(j,1,M) scanf("%lld",&a[i][j]);
    rep(i,1,N) rep(j,1,M) X[i]=X[i]+a[i][j];
    rep(i,1,N) rep(j,1,M) Y[j]=Y[j]+a[i][j];
    rep(i,1,N) A.push(X[i]);
    rep(i,1,M) B.push(Y[i]);
    rep(i,1,K){
        t=A.top(); A.pop(); sumA[i]=t; A.push(t-M*P);
        t=B.top(); B.pop(); sumB[i]=t; B.push(t-N*P);
    }
    rep(i,1,K) sumA[i]+=sumA[i-1],sumB[i]+=sumB[i-1];
    ans=sumB[K];
    rep(i,1,K){
        ans=max(ans,sumA[i]+sumB[K-i]-1LL*i*(K-i)*P);
    }
    printf("%lld
",ans);
    return 0;
}

C .DZY Loves Fibonacci Numbers

pro：给定一个大小为N的数组，现在进行Q次操作，1操作为区间加值，假如是区间[L,R]，那么a[i]+=F[i-L+1]，F是fib数列； 2操作为区间求和； N,Q<3e5；

sol：此题好像有几种方法，官方题解是用逆元blabla，感觉有点取巧。然后线段树有两种解法。一种是利用fib数列的性质，fib加fib还是有fib的性质，可以参考：

https://blog.csdn.net/johann_oier/article/details/49070067 。但是这种方法的tag传递还是容易出错。

另外一种方法是利用fib数列的另外一个性质：Fn+m=Fn+1*Fm+Fn*Fm-1；所以我们可以可以把相同的部分提出来，不相同的用前缀和操作。

即假如对区间[L,R]操作，对x增加F[x-L+1]=F[x+1]*F[-L]+F[x]*F[-1-L]；而F[x+1]和F[x]我们可以预处理出来(代码里是A和B，而F[-L]我们不难倒推出来)

这种方法比较巧妙，这样救和普通lazy操作无异，所以常数很小。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int Mod=1e9+9;
const int maxn=2000010;
int sum[maxn],lazy1[maxn],lazy2[maxn],N;
int A[maxn],B[maxn],F[maxn],pre[maxn],fcy[maxn];
void MOD(int &x){ if(x>=Mod) x-=Mod;}
void pushup(int Now)
{
    sum[Now]=(sum[Now<<1]+sum[Now<<1|1])%Mod;
}
void build(int Now,int L,int R)
{
    MOD(A[Now]=(pre[R+1]-pre[L]+Mod));
    MOD(B[Now]=(pre[R]-pre[L-1]+Mod));
    if(L==R){ scanf("%d",&sum[Now]); return;}
    int Mid=(L+R)>>1;
    build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R);
    pushup(Now);
}
void pushdown(int Now,int L,int R)
{
    int Mid=(L+R)>>1;
    if(lazy1[Now]){
        MOD(sum[Now<<1]+=1LL*lazy1[Now]*A[Now<<1]%Mod);
        MOD(lazy1[Now<<1]+=lazy1[Now]);
        MOD(sum[Now<<1|1]+=1LL*lazy1[Now]*A[Now<<1|1]%Mod);
        MOD(lazy1[Now<<1|1]+=lazy1[Now]);
        lazy1[Now]=0;
    }
    if(lazy2[Now]){
        MOD(sum[Now<<1]+=1LL*lazy2[Now]*B[Now<<1]%Mod);
        MOD(lazy2[Now<<1]+=lazy2[Now]);
        MOD(sum[Now<<1|1]+=1LL*lazy2[Now]*B[Now<<1|1]%Mod);
        MOD(lazy2[Now<<1|1]+=lazy2[Now]);
        lazy2[Now]=0;
    }
}
void update(int Now,int L,int R,int l,int r)
{
    if(l<=L&&r>=R){
        MOD(sum[Now]+=1LL*fcy[1-l+N]*A[Now]%Mod);
        MOD(sum[Now]+=1LL*fcy[-l+N]*B[Now]%Mod);
        MOD(lazy1[Now]+=fcy[1-l+N]);
        MOD(lazy2[Now]+=fcy[-l+N]);
        return;
    }
    pushdown(Now,L,R); int Mid=(L+R)>>1;
    if(l<=Mid) update(Now<<1,L,Mid,l,r);
    if(r>Mid) update(Now<<1|1,Mid+1,R,l,r);
    pushup(Now);
}
int query(int Now,int L,int R,int l,int r)
{
    if(l<=L&&r>=R) return sum[Now];
    int res=0,Mid=(L+R)>>1; pushdown(Now,L,R);
    if(l<=Mid) (res+=query(Now<<1,L,Mid,l,r))%=Mod;
    if(r>Mid) (res+=query(Now<<1|1,Mid+1,R,l,r))%=Mod;
    pushup(Now); return res;
}
int main()
{
    int M,opt,L,R;
    scanf("%d%d",&N,&M);
    F[1]=1; F[2]=1;
    rep(i,3,N+1) MOD(F[i]=F[i-1]+F[i-2]);
    rep(i,1,N+1) MOD(pre[i]=pre[i-1]+F[i]);
    fcy[N+1]=1; fcy[N]=0; //对应负数的fib
    for(int i=N-1;i>=0;i--) MOD(fcy[i]=fcy[i+2]-fcy[i+1]+Mod);
    build(1,1,N);
    rep(i,1,M){
        scanf("%d%d%d",&opt,&L,&R);
        if(opt==1) update(1,1,N,L,R);
        else printf("%d
",query(1,1,N,L,R));
    }
    return 0;
}

D .DZY Loves Games

pro：给定N给点，有M条边的连通图，其中一些是黑点，一些是白点。一开始在1号点，保证1号是白点，N号是黑点。一开始有K滴血，每次走到一个黑点掉一滴血，每次在一个点会随机走到相邻的点，现在问第让他还有2滴血进入到N号点的概率。

sol：用高斯消元求出黑点之间走到的而不讲过其他黑点的概率，然后矩阵快速幂得到K-2次到N号点的概率。

（不会高斯消元，待补

。。。