Codeforces Round 1070 (Div. 2)

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（待补）