A

操作 2 会让奇数-1，偶数+1。

不难发现只有当 $a$ 为奇数时，我们能让 $a$ 减小，且只能减少 $1$。

如果 $a > b$，那么当且仅当 $a \oplus 1 = b$ 有解。

下面讨论 $a < b$ 的情况。

如果 $x \le y$，那么我们全部使用操作 $1$ 即可。

否则我们肯定是两种操作交替使用。

关于第一次和最后一次用哪种操作，判断 $a$ 与 $b-a$ 的奇偶即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int T, a, b, x, y;
int c[2];
void solve() {
    a=read(), b=read(), x=read(), y=read();
    if(a>b&&(a^1)!=b) {
        puts("-1");
        return;
    }
    if(a>b) {
        printf("%d\n",y);
        return;
    }
    ll ans=0;
    if(x<=y) {
        printf("%d\n",(b-a)*x);
    } else {
        if(a==b) {
            puts("0");
            return;
        }
        if(a&1) c[0]=y, c[1]=x;
        else c[0]=x, c[1]=y;
        printf("%d\n",(b-a)/2*(x+y)+(b-a)%2*c[(b-a)%2]);
    }
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

B

挺难的。

一个精妙的转化：$n$ 条路径加上 $\overline{PQ}$，一定构成一个 $n+1$ 边形。

不管它是凹是凸，其充要条件是任意 $n$ 条边长度大于剩下那条边。

我们取最长的那条边判一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=1e3+5;
int T, n;
double a[N];
PII x, y;
void solve() {
    n=read();
    x.fi=read(), x.se=read();
    y.fi=read(), y.se=read();
    double dis=sqrt(1.0*(y.fi-x.fi)*(y.fi-x.fi)+1.0*(y.se-x.se)*(y.se-x.se));
    rep(i,1,n) a[i]=1.0*read();
    if(n==1) {
        puts(a[1]==dis? "Yes":"No");
        return;
    }
    a[n+1]=dis;
    sort(a+1,a+n+2);
    double sum=0;
    rep(i,1,n) sum+=a[i];
    if(sum<a[n+1]) puts("No");
    else puts("Yes");
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

C

比 A 简单……

如果 $n$ 是奇数，那么容易想到一种构造方法：全填 $l$。此时一定有解。

显然其合法并且最优。

如果 $n$ 是偶数，考虑一种构造方法：我们填 $n-2$ 个 $l$，后面填 $2$ 个 $l’$。其中 $l’$ 是满足大于 $l$ 且l&l'=0的最小的数。这样与和、异或和都是 $0$。如果 $l’ > r$ 就无解。

显然有 $l’ = 2^t > l$，$2^{t-1} \ge l$。

下证最优性：后两个数不可能更小了，前 $n-2$ 个数不可能更小了，$l$ 不可能更多了。于是最优。

下证无解性：此时 $[l,r]$ 夹处在 $[2^{t-1},2^{t}]$ 中间，不可能有与和为 $0$ 的数。故此时无解，既题目无解。

当 $n=2$ 的时候，不存在与和、异或和相等的两个正整数。

考虑每一位的运算，显然。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int T;
ll n, l, r, k;
void solve() {
    n=read(), l=read(), r=read(), k=read();
    if(n&1) {
        printf("%lld\n",l);
        return;
    }
    if(n==2) {
        puts("-1");
        return;
    }
    int i=0;
    while((1ll<<i)<=l||(1ll<<i)&l) i++;
    ll res=1ll<<i;
    if(res<=r) {
        printf("%lld\n",k<=n-2? l:res);
    } else puts("-1");
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

D

难题。

一开始根本无从下手。尝试 DP，发现无法消除“已经选了哪些点”的后效性。

一个高妙的转化：不考虑每个 $a_i$ 填什么，而是考虑每个操作删掉了哪个点。题目要求的其实是每个删点方案对应的操作区间数量之和。

我们能发现每个操作区间的右端点是唯一确定的，如果要删除点 $i$，只需要在 $[i,n]$ 中选择一个右端点（对应一个操作），在 $[1,i]$ 中选一个左端点（任意）。但是每个右端点只能被选择一次，有后效性。

考虑 DP。设 $f(i,j)$ 表示考虑了区间 $[1,i]$ 中的所有点，$[i,n]$ 还剩下 $j$ 个右端点可以选的方案数。

发现无法转移。因为随着 $i$ 的增长，可能会有的右端点不再能选。

设 $f(i,j)$ 表示考虑区间 $[i,n]$ 所有点即可，此时空出来的点以后肯定能选。

讨论当前点删不删即可转移

$$
f(i,j) = [j>0]f(i+1,j-1) + f(i+1,j) \times i \times (j+1)
$$

答案 $\sum_{i=0}^n f(1,i)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=5e3+5;
int T, n;
ll mod, f[N][N];
void solve() {
    n=read(), mod=read();
    rep(i,0,n+1) rep(j,0,n+1) f[i][j]=0;
    f[n+1][0]=1;
    per(i,n,1) rep(j,0,n-i+1) {
        if(j) (f[i][j]+=f[i+1][j-1])%=mod;
        (f[i][j]+=f[i+1][j]*i%mod*(j+1)%mod)%=mod;
    }
    ll ans=0;
    rep(i,0,n) (ans+=f[1][i])%=mod;
    printf("%lld\n",ans);
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

E

推到一半然后失败了。

待补。