當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Wannafly挑战赛29题解

發(fā)布時間：2025/6/17 编程问答 46 豆豆

生活随笔收集整理的這篇文章主要介紹了 Wannafly挑战赛29题解小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

這套題目非常有意思啊23333……話說為啥沒有上條先生的呢……

傳送門

\(A\) 御坂美琴

蠢了……首先先判總共加起來等不等于\(n\)，不是的話就不行

然后dfs記錄\(n\)不斷分下去能分成哪些數(shù)，用map記錄一下，判斷是否所有數(shù)都能被分出來就是了

//minamoto #include<bits/stdc++.h> #define int long long #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){int res,f=1;char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } const int N=1e5+5; int n,sum,x,m,a[N];map<int,bool>mp; void dfs(int n){if(mp[n])return;mp[n]=1;dfs(n/2),dfs(n-n/2); } signed main(){ // freopen("testdata.in","r",stdin);n=read(),m=read();fp(i,1,m)a[i]=read(),sum+=a[i];if(sum!=n)return puts("ham"),0;dfs(n);fp(i,1,m)if(!mp[a[i]])return puts("ham"),0;return puts("misaka"),0; }

\(B\) 白井黑子

好坑啊……話說居然有\(f(0)=1\)……

如果\(k=0\)，那么顯然只有\(f(a)=1\)且\(f(b)=1\)的時候是\(gg\)的，總的方案數(shù)減去這種方案數(shù)就行了

對于\(k>0\)的情況，顯然所有位上有\(0\)的都不用管了（\(0\)除外）。

首先\(f(a)\times f(b)\)最多只有\(2,3,5,7\)四個質(zhì)因子，那么如果\(ab\)不合法當(dāng)且僅當(dāng)\(f(a)\times f(b)\)里四個質(zhì)因子的出現(xiàn)次數(shù)模\(k\)都為\(0\)，把每個\(f(a)\)的四個質(zhì)因子的出現(xiàn)次數(shù)哈希一下，并順便算一下不合法的\(b\)的哈希值，用之前所有的減去不合法的就行了。開個\(map\)即可

所以我真的不知道為啥我死都用不了\(unordered\_map\)……

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define pi pair<int,int> #define fi first #define se second #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} ll read(){R ll res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } int n,k,cnt;ll res,x; inline bool ck0(R ll x){while(x){if(x%10==0)return true;x/=10;}return false;} inline bool ck1(R ll x){while(x){if(x%10!=1)return false;x/=10;}return true;} void qwq(){fp(i,1,n)x=read(),cnt+=ck1(x);printf("%lld\n",(1ll*n*(n-1)>>1)-(1ll*cnt*(cnt-1)>>1)); } const int P1=998244353,P2=1e9+7; const int Base1=233,Base2=19260817; pi bin[5],now,las;map<pi,int>mp; inline pi operator +(const pi &a,const pi &b){return pi((a.fi+b.fi)%P1,(a.se+b.se)%P2);} inline pi operator *(const int &a,const pi &b){return pi(1ll*a*b.fi%P1,1ll*a*b.se%P2);} int c[15]; int main(){ // freopen("testdata.in","r",stdin);n=read(),k=read();if(!k)return qwq(),0;bin[0].fi=Base1,bin[0].se=Base2;fp(i,1,5)bin[i].fi=1ll*bin[i-1].fi*Base1%P1,bin[i].se=1ll*bin[i-1].se*Base2%P2;fp(i,1,n){x=read();if(ck0(x))continue;fp(j,0,3)c[j]=0;while(x){switch(x%10){case 0:break;case 1:break;case 2:++c[0];break;case 3:++c[1];break;case 4:++c[0],++c[0];break;case 5:++c[2];break;case 6:++c[0],++c[1];break;case 7:++c[3];break;case 8:c[0]+=3;break;case 9:++c[1],++c[1];break;}x/=10;}now.fi=now.se=las.fi=las.se=0;fp(j,0,3)now=now+c[j]%k*bin[j],las=las+(k-c[j]%k)%k*bin[j];res+=cnt-mp[las],++mp[now],++cnt;}printf("%lld\n",res);return 0; }

\(C\) 左方之地

根據(jù)期望的線性，我們轉(zhuǎn)化為求每個節(jié)點(diǎn)的深度的期望

因?yàn)槊總€子樹中的節(jié)點(diǎn)編號都小于自己的標(biāo)號，那么我們考慮這樣一種構(gòu)造法：欽定第一個點(diǎn)為根節(jié)點(diǎn)，之后再把第二個點(diǎn)掛上去，再掛第三個點(diǎn)……容易發(fā)現(xiàn)這樣一定滿足子樹中所有節(jié)點(diǎn)標(biāo)號小于自己。因?yàn)榭偟呐帕袀€數(shù)有\(n!\)種，這樣構(gòu)造出的樹也總共有\(n!\)種，所以我們的排列和二叉樹就是一一對應(yīng)的了

因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(i\)號節(jié)點(diǎn)的深度和它后面所有節(jié)點(diǎn)都沒有關(guān)系，那么我們就一個一個來考慮了

設(shè)\(f_i\)，表示“所有\(i\)個節(jié)點(diǎn)的樹中，所有能掛葉子的位置，它們的父親的深度的和”

這個可能比較難理解，以樣例那棵樹為例，\(1\)下面可以掛一個葉子，\(2\)下面可以掛\(1\)個葉子，\(3\)下面可以掛\(2\)個葉子，那么這棵樹的權(quán)值就是\(1\times 1+1\times 2+2\times 3=9\)，而\(f_i\)就是所有\(i\)個節(jié)點(diǎn)的樹的權(quán)值之和

考慮一下這東西怎么轉(zhuǎn)移，先把柿子給出來

\[f_i=if_{i-1}-f_{i-1}+2(f_{i-1}+i!)\]

首先\(i-1\)個節(jié)點(diǎn)共有\(i!\)棵樹，第\(i\)個節(jié)點(diǎn)在每棵樹上有\(i\)個位置可以掛，所以每棵樹會被掛到\(i\)次，那么不考慮對深度的影響的話就是\(if_{i-1}\)。然而掛上去的那個位置會少掉，那么要減去一個\(f_{i-1}\)，而新掛上的葉子的深度是原來節(jié)點(diǎn)的深度\(+1\)，而且新掛上去的節(jié)點(diǎn)會提供兩個可以掛葉子的位置，總共掛了\(i!\)次，所以要加上后面的東西

所以這東西和期望深度有半毛錢關(guān)系么……

我們發(fā)現(xiàn)后面那個東西似乎很有用誒……“新掛上的葉子的深度是原來節(jié)點(diǎn)的深度\(+1\)”……那么\(i\)掛上去的所有情況的深度總數(shù)就是\(f_{i-1}+i!\)，而樹的情況總共有\(i!\)種，那么期望深度就是\({f_i+i!\over i!}\)

然后直接遞推就可以了

\(D\) 風(fēng)斬冰華

所以\(dp\)是咱的硬傷啊……

我們先把它轉(zhuǎn)化成一棵無根樹，那么影響每個節(jié)點(diǎn)度數(shù)的可以分為兒子和父親的情況來考慮，父親的情況還要考慮是先于父親刪還是后于父親刪

設(shè)\(dp_{u,0/1/2}\)分別表示不刪\(/\)先于父親刪\(/\)后于父親刪的最大權(quán)值

首先\(dp_{u,0}\)很好轉(zhuǎn)移

\[dp_{u,0}=\sum_{(u,v)\in E} \max(dp_{v,0},dp_{v,1})\]

然而\(dp_{u,1}\)和\(dp_{u,2}\)的轉(zhuǎn)移就顯得有些辣手了

我們先考慮每個兒子的貢獻(xiàn)，如果這個兒子保留，貢獻(xiàn)就是\(\max(dp_{v,0},dp_{v,2})\)，如果刪掉，貢獻(xiàn)就是\(dp_{v,1}\)

那么我們一開始強(qiáng)制所有節(jié)點(diǎn)都刪掉（有可能有的\(dp_{v,1}\)不合法，這種情況要除去），并計算貢獻(xiàn)。那么如果要把這個節(jié)點(diǎn)保留下來，貢獻(xiàn)就要加上\(\max(dp_{v,0},dp_{v,2})-dp_{v,1}\)

我們把所有的\(\max(dp_{v,0},dp_{v,2})-dp_{v,1}\)從大到小排個序，先加點(diǎn)加到滿足度數(shù)\(\geq l\)，然后在滿足度數(shù)限制的情況下把剩下能加的點(diǎn)都加進(jìn)去就行了（具體細(xì)節(jié)可以看代碼）

\(E\) 一方通行

沒有題解的代碼食用體驗(yàn)極差……

我們可以把答案拆成若干條路徑（這里的路徑需要至少有兩個節(jié)點(diǎn)），相鄰兩條路徑之間通過一條跨越樹的邊相連，即每一段都是某棵樹上的一條路徑。這些路徑需要兩兩不交，并且相鄰兩端不在同一棵樹上。我們需要先計算選取路徑的方案數(shù)，再計算它們排列的方案數(shù)

先考慮一棵樹，我們設(shè)\(f_{u,i,j,0/1/2}\)記錄方案數(shù)，表示\(u\)所在的子樹，從中選出\(j\)條路徑，這些路徑上總共有\(i\)個點(diǎn)，\(0\)表示\(u\)不在路徑中，\(1\)表示\(u\)是路徑的端點(diǎn)且這條路徑還需要延伸，\(2\)表示\(u\)所在的路徑已經(jīng)全部選完了。轉(zhuǎn)移的話……太長了看代碼吧……

那么整棵樹的方案就是\(f_{1,i,j,0}+f_{1,i,j,2}\)，記為\(sum_{T,i,j}\)，\(T\)表示這是第幾棵樹

然后我們需要把它們給排列起來，枚舉一下三棵樹上選擇的路徑條數(shù)\(x,y,z\)，可以轉(zhuǎn)化成這樣一個問題：有三種顏色的物品，每種顏色的物品分別有\(x,y,z\)，求沒有兩種相同顏色相鄰的排列數(shù)

設(shè)\(g_{i,j,k,op}\)表示三種顏色的物品分別有\(i,j,k\)個，且最后一個顏色為\(op\)的排列個數(shù)，轉(zhuǎn)移的話，枚舉一下新加的物品是什么顏色就行了，如果把三種顏色分別記為\(0,1,2\)的話，順便可以記一個\(g_{i,j,k,3}\)表示\(g_{i,j,k,0}+g_{i,j,k,1}+g_{i,j,k,2}\)

接下來就是統(tǒng)計答案的時間~~~

枚舉三棵樹分別選了\(x,y,z\)個點(diǎn)，枚舉三棵樹上分別有\(i,j,l\)條路徑，那么答案就要加上

\[sum_{0,x,i}\times sum_{1,y,j}\times sum_{2,z,l}\times g_{i,j,l,3}\times 2^{i+j+l}\times i!\times j!\times l!\]

前面三個\(sum\)好理解，\(g_{i,j,l,3}\)就是合法排列個數(shù)，然后我們數(shù)的路徑都是無向的所以要給每條路徑定向，乘上個\(2^{i+j+l}\)，順便我們的\(g_{i,j,l,3}\)里面算的時候默認(rèn)所有顏色的物品等價，所以要乘上后面三個階乘

//minamoto #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } const int N=505,P=998244353; inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;} inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;} inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;} inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;} int ksm(R int x,R int y){R int res=1;for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;return res; } struct eg{int v,nx;}e[N<<1];int head[N],tot; inline void Add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;} int fac[15],bin[15],sz[N],f[N][21][21][3],g[15][15][15][5],sum[3][15][15]; int n,k; void dfs(int u,int fa){f[u][0][0][0]=1,sz[u]=1;go(u)if(v!=fa){dfs(v,u);fd(a,min(sz[u],k),0)fd(c,min(sz[u],k),0)if(f[u][a][c][0]||f[u][a][c][1]||f[u][a][c][2]){R int x=f[u][a][c][0],y=f[u][a][c][1],z=f[u][a][c][2];f[u][a][c][0]=f[u][a][c][1]=f[u][a][c][2]=0;fd(b,min(sz[v],k-a),0)fd(d,min(sz[v],k-a),0)if(f[v][b][d][0]||f[v][b][d][1]||f[v][b][d][2]){upd(f[u][a+b][c+d][0],mul(x,add(f[v][b][d][0],f[v][b][d][2]))),upd(f[u][a+b+2][c+d][1],mul(x,f[v][b][d][0])),upd(f[u][a+b+1][c+d][1],mul(x,f[v][b][d][1])),upd(f[u][a+b][c+d][1],mul(y,add(f[v][b][d][0],f[v][b][d][2]))),upd(f[u][a+b][c+d+1][2],mul(y,f[v][b][d][1])),upd(f[u][a+b+1][c+d+1][2],mul(y,f[v][b][d][0])),upd(f[u][a+b][c+d][2],mul(z,add(f[v][b][d][0],f[v][b][d][2])));}}sz[u]+=sz[v];}fd(a,min(sz[u],k),0)fd(c,min(sz[u],k),0)upd(f[u][a][c+1][2],f[u][a][c][1]); } int main(){ // freopen("testdata.in","r",stdin);n=read(),k=read(),fac[0]=bin[0]=1;fp(i,1,k)fac[i]=mul(fac[i-1],i),bin[i]=add(bin[i-1],bin[i-1]);fp(T,0,2){tot=0,memset(head,0,(n+1)<<2);for(R int i=1,u,v;i<n;++i)u=read(),v=read(),Add(u,v),Add(v,u);memset(f,0,sizeof(f));dfs(1,0);fd(i,k,0)fd(j,k,0)sum[T][i][j]=add(f[1][i][j][0],f[1][i][j][2]);}g[1][0][0][0]=g[1][0][0][3]=1,g[0][1][0][1]=g[0][1][0][3]=1,g[0][0][1][2]=g[0][0][1][3]=1;fp(i,0,k)fp(j,0,k-i)fp(l,0,k-i-j)if(i+j+l>1){fp(op,0,2){R int res=0;if(op==0&&i)upd(res,dec(g[i-1][j][l][3],g[i-1][j][l][0]));if(op==1&&j)upd(res,dec(g[i][j-1][l][3],g[i][j-1][l][1]));if(op==2&&l)upd(res,dec(g[i][j][l-1][3],g[i][j][l-1][2]));g[i][j][l][op]=res,upd(g[i][j][l][3],res);}}int res=0;fp(x,0,k)fp(y,0,k-x){R int z=k-x-y;fp(i,0,x)if(sum[0][x][i])fp(j,0,y)if(sum[1][y][j])fp(l,0,z)if(sum[2][z][l])upd(res,1ll*sum[0][x][i]*sum[1][y][j]%P*sum[2][z][l]%P*g[i][j][l][3]%P*bin[i+j+l]%P*fac[i]%P*fac[j]%P*fac[l]%P);}printf("%d\n",res);return 0; }

\(F\) 最后之作

我感覺我已經(jīng)是個廢人了……

注意\(g_{i,j}\)表示的是\(s_1[i,j],s_2[i,j],...,s_n[i,j]\)這\(n\)個串中本質(zhì)不同的串的個數(shù)，也就是說這個值值域?yàn)?span id="ze8trgl8bvbq" class="math inline">\([1,n]\)

我們設(shè)\(f_i\)表示前\(i\)個串劃分的最大答案，那么轉(zhuǎn)移顯然

\[f_i=\max\{f_{j-1}+p\times g_{i,j}-a_j(i-j+1)-b_j\}\]

把柿子化一下

\[f_i=\max\{-a_j\times i+p\times g_{j,i}+f_{j-1}+a_{j-1}(j-1)-b_j\}\]

也就是說，如果不考慮\(p\times g_{j,i}\)這一項(xiàng)的話，這就是一個以\(i\)為自變量的一次函數(shù)。若干個一次函數(shù)取最大值，直接上李超線段樹就行了

然而\(p\times g_{j,i}\)卻使這個轉(zhuǎn)移變得非常辣手……因?yàn)檫@個時候它就是一個一次函數(shù)加一個分段函數(shù)的和了

等會兒？分段函數(shù)？仔細(xì)看看啊……\(g_{i,j}\)的取值最多只有\(n\)個，而且對于一個固定的\(i\)，\(g_{i,j}\)顯然是遞減的，所以\(g_{i,j}\)可以看做一個分段函數(shù)

那么我們對于每一段分別考慮就可以了呀。我們開\(n\)棵線段樹，第\(k\)棵線段樹上記錄所有滿足\(g_{j,i}=k\)的線段

對于每一個\(i\)，預(yù)處理出所有\(g_{j,i}\)變化的位置（怎么處理待會兒會說），記\(pos_{i,j}\)表示\(g_{pos_j,i}=j\)且\(g_{pos_j+1,i}<j\)（也就是說\(g\)的值的\(j\)和\(j-1\)之間的分界點(diǎn)），那么我們把所有\(pos_{i-1,j}\)到\(pos_{i,j}\)之間的線段全都加入第\(j\)棵線段樹就行了

等會兒？你這樣會不會有點(diǎn)問題？比方說我現(xiàn)在滿足\(g_{j,i}=k\)，然后你把第\(j\)條線段加入了第\(k\)棵線段樹，那么當(dāng)你做到\(i+1\)的時候，\(g_{j,i+1}\)有可能會大于\(k\)啊？（比方說\(g_{j,i+1}=k+1\)），你線段樹上存的線段就錯掉了啊？

這種情況是不需要擔(dān)心的，首先按照我們上面的處理過程，第\(k+1\)棵線段樹也就加入這條線段。那么這兩棵線段樹里算出來的值是一樣的，只有\(p\times g_{j,i}\)不一樣。因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(p\geq 0\)，所以有\(p\times k+1\)就絕對不會用\(p\times k\)來更新答案

這樣的話，每條線段會被加入\(n\)次，總共有\(len\)條線段，總復(fù)雜度就是\(O(nlen\log len)\)

然后就是這個預(yù)處理分界點(diǎn)的問題，如果用后綴數(shù)組，直接求出\(height\)之后瞎搞就可以了。如果用\(SAM\)的話，我們對所有串建一個廣義\(SAM\)，然后把\(parent\)樹樹剖了，把所有\(n\)個串中前綴\(s[1,i]\)對應(yīng)的節(jié)點(diǎn)按\(dfs\)序排個序，那么相鄰節(jié)點(diǎn)的\(LCA\)的深度就代表這兩個串第一次相等的長度，那么在這之前它們就都是不等的了（不明白的話可以看看代碼，畫個圖理解）

然后……很多細(xì)節(jié)還是看代碼好了……

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define inf 1e18 #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } int read(char *s){R int len=0;R char ch;while(((ch=getc())>'z'||ch<'a'));for(s[++len]=ch;(ch=getc())>='a'&&ch<='z';s[++len]=ch);return s[len+1]='\0',len; } const int N=2e6+5; int ch[N][26],l[N],fa[N],pos[N],cnt=1,las; void ins(int c){int p=las,np=las=++cnt;l[np]=l[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{int q=ch[p][c];if(l[q]==l[p]+1)fa[np]=q;else{int nq=++cnt;l[nq]=l[p]+1;memcpy(ch[nq],ch[q],104);fa[nq]=fa[q],fa[q]=fa[np]=nq;for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;}} } struct eg{int v,nx;}e[N<<1];int head[N],tot; inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;} int dep[N],sz[N],son[N],top[N],dfn[N],tim; inline bool cmp(const int &x,const int &y){return dfn[x]<dfn[y];} void dfs1(int u){sz[u]=1,dep[u]=dep[fa[u]]+1;go(u){dfs1(v),sz[u]+=sz[v];sz[v]>sz[son[u]]?son[u]=v:0;} } void dfs2(int u,int t){top[u]=t,dfn[u]=++tim;if(!son[u])return;dfs2(son[u],t);go(u)if(!top[v])dfs2(v,v); } int LCA(R int u,R int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}return dep[u]<dep[v]?u:v; } struct node{node *lc,*rc;ll b,k,lv,rv;inline void ins(R ll bb,R ll kk,R int l,R int r){b=bb,k=kk,lv=k*l+b,rv=k*r+b;}inline ll calc(R int x){return k*x+b;} }pool[N<<2],*rt[N];int num; inline node *newnode(){return &pool[num++];} ll b,k,bb,kk,res;int x; void build(node* &p,int l,int r){p=newnode(),p->k=0,p->b=p->lv=p->rv=inf;if(l==r)return;int mid=(l+r)>>1;build(p->lc,l,mid),build(p->rc,mid+1,r); } void query(node *p,int l,int r){cmin(res,p->calc(x));if(l==r)return;int mid=(l+r)>>1;x<=mid?query(p->lc,l,mid):query(p->rc,mid+1,r); } void update(node *p,int l,int r){ll lv=k*l+b,rv=k*r+b;if(lv>=p->lv&&rv>=p->rv)return;if(lv<p->lv&&rv<p->rv)return p->ins(b,k,l,r),void();int mid=(l+r)>>1;double x=(b-p->b)/(p->k-k);if(lv<=p->lv){if(x<=mid)update(p->lc,l,mid);else bb=p->b,kk=p->k,p->ins(b,k,l,r),b=bb,k=kk,update(p->rc,mid+1,r);}else{if(x<=mid)bb=p->b,kk=p->k,p->ins(b,k,l,r),b=bb,k=kk,update(p->lc,l,mid);else update(p->rc,mid+1,r);} } int A[N],B[N],f[2][N];char s[N]; int n,len,p,t;ll dp[N]; int main(){ // freopen("testdata.in","r",stdin);n=read(),len=read(),p=read();fp(i,1,len)A[i]=read();fp(i,1,len)B[i]=read();fp(i,1,n){read(s);las=1;fp(j,1,len)ins(s[j]-'a'),pos[++t]=las;}fp(i,2,cnt)add(fa[i],i);dfs1(1),dfs2(1,1);fp(i,1,n)build(rt[i],1,len);for(R int i=1,t=0;i<=len;++i,t^=1){fp(j,1,n)f[t][j]=pos[(j-1)*len+i];sort(f[t]+1,f[t]+1+n,cmp);fd(j,n,2)f[t][j]=l[LCA(f[t][j],f[t][j-1])];f[t][1]=i;sort(f[t]+2,f[t]+1+n);fp(j,2,n)f[t][j]=i-f[t][j];fp(j,1,n)fp(l,f[t^1][j],f[t][j]-1){b=B[l+1]-dp[l]-1ll*l*A[l+1],k=A[l+1];update(rt[j],1,len);}dp[i]=-inf,x=i;fp(j,1,n)if(f[j]!=f[j+1])res=inf,query(rt[j],1,len),cmax(dp[i],1ll*p*j-res);}printf("%lld\n",dp[len]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bztMinamoto/p/10617941.html

總結(jié)

以上是生活随笔為你收集整理的Wannafly挑战赛29题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Python开发【第十二篇】：DOM
下一篇： Dev c++中{ }不能自动缩进