前言：

A了四题，第五题差点意思，不过也是上了一点分，感觉这场算是比较简单（应该）？

A.困难数学题

相同的数异或肯定为0了，再来一次也是0

void solve(){
    int n;
    cin>>n;
    cout<<0;
}

B. 构造序列

使用n个正数和m个负数，满足正数不与正数相邻，负数不与负数相邻，问序列最长能构造多长

思路：考虑负数正数相邻，n==m肯定都是可以的，任意一个多一也是可以的，多二就不行了，因为会相邻

void solve(){
    int n,m;
    cin>>n>>m;
    cout<<min(n,m)*2+(n!=m);
}

C.连点成线

感觉和之前的一道线分割点有点像（题目类型上）

思路：直接暴力，点塞数组里面正的排一次算最值，x,y坐标交换再算一次，就可以了

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int> > dp(m+1,vector<int>(2,0));
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        dp[i][0]=x;
        dp[i][1]=y;
    }
    sort(dp.begin(),dp.end());
    int ans = 0;
    map<LL,LL> q;
    int mx ,mi;
    for(int i=1;i<=m;i++){
       if(!q[dp[i][0]]){
            mi = dp[i][1];
            q[dp[i][0]] = 1;
       }
       else{
            ans = max(ans , dp[i][1]-mi);
       }
    }
    for(int i=1;i<=m;i++){
       swap(dp[i][0],dp[i][1]);
    }
    sort(dp.begin(),dp.end());
     map<LL,LL> qq;
    for(int i=1;i<=m;i++){
       if(!qq[dp[i][0]]){
            mi = dp[i][1];
            qq[dp[i][0]] = 1;
       }
       else{
            ans = max(ans , dp[i][1]-mi);
       }
    }
    cout<<ans;
}

D.我们N个真是太厉害了

an个数看看能否表示出1-n的所有数字

考虑dp,从小到大排序，然后从n开始向下遍历，如果i-x有出现，说明i可以凑出来，这样复杂度大概在on2,考虑到i是从大到小，小的会被重复遍历，考虑在已经遍历过的地方直接结束循环

void solve(){
    int n;
    cin>>n;
    vector<int> a(n,0);
    vector<bool> dp(n + 1, false);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    dp[0] = true;
    for (int x : a) {
        if(x>n) continue;
        for (int i = n; i >= x; --i) {
            if(dp[i]) break;
            if (dp[i - x]) {
                dp[i] = true;
            }
        }
    } 
    for(int i=1;i<=n;i++){
        if(!dp[i]){
            cout<<i<<endl;
            return;
        }
    }
    cout<<"Cool!"<<endl;
}

E.折返跑

两个杆子是1和n最多可以推n−2次，而且题目要求除了最后一趟每次都推，那不就是要推m−1次 ,所以结果就是C(n-2,m-1)次

直接上组合数模板就行了

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
typedef long long int LL;
const int N = 2e6 + 5;
const int mod = 1e9 + 7;
const int p = 1e9+7;
int64_t fact[N];
int64_t pw(int64_t a, int64_t b) {
    int64_t r = 1;
    while(b > 0) {
        if(b & 1) r = (r * a) % mod;
        b /= 2;
        a = (a * a) % mod; 
    }
    return r;
}
int64_t C(int64_t n, int64_t k) {
    if(n < k) return 0LL;
    return (fact[n] * pw((fact[n - k] * fact[k]) % mod, mod - 2)) % mod;
}
void solve(){
    LL n,k;
    cin>>n>>k;
    cout<<C(n-2,k-1)%p<<endl;
}
int main(){
    int t;
    cin>>t;
    fact[0] = 1;
    for(int64_t i = 1; i < N; ++i) fact[i] = (fact[i - 1] * i) % mod;
    while(t--){
        solve();
    }
}