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

Zhengrui 2022ABDay1 B

考慮進(jìn)行轉(zhuǎn)化，在一個(gè)格子內(nèi)，如果某條邊有水管連接，那么就是 \(1\)，否則就是 \(0\)，所以高級(jí)水管等價(jià)于相對(duì)的兩條邊的狀態(tài)相反。

一個(gè)狀態(tài)合法等價(jià)于所有邊兩邊標(biāo)的數(shù)都是一樣的，最外圍的邊都認(rèn)為值標(biāo) \(0\)。

若一個(gè)格子里填的是高級(jí)水管，那么就是好格子，否則就是壞格子。

考慮一行所有豎著的邊，如果兩個(gè)邊標(biāo)的數(shù)相同，且之間的邊數(shù)為奇數(shù)，那么里面一定有一個(gè)壞格子。如果標(biāo)的數(shù)不同，一樣有類似的限制。

不難發(fā)現(xiàn)我們僅有這樣的限制，也就是說，如果所有限制都滿足，那么一定可以構(gòu)造出合法解。

考慮把所有行限制放在左邊，所有列限制放在右邊，考慮如果兩個(gè)限制有交點(diǎn)，那么連一條邊。限制的個(gè)數(shù)確實(shí)是 \(n^3\) 個(gè)，但是大部分都是沒有邊相連的，這是因?yàn)槲覀兊倪厰?shù)是 \(n^2\) 的。剩下的就是求一個(gè)最小邊覆蓋，跑網(wǎng)絡(luò)流即可。

沒有邊相連的點(diǎn)一定有一個(gè) \(1\) 的代價(jià)。

不過還有兩個(gè)限制沒有考慮：某個(gè)格子必須是好格子以及某個(gè)格子我不能填好格子。

首先如果某個(gè)格子我不能填好格子的話，那么它一定是沒有任何貢獻(xiàn)的，我們按照需要填就可以。

至于某個(gè)格子必須是好格子這個(gè)限制，其實(shí)也是好做的，我們只需要關(guān)注所有限制是否滿足，即是否存在一個(gè)限制里面所有的格子都要求是好的。

struct edge{
    int to,next,f;
    inline void Init(int to_,int ne_,int f_){
        to=to_;next=ne_;f=f_;
    }
}li[N*N<<1];
int head[N*N*N],now[N*N*N],tail=1,n,m,de[N*N*N],tot,c[N],pl[N][N],pr[N][N];
bool flag=1;
int s,t,d[N*N*N];
char a[N][N];
vi L,R;

inline void Add(int from,int to,int f){
    li[++tail].Init(to,head[from],f);head[from]=tail;
    swap(from,to);li[++tail].Init(to,head[from],0);head[from]=tail;
}
queue<int> q;
inline bool bfs(){
    mset(d,0);
    q.push(s);d[s]=1;
    while(q.size()){
        int top=q.front();q.pop();now[top]=head[top];
        Next(top){
            int to=li[x].to,f=li[x].f;
            if(d[to]||!f) continue;
            d[to]=d[top]+1;q.push(to);
        }
    }
    if(d[t]) return 1;return 0;
}
inline int Dinic(int k,int flow){
    if(k==t) return flow;
    int rest=flow,x;
    for(x=now[k];x&&rest;x=li[x].next){
        int to=li[x].to,f=li[x].f;
        if(d[to]!=d[k]+1||!f) continue;
        int re=Dinic(to,min(rest,f));
        if(!re) d[to]=-INF;
        rest-=re;li[x].f-=re;li[x^1].f+=re;
    }
    now[k]=x;
    return flow-rest;
}
inline int RunDinic(){
    int ans=0;
    while(bfs()){
        ans+=Dinic(s,INF);
    }
    return ans;
}
inline void chk(int x,int k){
    if(c[x]==-1) c[x]=k;else if(c[x]!=k) flag=0;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,1,n){
        scanf("%s",a[i]+1);
    }
    rep(i,1,n){
        mset(c,-1);
        c[1]=0;c[m+1]=0;
        rep(j,1,m){
            if(a[i][j]=='1'||a[i][j]=='2') chk(j,1),chk(j+1,0);
            else if(a[i][j]=='3'||a[i][j]=='4') chk(j,0),chk(j+1,1);
        }
        for(int j=1,k=2;j<=m+1&&k<=m+1;j=k++){
            while(c[k]==-1) k++;
            if(((k-j)&1)==(c[k]^c[j])) continue;
            bool ok=0;
            rep(o,j,k-1) if(a[i][o]=='x') ok=1;
            if(ok) continue;
            rep(o,j,k-1) if(a[i][o]=='.') ok=1;
            if(!ok){
                flag=0;continue;
            }
            tot++;L.pb(tot);
            rep(o,j,k-1) pl[i][o]=tot;
        }
    }
    rep(j,1,m){
        mset(c,-1);
        rep(i,1,n){
            if(a[i][j]=='1'||a[i][j]=='3') chk(i,1),chk(i+1,0);
            if(a[i][j]=='2'||a[i][j]=='4') chk(i,0),chk(i+1,1);
        }
        c[1]=0;c[n+1]=0;
        for(int i=1,k=2;i<=n+1&&k<=n+1;i=k++){
            while(c[k]==-1) k++;
            if(((k-i)&1)==(c[k]^c[i])) continue;
            bool ok=0;
            rep(o,i,k-1) if(a[o][j]=='x') ok=1;
            if(ok) continue;
            rep(o,i,k-1) if(a[o][j]=='.') ok=1;
            if(!ok){
                flag=0;continue;
            }
            tot++;R.pb(tot);
            rep(o,i,k-1) pr[o][j]=tot;
        }
    }
    if(!flag){
        puts("-1");return 0;
    }
    rep(i,1,n)rep(j,1,m){
        if(a[i][j]=='.'&&pl[i][j]&&pr[i][j]){
            Add(pl[i][j],pr[i][j],1);
            de[pl[i][j]]++;
            de[pr[i][j]]++;
        }
    }
    s=++tot;t=++tot;
    for(int x:L){
        if(de[x]) Add(s,x,1);
    }
    for(int x:R){
        if(de[x]) Add(x,t,1);
    }
    int ans=n*m;
    rep(i,1,n)rep(j,1,m){
        if(a[i][j]=='x') ans--;
    }
    int cnt=0;
    for(int x:L) if(!de[x]) ans--;else cnt++;
    for(int x:R) if(!de[x]) ans--;else cnt++;
    ans-=(cnt-RunDinic());
    printf("%d\n",ans);
    return 0;
}

Zhengrui 2022ABDay1 C

考慮設(shè) \(f_{x,i}\) 表示 \(x\) 子樹在 \(i\) 已經(jīng)選的情況下的最優(yōu)解，而 \(g_x\) 表示任意情況下 \(x\) 子樹的最優(yōu)解。

考慮轉(zhuǎn)移，顯然如果 \(f_{x,i}\) 是從 \(f_{to,i}\) 轉(zhuǎn)移過來，因?yàn)?\(i\) 被選的代價(jià)減重了，所以要加上 \(s\)。或者我們考慮從 \(g_{to}\) 轉(zhuǎn)移過來。

不難證明最優(yōu)解的方案一定是包含在其中的。而其余的方案一定都是合法的，這保證了做法的正確性，代碼復(fù)雜度完虐 std 做法。

#include <bits/stdc++.h>
using namespace std;
long long n,a[1010],t,d,s,dis[1010][1010],f[1010][1010],g[1010];
vector<pair<int,int> >v[1010];
void DFS(int rt,int x,int fa){
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i].first;
		long long val=v[x][i].second;
		if(to==fa)continue;
		dis[rt][to]=dis[rt][x]+val;
		DFS(rt,to,x);
	}
}
void dfs(int x,int fa){
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i].first;
		if(to==fa)continue;
		dfs(to,x);
	}
	for(int i=1;i<=n;i++){
		f[x][i]=a[x]*(dis[x][i]<=d)-s;
		for(int j=0;j<v[x].size();j++){
			int to=v[x][j].first;
			if(to==fa)continue;
			f[x][i]+=max(g[to],f[to][i]+s);
		}
	}
	for(int i=1;i<=n;i++)g[x]=max(g[x],f[x][i]);
}		
int main(){
	scanf("%lld%lld%lld%lld",&n,&t,&d,&s);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]*=t;
	for(int i=1;i<n;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		v[x].push_back({y,w});
		v[y].push_back({x,w});
	}
	for(int i=1;i<=n;++i)DFS(i,i,0);
	dfs(1,0);
	printf("%lld\n",g[1]);
}

這里由于不想寫了，粘了別人的一份代碼過來。

考慮 std 做法怎么做。轉(zhuǎn)移其實(shí)只需要知道 \(u\) 子樹內(nèi)最淺的被選點(diǎn)是哪個(gè)和最深的能被最選點(diǎn)選到的點(diǎn)是哪個(gè)即可，考慮兩種情況只會(huì)出現(xiàn)一種，所以可以轉(zhuǎn)移。

轉(zhuǎn)移是一個(gè)樹形 DP，不過要我的做法要大分討。

看了下 maoyiting 的代碼，發(fā)現(xiàn)其實(shí)都可以用背包來轉(zhuǎn)移，全都放在背包里進(jìn)行轉(zhuǎn)移顯然能有效降低代碼復(fù)雜度。

Zhengrui 2022NOIPDay4 B

感覺思路還是比較自然的。首先考慮是一個(gè)排列怎么做，考慮里面 \(n\) 在 \(B\) 序列中的位置在哪里，設(shè)為 \(q\)，那么首先 \(n\) 在 \(A\) 中的出現(xiàn)位置一定小于等于 \(q\)，其次 \(A_1,\cdots,A_q\) 中的數(shù)一定會(huì)在 \(B_1,\cdots,B_q\) 中出現(xiàn)，因?yàn)槲覀兊?\(q\) 一定會(huì)把堆中的數(shù)清空。于是我們就把整個(gè)序列分成了兩部分，分別進(jìn)行計(jì)算即可。這提示我們區(qū)間 DP。

考慮設(shè) \(f_{l,r,x}\) 表示考慮 \(l\) 到 \(r\) 中小于等于 \(x\) 中出現(xiàn)的數(shù)，方案數(shù)數(shù)多少，枚舉 \(x\) 的出現(xiàn)位置即可。注意為了保證不算重，我們只需要關(guān)注那些 \(a_k\le x\) 的數(shù)即可。

int n,a[N],f[N][N][N],cnt[N],po[N];

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]);
    rep(i,1,n) cnt[a[i]]++;
    rep(i,1,n) cnt[i]+=cnt[i-1];
    dec(i,1,n) a[i]=cnt[a[i]]--;
    // rep(i,1,n) printf("%lld ",a[i]);puts("");
    rep(i,1,n) po[a[i]]=i;
    rep(i,1,n){
        rep(j,0,n) f[i][i][j]=1;
    }
    rep(i,2,n){
        rep(j,1,n-i+1){
            int l=j,r=j+i-1;
            f[l][r][0]=1;
            int minn=INF,maxx=-INF;
            rep(k,l,r) cmin(minn,a[i]),cmax(maxx,a[i]);
            rep(x,1,n){
                int posi=po[x];
                if(posi<l||posi>r){
                    f[l][r][x]=f[l][r][x-1];
                    // printf("f[%d][%d][%d]=%d\n",l,r,x,f[l][r][x]);
                    continue;
                }
                if(posi==r){
                    f[l][r][x]=f[l][r][x-1];
                    // printf("f[%d][%d][%d]=%d\n",l,r,x,f[l][r][x]);
                    continue;
                }
                rep(k,posi,r-1){
                    if(a[k]>x) continue;
                    f[l][r][x]=(f[l][r][x]+f[l][k][x-1]*f[k+1][r][x]%mod)%mod;
                }
                if(a[r]<=x) (f[l][r][x]+=f[l][r][x-1])%=mod;
                // printf("f[%d][%d][%d]=%d\n",l,r,x,f[l][r][x]);
            }
        }
    }
    int ans=f[1][n][n];
    printf("%lld\n",ans);
    return 0;
}

CF1004D

由于對(duì)稱，不妨設(shè) \(x\le \lceil\frac{n}{2}\rceil,y\le \lceil\frac{m}{2}\rceil\)，那么矩陣最大值應(yīng)該就是 \(n+m-x-y\)。首先特判掉 \(n=m\) 且都為奇數(shù)，并且 \(x,y\) 都在中間的情況，除去這種情況，其余情況下，第一個(gè)被矩陣卡出去的數(shù)字一定不是 \(4\) 的倍數(shù)，而比它小的數(shù)字除了 \(0\) 之外都是 \(4\) 的倍數(shù)。由此可以知道 \(x\) 是多少，這樣的話可以枚舉 \(n,m\)，這樣 \(n,m,x,y\) 都知道了，直接構(gòu)造出來矩形，判斷即可。

CF677D

設(shè) \(v_t\) 表示所有權(quán)值為 \(t\) 的位置組成的集合，我們只需要考慮所有 \(v_{t-1}\) 到 \(v_t\) 的轉(zhuǎn)移即可。有兩種轉(zhuǎn)移方式，一是直接在原圖上跑多元 bfs，二是對(duì)于 \(v_{t}\) 中的每一個(gè)數(shù)，枚舉 \(v_{t-1}\) 中的每個(gè)位置，然后轉(zhuǎn)移。

考慮把這兩個(gè)結(jié)合一下：設(shè) \(a=|v_{t-1}|,b=|v_t|\)，若 \(ab<nm\)，則用第二種轉(zhuǎn)移，否則用第一種轉(zhuǎn)移。

證明復(fù)雜度是正確的，考慮 \(ab<nm\)，則根據(jù)柯西不等式有：

\[(\sum\limits_{i}|v_{i-1}||v_i|)^2\le (\sum\limits_{i}|v_i|^2)^2\le (nm\sqrt{nm})^2 \]

考慮 \(ab>nm\)，則有 \(\sum\limits_{i}[ab>nm]nm\)，前者需要滿足 \(a,b\) 至少一個(gè)大于 \(\sqrt{nm}\)，因此也是 \(nm\sqrt{nm}\)。

所以復(fù)雜度是正確的。

CF contest1737 D

顯然把每條邊移到 \(1,n\) 中間，且由于操作，每個(gè)邊都可以移到 \(1,n\) 中間，證明是顯然的。所以 floyed 預(yù)處理一下即可。

ZR 2354

考慮枚舉一下種族顯然是可以做到 \(n^3\) 的，如果一個(gè)種族出現(xiàn)了 \(cnt\) 次，那么顯然我們背包的大小可以限制在 \([-cnt,cnt]\) 內(nèi)，這樣就可以把這個(gè)題優(yōu)化到 \(n^2\)。

#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 3010
#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,c[N],f[N][2*N],cnt[N],v[N],siz[N],m,base,g[2*N],ans;
vi e[N];

inline void dfs(int k,int fat){
    siz[k]=1;
    rep(i,-m,m) f[k][i+base]=0;
    if(v[k]==1) f[k][base+1]=1;
    else f[k][base-1]=1;
    for(int to:e[k]) if(to!=fat) dfs(to,k);
    for(int to:e[k]) if(to!=fat){
        rep(i,-m,m) g[i+base]=0;
        rep(i,max(-siz[k],-m),min(siz[k],m)){
            rep(j,max(-m-i,max(-siz[to],-m)),min(m-i,min(siz[to],m))){
                g[i+j+base]=(g[i+j+base]+f[k][i+base]*f[to][j+base]%mod)%mod;
            }
        }
        siz[k]+=siz[to];
        rep(i,-m,m) f[k][i+base]=(f[k][i+base]+g[i+base])%mod;
    }
    // rep(i,-siz[k],siz[k]){
    //     printf("f[%d][%d]=%d\n",k,i,f[k][i+base]);
    // }
    rep(i,1,m) ans=(ans+f[k][i+base])%mod;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(c[i]);
    rep(i,1,n-1){
        int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
    }
    base=n;
    rep(i,1,n) cnt[c[i]]++;
    rep(i,1,n){
        // printf("i=%d\n",i);
        // if(c[i]==i) v[i]=1;
        // else v[i]=-1;
        rep(j,1,n) if(c[j]==i) v[j]=1;else v[j]=-1;
        m=cnt[i];
        dfs(1,0);
        // printf("m=%d\n",m);
        // printf("ans=%d\n",ans);
    }
    printf("%lld\n",ans);
    return 0;
}

ZR 2356

經(jīng)過觀察樣例，我們可以考慮通過構(gòu)造出 \(+1\) 和 \(\times 2\) 兩種操作來進(jìn)行構(gòu)造。

重點(diǎn)是如何構(gòu)造出 \(+1\)，我們用 \((x,y)\) 來表示那些滿足如下條件的 LCS：\(x,y\) 是該 \(LCS\) 在 \(s,t\) 中的最靠前的匹配位置。那么我們?nèi)绾巫龅?\(+1\)，一個(gè)想法是讓 \((x-1,y)\) 來代表一個(gè) LCS，\((x,y)\) 來代表剩下的 \(K-1\) 個(gè) LCS，我們要利用 \((x-1,y)\) 來考慮構(gòu)造出 \(+1\)，不妨設(shè) \(s_{x}=s_{x-1}=t_y=1\)，那么如下構(gòu)造可以進(jìn)行 \(+1\)：

\[\begin{aligned} s' &= s + 000\\ t' &= t + 0100 \end{aligned} \]

\(+1\) 的原因是 \((x-1,y)\) 會(huì)在 \(s\) 的末尾剩下一個(gè) \(1\)，從而可以有一個(gè) \(100\) 的配對(duì),同樣也可以有一個(gè) \(000\) 的配對(duì)。而且對(duì)于 \((x,y)\) 都會(huì)產(chǎn)生 \(000\) 的配對(duì)，所以就多出來了一個(gè)。

同時(shí)，不難發(fā)現(xiàn)之前的 \((x-1,y)\) 代表一個(gè)，剩下都由 \((x,y)\) 代表的性質(zhì)不變。

同樣，如下構(gòu)造可以進(jìn)行 \(\times 2\)：

\[\begin{aligned} s' &= s + 011000\\ t' &= t + 101000 \end{aligned} \]

容易發(fā)現(xiàn) LCS 個(gè)數(shù)確實(shí)變成了兩倍，只需要考慮是否滿足性質(zhì)即可。不難發(fā)現(xiàn)是滿足性質(zhì)的（\(11000\) 的配對(duì)。）

ZR 2357

首先可以線段樹優(yōu)化建圖跑 spfa，不過沒寫。

考慮一個(gè)樸素的 DP，設(shè) \(f_i\) 表示從 \(i\) 到 \(n\) 的最優(yōu)值，有一個(gè) naive 的 DP：

\[f_i=\max\limits_{i+1\le j\le i+T_i}\{ f_j-\lfloor \frac{j-i}{K} \rfloor\times D \} + H_i \]

考慮 \(\lfloor\frac{j-i}{K}\rfloor=\lfloor\frac{j}{K}\rfloor-\lfloor\frac{i}{K}\rfloor-[j\bmod K<i\bmod K]\)，所以 DP 可以寫成：

\[f_i=\max\limits_{i+1\le j\le i+T_i}\{ f_j-\lfloor\frac{j}{K}\rfloor\times D +[j\bmod K<i\bmod K]\times D\}+H_i+\lfloor\frac{i}{K}\rfloor\times D \]

首先一個(gè)想法是對(duì)于每一個(gè) \(i\bmod K\) 都開一個(gè)樹狀數(shù)組，可以做到 \(nK\log n\)，不過我們可以用兩個(gè)樹狀數(shù)組，一個(gè)表示前綴 \(f_i-\lfloor\frac{j}{K}\rfloor\times D\) 的最大值，一個(gè)表示后綴的最大值，然后轉(zhuǎn)移即可。這里的前綴后綴是在 \(\bmod K\) 的意義下。

復(fù)雜度 \(n\log n\)。

ZR 2399

稍微手玩以下就會(huì)發(fā)現(xiàn)如果一個(gè) \(n\time m\) 的矩形，被填了一個(gè) \(a\times b\) 的左上角，且 \(a<n,b<m\)，發(fā)現(xiàn)這樣是無(wú)法繼續(xù)往下填的，也就是說，我們考慮每次填一個(gè)矩形 \(a\times b\) 必須要滿足 \(a=n\) 或者 \(b=m\)。

不妨假設(shè) \(n<m\)，經(jīng)過構(gòu)造后可以分別知道 \(n\) 為 \(1,2\)，是奇數(shù)，是偶數(shù)時(shí)能填的矩形，往上填即可。

經(jīng)過討論不難發(fā)現(xiàn)不用再計(jì)算 \(m,n\)。

下面放一張討論結(jié)果。

ZR 2400

觀察可知 \(n\) 很大的時(shí)候 \(d\) 不會(huì)很大，因?yàn)橛兄涤虻南拗疲?jīng)過一些估算可以知道 \(nd\le 2\times 10^6\)，不過我們可以直接枚舉 \(d\)，寫個(gè)卡時(shí)就行。這是小問題。

枚舉 \(d\) 之后考慮怎么做，題目要求兩個(gè)等差數(shù)列，考慮一個(gè)怎么做，設(shè) \(b_i=a_i-(i-1)d\)，然后假設(shè)首項(xiàng)為 \(x\)，那么答案應(yīng)該就是：

\[\sum\limits_{x<b_i} |x-b_i|+\sum\limits_{x\ge b_i} \frac{|x-b_i|}{2} \]

注意第二個(gè) \(\sum\) 會(huì)有一些奇偶性的問題，我們先不去管它，發(fā)現(xiàn)整個(gè)式子相當(dāng)于一個(gè)帶權(quán)中位數(shù)，那么在把所有的 \(c\) 排序之后我們應(yīng)該選第 \(n-\lceil\frac{n}{3}\rceil+1\) 這個(gè)位置的 \(c\)，注意這里相當(dāng)于是取到最小值的最右邊的 \(c\)，所以考慮上奇偶性就在考慮一下左邊的那個(gè) \(c\) 值減一即可。

兩個(gè)等差數(shù)列相當(dāng)于一個(gè)前綴和一個(gè)后綴，考慮預(yù)處理之后枚舉斷點(diǎn)，預(yù)處理的時(shí)候需要維護(hù)中位數(shù)，除了線段樹，還可以用常數(shù)更小的對(duì)頂堆來實(shí)現(xiàn)，只需要同時(shí)維護(hù)一個(gè)堆的奇數(shù)和，奇數(shù)個(gè)數(shù)，偶數(shù)和，偶數(shù)個(gè)數(shù)，另一個(gè)堆的和和個(gè)數(shù)就可以了。

詳細(xì)看代碼。

#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 100010
#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=1e18;
const dd eps=1e-9;

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,a[N],ans,pr[N],su[N],b[N];
int sum,cnt[2],sm[2],cn;
priority_queue<int> q1;
priority_queue<int,vc<int>,greater<int> > q2;

inline void push_1(int x){
    cnt[x&1]++;
    sm[x&1]+=x;
    q1.push(x);
}
inline void push_2(int x){
    sum+=x;
    cn++;
    q2.push(x);
}
inline int pop_1(){
    int x=q1.top();
    cnt[x&1]--;
    sm[x&1]-=x;
    q1.pop();
    return x;
}
inline int pop_2(){
    int x=q2.top();
    sum-=x;
    cn--;
    q2.pop();
    return x;
}
inline int get_ans(int x){
    int o=x&1;
    int nowans=(x*cnt[o]-sm[o])/2+(x*cnt[o^1]-sm[o^1]+cnt[o^1])/2+cnt[o^1]+sum-cn*x;
    // printf("x=%d nownas=%lld\n",x,nowans);
    return nowans;
}
inline void solve(int *f){
    while(q1.size()) q1.pop();
    while(q2.size()) q2.pop();
    sm[0]=sm[1]=cnt[0]=cnt[1]=sum=0;cn=0;
    f[0]=0;
    rep(i,1,n){
        // printf("i=%d\n",i);
        if(q2.size()==0){
            push_2(b[i]);
            int k=q2.top();
            f[i]=min(get_ans(k),get_ans(k-1));
            continue;
        }
        int to=q2.top();
        if(to<=b[i]) push_2(b[i]);
        else push_1(b[i]);
        if(q1.size()<i-(i+2)/3){
            assert(q2.size());
            push_1(pop_2());
        }
        if(q1.size()>i-(i+2)/3){
            assert(q1.size());
            push_2(pop_1());
        }
        int k=q2.top();
        f[i]=min(get_ans(k),get_ans(k-1));
    }
}
inline void calc(int d){
    // printf("d=%d\n",d);
    rep(i,1,n) b[i]=a[i]-(i-1)*d;
    // rep(i,1,n){
        // printf("b[%d]=%d\n",i,b[i]);
    // }
    solve(pr);reverse(b+1,b+n+1);solve(su);
    rep(i,0,n){
        ans=min(ans,pr[i]+su[n-i]);
        // printf("pr[%d]=%d su[%d]=%d\n",i,pr[i],n-i,su[n-i]);
    }
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    ans=INF;
    read(n);rep(i,1,n) read(a[i]);
    for(int i=1;clock()<=0.8*CLOCKS_PER_SEC;i++) calc(i),calc(-i);
    // calc(3);
    printf("%lld\n",ans);
    return 0;
}

posted @ 2023-07-13 21:32 NuclearReactor 閱讀(28) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

HeNuclearReactor