A. Median of an Array
排序
大概思路
直接排序，然后从下标 $\frac{1+n}{2}$ 处一直往后查到第一个不等于 $a_{\frac{1+n}{2}}$ 的数即可
参考代码
void solve(){
CIN(n);
vector<ll>a;a.push_back(-1);
FOR(i,1,n){
CIN(tmp);a.push_back(tmp);
}
sort(a.begin(),a.end());
ll ans=0,ck=a[(1+n)/2];
FOR(i,(1+n)/2,n){
if(a[i]!=ck)break;
ans++;
}
cout<<ans<<ET;
}
B. Maximum Sum
区间最大子串和
大概思路
查一遍区间最大子串和，然后乘上 $2^k-1$ ，再加上总和即可，注意取模
参考代码
ll powp(ll x,ll n){
ll ans=1;
while(n){
if(n&1){ans*=x;ans%=M;}
x*=x;x%=M;n>>=1;
}
return ans;
}
inline ll MO(ll x){return (x%M+M)%M;}
void solve(){
CIN(n);CIN(k);
vector<ll> pre(n+1,0);
FOR(i,1,n){CIN(tmp);pre[i]=pre[i-1]+tmp;}
ll mx=0;ans=-1e18;
FOR(i,1,n){
mx=min(mx,pre[i-1]);
ans=max(ans,pre[i]-mx);
}
if(ans<=0){
cout<<MO(pre[n])<<ET;
}else{
cout<<MO(MO(pre[n]-ans)+MO(MO(ans)*MO(powp(2,k))))<<ET;
}
}
C. Tree Cutting
DFS，二分，贪心
大概思路
最小值的最大值，一眼二分。每次二分跑一遍DFS统计最大可删边次数即可。
参考代码
const int MAXN=1e5+5;
int n,k;
vector<int> edg[MAXN];
int siz[MAXN],cnt;
//图论，树论（各种意义上的树）不熟导致的
void dfs(int u,int From,int x){
siz[u]=1;
for(auto v:edg[u])if(v!=From){//无向无环图（树），只需保证下一条边不往回走就可以不发生死循环
dfs(v,u,x);//DFS收集子树大小
siz[u]+=siz[v];
}
if(siz[u]>=x){//子树满足条件，siz置0（剪掉）
cnt++;
siz[u]=0;
}
}
int ck(int x){
cnt=0;
dfs(1,0,x);//任取一节点开始DFS，统计最大删边次数（贪心）
return cnt-1;//DFS的贪心删法可能会剩一个小于x大小的联通快，所以要撤回一次删除
}
void solve(){
cin>>n>>k;
FOR(i,1,n)edg[i].clear();
FOR(i,1,n-1){
CIN(u);CIN(v);
edg[u].push_back(v);
edg[v].push_back(u);
}
int l=1,r=n+1;
while(l<=r){
int mid=l+r>>1;
if(ck(mid)>=k)l=mid+1;
else r=mid-1;
}
cout<<l-1<<ET;
}
D. Birthday Gift
前缀异或和，拆位，数位DP
大概思路
题意大概是问你把一段序列拆成多段，各段的异或和，或在一起小于等于某个数，最多能拆成多少段。
首先前缀异或和一下，得到 $pre_i$，每段的异或和此时可以表示为 $pre_{r_i}\otimes pre_{{l_i}-1}$，也就是 $pre_{r_i}\otimes pre_{r_{i-1}}$，原问题可转化为，取一段序列 $0=r_0<r_1<r_2<\dots<r_k=n$ 使得任意 $i\in[1,n]$ 都有 $pre_{r_i}\otimes pre_{r_{i-1}}\le x$，最多能选多少段这样的序列。
这里我们可以按位从前往后枚举，每次取消一个x的有效位，换取后面的所有位都能随意取的收益，遍历收集最大答案即可。
参考代码
void solve(){
CIN(n);CIN(x);x++;
vector<ll> pre(n+1);
FOR(i,1,n){cin>>pre[i];pre[i]^=pre[i-1];}
ll ans=-1;
ll HEAD=0;
rFOR(i,30,0){
HEAD|=(1LL<<i);//获得“取反匹配串”，当一个数与该“取反匹配串”相与不为0时，说明我们不想让这个数出现的一些数位为1，那么这个数就“不合法”
if((x>>i)&1){
//当然这题你直接在这里用ll HEAD=((((~x)>>i)^1)<<i)也是可行的，用HEAD不断记录前到后只是数位DP的一种思想体现
int cnt=0;
if((HEAD&pre[n])!=0){HEAD^=(1LL<<i);continue;}//如果全异或不匹配，说明没法完成匹配，因为这说明非法数位的数量是奇数，没法通过适当分组消掉所有的非法数位
FOR(i,1,n)if((HEAD&pre[i])==0)cnt++;//如果可行就记录答案
ans=max(ans,cnt);
HEAD^=(1LL<<i);//保证到当前数位为止数位都是取反的
}
}
CA;
}
这里附上kk神的思路（差不多，就是在枚举拆位时，采用的是贪心遍历统计答案，感觉这样写比前缀异或和更直观一点）：
void crossparallel() {
int n, x;
cin >> n >> x;
vector<int> a(n + 1);
int ans = 0;
int tmp = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
tmp ^= a[i];
if ((tmp | x) <= x) {
ans++;
tmp = 0;
}
}
if (tmp) {
ans = 0;
}
for (int i = 31; i >= 0; i--) {
if ((x >> i) & 1) {
int now = (x ^ (1 << i)) | ((1 << i) - 1);
int cur = 0;
int res = 0;
for (int j = 1; j <= n; j++) {//直接上贪心，满足条件直接输出
cur ^= a[j];
if ((cur | now) == now) {
res++;
cur = 0;
}
}
if (!cur)//可以证明，如果有剩，说明没法匹配（非法数位为奇数个，匹配不完）
ans = max(ans, res);
}
}
if (ans)
cA;
else
c1;
}
E. Girl Permutation
组合数，逆元
大概思路
易知，如果premax最后一位不等于sufmax的第一位，那么肯定输出 $0$
不然就直接不考虑数组最大值所在位，先从剩下的 $n-1$ 个数中任取 $m_1-1$ 个数（$\textrm{C}_{n-1}^{m-1}$），放在最大值前面，然后从前往后遍历，假象自己在一个队列中维护“数的大小关系”，如果这个数对应的下标是“premax”所在处，那么这个数只能放在队首，对总方案数贡献为 $1$；如果这个数对应的下标不是“premax”所在处，那么这个数可以插在队首以前的任何一个位置，对总方案数贡献为 $i-1$。
对sufmax那边的处理也差不多，倒序收集一遍方案数就行。
参考代码
const int MAXN=2e5+5;
ll fac[MAXN],invfac[MAXN];
ll C(ll m,ll n){return (m<0||m>n)?0:MO(MO(fac[n]*invfac[m])*invfac[n-m]);}
ll powp(ll x,ll n){
ll ans=1;
while(n){
if(n&1)ans=MO(ans*x);
x=MO(x*x);n>>=1;
}
return ans;
}
void pre(){//预处理组合数
fac[0]=fac[1]=invfac[0]=invfac[1]=1;
FOR(i,2,MAXN-1){
fac[i]=MO(fac[i-1]*i);
invfac[i]=powp(fac[i],M-2);
}
}
bool ism[200005];
void solve(){
CIN(n);CIN(m1);CIN(m2);
memset(ism,0,sizeof ism);
int a,b;
FOR(i,1,m1){CIN(tmp);ism[tmp]=1;if(i==m1)a=tmp;}
FOR(i,1,m2){CIN(tmp);ism[tmp]=1;if(i== 1)b=tmp;}
if(a!=b){cout<<0<<ET;return;}
ll ans=C(a-1,n-1);
FOR (i,1,a-1)if(!ism[i])ans=MO(ans*(i-1));
rFOR(i,n,a+1)if(!ism[i])ans=MO(ans*(n-i));
CA;
}
F. Nobody is needed
待补题
附录
这里贴上用到的头部和main函数：
#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
//趋向for循环，一般情况别用，规定方向时会跳出的循环在这里不会跳出
#define rep(i,a,b) for(ll i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
std::mt19937 myrand(time(0));
ll rnd(ll l, ll r) {return std::uniform_int_distribution<ll>(l, r)(myrand);}
//没有C++20就不能用ranges了//CF又可以用C++20了，封印解除
#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}
string ANS[2]={"No\n","Yes\n"};
void solve(){
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//pre();
//CIN(t);while(t--)
solve();
return 0;
}