当前位置：首页 > news >正文

Codeforces Round 1070 (Div. 2)

news 2026/3/27 1:11:44

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

题目偏思维，前3道题没有算法

问题是有一个01环，你需要顺时针移动环，每一位相当于是按位或 |

问你最多需要顺时针转多少格子，不难考虑到如果1000，你需要3步11000也是三步

实际上就是求最连续0序列

给你了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 ;
}