Codeforces Round 922 (Div. 2)（A~D）补题

A题考虑贪心，要使使用的砖头越多，每块转的k应尽可能小，最小取2，最后可能多出来，多出来的就是最后一块k=3，我们一行内用到的砖头就是 m2 \frac{m}{2}2m​下取整，然后乘以行数就是答案。

#include  #define rep(i,a,b) for(int i = (a); i = (b); --i)#define ls p<<1#define rs p<<1|1#define PII pair#define ll long long#define ull unsigned long long#define db double#define endl '\n'#define debug(a) cout<<#a<<"=">n>>m;cout<<m/2*n<>t;while(t--)solve();return 0;}

B题就是猜的一个排序，$对于i,a[i]+b[i]越大我们就考虑将他往后放,有一点贪心的思想吧，如果a[i]+b[i]越大放在前面产生的逆序对可能就越多，所以我们考虑将大的往后放$
b题wa了两发，第一次是排序的时候弄反了。
第二次写排序函数的时候降序就写$<不要写<=，写了<=re了$

#include  #define rep(i,a,b) for(int i = (a); i <= (b); ++i)#define fep(i,a,b) for(int i = (a); i >= (b); --i)#define ls p<<1#define rs p<<1|1#define PII pair<int, int>#define ll long long#define ull unsigned long long#define db double#define endl '\n'#define debug(a) cout<<#a<<"="<<a<<endl;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define INF 0x3f3f3f3f #define x first#define y second//#define int long longusing namespace std;const int N=2e5+10;struct node{int a,b,sum;}kk[N];bool cmp(node t1,node t2){return t1.sum<t2.sum;}void solve(){int n;cin>>n;rep(i,1,n)cin>>kk[i].a;rep(i,1,n)cin>>kk[i].b;rep(i,1,n)kk[i].sum=kk[i].a+kk[i].b;sort(kk+1,kk+1+n,cmp);rep(i,1,n)cout<<kk[i].a<<' ';cout<<endl;rep(i,1,n)cout<<kk[i].b<<' ';cout<<endl;}signed main(){IOS//freopen("1.in", "r", stdin);int t;cin>>t;while(t--)solve();return 0;}

c题是位运算+贪心
一般1e18很可能就是$log$的算法，涉及到异或这些很可能就是要考虑每一位的影响。
这道题就是需要考虑每一位对答案的贡献，这种贡献法也是很常用的思考方式。
赛时有框架了，但是贪心的细节没考虑好没过。
大佬指导的是位运算很多时候需要考虑贪心，因为位与位之间独立。
我们考虑如果a，b两个数的二进制下第i位
当 ai= bi时无论 x 取何值这一位对答案的贡献都是 0 , 我们就然 x 的这一位为 0 因为 x 要小于 r ， x 后面会有用当a_i=b_i时无论x取何值这一位对答案的贡献都是0,我们就然x的这一位为0因为x要小于r，x后面会有用当ai​=bi​时无论x取何值这一位对答案的贡献都是0,我们就然x的这一位为0因为x要小于r，x后面会有用
当 ai≠ bi时这时看 xi= 1 是否能然答案变小，如果可以就让 xi= 1 否则就然 xi= 0当a_i\not=b_i时这时看x_i=1是否能然答案变小，如果可以就让x_i=1否则就然x_i=0当ai​=bi​时这时看xi​=1是否能然答案变小，如果可以就让xi​=1否则就然xi​=0
xi= 1 需要建立在 x < r 的前提下x_i=1需要建立在x<r的前提下xi​=1需要建立在x<r的前提下

#include  #define rep(i,a,b) for(int i = (a); i <= (b); ++i)#define fep(i,a,b) for(int i = (a); i >= (b); --i)#define ls p<<1#define rs p<<1|1#define PII pair<int, int>#define ll long long#define ull unsigned long long#define db double#define endl '\n'#define debug(a) cout<<#a<<"="<<a<<endl;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define INF 0x3f3f3f3f #define x first#define y second#define int long longusing namespace std;const int N=64;int work(int x,int i){return x&(1ll<<i);}void solve(){int a,b,r;cin>>a>>b>>r;if(a<b)swap(a,b);int ans=0;fep(i,60,0){if(work(a,i)==work(b,i))continue;if(r>=(1ll<<i)){int kk=abs(ans+(work(a,i)^(1ll<<i))-(work(b,i)^(1ll<<i)));if(kk<abs(ans)){ans=kk;r-=(1ll<<i);}elseans+=(work(a,i)^0)-(work(b,i)^0);}elseans+=(work(a,i)^0)-(work(b,i)^0);}cout<<abs(ans)<<endl;}signed main(){IOS//freopen("1.in", "r", stdin);int t;cin>>t;while(t--)solve();return 0;}

D
二分+大根堆优化dp
首先需要二分答案，在b站的一个up看的讲解b站的up讲解
这种题目就是可以通过二分答案然后变成简单的check。
接下来需要考虑如何check，由于我们删数的位置不确定，同时我们需要求的是在满足一定条件下的最优化问题，这时我们可以考虑一下dp
$f[i]表示处理好的前i个（前i个的区间间隔均<mid）$
$并且删除第i个元素，所有删除元素的和的最小值$
$考虑转移:f[i]=f[k]+a[i],其中k是满足区间和小于mid的f中的最小值$
我们可以看到枚举状态 O ( n ) ，枚举转移也需要 O ( n ) , 这样复杂度就是 O ( n2l o g n )我们可以看到枚举状态O(n)，枚举转移也需要O(n),这样复杂度就是O(n^2logn)我们可以看到枚举状态O(n)，枚举转移也需要O(n),这样复杂度就是O(n2logn)
$考虑优化可以用优先队列维护和双指针维护满足条件的区间，以及区间内的f的最小值$
$由于状态的设计所以状态需要计算到n+1,因为n有删或不删两种情况，这是一个常用的小技巧$

#include  #define int long long#define rep(i,a,b) for(int i = (a); i <= (b); ++i)#define fep(i,a,b) for(int i = (a); i >= (b); --i)#define ls p<<1#define rs p<<1|1#define PII pair<int, int>#define pll pair<long long, long long>#define ll long long#define ull unsigned long long#define db double#define endl '\n'#define debug(a) cout<<#a<<"="<<a<<endl;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define INF 0x3f3f3f3f #define x first#define y secondusing namespace std;const int N=1e5+10;int n,a[N],f[N];bool check(int x){priority_queue<pll,vector<pll>,greater<pll>>q;int l=0,ss=0;q.push({0,0});rep(i,1,n+1){while(l<i&&ss>x){ss-=a[l];l++;}while(q.size()&&q.top().y<l-1)q.pop();f[i]=q.top().x+a[i];q.push({f[i],i});ss+=a[i];}return f[n+1]<=x;}void solve(){cin>>n;rep(i,1,n)cin>>a[i];a[n+1]=0;int l=0,r=1e15;while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;elsel=mid+1;}cout<<l<<endl;rep(i,0,n+1)f[i]=0;}signed main(){IOS//freopen("1.in", "r", stdin);int t;cin>>t;while(t--)solve();return 0;}