Silverwolfnya

2025/9/25

abc416_f

題意：樹上選\(k\)條不相交的鏈，使得其貢獻和最大.

可以考慮樹形\(dp\).

考慮狀態(tài)的設(shè)計如下：設(shè)\(dp_{u,i,0/1/2}\)表示當前選了以\(u\)為根的子樹，且當前子樹的根節(jié)點的狀態(tài)為\(0/1/2\)的最大子樹貢獻.

\(0:\)所選的子樹不在任何一條鏈中
\(1:\)所選的子樹留了向上轉(zhuǎn)移的接口，可以作為一條鏈向上拼接
\(2:\)所選的子樹不留向上轉(zhuǎn)移的接口，不能作為鏈向上拼接

可以以樹形背包的方式去做轉(zhuǎn)移。

首先根據(jù)定義可以得到這樣的轉(zhuǎn)移：

\(dp_{u,i+j,0}\leftarrow max(dp_{u,i,0}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)
\(dp_{u,i+j,1}\leftarrow max(dp_{u,i,1}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)
\(dp_{u,i+j,2}\leftarrow max(dp_{u,i,2}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)

考慮拼出一條留接口的鏈的轉(zhuǎn)移：

\(dp_{u,i+j,1}\leftarrow max(dp_{u,i,0}+dp_{v,j,1}+a_u)\)

同理，考慮不留接口的向上轉(zhuǎn)移，值得注意的是，你把\(u\)節(jié)點同時接入兩條邊，會讓鏈數(shù)減\(1\)，故轉(zhuǎn)移方程如下：

\(dp_{u,i+j-1,2}\leftarrow max(dp_{u,i,1}+dp_{v,j,1})\)

注意保證\(dp\)的無后效性，可以用滾動數(shù)組處理一下.

時間復雜度\(O(nk^2)\).

9.26

感覺一整天都在想這一道題來著

CF2150C

首先比較套路地，把\(\text{Bob}\)的序列處理成\([1,2,3...n]\)，同步更新\(Alice\)的序列和值域序列。

模擬一下兩人取數(shù)的過程，你發(fā)現(xiàn)，當?shù)?span id="w0obha2h00" class="math inline">\(i\)個位置的\(a_i\)被\(\text{Bob}\)取走后，那么滿足如下條件的，\(Alice\)一定無法取得：\(j>i\and a_j<a_i\).

不妨設(shè)計\(dp_{i,j}\)表示當前考慮到了第\(i\)個位置，且被\(Bob\)取走的最大值，即\(\text{Alice}\)放棄的最大值，此時\(\text{Alice}\)取數(shù)能取的最大貢獻.

設(shè)計推表轉(zhuǎn)移，可以大致分為四種情況：

\(a_i<j\)選\(a_i\)，由上面得到的性質(zhì)，這部分是不合法的，所以不做轉(zhuǎn)移
\(a_i<j\)不選\(a_i\)，\(dp_{i-1,j}\rightarrow dp_{i,j}\)
\(a_i>j\)選\(a_i\)，\(dp_{i-1,j}+w_{a_i}\rightarrow dp_{i,j}\)
\(a_i>j\)不選\(a_i\)，\(max(dp_{i-1,j}+w_{a_i})\rightarrow dp_{i,a_i}\)

這樣暴力轉(zhuǎn)移是\(O(n^2)\)的.

但是，你發(fā)現(xiàn)轉(zhuǎn)移分為了三段區(qū)間，\([0,a_i),a_i,(a_i,n]\)，由上述轉(zhuǎn)移可以發(fā)現(xiàn)，實際上就是對\([0,a_i)\)做區(qū)間加，對\(a_i\)做覆蓋，對\((a_i,n]\)保持不變，所以可以維護一顆線段樹，維護區(qū)間最值以及區(qū)間加輔助轉(zhuǎn)移。

這樣可以將時間復雜度優(yōu)化到\(O(n\log n)\).

洗完澡補了一下網(wǎng)絡(luò)賽的題

25CCPC網(wǎng)絡(luò)賽C

首先問題可以直接轉(zhuǎn)化成，進行\(n-1\)輪的連邊，每次連邊的代價是\((a_u+a_v)\% k\),問最小代價，因此把每個點的權(quán)值由\(a_i\)處理成\(a_i\% k\).

這是稠密圖的最小生成樹問題，我們可以用類似\(\text{Prim}\)算法的方式解決，首先考慮樸素版的算法，也就是每次枚舉當前聯(lián)通塊，找到與當前聯(lián)通塊內(nèi)最小的邊權(quán)并加入.

本題有完全圖的特殊性，而且所有邊權(quán)都是可以計算得到的，對于某個點的延伸，要加入的邊權(quán)，一定是當前與它沒有聯(lián)通的點中邊權(quán)最小的那個，這樣貪心是不會劣的，最小的邊權(quán)的確定可以二分找第一個\(\geq k-a_u\)的位置,如沒找到就加入第一個點.

我們用一個\(\text{set}\)維護當前還沒有被加入大聯(lián)通塊的點，每次向大聯(lián)通塊中加入新的點時，按以上規(guī)則更新新邊，這樣的操作一共會進行\(n-1\)輪.

因此，我們得到\(O(n\log n)\)的做法.

2025/9/27

今天主要是和隊友\(\text{vp}\).

晚上寫\(\text{abc}\)狀態(tài)前所未有的差.

abc_425f

考慮一個顯然的狀壓\(dp\)如：\(dp_{i,sta}\)表示當前考慮到了第\(i\)個被放入的字符串，且當前選入的字符的二進制狀態(tài)為\(sta\).

轉(zhuǎn)移的時候，我們只要枚舉當前狀態(tài)從哪里轉(zhuǎn)移過來，如果多個轉(zhuǎn)移進入的狀態(tài)的哈希值是相同的，只記一個就好了，那我們可以預處理\(2^n\)種不同的子序列的哈希值，然后開桶去重即可，不作任何優(yōu)化，時間復雜度是\(O(n^2 2^n)\)的.

我認為本題的優(yōu)化是挺啟發(fā)式的，優(yōu)化如下：

枚舉了第\(i\)個被放入的狀態(tài)時，有效的狀態(tài)一定滿足其二進制位恰好是\(i\)位，故我們可以按二進制編碼的位數(shù)從小排序，然后雙指針.
在轉(zhuǎn)移的時候，我們只需要枚舉當前狀態(tài)所有二進制下的\(1\)位,可以用\(\text{lowbit}\)優(yōu)化.

計算一下復雜度：
\((2^1+2^2+.....2^n)n=O(n2^{n+1})\).

常數(shù)很大，卡了過去，不知道是不是評測機波動.

代碼實現(xiàn)如下.

/*
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神獸保佑,代碼無bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<bitset>
#include<cstring>
#include<queue>
#include<iomanip>
#define mt make_tuple
//cout << setprecision(3) ; //輸出3位小數(shù)，3.142
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll=long long;
using i128=__int128;
typedef pair<int,int>pii;
typedef tuple<int,int,int>ti3;
const int N=3e5+10;
//讀錯題了，傻逼，你是人嗎
//可以任意插 顯然有類似狀壓dp的做法
//998244353
struct Hash{
private:
const int base=1331;//具體使用可以修改成雙模或雙base防止hack
const i128 mod=100000000000000049;
i128 mo(i128 x){
    return (x%mod+mod)%mod;
}
public:
    int n;//長度
    i128 s=0;
    Hash(){}
    Hash(string str){//傳入的參數(shù)不需要前面加空格，正常輸入即可
        n=str.length();
        for(int i=1;i<=n;i++){
            s=mo(s*base+(str[i-1]-'a'+1))%mod;//這里具體問題記得修改
        }
    }
    ll get(){
        return s;
    }
};
const int mod=998244353;
int lowbit(int x){
    return x&-x;
}
void Silverwolf(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int>hash(1<<n,-1);
    vector<int>lsh;
    for(int sta=1;sta<(1<<n);sta++){
        string su;
        for(int i=0;i<n;i++){
            if(sta>>i&1){
                su.pb(s[i]);
            }
        }
        hash[sta]=Hash(su).get();
        lsh.pb(hash[sta]);
    }
    lsh.pb(-1);
    lsh.pb(-2);
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    for(int sta=0;sta<(1<<n);sta++){
        hash[sta]=lower_bound(lsh.begin(),lsh.end(),hash[sta])-lsh.begin();
    }
    vector<int>bit;
    for(int i=0;i<(1<<n);i++)bit.pb(i);
    sort(bit.begin(),bit.end(),[&](int x,int y){
        return __builtin_popcount(x)<__builtin_popcount(y);
    });
    vector<int>dp(1<<n,0);
    dp[0]=1;
    vector<bool>vis(1<<(n+1),false);
    int l=1;
    for(int i=1;i<=n;i++){
        for(int j=l;j<(1<<n);j++){
            l=j;
            int sta=bit[j];
            if(__builtin_popcount(sta)>i)break;
            for(int j=sta,k;j;j-=1<<k){
                k=__lg(j);
                if(!(sta>>k&1))continue;
                int nsta=sta^(1<<k);
                if(!vis[hash[nsta]]){
                    dp[sta]=(dp[sta]+dp[nsta])%mod;
                    vis[hash[nsta]]=true;
                }
            }
             for(int j=sta,k;j;j-=1<<k){
                k=__lg(j);
                if(!(sta>>k&1))continue;
                int nsta=sta^(1<<k);
                vis[hash[nsta]]=false;
            }
        }
    }
    cout<<dp[(1<<n)-1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int T;cin>>T;while(T--)
    Silverwolf();
    //愿艾利歐三度為你窺見，令你的生命永不停歇，駭入永遠成功，游戲永遠勝利。
    //游戲就只是為了游戲，僅此而已
    //acm這種東西，三兩下搞定就好啦
    return 0;
}

[2024ICPC沈陽M]

賽時出的思路很快，但是最后沒想出判非\(0\)環(huán)的方法.

考慮由\(a\% n\)向\((a+b)\% n\) 建邊，若能為無窮集當且僅當出現(xiàn)了非\(0\)權(quán)環(huán)，或當前點能夠指向非\(0\)權(quán)環(huán).

不妨縮點后跑\(dp\)，那么現(xiàn)在問題瓶頸只在于判定\(0\)權(quán)環(huán)，我們考慮對于強連通分量內(nèi)的點\(\text{bfs}\)，如果出現(xiàn)了沖突，則說明有非\(0\)權(quán)值的環(huán)。

時間復雜度\(O(n+m+q)\)，感覺代碼實現(xiàn)的很丑。

#include<bits/stdc++.h>
//#define int long long 
#define pb push_back
#define mt make_tuple
#define fi first 
#define se second
using ll=long long;
const int N=5e5+3;
using namespace std;
typedef pair<int,int>pii;
typedef pair<string,int>psi;
typedef tuple<int,int,int>ti3;
class Tarjan{
    public:
    int n,idx,top;
    vector<int> dfn,low,col,into;
    vector<ti3> edg;
    vector<vector<int>> e;
    vector<vector<int>> scc;
    vector<vector<pii>>scc2;//把環(huán)上的邊記錄下來
    vector<int> stk;
    bitset<N>in;
    vector<int>tag;//標記某些位置為1
    vector<int>dp;
    //vector<int>cnt_edge;//一個聯(lián)通塊中的邊的數(shù)量
    //vector<int>cnt_point;
    ll ans=1;
    Tarjan(int n):n(n){
        idx=0,top=0;
        e.resize(n+1);
        scc.resize(n+1);
        scc2.resize(n+1);
        dfn.assign(n+1,0);
        low.assign(n+1,0);
        col.assign(n+1,0);
        into.assign(n+1,0);
        stk.assign(n+1,0);
        //in.assign(n+1,0);
        tag.assign(n+1,0);
        dp.assign(n+1,0);
        //cnt_edge.assign(n+1,0);
        //cnt_point.assign(n+1,0);
    }
    void add(int u,int v,int w){
        e[u].pb(v);
        edg.pb(mt(u,v,w));
    }
    void tarjan(){
        for(int i=0;i<n;++i){
            if(!dfn[i])
                tarjan(i);
        }
    }
    void tarjan(int u){
        dfn[u]=low[u]=++idx;
        stk[++top]=u;
        in[u]=true;
        for(int &v:e[u]){
            if(!dfn[v])
                tarjan(v),low[u]=min(low[u],low[v]);
            else
                if(in[v])
                    low[u]=min(low[u],dfn[v]);
        }

        if(dfn[u]==low[u]){
            while(stk[top]!=u){
                in[stk[top]]=false;
                col[stk[top--]]=u;
                //cnt_point[u]++;
            }
            col[stk[top]]=u;
            //cnt_point[u]++;
            in[stk[top--]]=false;
        }
    }
    void check_cir(){
        vector<bool>vis(n+1,false);//bfs 一下
        vector<ll>dis(n+1,0);
        auto bfs=[&](int u)->bool{//判是否有非零環(huán)
            queue<int>q;
            q.push(u);
            vis[u]=true;
            while(q.size()){
                //assert(q.size()<5e7);
                auto now=q.front();
                q.pop();
                for(auto &[v,w]:scc2[now]){
                    if(!vis[v]){
                        vis[v]=true;
                        q.push(v);
                        dis[v]=dis[now]+w;
                    }else{
                        if(dis[now]+w!=dis[v]){
                            return true;
                        }
                    }
                }
            }
            return false;
        };
        for(int i=0;i<n;i++){
            if(col[i]==i){
                bool ok=bfs(i);
                if(ok)tag[i]=1;
            }
        }

    }
    void get_scc(){
        for(auto &[u,v,w]:edg){
            // cout<<col[u]<<' '<<col[v]<<'\n';
            if(col[u]==col[v]){
                // tag[col[u]]+=w;
                scc2[u].pb({v,w});
                // scc2[v].pb({u,w});
                //cnt_edge[col[u]]++;
            }
            else{
                scc[col[v]].pb(col[u]);//建反邊
                into[col[u]]++;
            }
        }
       
        
    }
    void DP(){
        queue<int>q;
        for(int i=0;i<n;i++){
            if(col[i]==i&&into[i]==0)q.push(i);
        }
        while(q.size()){
            //assert(q.size()<5e7);
            auto u=q.front();
            q.pop();
            dp[u]=max(dp[u],tag[u]);
            for(int v:scc[u]){
                dp[v]=max(dp[v],dp[u]);
                if(--into[v]==0)q.push(v);
            }
        }
    }
    void work(){
        tarjan();
        get_scc();
        check_cir();
        DP();
        // for(int i=0;i<n;i++)cout<<cnt[i]<<' ';cout<<"\n";
        // for(int i=0;i<n;i++)cout<<col[i]<<' ';cout<<'\n';
        // for(int i=0;i<n;i++)cout<<tag[i]<<' ';cout<<"\n";
        // for(int i=0;i<n;i++)cout<<dp[i]<<' ';cout<<"\n";
    }
};

int get(int x,int m){
    return (x%m+m)%m;
}
void Silverwolf(){
    int n,m,q;
    cin>>n>>m>>q;
    Tarjan ta(n);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(b==0)continue;
        int u=get(a,n);
        int v=get(a+b,n);
        // cout<<u<<' '<<v<<"\n";
        ta.add(u,v,b);
        
    }
    ta.work();
    for(int i=1;i<=q;i++){
        int u;cin>>u;
        u=get(u,n);
        if(ta.dp[ta.col[u]])cout<<"Yes\n";
        else cout<<"No\n";
    }
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}

2025/9/29

2024杭州站M

首先轉(zhuǎn)化一下問題.

對于每個區(qū)間\([l,r]\)，設(shè)最小值的位置在\(pos\)，都滿足\((a_{pos+k})|(a_j+k)[l\leq j\leq r ]\)成立.

每個區(qū)間都當且僅與最小值有關(guān)，考慮值域分治，每次首先找到最小值的位置\(pos\)，并劃分其統(tǒng)轄區(qū)間\([l,r]\).

上述式子可以做一個如下等價：

\[gcd(a_l+k,a_{l+1}+k+,....,a_r+k)=\\gcd(a_{l+1}-a_{l},a_{l+2}-a_{l+1},....,a_{r}-a_{r-1},a_{pos}+k)=\\a_{pos}+k \]

即\(a_{pos}+k\)必須是\(gcd(a_{l+1}-a_{l},a_{l+2}-a_{l+1},....,a_{r}-a_{r-1})\)的因子

遞歸上述過程，可以用笛卡樹實現(xiàn)，用\(ST\)表快速維護區(qū)間內(nèi)的\(\text{gcd}\)即可.

時間復雜度為\(O(n\log n\log A+nd(A))\)，其中\(d(x)\)表示因子數(shù)量.

代碼實現(xiàn)的真的非常丑。板子抄錯猛猛\(\text{WA}\).

#include<bits/stdc++.h>
#define mt make_tuple
#define fi first
#define se second
using ll=long long;
using namespace std;
typedef pair<int,int>pii;
typedef tuple<int,int,int>ti3;
//最值分治聽起來挺有道理的
//最值分治+區(qū)間gcd 之類的東西
template<class T>
class ST{
public:
    vector<vector<T>>gd;
    vector<T>a;
    vector<int>lg2;
    int n;
    ST(int n,vector<T>a):n(n),a(a){
        gd.assign(20,vector<T>(n+1,0));
        // mn.assign(20,vector<T>(n+1,0));
        lg2.assign(n+1,-1);
        for(int i=1;i<=n;i++)lg2[i]=lg2[i/2]+1;
        int k=lg2[n];
        for(int i=0;i<=n;i++){
            gd[0][i]=gd[0][i]=a[i];
        }
        for(int j=1;j<=k;j++){
            for(int i=0;i<=n-(1<<j)+1;i++){
                gd[j][i]=__gcd(gd[j-1][i],gd[j-1][i+(1<<(j-1))]);
            }
        }
    }
    T Gcd(int l,int r){
        int k=lg2[r-l+1];
        return __gcd(gd[k][l],gd[k][r-(1<<k)+1]);
    }
};
const int inf=1e9+7;
class CatlanTree{//笛卡爾樹板子 默認以最小值為根
public:
    vector<int>p,fa;
    vector<vector<int>>ch;
    int n,root,k;
    CatlanTree(){
        cin>>n>>k;
        p.resize(n+1);
        fa.assign(n+1,0);
        ch.assign(n+1,vector<int>(2,0));
        for(int i=1;i<=n;i++)cin>>p[i];
        vector<int>stk(n+2);
        int top=0;
        for(int i=1;i<=n;i++){
            int lst=0;
            while(top&&p[stk[top]]>=p[i]){
                lst=stk[top];
                top--;
                
            }
            if(top){
                fa[i]=stk[top];
                ch[stk[top]][1]=i;
            }
            if(lst){
                ch[i][0]=lst;
                fa[lst]=i;
            }
            stk[++top]=i;
        }
        for(int i=1;i<=n;i++)if(fa[i]==0)root=i;
    }
    void work(){
        vector<int>cha(n+1,0);
        set<int>val;
        for(int i=2;i<=n;i++)cha[i]=abs(p[i]-p[i-1]);
        ST<int> st(n,cha);
        bool ok=true;
        auto dfs=[&](auto &&dfs,int u)->ti3{
            if(u==0)return mt(n,0,0);
            auto [l1,r1,mn1]=dfs(dfs,ch[u][0]);
            auto [l2,r2,mn2]=dfs(dfs,ch[u][1]);
            int l=min({l1,l2,u});
            int r=max({r1,r2,u});
            int len=r-l+1;
            if(len!=1){
                int gcd=st.Gcd(l+1,r);
                //枚舉gcd的因子吧，感覺
                int mn=p[u];
                if((mn1==0||mn==mn1)&&(mn==mn2||mn2==0)){
                    return {l,r,p[u]};
                }
                if(ok){
                    //枚舉因子
                    for(int x=1;x<=gcd/x;x++){
                        if(gcd%x==0){
                            if(x-mn>0)val.insert(x-mn);
                            if(gcd/x-mn>0)val.insert(gcd/x-mn);
                        }
                    }
                    ok=false;
                }
                vector<int>del;//待刪除對象
                for(auto x:val){
                    if(__gcd(gcd,mn+x)!=mn+x)del.push_back(x);
                }
                for(auto d:del)val.erase(d);
                
            }
            return {l,r,p[u]};
        };
        
        dfs(dfs,root);
        ll ans=0,cnt=0;
        int mn=*min_element(p.begin()+1,p.end());
        int mx=*max_element(p.begin()+1,p.end());
        if(ok){
            //特判全相等
            cnt=k;
            ans=1ll*k*(k+1)/2;
        }
        for(auto x:val){
            if(x<=k){
                cnt++;
                ans+=x;
            }
        }
        cout<<cnt<<' '<<ans<<'\n';

    }
};
void Silverwolf(){
    CatlanTree tr;
    tr.work();
    // int n,k;
    // cin>>n>>k;
    // vector<int>a(n+1,0);
    // for(int i=1;i<=n;i++)cin>>a[i];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;while(T--)
    Silverwolf();
    return 0;
}

首先，將\(a_i>a_{i+1}\)的位置標記成\(1\)，其中\(1\leq i<n\)，發(fā)現(xiàn)任意一個段中除了段尾可以被標記成\(1\)，其他位置都不能被標記成\(1\)，注意對于每個\(k\)，其段尾的位置一定是\(k,2k,3k....\lfloor\frac{n}{k}\rfloor k\)，因此，對于一個被標記為\(1\)的位置\(p\)，其可能合法的位置有且僅有\(p\)的因子，若有很多這樣的位置，維護出其\(\text{gcd}\)后枚舉因子即可.

動態(tài)維護\(gcd\)，用線段樹維護，時間復雜度\(O(q\log n)\).

枚舉因子\(O(q\sqrt n)\).

到這里本題也已經(jīng)可以通過了.

可以歐拉篩優(yōu)化一下，這樣復雜度就是\(O(q\log n)\)了.

今天還零零散散寫了幾道題，感覺比較水，不想寫題解了（

posted on 2025-09-26 00:11 __Silverwolf 閱讀(23) 評論(0) 收藏舉報

刷新頁面返回頂部