学习笔记13：Codeforces Round 920 (Div. 3)

会赢的。

B

结合样例想清楚有几种情况就比较好写，一下称 原来数组为a ，结果数组为b

1.a中所有1的位置，b都是1

? ? ? ? 1.1 b数组中还有额外的1,但是同样位置的a数组是0，这时需要额外添加操作3

? ? ? ? 1.2 b中没有额外的1，不需要操作

2.a中的1的位置b却是0

? ? ? ? 显然需要优先使用掉这些a是1，b是0的位置，把1尝试转移到b是1,但a是0的位置

????????（1次换的操作一定是优于一次添加+一次移除的）

? ? ? ? 尽可能使用完这些不一样的位置时候有三种情况

·? ? ? ? 2.1 ab数组相等了

? ? ? ? ?2.2 a数组还有多余的1，需要移除

? ? ? ? ?2.3 b数组还有多余的1，需要添加

3.不是前两种情况时，a中0的位置 ，b却是1

????????直接添加

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <set>

using namespace std;
#define int long long
const int N = 1000010;
char a[N],b[N];
int n,m,k;
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int d=0;
    int s=0;
    for(int i=1;i<=n;i++){
         cin>>b[i];
         if(a[i]=='1' && b[i]=='0') d++;
         if(b[i]=='1' && a[i]=='0') s++;
    }
    if(d==s) cout<<d<<endl;
    else{
        if(d){
            if(d<s)cout<<d+abs(d-s)<<endl;
            else cout<<s+abs(d-s)<<endl;
            
        }else{
            cout<<s<<endl;
        }
    }


    
}
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

C

分析：一旦在两个需要用的时间点选择关机，那么一定是在前一个点用完立马关掉

只需要和一直开机的耗电量作比较即可，每一个间隔的选择都不影响下一次间隔（除非最优解电也不够用）。每一次间隔都是最优解，局部最优解得出全局最优解。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <set>

using namespace std;
#define int long long
const int N = 1000010;
int a[N],b[N];
int n,m,k;
void solve(){
    int n,f,aa,b;
    cin>>n>>f>>aa>>b;
    int ff=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if((a[i]-a[i-1])*aa>=b){
            f-=b;
        }else{
            f-=(a[i]-a[i-1])*aa;
        }
        if(ff)continue;
        if(f<=0 ){
            cout<<"NO"<<endl;
            ff=1;
        }
    } 
    
    if(!ff)cout<<"YES"<<endl;


    
}
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

D

用a数组的最小和b数组的最大，和a数组的最大和b数组的最小比较，取最大值，然后把两个数去除。

#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<map>
#include<deque>
using namespace std;
#define int long long
const int N = 1000010;
int a[N];

void solve(){
    int n,m;
    cin>>n>>m;
    int x;
    deque<int>q1,q2;
    for(int i=1;i<=n;i++){
        cin>>x;
        q1.push_back(x);
    }
    for(int i=1;i<=m;i++){
        cin>>x;
        q2.push_back(x);
    }
    sort(q1.begin(),q1.end());
    sort(q2.begin(),q2.end());
    int ans=0;
    for(int i=1;i<=n;i++){
        if(abs(q1.front()-q2.back()) > abs(q1.back()-q2.front())){
           ans+= abs(q1.front()-q2.back());
           q1.pop_front();
           q2.pop_back();
        }else{
            ans+= abs(q1.back()-q2.front());
           q1.pop_back();
           q2.pop_front();
        }
    }
    cout<<ans<<endl;
    
    
    
    
}
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

E

博弈论

Alice 和 Bob 的爱恨情仇

分析：已知Alice和Bob的坐标，每个人的操作其实可以看成? ? 纵坐标-1 横坐标（-1，0，+1）

所以其实两点纵坐标相遇的时间点我们是知道的（如果Alice在Bob下面或同一横坐标，那么一定是平局)，abs(Alice y-Bob y)?这是纵坐标距离，如果是奇数，Alice才有取胜的可能，,如果是偶数，Bob才有赢的可能，然后我们直接算出在最后一步时，可能取胜方能到的横坐标是否能完全包含另一方即可，如果不能包含，取胜的机会就没有了（只有这一次机会），另一方可以选择从一开始就直接向着没有被包含的区间走。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <set>

using namespace std;
#define int long long
const int N = 1000010;
int a[N],b[N];
int n,m,k;
void solve(){
    int n,m;
    cin>>n>>m;
    int xa,xb,ya,yb;
    cin>>xa>>ya>>xb>>yb;
    int diss=abs(xa-xb);
    int dis=diss/2;
    int sa=max((int)1,ya-dis);
    int ea=min(m,ya+dis);
    int bs=max((int)1,yb-dis);
    int be=min(m,yb+dis);
    if(xb-xa<=0){
        cout<<"Draw"<<endl;
        return ;
    }
    if(diss%2){
        sa=max((int)1,sa-1);
        ea=min(m,ea+1);
        if(sa<=bs && ea>=be){
            cout<<"Alice"<<endl;
        }else{
            cout<<"Draw"<<endl;
        }
    }else{
        if(sa>=bs && ea<=be){
            cout<<"Bob"<<endl;
        }else{
            cout<<"Draw"<<endl;
        }
    }
}
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

? F

根号分治+前缀和

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<array>
using namespace std;
typedef long long LL;
#define int long long
typedef pair<int,int> PII;
const int N=1000010;
int ans[N],a[N];

void solve(){
    int n,m,q;
    cin>>n>>q;
    const int S=350;
    vector<vector<array<int,3>>>query(S+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=q;i++){
        int s,d,k;
        cin>>s>>d>>k;
        if(d>S){
            int sum=0;
            for(int j=0;j<k;j++){
                sum+=(j+1)*a[s];
                s+=d;
            }
            ans[i]=sum;
        }else{
            query[d].push_back({s,k,i});
        }
    }
    for(int i=1;i<=S;i++){
        if(query[i].size()==0) continue;
        vector<int>s1(n+1),s2(n+1);
        for(int j=1;j<=n;j++){
            int t=(j+i-1)/i;
            s1[j]=a[j];
            s2[j]=a[j]*t;
            if(t>1){
                s1[j]+=s1[j-i];
                s2[j]+=s2[j-i];
            }
        }
        for(auto c:query[i]){
            int ed=c[0]+i*(c[1]-1);
            int cnt=(c[0]+i-1)/i;
            if(cnt==1){
                ans[c[2]]=s2[ed];
            }else{
                int beg=max((int)0,c[0]-i);
                ans[c[2]]=s2[ed]-s2[beg]-(cnt-1)*(s1[ed]-s1[beg]);   
            }
        }

    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<" ";
    cout<<endl;
}
signed main(){
    
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}
        

????????