这次看到 C 题分数 1750 就开始害怕了，用小号打的比赛，一直觉得做不出来，最后才想到

A. Max Plus Size

题意

给你一些整数，选择一些涂成红色，两两不能相邻，你的得分为：
$$[红色元素的个数]+[红色元素的最大值]$$

找到最大的得分

思路

尽量选得多一些，所以有两种：选第奇数个，选第偶数个

两种分别求出最大值，最后比较、输出就行了

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){int n;cin>>n;vector<int> v(n+1);for(int i=1;i<=n;i++){cin>>v[i];}int mxji=0,mxou=0;for(int i=1;i<=n;i+=2){mxji=max(mxji,v[i]);}for(int i=2;i<=n;i+=2){mxou=max(mxou,v[i]);}cout<<max(mxji+(n+1)/2,mxou+(n/2))<<endl; // (n+1)/2 表示 n/2 向上取整
}
signed main(){int t;cin>>t;while(t--){solve();}return 0;
}

B. All Pairs Segments

题意

有亿点绕

给你数轴上的 $n$ 个点，$x_1,x_2,...,x_n$，已经按升序排列，

对于每个 $(i,j)(1\le i<j\le n)$，你在 $[i,j]$ 区间画一条线段（闭区间包含两端）。

有 $q$ 次询问，第 $i$ 次让你找到：整个数轴上有多少个整数点被 $k_i$ 条线段覆盖 $(1\le ki\le 10^{18})$

思路

对于每个点，有两种情况：

• 是已经给出的点

  此情况下每个点要逐一判断被几条线段覆盖，存到 map 中

  如果当前下标为 $i$，则被 $C_n^2-C_{i-1}^2-C_{n-i}^2$ 个线段覆盖的点数量 $+1$

• 不是给出的点

  此情况下，对于在两个给出的点 之间 的所有点，覆盖线段的数量相等

  则下标为 $i$ 和 $i+1$ 之间时，则被 $C_n^2-C_i^2-C_{n-i}^2$ 个线段覆盖的点数量 $+(x_{i+1}-x_i-1)$

  同样存到 map 中

最终每次输出 map 中的数值就可以了

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;int C(int k,int p){return k*(k-1)/2;
}void solve(){int n,q;cin>>n>>q;vector<int> v(n+1);map<int,int> mp;for(int i=1;i<=n;i++){cin>>v[i];int num=C(n,2)-C(i-1,2)-C(n-i,2);mp[num]++;}for(int i=1;i<=n-1;i++){int num=C(n,2)-C(i,2)-C(n-i,2);mp[num]+=(v[i+1]-v[i]-1);}while(q--){int k;cin>>k;cout<<mp[k]<<" ";}cout<<endl;
}signed main(){int t;cin>>t;while(t--){solve();}return 0;
}

C. Cards Partition

题意

你有一些卡牌，上面有 $n$ 种数字，写着数字 $i$ 的卡牌共有 $a_i$ 个。

你可以再次购买 $\le k$ 张卡牌，上面可以写上任意数

随后你必须将卡牌分成若干层，每层卡牌数量相同，且一层内不能重复出现相同卡牌

找出最大的 每层的数量

思路

按从大到小的顺序枚举每层卡牌的数量，若当前符合要求直接输出

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){int n,k;cin>>n>>k;int mx=0,sum=0;for(int i=1;i<=n;i++){int ai;cin>>ai;sum+=ai;mx=max(mx,ai);}for(int i=n;i>=1;i--){int cur=(sum+k)/i;if(cur>=mx&&cur*i>=sum){cout<<i<<endl;return;}}
}
signed main(){int t;cin>>t;while(t--){solve();}return 0;
}