不敲代碼的意念刷題計劃

CF504E Misha and LCP on Tree

題：給出一棵 n n n結點的樹，每個結點上有一個字符， ( x , y ) (x,y) (x,y)表示從點 x x x到點 y y y路徑上字符組成的字串，有 q q q個查詢，每個查詢給出 a , b , c , d a,b,c,d a,b,c,d，求 ( a , b ) (a,b) (a,b)和 ( c , d ) (c,d) (c,d)的最長公共前綴，( n , q ≤ 300000 n,q\le300000 n,q≤300000)，
解：定義串 s s s的哈希函式為 h s ( s ) = ∑ i = 1 n ( s i ? ′ 0 ′ + 1 ) ? b a s e i hs(s)=\sum\limits_{i=1}^n(s_i-'0'+1)*base^i hs(s)=i=1∑n?(si??′0′+1)?basei
定義 f ( x , y ) f(x,y) f(x,y)為 ( x , y ) (x,y) (x,y)的哈希值，對于每一個結點 u u u，記錄 f ( 1 , u ) f(1,u) f(1,u)和 f ( u , 1 ) f(u,1) f(u,1)，設點 s s s為 t t t的祖先，則 f ( s , t ) = ( f ( 1 , t ) ? f ( 1 , f a s ) ) ? i n v ( b a s e d e p s ? 1 ) f(s,t)=(f(1,t)-f(1,fa_s))*inv(base^{dep_s-1}) f(s,t)=(f(1,t)?f(1,fas?))?inv(basedeps??1) f ( t , s ) = f ( t , 1 ) ? b a s e d e p t ? d e p s ? f ( s , 1 ) f(t,s)=f(t,1)-base^{dep_t-dep_s}*f(s,1) f(t,s)=f(t,1)?basedept??deps??f(s,1)同時，若 s s s和 t t t互不為祖先，求出其 l c a lca lca拆分出兩條路徑并采用，仍然可用上述方法 O ( 1 ) O(1) O(1)求出哈希值，
從而，對于每個查詢，求出 l c a ( a , b ) lca(a,b) lca(a,b)和 l c a ( c , d ) lca(c,d) lca(c,d)，二分 ( a , b ) (a,b) (a,b)和 ( c , d ) (c,d) (c,d)最長公共前綴的長度，長鏈剖分求 b b b和 d d d的 k k k級祖先，判斷哈希值是否相等即可，時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)，

CF505E Mr. Kitayuta vs. Bamboos

有 n n n朵花，第 i i i朵花最初高度為 h i h_i hi?，每天晚上長高 a i a_i ai?，每天白天可以使用 k k k次魔法，魔法選擇一朵花 i i i，將其高度變為 m a x ( 0 , h i ? p ) max(0,h_i-p) max(0,hi??p)， m m m天后所有花中的最大高度最小是多少？
n ≤ 100000 ; m ≤ 5000 ; k ≤ 10 ; p , a i , h i ≤ 1 e 9 n\le100000;m\le5000;k\le10;p,a_i,h_i\le1e9 n≤100000;m≤5000;k≤10;p,ai?,hi?≤1e9

二分 m m m天后花的最大高度 H H H，判斷 m m m天后花的高度是否都 ≤ H \le H ≤H，由 h i = m a x ( 0 , h i ? p ) h_i=max(0,h_i-p) hi?=max(0,hi??p)的限制，在 h i ≤ p h_i\le p hi?≤p時，會浪費 p ? h i p-h_i p?hi?的長度，因此需要考慮盡可能少的浪費長度，
問題轉換：有 n n n朵花，第 i i i朵花最初高度為 H H H，每天白天長矮 a i a_i ai?，每天晚上可以使用 k k k次魔法，魔法選擇一朵花 i i i，將其高度增加 p p p， m m m天后花的高度是否大于 h i h_i hi?？程序中花的高度要 ≥ 0 \ge0 ≥0，每次貪心選擇最快會長矮為負數的花使用魔法長高即可，
? 過 程 中 花 的 高 度 ≥ 0 的 條 件 仍 然 充 滿 疑 問 中 ? -程序中花的高度\ge0的條件仍然充滿疑問中- ?過程中花的高度≥0的條件仍然充滿疑問中?

arc110F

給定 0 , 1 , . . . , n ? 1 0,1,...,n-1 0,1,...,n?1的排列 P 0 P 1 . . . P n ? 1 P_0P_1...P_{n-1} P0?P1?...Pn?1?，執行交換 p i p_i pi?和 p ( i + p i ) ? m o d ? n p_{(i+p_i)\bmod n} p(i+pi?)modn?最多 200000 200000 200000次，使得排列升序，
解：先不停執行 p i = 1 p_i=1 pi?=1將 0 0 0交換到位置 n ? 1 n-1 n?1，然后把 1 , 2 , . . . , n ? 1 1,2,...,n-1 1,2,...,n?1逐個交換到位置 n ? 2 , n ? 3 , . . . , 0 n-2,n-3,...,0 n?2,n?3,...,0（重復交換一個位置，總是得到不同的數，但由于 0 , 1 , 2 , . . . , x 0,1,2,...,x 0,1,2,...,x被排在交換位置的 1 x + 1 1~x+1 1 x+1步中，故當 a n ? x ? i = x a_{n-x-i}=x an?x?i?=x之前不會打亂順序），最后，將得到一個 n ? 1 , n ? 2 , . . . , 2 , 1 , 0 n-1,n-2,...,2,1,0 n?1,n?2,...,2,1,0的降序排列，此時，因為 1 1 1可以自由移動，因此對于 2 , 3 , 4 , . . . , n ? 1 2,3,4,...,n-1 2,3,4,...,n?1先把 1 1 1移動到對應要交換的位置，然后再進行交換，

arc109D

首先，把一個格子分成四塊，每一塊格子可以唯一表示一個 L L L形，

其次，觀察 L L L形的移動，一個重心可以向其周圍 7 7 7個位置移動（除了重心格子角的那邊），

于是可以將問題轉換為重心的移動，將 L L L形轉換為新棋盤中重心的坐標，觀察上述移動策略可以發現，若重心坐標為 x , y x,y x,y且 x ≠ y x\neq y x?=y，則答案為 m a x ( ∣ x ∣ , ∣ y ∣ ) max(|x|,|y|) max(∣x∣,∣y∣)，否則為 ∣ x ∣ + 1 |x|+1 ∣x∣+1，

arc109E

首先，若兩邊同色，則所有方塊顏色必然相同，
其次，若 [ 1 , L ] [1,L] [1,L]為白色， [ R , n ] [R,n] [R,n]為黑色，當 s ? L < R ? s s-L<R-s s?L<R?s，則 [ 1 , R ? 1 ] [1,R-1] [1,R?1]為白色， [ R , n ] [R,n] [R,n]為黑色，方法是后手一直往 [ 1 , L ] [1,L] [1,L]方向跑，而先手距離 [ R , n ] [R,n] [R,n]之間必然有白色方塊，反之，當 [ s ? L ≥ R ? s ] [s-L\ge R-s] [s?L≥R?s]，則 [ 1 , L ] [1,L] [1,L]最終為白色， [ L + 1 , n ] [L+1,n] [L+1,n]最終為黑色，當 [ 1 , L ] [1,L] [1,L]為黑色， [ R , n ] [R,n] [R,n]為白色亦然，
特別地，當 s ? L ≠ R ? s s-L\neq R-s s?L?=R?s，將顏色取反具有對稱性，黑白數量相等，
當 s ? L = R ? s s-L=R-s s?L=R?s，由于黑色先手，當 [ 1 , L ] [1,L] [1,L]白( [ R , n ] [R,n] [R,n]黑)，則 [ 1 , L ] [1,L] [1,L]白， [ L + 1 , n ] [L+1,n] [L+1,n]黑)；當 [ 1 , L ] [1,L] [1,L]黑( [ R , n ] [R,n] [R,n]白)， [ 1 , R ? 1 ] [1,R-1] [1,R?1]黑， [ R , n ] [R,n] [R,n]白，這部分單獨處理即可，
這部分列舉 s s s的位置，其方案數為 ∑ i = 1 s ? i > 1 , s + i < n 2 2 i \sum\limits_{i=1}^{s-i>1,s+i<n}2^{2i} i=1∑s?i>1,s+i<n?22i，其黑色染色數量為 ∑ i = 1 s ? i > 1 , s + i < n 2 2 i ? 1 ? ( n ? ( s ? i ? 1 ) + s + i = n + 2 ? i + 1 ) = ( ( n + 1 ) ? ∑ i = 1 s ? i > 1 , s + i < n 2 2 i ? 1 ) + ( ∑ i = 1 s ? i > 1 , s + i < n 2 2 i ? i ) \sum\limits_{i=1}^{s-i>1,s+i<n}2^{2i-1}*(n-(s-i-1)+s+i=n+2*i+1)\\ =((n+1)*\sum\limits_{i=1}^{s-i>1,s+i<n}2^{2i-1})+(\sum\limits_{i=1}^{s-i>1,s+i<n}2^{2i}*i) i=1∑s?i>1,s+i<n?22i?1?(n?(s?i?1)+s+i=n+2?i+1)=((n+1)?i=1∑s?i>1,s+i<n?22i?1)+(i=1∑s?i>1,s+i<n?22i?i)
該式子可以通過前綴和計算，時間復雜度 O ( n ) O(n) O(n)，

#include<bits/stdc++.h>//寫個代碼驗證答案
using namespace std;
const int N=2e5+5,mod=998244353;
typedef long long ll;
int n;
ll f1[N],f2[N],f3[N];
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
int main()
{
    scanf("%d",&n);
    if(n==1) printf("%d\n",qpow(2,mod-2));
    else
    {
        ll sum=qpow(2,n),isum=qpow(sum,mod-2);
        for(int i=1;i<N;i++)
        {
            f1[i]=(f1[i-1]+qpow(2,2*i))%mod;
            f2[i]=(f2[i-1]+qpow(2,2*i-1))%mod;
            f3[i]=(f3[i-1]+i*qpow(2,2*i)%mod)%mod;
        }
        for(int s=1;s<=n;s++)
        {
            if(s==1||s==2||s==n-1||s==n)
            {
                printf("%lld\n",1ll*n*(mod-mod/2)%mod);
                continue;
            }
            int k=min(s-2,n-s-1);//1<=i<=k
            ll ans=1ll*(sum+mod-f1[k])%mod*n%mod*isum%mod*(mod-mod/2)%mod;
            ans=(ans+(f2[k]*(n+1)%mod+f3[k])%mod*isum%mod)%mod;
            printf("%lld\n",ans);
        }
    }
}

arc108F

設直徑長度為 d d d，
首先，若存在兩條及以上的直徑，由鴿巢原理必有直徑的兩個端點被染成同色，答案是 d ? 2 n d*2^n d?2n，
否則，不妨令直徑序列為 a 1 , a 2 , . . . , a k a_1,a_2,...,a_k a1?,a2?,...,ak?，若 a 1 a_1 a1?和 a k a_k ak?同色，則答案是 d d d，否則只考慮 a 1 a_1 a1?白色， a k a_k ak?黑色的情況(最后答案乘 2 2 2即可)：
1.若 a 2 a_2 a2?為黑或 a k ? 1 a_{k-1} ak?1?為白，則答案一定是 d ? 1 d-1 d?1，
2.若存在 ( a 2 , a k ) (a_2,a_k) (a2?,ak?)和 a 1 , a k ? 1 a_1,a_{k-1} a1?,ak?1?之外其它長度為 d ? 1 d-1 d?1的路徑答案是 d ? 1 d-1 d?1，
3.不存在其它路徑且 a 2 a_2 a2?染成白色， a k ? 1 a_{k-1} ak?1?染成黑色，接續考慮 a 3 , a k ? 2 a_3,a_{k-2} a3?,ak?2?，依此類推，直到最后直徑上剩余一個結點或不剩余結點為止，

arc108E

加入 0 , n + 1 0,n+1 0,n+1兩個位置，令 f ( l , r ) f(l,r) f(l,r)表示 [ l + 1 , r ? 1 ] [l+1,r-1] [l+1,r?1]中首項 > l >l >l，末項 < r <r <r的子序列的期望長度，轉移方程為 f ( l , r ) = 1 + ∑ i = 1 k ( f ( l , s i ) + f ( s i , r ) ) / k f(l,r)=1+\sum\limits_{i=1}^k(f(l,s_i)+f(s_i,r))/k f(l,r)=1+i=1∑k?(f(l,si?)+f(si?,r))/k其中 l < s i , a s i < r l<s_i,a_{s_i}<r l<si?,asi??<r，線段樹優化即可，巧妙之處在于擴展 0 , n + 1 0,n+1 0,n+1，使得 s i , a s i s_i,a_{s_i} si?,asi??的范圍變得一致，且期望 D P DP DP具有可加性質，