我們剛剛知道那些題的解法-3

NOIPDay1T4

考慮以下問題，斜率為 \(-1\) 的直線上區間加，詢問一個點左下角的值的和。

如果線是水平或垂直的，那么顯然可以用掃描線來解決。考慮這個題如何掃描線。

首先我們肯定要斜著掃描，掃描的時候注意維護的是 \(x\) 軸和 \(y\) 軸上的值的和而不是掃描線上的值得和。詢問只需要考慮所有掃描過的線段，然后用如圖的方式去重即可。

本題代碼：

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 1000100
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int base=450000;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,m,Q;
struct BIT{
    int p1[N<<1],p2[N<<1];
    inline int lowbit(int x){return x&(-x);}
    inline void Add(int w,int x){
        if(!w) return;assert(w);
        for(int i=w;i<=2*base;i+=lowbit(i)) p1[i]+=x;
        for(int i=w;i<=2*base;i+=lowbit(i)) p2[i]+=x*w;
    } 
    inline int Ask(int w){
        int res=0;if(!w) return res;
        for(int i=w;i;i-=lowbit(i)) res+=p1[i];res*=(w+1);
        for(int i=w;i;i-=lowbit(i)) res-=p2[i];
        // printf("Ask(%d)=%d\n",w,res);
        return res;
    }
    inline void Clear(int n){
        mset(p1,0);mset(p2,0);
    }
    inline int Ask(int l,int r){
        if(r<l) return 0;
        return Ask(r)-Ask(l-1);
    }
}bitx,bity;
struct Squ{
    int a,b,c,d;
    inline void Add(int dx,int dy){
        a+=dx;b+=dy;c+=dx;d+=dy;
    }
}sq[N];
struct Ques{
    int l,r,w;
};
vc<Ques> qr[N],qc[N],qx[N],qy[N],qqx[N],qqy[N];
vc<Ques> qur[N],quc[N],qux[N],quy[N];
int ans[N];

signed main(){
    // freopen("ex_A3.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);read(Q);
    rep(i,1,n){
        read(sq[i].a);read(sq[i].b);read(sq[i].c);read(sq[i].d);
    }
    rep(i,1,m){
        // printf("i=%d\n",i);
        int po,id,dis;
        read(po);read(id);read(dis);
        if(po==0||po==4){
            if(po==0){
                qr[sq[id].b].pb({sq[id].a,sq[id].a+dis-1,1});
                qr[sq[id].b].pb({sq[id].c+1,sq[id].c+1+dis-1,-1});
                qr[sq[id].d+1].pb({sq[id].a,sq[id].a+dis-1,-1});
                qr[sq[id].d+1].pb({sq[id].c+1,sq[id].c+1+dis-1,1});
                sq[id].Add(dis,0);
            }
            else{
                qr[sq[id].b].pb({sq[id].a-dis+1,sq[id].a,1});
                qr[sq[id].b].pb({sq[id].c+1-dis+1,sq[id].c+1,-1});
                qr[sq[id].d+1].pb({sq[id].a-dis+1,sq[id].a,-1});
                qr[sq[id].d+1].pb({sq[id].c+1-dis+1,sq[id].c+1,1});
                sq[id].Add(-dis,0);
            }
        }
        else if(po==2||po==6){
             if(po==2){
                qc[sq[id].a].pb({sq[id].b,sq[id].b+dis-1,1});
                qc[sq[id].a].pb({sq[id].d+1,sq[id].d+1+dis-1,-1});
                qc[sq[id].c+1].pb({sq[id].b,sq[id].b+dis-1,-1});
                qc[sq[id].c+1].pb({sq[id].d+1,sq[id].d+1+dis-1,1});
                sq[id].Add(0,dis);
            }
            else{
                qc[sq[id].a].pb({sq[id].b-dis+1,sq[id].b,1});
                qc[sq[id].a].pb({sq[id].d+1-dis+1,sq[id].d+1,-1});
                qc[sq[id].c+1].pb({sq[id].b-dis+1,sq[id].b,-1});
                qc[sq[id].c+1].pb({sq[id].d+1-dis+1,sq[id].d+1,1});
                sq[id].Add(0,-dis);
            }
        }
        else if(po==1||po==5){
            if(po==1){
                qx[sq[id].b-sq[id].a+1+base].pb({sq[id].a-1+1,sq[id].a-1+dis-1+1,-1});
                qx[sq[id].b-sq[id].c+base].pb({sq[id].c+1,sq[id].c+dis-1+1,1});
                qx[sq[id].d+1-sq[id].a+1+base].pb({sq[id].a-1+1,sq[id].a-1+dis-1+1,1});
                qx[sq[id].d+1-sq[id].c+base].pb({sq[id].c+1,sq[id].c+dis-1+1,-1});
                qy[sq[id].b-sq[id].a+1+base].pb({sq[id].b+1,sq[id].b+dis-1+1,-1});
                qy[sq[id].b-sq[id].c+base].pb({sq[id].b+1,sq[id].b+dis-1+1,1});
                qy[sq[id].d+1-sq[id].a+1+base].pb({sq[id].d+1+1,sq[id].d+1+dis-1+1,1});
                qy[sq[id].d+1-sq[id].c+base].pb({sq[id].d+1+1,sq[id].d+1+dis-1+1,-1});
                sq[id].Add(dis,dis);
            }
            else{
                qx[sq[id].b-sq[id].a+1+base].pb({sq[id].a-1-dis+1+1,sq[id].a-1+1,-1});
                qx[sq[id].b-sq[id].c+base].pb({sq[id].c-dis+1+1,sq[id].c+1,1});
                qx[sq[id].d+1-sq[id].a+1+base].pb({sq[id].a-1-dis+1+1,sq[id].a-1+1,1});
                qx[sq[id].d+1-sq[id].c+base].pb({sq[id].c-dis+1+1,sq[id].c+1,-1});
                qy[sq[id].b-sq[id].a+1+base].pb({sq[id].b-dis+1+1,sq[id].b+1,-1});
                qy[sq[id].b-sq[id].c+base].pb({sq[id].b-dis+1+1,sq[id].b+1,1});
                qy[sq[id].d+1-sq[id].a+1+base].pb({sq[id].d+1-dis+1+1,sq[id].d+1+1,1});
                qy[sq[id].d+1-sq[id].c+base].pb({sq[id].d+1-dis+1+1,sq[id].d+1+1,-1});
                sq[id].Add(-dis,-dis);
            }
        }
        else if(po==3||po==7){
            if(po==3){
                qqx[sq[id].b+sq[id].a].pb({sq[id].a-dis+1,sq[id].a,1});
                qqx[sq[id].b+sq[id].c+1].pb({sq[id].c+1-dis+1,sq[id].c+1,-1});
                qqx[sq[id].d+1+sq[id].a].pb({sq[id].a-dis+1,sq[id].a,-1});
                qqx[sq[id].d+1+sq[id].c+1].pb({sq[id].c+1-dis+1,sq[id].c+1,1});
                qqy[sq[id].b+sq[id].a].pb({sq[id].b,sq[id].b+dis-1,1});
                qqy[sq[id].b+sq[id].c+1].pb({sq[id].b,sq[id].b+dis-1,-1});
                qqy[sq[id].d+1+sq[id].a].pb({sq[id].d+1,sq[id].d+1+dis-1,-1});
                qqy[sq[id].d+1+sq[id].c+1].pb({sq[id].d+1,sq[id].d+1+dis-1,1});
                sq[id].Add(-dis,dis);
            }
            else{
                qqx[sq[id].b+sq[id].a].pb({sq[id].a,sq[id].a+dis-1,1});
                qqx[sq[id].b+sq[id].c+1].pb({sq[id].c+1,sq[id].c+1+dis-1,-1});
                qqx[sq[id].d+1+sq[id].a].pb({sq[id].a,sq[id].a+dis-1,-1});
                qqx[sq[id].d+1+sq[id].c+1].pb({sq[id].c+1,sq[id].c+1+dis-1,1});
                qqy[sq[id].b+sq[id].a].pb({sq[id].b-dis+1,sq[id].b,1});
                qqy[sq[id].b+sq[id].c+1].pb({sq[id].b-dis+1,sq[id].b,-1});
                qqy[sq[id].d+1+sq[id].a].pb({sq[id].d+1-dis+1,sq[id].d+1,-1});
                qqy[sq[id].d+1+sq[id].c+1].pb({sq[id].d+1-dis+1,sq[id].d+1,1});
                sq[id].Add(dis,-dis);
            }
        }
    }
    rep(i,1,n){
        // printf("i=%d\n",i);
        int id=i;
        qr[sq[id].b].pb({sq[id].a,sq[id].a,1});
        qr[sq[id].b].pb({sq[id].c+1,sq[id].c+1,-1});
        qr[sq[id].d+1].pb({sq[id].a,sq[id].a,-1});
        qr[sq[id].d+1].pb({sq[id].c+1,sq[id].c+1,1});
    }
    // puts("Finish Prepare");
    rep(i,1,Q){
        // printf("i=%d\n",i);
        int px,py;read(px);read(py);
        qur[py].pb({px,-1,i});quc[px].pb({py,-1,i});
        qux[py-px+base].pb({px,py,i});
        quy[px+py].pb({px,py,i});
    }
    // puts("2");
    // Change There!!!
    rep(i,1,2*base){
        // printf("i=%d\n",i);
        for(Ques now:qr[i]){
            // printf("now.l=%d now.r=%d now.w=%d\n",now.l,now.r,now.w);
            bitx.Add(now.l,now.w);
            bitx.Add(now.r+1,-now.w);
        }
        for(Ques now:qur[i]){
            // printf("now.l=%d\n",now.l);
            ans[now.w]+=bitx.Ask(1,now.l);
            // printf("ans[%d]=%d\n",now.w,ans[now.w]);
        }
    }
    // puts("3");
    // printf("ans[2]=%d\n",ans[2]);
    bitx.Clear(2*base);
    rep(i,1,2*base){
        for(Ques now:qc[i]){
            // printf("now.l=%d now.r=%d now.w=%d\n",now.l,now.r,now.w);
            bitx.Add(now.l,now.w);
            bitx.Add(now.r+1,-now.w);
        }
        for(Ques now:quc[i]){
            // printf("now.l=%d\n",now.l);
            ans[now.w]+=bitx.Ask(1,now.l);
            // printf("ans[%d]=%d\n",now.w,ans[now.w]);
        }
    }
    // puts("4");
    bitx.Clear(2*base);
    // printf("ans[2]=%d\n",ans[2]);
    rep(i,1,2*base){
        // printf("i=%d\n",i);
        for(Ques now:qx[i]){
            bitx.Add(now.l,now.w);
            bitx.Add(now.r+1,-now.w);
        }
        for(Ques now:qy[i]){
            bity.Add(now.l,now.w);
            bity.Add(now.r+1,-now.w);
        }
        for(Ques now:qux[i]){
            now.l++;now.r++;
            int nowans=bitx.Ask(now.l,2*base)+bity.Ask(1,now.r)-bitx.Ask(1,now.l-1)-bity.Ask(now.r+1,2*base);
            // assert(nowans%2==0);
            ans[now.w]+=(nowans)/2;
        }
        // printf("ans[1]=%d\n",ans[1]);
    }
    // printf("ans[2]=%d\n",ans[2]);
    bitx.Clear(2*base);bity.Clear(2*base);
    // printf("ans[2]=%d\n",ans[2]);
    // puts("5");
    rep(i,1,2*base){
        // printf("i=%d\n",i);
        for(Ques now:qqx[i]){
            // puts("why1");
            bitx.Add(now.l,now.w);
            bitx.Add(now.r+1,-now.w);
        }
        for(Ques now:qqy[i]){
            // puts("why2");
            // printf("now.l=%d now.r=%d now.w=%d\n",now.l,now.r,now.w);
            bity.Add(now.l,now.w);
            // puts("here");
            bity.Add(now.r+1,-now.w);
        }
        for(Ques now:quy[i]){
            // puts("why");
            int nowans=bitx.Ask(1,now.l)+bity.Ask(1,now.r)-bitx.Ask(now.l+1,2*base)-bity.Ask(now.r+1,2*base);
            // assert(nowans%2==0);
            ans[now.w]+=(nowans)/2;
        }
        // printf("ans[1]=%d\n",ans[1]);
    }
    // puts("6");
    // printf("ans[1]=%d\n",ans[1]);
    // printf("ans[2]=%d\n",ans[2]);
    rep(i,1,Q){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

/*
1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2
*/

CSPDay1T3

證明貪心只需要證明移動的話一定不優即可。證明的時候利用代數推導，表示出移動后代價的增量來證明。

CSPDay2T1

考慮我們只維護值域上的值，放進 \(vis\) 中，考慮 \(vis\) 中的數不能出現重復，所以最優方案一定是每個位置都是 \(1\)，所以最優情況是 \(1,2,4,8...\)，這樣 vis 數組每個位置都是 \(1\)。

所以一旦長度超過 \(20\) 是必定有解的。

CSPDay2T3

其實這個復雜度就和折半搜索，但是奈何我從來沒有做過折半搜索。

前 \(18\) 和后 \(18\) 暴力做，現在變成了在前面選一個數和在后面選一個數的異或和小于等于 \(m\)，求和的最大值。考慮左右數建出 \(01trie\)，我們直接在上面 dfs 復雜度就是對的，首先兩個數某一位異或值不能大于 \(m\) 這一位，其次如果小于，下面走 \(0\) 還是 \(1\) 就沒有限制了，可以預處理 \(trie\) 樹上每個子樹的最大值，這樣一次 dfs 的復雜度就應該是 \(O(\log m)\) 的。

int n,m,a[N],b[N];

struct Trie{
    int tot,ch[N][2],val[N];
    inline Trie(){tot=1;}
    inline void Insert(int x,int v){
        int p=1;
        dec(i,0,30){
            int now=(x>>i)&1;
            if(!ch[p][now])  ch[p][now]=++tot;
            p=ch[p][now];cmax(val[p],v);
        }
        // printf("tot=%d\n",tot);
    }
}t1,t2;

inline void Build(int l,int r,int op){
    int len=r-l+1;
    for(int s=0;s<=(1<<len)-1;s++){
        int suma=0,sumb=0;
        rep(j,0,len-1)if((s>>j)&1){
            suma^=a[j+l];
            sumb+=b[j+l];
        }
        if(op) t1.Insert(suma,sumb);
        else t2.Insert(suma,sumb);
    }
}
inline int dfs(int d,int x,int y){
    // printf("d=%d x=%d y=%d\n",d,x,y);
    if(d==-1){return t1.val[x]+t2.val[y];}
    int now=(m>>d)&1,Ans=0;
    rep(i,0,1)rep(j,0,1)if((i^j)<=now&&t1.ch[x][i]&&t2.ch[y][j]){
        if((i^j)<now) Ans=max(Ans,t1.val[t1.ch[x][i]]+t2.val[t2.ch[y][i]]);
        else Ans=max(Ans,dfs(d-1,t1.ch[x][i],t2.ch[y][j]));
    }
    // printf("d=%d x=%d y=%d Ans=%d\n",d,x,y,Ans);
    return Ans;
}

signed main(){
    read(n);read(m);
    rep(i,1,n) read(a[i]);rep(i,1,n) read(b[i]);
    Build(1,n/2,1);Build(n/2+1,n,0);
    // exit(0);
    int ans=dfs(30,1,1);
    printf("%lld\n",ans);
    return 0;
}

NOIPDay2T2

感覺就很拉格朗日插值，但是沒有寫。

推式子推到了下面的地方：

\[\begin{aligned} \sum\limits_{i=1}^{k}i^{m+n}-(i-1)^mi^n+(i-1)^ni^m +(i-1)^{m+n} \end{aligned} \]

其實到這里是可以大概推測它是一個 \(n+m+1\) 次方的一個多項式，但是嚴格證明需要把它化成下面的形式：

\[\sum\limits_{i=1}^k (i^m-(i-1)^m)(i^n-(i-1)^n) \]

利用第二類斯特林數，可以類似證明自然數冪和多項式次數的方式去證明這個式子的多項式次數。

拉格朗日插值即可。

inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int a){return ksm(a,mod-2,mod);}

int t,invjie[N],jie[N],x[N],y[N];

inline int Lag(int h,int len){
    int sum=1;rep(i,1,len) sum=sum*(h-x[i])%mod;
    rep(i,1,len) x[i]=sum*inv(h-x[i])%mod;
    int ans=0;
    rep(i,1,len){
        ans=(ans+y[i]*x[i]%mod*invjie[i-1]%mod*invjie[len-i]%mod*(((len-i)&1)?(mod-1):1)%mod)%mod;
    }
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);jie[0]=1;
    rep(i,1,200003) jie[i]=jie[i-1]*i%mod;
    invjie[200003]=inv(jie[200003]);
    dec(i,0,200003-1) invjie[i]=invjie[i+1]*(i+1)%mod;
    while(t--){
        int n,m,k;read(n);read(m);read(k);
        rep(i,1,n+m+2){
            x[i]=i;y[i]=((ksm(i,m,mod)-ksm(i-1,m,mod))%mod)*((ksm(i,n,mod)-ksm(i-1,n,mod))%mod)%mod;
            y[i]=(y[i]+mod)%mod;y[i]=(y[i]+y[i-1])%mod;
            // printf("y[%d]=%d\n",i,y[i]);
        }
        if(k<=n+m+2){
            printf("%lld\n",y[k]);continue;
        }
        else{
            int ans=Lag(k,n+m+2);
            printf("%lld\n",ans);
        }
    }
}

NOIPDay2T3

賽事想到了 DDP，但是沒打，因為從來沒有打過 DDP，用 DDP 是兩個 \(\log\)。

一種更好的做法是我們可以考慮樹上倍增預處理，DDP 的思路也是我們樹剖之后相鄰兩個區間合并，不如直接樹上倍增，復雜度還少一個 \(\log\)，注意如果一條邊有 \(3\) 個及以上顏色是可以選的，那么我們就可以認為是這條邊一定可以選出一個與兩邊顏色都不同的一種顏色，我們給這條邊打個標記，這樣，就可以認為每條邊的顏色最多只有 \(2\) 中，設 \(f_{i,j,0/1,0/2}\) 表示從 \(i\) 往上跳 \(2^j\) 步得到的路徑中，最上面和最下面的邊顏色是什么樣的，預處理后直接合并即可。

map<P,vi >cnt;
map<P,bool >vis;
int n,m,fa[N][21],Q,dep[N];
vc<P> e[N];
array<int,3> f[N][21][2][2],g[2][2],h[2][2],a[2][2],b[2][2];
typedef array<int,3> ar;

inline void Print(ar now){
    rep(i,0,2) printf("%d ",now[i]);puts("");
}
inline void Merge(ar a[2][2],ar b[2][2]){
    mset(g,-1);
    rep(i,0,1)rep(j,0,1)rep(i2,0,1)rep(j2,0,1){
        if(a[i][j][0]==-1||b[i2][j2][0]==-1) continue;
        if(a[i][j][2]==-3||b[i2][j2][1]==-3){
            cmax(g[i][j2][0],a[i][j][0]+b[i2][j2][0]+1);
        }
        else{
            if(a[i][j][2]!=b[i2][j2][1]) cmax(g[i][j2][0],a[i][j][0]+b[i2][j2][0]+1);
            else cmax(g[i][j2][0],a[i][j][0]+b[i2][j2][0]);
        }
        g[i][j2][1]=a[i][j][1];g[i][j2][2]=b[i2][j2][2];
    }
    // rep(i,0,1)rep(j,0,1)Print(g[i][j]);
}
inline void dfs(int k,int fat){
    dep[k]=dep[fat]+1;
    fa[k][0]=fat;rep(i,1,20) fa[k][i]=fa[fa[k][i-1]][i-1];
    rep(i,1,20){
        Merge(f[k][i-1],f[fa[k][i-1]][i-1]);
        rep(j,0,1)rep(o,0,1){
            f[k][i][j][o]=g[j][o];
            // printf("f[%d][%d][%d][%d]: ",k,i,j,o);
            // Print(f[k][i][j][o]);
        }
    }
    for(P to:e[k])if(to.fi!=fat){
        vi now=cnt[mp(k,to.fi)];
        rep(i,0,1){
            if((i==1)&&now.size()==1) continue;
            f[to.fi][0][i][i]={0,now[i],now[i]};
            // printf("f[%d][%d][%d][%d]: ",to.fi,0,i,i);Print(f[to.fi][0][i][i]);
        }
        dfs(to.fi,k);
    }
}
inline void Ask(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    mset(a,-1);mset(b,-1);
    bool ao=0,bo=0;
    dec(i,0,20) if(dep[fa[u][i]]>=dep[v]){
        if(!ao){
            rep(j,0,1)rep(k,0,1) a[j][k]=f[u][i][j][k];ao=1;
        }
        else{
            Merge(a,f[u][i]);
            rep(j,0,1)rep(k,0,1) a[j][k]=g[j][k];
        }
        u=fa[u][i];
    }
    if(u==v){
        rep(i,0,1)rep(j,0,1) h[i][j]=a[i][j];
        return;
    }
    dec(i,0,20){
        if(fa[u][i]!=fa[v][i]){
            if(!ao){
                rep(j,0,1)rep(k,0,1) a[j][k]=f[u][i][j][k];ao=1;
            }
            else{
                Merge(a,f[u][i]);
                rep(j,0,1)rep(k,0,1) a[j][k]=g[j][k];
            }
            if(!bo){
                rep(j,0,1)rep(k,0,1) b[j][k]=f[v][i][j][k];
                bo=1;
            }
            else{
                Merge(b,f[v][i]);
                rep(j,0,1)rep(k,0,1) b[j][k]=g[j][k];
            }
            u=fa[u][i];v=fa[v][i];
        }
    }
    if(!ao){
        // puts("Here");
        // printf("u=%d\n",u);
        rep(j,0,1)rep(k,0,1){
            a[j][k]=f[u][0][j][k];
            // printf("f[%d][%d][%d][%d]: ",u,0,j,k);Print(f[u][0][j][k]);
        }
        ao=1;
    }
    else{
        Merge(a,f[u][0]);
        rep(j,0,1)rep(k,0,1) a[j][k]=g[j][k];
    }
    if(!bo){
        rep(j,0,1)rep(k,0,1) b[j][k]=f[v][0][j][k];
        bo=1;
    }
    else{
        Merge(b,f[v][0]);
        rep(j,0,1)rep(k,0,1) b[j][k]=g[j][k];
    }
    rep(i,0,1)rep(j,i,1) swap(b[i][j],b[j][i]);
    rep(i,0,1)rep(j,0,1)swap(b[i][j][1],b[i][j][2]);
    // rep(i,0,1)rep(j,0,1){
    //     printf("a[%d][%d]: ",i,j);Print(a[i][j]);
    // }
    // rep(i,0,1)rep(j,0,1){
    //     printf("b[%d][%d]: ",i,j);Print(b[i][j]);
    // }
    Merge(a,b);rep(i,0,1)rep(j,0,1) h[i][j]=g[i][j];
}

int main(){
    freopen("my.in","r",stdin);
    freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,1,m){
        int u,v,w;read(u);read(v);read(w);
        vi now=cnt[mp(u,v)];
        if(!now.size()){
            now.pb(w);e[u].pb(mp(v,0));e[v].pb(mp(u,0));
            cnt[mp(u,v)]=cnt[mp(v,u)]=now;
        }
        else{
            bool op=1;
            for(int x:now) if(x==w){op=0;break;}
            if(!op) continue;
            if(now.size()>=2){
                vis[mp(u,v)]=vis[mp(v,u)]=1;
                now.clear();now.pb(-3);now.pb(-3);
            }
            else now.pb(w);
            cnt[mp(u,v)]=cnt[mp(v,u)]=now;
        }
    }
    rep(i,1,n)for(int j=0;j<e[i].size();j++){
        P to=e[i][j];
        if(vis[mp(i,to.fi)]) e[i][j].se=1;
    }
    mset(f,-1);
    dfs(1,0);
    read(Q);
    rep(i,1,Q){
        int u,v;read(u);read(v);
        if(u==v){
            puts("0");continue;
        }
        Ask(u,v);
        int ans=0;
        rep(i,0,1)rep(j,0,1)ans=max(ans,h[i][j][0]);
        printf("%d\n",ans);
    }
}

錯誤總結：

合并寫錯

CSPDay2T4

考慮設 \(y_i=k_ix+b_i\)，假設 \(k_j\) 大于 \(0\)，需要 \(y_i\) 最大，\(k_j\) 小于 \(0\)，需要 \(k_j\) 最小。那么我們對于所有的 \(x_i\)，求出取最大和取最小的直線編號。

有個限制是 \(i\not=j\)，考慮如果把 \(i\) 放在外層，那么內層顯然要么是次大值，要么是次小值，可以通過掃描線取一下前綴和后綴，解決這個問題。

如果把 \(i\) 放在內層，那么需要選一個 \(j\not=i\) 且 \(y_j\) 最大，一樣還是前綴和后綴用掃描線掃一下可以解決。

int K[N],B[N],n,Q,x[N],rt,ymax[N],ymin[N],cymx[N],cymi[N],ans[N];
struct LCT{
    #define ls(k) p[k].ls
    #define rs(k) p[k].rs
    #define F(id,x) K[id]*(x)+B[id]
    struct Node{
        int ls,rs,mx,mi;
    }p[N];
    int tot;
    inline LCT(){tot=0;}
    inline void ChangeMin(int &k,int l,int r,int z,int y,int id){
        if(!k){k=++tot;assert(tot<=N-1);}
        if(l==r){if(!p[k].mi||F(p[k].mi,l)>F(id,l)) p[k].mi=id;return;}int mid=(l+r)>>1;
        if(z<=l&&r<=y){
            if(!p[k].mi) p[k].mi=id;
            if(F(p[k].mi,mid)>F(id,mid)) swap(p[k].mi,id);
            (F(id,l)<F(p[k].mi,l))?ChangeMin(ls(k),l,mid,z,y,id):ChangeMin(rs(k),mid+1,r,z,y,id);
            return;
        }
        if(z<=mid) ChangeMin(ls(k),l,mid,z,y,id);if(mid<y) ChangeMin(rs(k),mid+1,r,z,y,id);
    }
    inline void ChangeMax(int &k,int l,int r,int z,int y,int id){
        if(!k){k=++tot;}
        if(l==r){if(!p[k].mx||F(p[k].mx,l)<F(id,l)) p[k].mx=id;return;}int mid=(l+r)>>1;
        if(z<=l&&r<=y){
            if(!p[k].mx) p[k].mx=id;
            if(F(p[k].mx,mid)<F(id,mid)) swap(p[k].mx,id);
            (F(id,l)>F(p[k].mx,l))?ChangeMax(ls(k),l,mid,z,y,id):ChangeMax(rs(k),mid+1,r,z,y,id);
            return;
        }
        if(z<=mid) ChangeMax(ls(k),l,mid,z,y,id);if(mid<y) ChangeMax(rs(k),mid+1,r,z,y,id);
    }
    inline void Change(int &k,int l,int r,int z,int y,int id){
        ChangeMin(k,l,r,z,y,id);ChangeMax(k,l,r,z,y,id);
    }
    inline int AskMin(int k,int l,int r,int w){
        if(!k) return 0;if(l==r) return p[k].mi;
        int mid=(l+r)>>1;int id=-1;
        if(w<=mid) id=AskMin(ls(k),l,mid,w);else id=AskMin(rs(k),mid+1,r,w);
        if(id==0) return p[k].mi;
        return (F(id,w)<F(p[k].mi,w))?id:p[k].mi;
    }
    inline int AskMax(int k,int l,int r,int w){
        if(!k) return 0;if(l==r) return p[k].mx;
        int mid=(l+r)>>1;int id=-1;
        if(w<=mid) id=AskMax(ls(k),l,mid,w);else id=AskMax(rs(k),mid+1,r,w);
        if(id==0) return p[k].mx;
        return (F(id,w)>F(p[k].mx,w))?id:p[k].mx;
    }
    inline void Clear(){mset(p,0);rt=0;tot=0;}
}st;
struct Ques{
    int id,w;
};
vc<Ques> qmx[N],qmi[N];

signed main(){
    freopen("my.in","r",stdin);
    freopen("my.out","w",stdout);
    read(n);
    rep(i,1,n){
        read(K[i]);read(B[i]);
    }
    read(Q);
    rep(i,1,Q) read(x[i]);
    rep(i,1,n){
        st.Change(rt,-Len,Len,-Len,Len,i);
    }
    // exit(0);
    //插入所有的直線
    rep(i,1,Q){
        ymax[i]=st.AskMax(rt,-Len,Len,x[i]);
        ymin[i]=st.AskMin(rt,-Len,Len,x[i]);
        // qmx[ymax[i]].pb({i,F(ymax[i],x[i])});
        // qmx[ymin[i]].pb({i,F(ymin[i],x[i])});
        qmx[ymax[i]].pb({i,x[i]});
        qmi[ymin[i]].pb({i,x[i]});
    }
    st.Clear();
    rep(i,1,n){
        if(i!=1){
            for(Ques now:qmx[i]){
                int id=st.AskMax(rt,-Len,Len,now.w);
                if(!cymx[now.id]||F(cymx[now.id],x[now.id])<F(id,x[now.id])) cymx[now.id]=id;
            }
            for(Ques now:qmi[i]){
                int id=st.AskMin(rt,-Len,Len,now.w);
                if(!cymi[now.id]||F(cymi[now.id],x[now.id])>F(id,x[now.id])) cymi[now.id]=id;
            }
        }
        st.Change(rt,-Len,Len,-Len,Len,i);
    }
    st.Clear();
    dec(i,1,n){
        if(i!=n){
            for(Ques now:qmx[i]){
                int id=st.AskMax(rt,-Len,Len,now.w);
                if(!cymx[now.id]||F(cymx[now.id],x[now.id])<F(id,x[now.id])) cymx[now.id]=id;
            }
            for(Ques now:qmi[i]){
                int id=st.AskMin(rt,-Len,Len,now.w);
                // printf("i=%d\n",i);
                // printf("id=%d\n",id);
                if(!cymi[now.id]||F(cymi[now.id],x[now.id])>F(id,x[now.id])) cymi[now.id]=id;
            }
        }
        st.Change(rt,-Len,Len,-Len,Len,i);
    }
    //對于每個 x[i] 維護好了 取到次大值和次小值的直線 id。
    // rep(i,1,Q){
    //     printf("x[%d]=%d ymax[%d]=%d ymin[%d]=%d cymx[%d]=%d cymi[%d]=%d\n",i,x[i],i,ymax[i],i,ymin[i],i,cymx[i],i,cymi[i]);
    // }
    rep(i,1,Q){
        ans[i]=-INF;
        cmax(ans[i],max(F(ymax[i],F(cymx[i],x[i])),F(ymin[i],F(cymi[i],x[i]))));
        if(ymax[i]!=cymi[i]) cmax(ans[i],F(ymax[i],F(cymi[i],x[i])));
        if(ymin[i]!=cymx[i]) cmax(ans[i],F(ymin[i],F(cymx[i],x[i])));
    }
    //在 yi 作為外層時的答案。
    rep(i,1,n){
        qmx[i].clear();qmi[i].clear();
    }
    rep(i,1,Q){
        qmx[ymax[i]].pb({i,F(ymax[i],x[i])});
        qmx[ymin[i]].pb({i,F(ymin[i],x[i])});
    }
    st.Clear();
    rep(i,1,n){
        if(i!=1){
            for(Ques now:qmx[i]){
                int id=st.AskMax(rt,-Len,Len,now.w);
                if(id) cmax(ans[now.id],F(id,now.w));
            }
        }
        st.Change(rt,-Len,Len,-Len,Len,i);
    }
    st.Clear();
    dec(i,1,n){
        if(i!=n){
            for(Ques now:qmx[i]){
                int id=st.AskMax(rt,-Len,Len,now.w);
                if(id) cmax(ans[now.id],F(id,now.w));
            }
        }
        st.Change(rt,-Len,Len,-Len,Len,i);
    }
    rep(i,1,Q){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

錯誤總結：

主席樹寫Change寫錯
n,q 寫反了

CSPDay3T4

博弈，考慮角色一定是一個追一個跑，且不難發現跑的那個是一定要走到兩個點滿足追的那個都是走不到的才能弄到平局。有了這個觀察之后就好寫很多。

NOIPDay3T2

首先有一個 naive 的貪心，但是不難發現難以處理點權相同的情況，所以答案不僅和值有關，還和輸的形態有關，貪心不行，提示我們想動態規劃。

不難發現我們只需要知道自己與父親的連邊究竟是小于等于自己還是大于自己即可，于是可以設 \(f_{k,0/1}\) 表示自己與父親之間的邊是小于等于 \(a_k\) 還是大于 \(a_k\)，轉移的時候對于每個點預處理出 \(w_{to,0/1}\) 表示這條邊的權值小于 \(a_{k}\) 還是大于 \(a_k\)，以及貢獻是多少，一開始認為趨勢 \(w_{to,0}\)，然后作差排序，貪心選擇即可。

int n,m,a[N],ans,f[N][2],w[N][2];
vi e[N],v;

inline void dfs(int k,int fa){
    // if(k==64469){
    //     assert(0);
    //     // printf("k=%d fa=%d\n",k,fa);
    //     assert(0);
    // }
    // if(k==51462) printf("k=%d fa=%d\n",k,fa);
    for(int to:e[k]){
        // if(k==51462) printf("to=%d\n",to);
        if(to!=fa){
            // if(k==51462) printf("to=/d\n",to);
            dfs(to,k);
            // puts("Now");
        }
    }
    // if(k==51462) puts("Here");
    int sum=0;v.clear();
    for(int to:e[k]) if(to!=fa){
        if(a[to]<a[k]){
            w[to][0]=max(f[to][0]+a[to],f[to][1]+a[k]);
            w[to][1]=f[to][1]+m;
        }
        else if(a[to]==a[k]){
            w[to][0]=f[to][0]+a[k];
            w[to][1]=f[to][1]+m;
        }
        else{
            w[to][0]=f[to][0]+a[k];
            w[to][1]=max(f[to][1]+m,f[to][0]+a[to]);
        }
        // printf("w[%d][1]=%d w[%d][0]=%d\n",to,w[to][1],to,w[to][0]);
        v.pb(w[to][1]-w[to][0]);
        sum+=w[to][0];
    }
    sort(v.begin(),v.end(),[&](int i,int j){return i>j;});
    // if(k==51462) puts("here");
    f[k][0]=f[k][1]=sum;
    if(v.size()) rep(i,0,((int)v.size())/2-1){
        // if(k==51462) printf("i=%d\n",i);
        if(v[i]>0) f[k][0]+=v[i];else break;
    }
    if(v.size()) rep(i,0,((int)v.size())/2-2){
        // if(k==51462) printf("i=%d\n",i);
        if(v[i]>0) f[k][1]+=v[i];else break;
    }
    // if(k==51462) puts("Here");
    if(!v.size()){
        f[k][1]=-INF;f[k][0]=0;
    }
    if(a[k]==m&&k!=1){
        f[k][1]=-INF;
    }
    if(e[k].size()<=2&&k!=1){
        f[k][1]=-INF;
    }
    // printf("f[%d][0]=%d f[%d][1]=%d\n",k,f[k][0],k,f[k][1]);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);rep(i,1,n) read(a[i]);
    // printf("a[90]=%d a[63]=%d\n",a[90],a[63]);
    rep(i,1,n-1){
        int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
    }
    dfs(1,0);
    int ans=0;
    if(e[1].size()&1) ans=f[1][0];
    else{
        ans=f[1][1];
        // ans=max(f[1][0],f[1][1]);
    }
    printf("%lld\n",ans);
    return 0;
}

不過這份代碼大樣例 RE 的情況下居然過了。

NOIPDay3T3

考慮如果欽定 \(a_i\) 一定在答案中，那么答案一定是其一個約數，所以我們可以枚舉所有它的約數，然后算一下狄利克雷前綴和，來計算其每一個約數出現了多少次，選滿足條件的最大的即可。

考慮題目保證要選擇 \(\frac{n+1}{2}\) 上取整的數字，所以隨機一個數其滿足條件的概率是 \(\frac{1}{2}\)，于是可以多隨機幾次。

注意狄利克雷前綴和怎么做，我們實際上是之關注約數上的值，所以沒有必要處理處所有的質數，只需要處理出那些能給約數之間帶來轉移的質數，換句話說，也就是在這些約數中出現過的質數，即當前枚舉值的所有質因子。

mt19937 rnd(time(0)+time(0));
int d[N],f[N],n,a[N];
bool no[N];
vi v,p;

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

inline int Calc(int x){
    int X=x;
    v.clear();int i;p.clear();
    for(i=1;i*i<x;i++)if(x%i==0){
        v.pb(i);v.pb(x/i);
    }
    if(i*i==x) v.pb(i);
    sort(v.begin(),v.end());
    fill(f,f+v.size(),0);
    for(i=2;i*i<=x;i++){
        if(x%i==0){
            p.pb(i);while(x%i==0) x/=i;
        }
    }
    if(x!=1) p.pb(x);
    // puts("v:");for(int x:v) printf("%d ",x);puts("");
    // puts("p:");for(int x:p) printf("%d ",x);puts("");
    rep(i,1,n){
        int g=gcd(a[i],X);
        // printf("a[i]=%d X=%d g=%d\n",a[i],X,g);
        f[lower_bound(v.begin(),v.end(),g)-v.begin()]++;
    }
    // rep(i,0,(int)v.size()-1) printf("f[%d]=%d\n",i,f[i]);
    int ans=1;
    for(int now:p){
        dec(i,1,(int)v.size()-1){
            if(v[i]%now==0){
                f[lower_bound(v.begin(),v.end(),v[i]/now)-v.begin()]+=f[i];
            }
        }
    }
    ans=1;
    // rep(i,0,(int)v.size()-1) printf("f[%d]=%d\n",i,f[i]);
    dec(i,0,(int)v.size()-1){
        if(f[i]>=(n+1)/2){
            // printf("v[%d]=%d\n",i,v[i]);
            return v[i];
        }
    }
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]);
    shuffle(a+1,a+n+1,rnd);
    int Ans=-INF;
    // puts("a:");rep(i,1,n) printf("%d ",a[i]);puts("");
    rep(i,1,min(n,12ll)){
        Ans=max(Ans,Calc(a[i]));
        // printf("i=%d Ans=%d\n",i,Ans);
    }
    printf("%lld\n",Ans);
    return 0;
}

犯的錯誤：

\(x\) 處理質數的時候被消成 \(1\)，忘記拷貝副本。（可以通過多謝函數來解決）。

NOIPDay3T4

原題鏈接

一個非常有難度的 DP。

首先考慮我們怎么做這個 DP，首先如果每個位置上的值都知道，在值域上從大到小考慮顯然是一個優美的選擇，但是現在每個位置上的值都不知道，這就很讓人頭疼。因為限制在后面，我們考慮從后往前 DP。設 \(f_{i,j}\) 表示考慮 \(i,n\) 中的每一個數，整個過程中我們相當于要維護一個集合，集合里的每一個數都相當于這個數有沒有出現過。考慮我們新加進去一個數 \(x\)，那么這個數最終會變成距離其最近的一個小于它的沒有出現過的位置對應的數，而如果不存在這樣的一個位置，說明這個數最終會變成 \(0\)，我們狀態中的 \(j\) 記錄的就是這個集合中的最長的出現過的數字的前綴長度。同時，我們認為兩個相同的數字是不同的，這樣方便我們處理，這樣做每一個方案都會被算重 \(2^n\)，除掉即可。

接下來考慮轉移。首先我們維護一個 \(Cnt_b\) 和 \(Cnt_p\) 表示到目前為止所有變成 \(0\) 的數和所有沒變成 \(0\) 的數字。

假如當前位置是一個要變成 \(0\) 的位置，那么考慮我們在這個位置上放的數一定是 \(1\) 到 \(j\) 中的數，且我們分析一下，這樣的數一共有 \(2j\) 個，\(1\) 到 \(j\) 都出現過了，這需要恰好 \(j\) 個，而前面又有 \(Cnt_b\) 個變成 \(0\) 的位置，這些位置上放的數一定也是 \(1\) 到 \(j\)，所以我們的轉移系數應該是 \(2j-j-Cnt_b=j-Cnt_b\)。

假如當前位置不是一個要變成 \(0\) 的位置，那么這是比較難辦的，其中的一個原因是我們沒有存下來這個集合。那我們不妨這樣做：我們只考慮前 \([1,j]\) 的方案數，而不考慮其它的方案數。其余的方案數等 \(j\) 變化的時候再考慮。

如果這個位置不會變成 \(0\)，那么其放的數一定是 \(\ge j+1\)，考慮如果放了一個數最后不會變成 \(j+1\)，那么 \(j\) 不會變化，有 \(f_{i,j}+=f_{i+1,j}\)。

否則，那么 \(j\) 會變化，設變成 \(j+k\)，那么我們這個數一定是在 \([j+1,j+k]\) 種選擇，如果選擇 \(j+1\) 的話，一共是有兩種選擇，因為 \(j+1\) 以前是從來沒有選過的。否則的話，因為其余位置都出現過，所以 \([j+2,j+k]\) 這個區間中只有 \(k-1\) 種選擇，所以總的方案數是 \(k+1\)。

還需要考慮后面這 \(k-1\) 個出現過的數字是怎么出來的，首先要在所有的沒變成 \(0\) 的位置上把它們選出來，因為我們已經考慮了前 \(j\) 個的位置，所以有一個 \(\binom{Cnt_p-j}{k-1}\) 的系數。其次，我們還有一個方案，就是在 \(k-1\) 個位置中填 \(k-1\) 個數，組成了連續的一段被選擇的數，設這一段的方案數為 \(G_{k-1}\)。

考慮如何求 \(G_{k-1}\)。設 \(g_{i,j}\) 表示考慮了 \(1,i\) 這 \(i\) 種數，可以不用，最后組成了 \(1,j\) 這樣一個前綴的方案數。那么考慮轉移，首先第 \(i\) 種數可以不用或者不做貢獻，那就是一個 \(g_{i-1,j}\)，注意我們只考慮做貢獻的數字的方案數。其次，如果其做的貢獻為 \(1\) 的話，那么可以在當前的序列的任何位置加一個數，且因為兩個相同大小的數認為不同，所以加的數有兩種選擇，系數是 \(2j\)。最后考慮兩個數都做貢獻，那么就是隨便插入，系數是 \((j-1)j\)，這樣就做完了。

講的可能不清晰，推一篇講的巨清晰的博客

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 2010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,g[N][N],jie[N],invjie[N],f[N][N];
bool vis[N];

inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}
inline int C(int n,int m){
    if(n<m) return 0;
    // printf("n=%d m=%d ans=%d\n",n,m,jie[n]*invjie[m]%mod*invjie[n-m]%mod);
    return jie[n]*invjie[m]%mod*invjie[n-m]%mod;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);
    rep(i,1,n){
        int x;read(x);vis[x]=1;
    }g[0][0]=1;
    rep(i,1,n){
        rep(j,0,i){
            g[i][j]=g[i-1][j];
            if(j) g[i][j]=(g[i][j]+g[i-1][j-1]*2*j%mod)%mod;
            if(j>1) g[i][j]=(g[i][j]+g[i-1][j-2]*(j-1)*j%mod)%mod;
        }
    }
    jie[0]=1;rep(i,1,2*n) jie[i]=jie[i-1]*i%mod;invjie[2*n]=inv(jie[2*n]);
    dec(i,0,2*n-1) invjie[i]=invjie[i+1]*(i+1)%mod;
    f[2*n+1][0]=1;int CntBreak=0,CntProtect=0;
    dec(i,1,2*n){
        if(vis[i]){
            rep(j,0,CntProtect) if(f[i+1][j]){
                f[i][j]=(f[i][j]+f[i+1][j])%mod;
                rep(k,1,CntProtect+1){
                    f[i][k+j]=(f[i][k+j]+f[i+1][j]*(k+1)%mod*C(CntProtect-j,k-1)%mod*g[k-1][k-1]%mod)%mod;
                }
            }
            CntProtect++;
        }
        else{
            rep(j,CntBreak+1,CntProtect) f[i][j]=(f[i][j]+f[i+1][j]*(j-CntBreak)%mod)%mod;
            CntBreak++;
        }
        // rep(j,0,n) printf("f[%d][%d]=%d\n",i,j,f[i][j]);
    }
    int ans=f[1][n]*inv(ksm(2,n,mod))%mod;
    printf("%lld\n",ans);
    return 0;
}

posted @ 2023-07-13 21:33 NuclearReactor 閱讀(14) 評論(0) 收藏舉報

刷新頁面返回頂部

HeNuclearReactor