Dashboard - Codeforces Round 1070 (Div. 2) - Codeforces

題目偏思維，前3道題沒有算法

B

 問題是有一個01環，你需要順時針移動環，每一位相當於是按位或 | 

問你最多需要順時針轉多少格子，不難考慮到如果1000，你需要3步11000也是三步

實際上就是求最連續0序列

C

 給你了n個數字，有k個操作，每一個操作加入一個新的數字到你的揹包裏（揹包初始是0），如果揹包內容為偶數，揹包清零

要求你輸出1-k此操作中每個操作數的最大答案

很顯然需要分奇數偶數去考慮

比如k=1，ans=Max_odd, 

　    k=2,  ans=Max_odd+Max_even ,

　　 k=3, ans=Max_odd+Max_even+Max2_even

就是先上一個奇數（如果有的話），然後一直累加偶數（這樣能保證bag不被清零）

偶數用完之後操作奇數

考慮到如果在k-1次操作上加上一個奇數必然答案會清零

所以我們考慮在k-2次操作上進行，我們把兩個奇數和為一個偶數然後讓這兩個奇數同歸於盡（當然這個作廢的奇數越小越好）

所以Ans_k=Ans_(k-2)+(odd+odd)*0 ，這裏乘零是因為方便閲讀他會作廢的相當於沒有，得出結論Ans_k=Ans_(k-2)

然後提交發現會WA，發現一種情況，當奇數的個數位偶數的時候，也就是把所有數都加在一起沒有辦法不等於0，因為你無法配對奇數使得最後餘下一個奇數，完成

void solve(){
    int n;
    cin>>n;
    vector<int>odd,even,dp(n+2,0);
    for(int i=0;i<n;i++){
        int u;cin>>u;
        if(u&1)odd.push_back(u);
        else even.push_back(u);
    }
    sort(all(even),greater<int>());
    sort(all(odd),greater<int>());
    if(odd.size()==0){
        for(int i=0;i<n;i++)cout<<0<<" ";
        cout<<endl;
        return ;
    }
    dp[1]=odd[0];
    int l=2;
    for(int i=0;i<even.size();i++){
        l++;
        dp[2+i]=dp[1+i]+even[i];
    }
    if(l<=n){
        for(;l<=n;l++){
            dp[l]=dp[l-2];
        }
        if(odd.size()%2==0)dp[n]=0;
    }
    for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
    cout<<endl;
    return ;
}

代碼有點屎

D

一個圖狀DP，賽事一直在推轉移方程，也沒有想到什麼好的遍歷方法，感覺難度在1600左右，如果前三個題壓到30min完成的話，興許運氣好可以A掉

學習之後解決

因為這個斐波那契數列是一個單調遞增的數列（前兩項除外）所以我們可以單調的從小查找到大節點

設當前處理的邊為u，v節點，我們假設v是這些數列的最後一位，u是倒數第二位，它有一個自己本身的斐波那契外還有一些數列

這些數列與u相連，我們假設這個節點為fa，則有w[v]=w[u]+w[fa]這樣的等式存在，所以我們就去找是否有一個fa節點與u相連而且值為w[v]-w[u]

所以説我們當前處理的這條{u，v}邊的價值就是1+Σfa節點的價值

這樣一來我們考慮如何構造動態轉移過程

我們可以設dp[u][k]為到u為最後節點，而且u前面那一個節點的大小為k的價值（斐波那契數組個數）

這樣一來就可以根據不同的k與w[u]進行組合組成多種預期下一個節點的數字

同理我們知道了w[u],w[v]之後也可以通過dp[u][w[v]-w[u]]來查詢有多少個fa節點符合可以和邊{u，v}拼接

回到最開始我們要對邊進行大小排序來保證小節點一定在大節點之前處理完成，這樣才能保證在處理當前{u，v}的時候不會漏掉fa節點

我們只需要記錄Σans(u,v)即可知道總的答案

void solve(){
    int n,m;cin>>n>>m;
    vector<int>w(n+1);
    vector<pii>Edge;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        Edge.push_back({u,v});
    }
    sort(all(Edge),[&](pii a,pii b){
        return w[a.second]<w[b.second];
    });
    int ans=0;
    vector<map<int,int>>dp(n+1);
    for(auto it:Edge){
        int u=it.first,v=it.second;
        int temp=(1+dp[u][w[v]-w[u]])%M;
        ans=(ans+temp)%M;
        dp[v][w[u]]=(temp+dp[v][w[u]])%M;
    }
    cout<<ans<<"\n";
    return ;
}

E（待補）