iwtgm-36

Codeforces Round 914 (Div. 2)

A.

遍历能攻击国王的点，用map存下
再遍历能攻击王后的点，若这个点之前已经存过，说明这个点可以同时攻击国王和王后，ans++

void solve(){
    int a,b;
    int x,y;
    cin>>a>>b>>x>>y;
    map<pair<int,int>,int> board;
    vector<pair<int,int>> path;
    path.push_back({a,b});
    path.push_back({-a,b});
    path.push_back({a,-b});
    path.push_back({-a,-b});
    path.push_back({b,a});
    path.push_back({-b,a});
    path.push_back({b,-a});
    path.push_back({-b,-a});
    for(auto [u,v]:path) board[{x+u,y+v}]=1;
    int ans=0;
    cin>>x>>y;
    for(auto [u,v]:path){
        ans += (board[{x+u,y+v}]>0);
        board[{x+u,y+v}]--;
    }
    cout<<ans<<endl;
}

B.

先排序，再求个前缀和
从后往前dp，若当前前缀和>=后一个数，（相当于这个数升级为后一个数，也就是答案和后一个答案一样）,dp[i]=dp[i+1]
若不大等于，那么dp[i]=i-1

#define int long long
pair<int,int> a[N],dp[N];
int pre[N];
void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first;a[i].second=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i].first;
    }
    for(int i=n;i>=1;i--){
        if(i==n){
            dp[i].second=n-1;
            dp[i].first=a[i].second;
        }
        else{
            if(pre[i]>=a[i+1].first){
                dp[i].second=dp[i+1].second;
                dp[i].first=a[i].second;
            }
            else {
                dp[i].second=i-1;
                dp[i].first=a[i].second;
            }
        }
    }
    sort(dp+1,dp+1+n);
    for(int i=1;i<=n;i++){
        cout<<dp[i].second<<' ';
    }
    cout<<endl;
}

C.

k>=3，一定是0，可以任意选两个i，j操作两次，操作后的结果一定相同，再一减就是0了
k=1，算一下所有减的结果，和原数组取最小值就行
k=2，一次减的结果放数组b里面，对a和b排序，双指针

#define int long long
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    if(k>=3){
        cout<<0<<'\n';
        return;
    }
    sort(a.begin(),a.end());

    vector<int>b;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            b.push_back(a[j]-a[i]);
        }
    }
    int m=b.size();
    sort(b.begin(),b.end());
    //cout<<b[0]<<'\n';

    if(k==1){
        cout<<min(a[0],b[0])<<'\n';
    } else {
        int mn=min(a[0],b[0]);
        //cout<<mn<<'\n';
        a.push_back(1e18); //上限
        int r=0;
        for(int i=0;i<m;i++){
            while(r<n&&a[r]<b[i]) r++;
            if(r>=1) mn=min(mn,b[i]-a[r-1]);
            mn=min(mn,a[r]-b[i]);
        }
        cout<<mn<<'\n';
    }
}