题目难度参考与目录
签到题：B , F , M , A
简单题：N , E , L , K , I
中等题：D , G , H , C
困难题：J
B.货币战争(签)
考点：数学
题目大意：题目给定基础装备数目和进阶装备与特权装备的对应关系，求出三种装备数目之和。
解题思路：观察到，实际上进阶装备与普通装备的决定关系为n*(n+1)/2(对于每一个基础装备i，他可以与编号在其后面的任意基础装备j形成一件新的进阶装备，于是进阶装备的数量应为普通装备的sum(n))，且特权装备数量与进阶装备数量相同，最终答案为n*(n+1)+n=n*(n+2)。
由于n的范围为1e5，1e5*1e5会爆掉int最大值，所以应该将答案强转为long long输出或者直接定义long long的变量。
B代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n; cin>>n;
cout<<1ll*n*(n+2)<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
F.琪露诺与笨蛋⑨(签)
考点：语法
题目大意：给定n个9以内的加减乘除运算，答案为9的占这些的比例是多少。
解题思路：按照加减乘除正常计算即可。
创建一个变量初始化为0，用他来记录答案为9的题目个数，最终答案应该为(答案为9的题目个数/题目总数n)。
你需要将答案写为百分比形式并保留两位小数，在c语言里你可以通过printf直接输出，在c++语言里你可以通过fixed setprecision()来精确的保留小数点后几位，其他语言的参赛选手请自行了解。
F代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n; cin>>n;
int d=0;
for(int i=0;i<n;i++){
int a,b; char c;
cin>>a>>c>>b;
if(c=='+'){
if(a+b==9) d++;
}
else if(c=='-'){
if(a-b==9) d++;
}
else if(c=='*'){
if(a*b==9) d++;
}
else {
if(b*9==a) d++;
}
}
cout<<fixed<<setprecision(2)<<double(d)/n*100<<"%\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
M.绝对对称(签)
考点：贪心
题目大意：一个数组中可以选定一个数字将其分成x/2与(x+1)/2，此操作可以无限次进行，当你将数组中的每一个数字连接起来看作一个字符串时，判断其是否能成为一个回文字符串。
解题思路：因为操作可以无限次被进行，那么将任意一个数字x分解为x个1，当一个字符串的所有字符都相同，他一定是一个回文字符串，所以此题的所有解一定为YES。
M代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n; cin>>n;
for(int i=0;i<n;i++){
int x; cin>>x;
}
cout<<"YES"<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
A.爱神使者(签)
考点：排序
题目大意：在一天的时间轴中有n个时间子段从l到(l+t)，其中l由h,m,s定义。只要t不为0，不能有任何时间子段与其他时间子段相交且不能超过这个时间轴。
解题思路：首先先记录给定值，(转化为时间轴或使用h,m,s,t四个数组进行描述)然后整体排序，可以使用sort排序，此题中冒泡排序也能通过，对于每一个前面的时间l[i]+t[i]不能＞l[j]+t[j] (i<j成立)由于排序的性质，我们只需要检查相邻的两个值是否符合即可，最后我们需要对最后一个时间段与一天的最后一个时刻进行特判。
本题当中一种转化为时间轴的手段，令 l =h * 3600 + m * 60 + s。
A代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int day=86400;
int n; cin>>n;
vector<pair<int,int>> v(n);
for(int i=0;i<n;i++){
int h,m,s,t;
cin>>h>>m>>s>>t;
int u=h*3600+m*60+s;
v[i]={u,t};
}
sort(v.begin(),v.end());
for(int i=1;i<n;i++){
if(v[i].first<v[i-1].first+v[i-1].second) {
cout<<"No"<<endl;
return;
}
}
if(v[n-1].first+v[n-1].second>=day){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
N.应邀评委 (ez)
考点:二分 | 数学
题目大意：给定的n个数与你给出的一个数，去掉一个最高分一个最低分能使选手及格的且与x接近的一个数。
解题思路：假定max为除了我们的数字以外其余数字最大的，min为最小的。我们可以将1.自己的分数无论是什么也不影响及格，2.自己的分数如果等于最大值依旧不合格，和3.其他。
(公式法)：三种情况讨论:对于情况1，答案是给定的x，对于情况2,答案是-1，对于情况3，我们给出的数一定在min与max之间，我们发现答案只能在min与max之间才会产生影响，于是题目所给公式中除了自己给出的评分外其余为已知量，将所给公式逆推解一元方程来获得答案。
(二分法)：对于上述的情况3，一定有当给出答案＞界定值k，从[k,max]一定都能及格，通过二分查询界定值，当界定值k<所给评定值x，那么答案为x，否则答案为k。
N代码参考.
公式法:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,x;
cin>>n>>x;
vector<int> v(n);
ll res=0;
int mx=0,mi=1e9+7;
for(int i=0;i<n;i++){
cin>>v[i];
res+=v[i];
mx=max(mx,v[i]);
mi=min(mi,v[i]);
}
res=res-mi-mx;
if(res/(n-2)>=6ll*1e8) {
cout<<x<<endl;
}
else if((res+mx)/(n-1)<6ll*1e8){
cout<<-1<<endl;
}
else{
ll ans=6ll*1e8;
ans*=(n-1);
ans=ans-res;
if(ans<x) cout<<x<<endl;
else cout<<ans<<endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
二分法:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,x;
cin>>n>>x;
vector<int> v(n);
ll res=0;
int mx=0,mi=1e9+7;
for(int i=0;i<n;i++){
cin>>v[i];
res+=v[i];
mx=max(mx,v[i]);
mi=min(mi,v[i]);
}
res=res-mi-mx;
if(res/(n-2)>=6ll*1e8) {
cout<<x<<endl;
}
else if((res+mx)/(n-1)<6ll*1e8){
cout<<-1<<endl;
}
else{
int l=0,r=1e9;
while(l<=r){
int mid=(l+r)>>1;
if((res+mid)/(n-1)>=6ll*1e8){
r=mid-1;
}
else l=mid+1;
}
if(l<x) cout<<x<<endl;
else cout<<l<<endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
E.符华抓赤鸢(ez)
考点：曼哈顿距离
题目大意：你初始位置位于{x,y}。其余有k个位置，每次所有位置都必须随机向四个方向移动但不会超出给定区域，在足够长的时间，你能不能保证与其他位置成功汇合。
解题思路：考虑到仅仅只有两个点的情况,我们先固定一个点，移动令一个点，只有两种可能:1.曼哈顿距离更近(-1)或2.曼哈顿距离更远(+1)。同理，我们再移动另一个点，此时依旧是两种可能:1.曼哈顿距离更近(-1)或2.曼哈顿距离更远(+1)。
我们将这两种情况排列组合[-1,-1],[-1,+1],[+1,-1],[+1,+1]。他们造成的影响永远是0或者2，在无数次的操作中，所有的点他们相对的距离仅仅会是无数个0或者2的改变，那么对于所有初始相差曼哈顿距离为偶数的点最终可以汇合，奇数的点永远无法汇合。
E代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,m,k; cin>>n>>m>>k;
int x,y; cin>>x>>y;
int a,b;
for(int i=0;i<k;i++){
cin>>a>>b;
if((abs(a-x)+abs(b-y))%2) {
cout<<"No"<<endl;
return;
}
}
cout<<"Yes"<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
L.画线游戏(ez)
考点：图论
题目大意：先手玩家需要画出一条线，这条线的两头必须都要连接到十字符号或交叉线的端口上（画的线不能与自己相交也不能触碰其他的线），最后在这条线上画出一段交叉线，随后交给另一方玩家行动。 双方玩家轮流画线，直到最后无线可画，最后画线的玩家就是胜利者。
解题思路：整个游戏过程中总端口数不发生改变为4*n(由于每次画线时我们需要消耗两个端口但随后画出的一个交叉线增加两个端口于是端口数没有发生变化)。
于是考虑到游戏不能进行下去的原因为不同端口之间被分割为不同的区域导致无法与其他端口相连，且终局时一定存在每个端口独立占据一个区域（原因：如果一个区域存在的端口数量大于1那么一定存在两个端口相连将其划分为两个区域每个区域各占据一个端口的操作）。
于是题目的结束条件就转变为了使用多少步操作将4n个端口划分为4n个区域。
我们考虑对于一个独立的十字自己与自己连接，他的连接操作永远相当于划分出一个单独的区域。而对于两个不同的十字连接，仅相当于将不同的联通块变成同一块联通区域（类似于并查集），该操作不会增加单独的区域，但是下一次连接就会相当于自己与自己连接。换句话说，对于n个十字，总有n-1次操作没有划分出新的区域（将n个独立区域连接为1个整体区域），其余操作都会划分出一个新的区域。
于是从游戏开始时到游戏结束无论怎么连接永远会在4n-1(增加到4n块区域）+n-1（不会增加新的区域的操作数）=5*n-2的操作总数时结束游戏。
在本题中，当n为奇数时，操作总数为奇数次，先手必胜。当n为偶数时，操作总数为偶数次，后手必胜。
L代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n; cin>>n;
cout<<(n&1?"YES":"NO")<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
K.花火娃娃(ez)
考点：简单博弈
题目大意：有n个正常娃娃，n个炸弹娃娃，两人轮流交换先后手且每次最少拿走两个娃娃，最多拿走k个娃娃，当一个人拿取娃娃时有2个以上炸弹娃娃，就会失败，由你先手操作。
解题思路：题目中有2*n个娃娃,每次最少拿走2个娃娃,则对局最多进行n轮，且没有人会在对局过程中选择一次拿走两个炸弹娃娃自杀，所以对局中剩余娃娃中一定永远存在炸弹娃娃。
考虑到两个人足够聪明，那么当他们操作时会拿走两个以上炸弹娃娃时当且仅当剩余娃娃仅剩下炸弹娃娃，题目的获胜条件就转换成了一次操作取走娃娃后其余娃娃仅剩下炸弹娃娃，即将n个正常娃娃全部取完。
考虑到取完n个正常的娃娃，因为题目中仅取走一个炸弹娃娃不会导致输掉游戏且剩余的娃娃之中永远都会存在炸弹娃娃，于是我们一次能取走正常娃娃的数量就将变成[1,k]个。
我们来考虑一种情况，对于正常娃娃剩余数量x时，且x小于等于k，我们可以一次将x个正常娃娃全部取走，这样下一次操作时仅剩下炸弹娃娃，则对手必输。对于这样我们用一次操作可以导致后手一定会失败的位置，我们称作必胜点。而当我们无论如何操作都会导致对手下一次操作能够使我们输掉比赛的地方我们称作必败点。
对于此题,根据前面分析，当正常娃娃数量为0时，无论如何取，都会导致自己失败，而[1,k]我们都可以通过一次操作将娃娃全部取走导致对手下一次一定失败，对于[k+1]的位置无论我们如何取走娃娃,都会导致剩余的正常娃娃落在[1,k]之间导致对手再进行一次操作让我们输掉游戏，所以也是一个必败点。
其他所有位置同理，当我们枚举所有必败点我们发现对于所有的答案当n个正常的娃娃是(k+1)的整数倍时我们一定会输掉游戏，反之我们可以获得游戏的胜利。
K代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define endl '\n'
void solve(){
int n,k; cin>>n>>k;
if((n%(k+1))!=0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
I.买谷(ez)
考点：01背包
题目大意：要购买n件商品，可以使用任意张满a减b的折扣券进行减价，但是初始花费要大于选择的这些折扣券a之和，最后花费的最小代价应该是多少。
解题思路：当我们不使用任何折扣券时我们花费的金额数目是固定的一个值k，当我们想让自己的花费最小可以转换成使用不超过固定值k的折扣券减少最多的价值v，每个折扣券不能重复使用。
于是题目转变成了01背包求取最大值,将花费的a看作代价，减免的b看作价值，在a小于等于容积k的情况下最大化减免的b。
01背包的做法与概念由读者自行了解，这里不做说明。
I代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,m; cin>>n>>m;
int res=0;
vector<int> a(n);
vector<int> w(m);
vector<int> v(m);
for(int i=0;i<n;i++) cin>>a[i],res+=a[i];
for(int i=0;i<m;i++) cin>>v[i]>>w[i];
vector<int> dp(res+1);
for(int i=0;i<m;i++){
for(int j=res;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<res-dp[res]<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
D.蕾耶拉找希娜(mid)
考点：bfs | 并查集
题目大意：n个节点m个边的图中，一条边可以抵达某一结点但有x个区域被定义为不可抵达，我们将除被定义为不可抵达的点称为可抵达点，最终输出 {能够抵达的位置/可抵达点总数}。
题解：容易想到暴力解法， 使用bfs模拟整个过程，中途遇到一个新的位置就把能够抵达的位置+1，整个bfs结束后我们就获得了能够抵达的位置，可抵达点根据定义知道就是n-x，这种写法可以通过本题。
还有一种解法是使用并查集，我们初始时定义每一个位置都是以自身为祖先的单个节点的树，他们的定义是这样的:能够其抵达祖先节点的其他节点是这颗树的子树。这样当两个点是b可抵达a的,我们就直接将b这个子树接到a的子树下面（其含义是当b能抵达a时，能够抵达b的所有点也一定可以抵达a)，于是当我们读入所有的边时就可以将他们进行合并，我们只需要尽量将a可达b时令1作为祖先，这样再去查询每个数的祖先节点是否是1就知道这个位置是否能抵达1了。
D代码参考.
bfs法:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,m,x;
cin>>n>>m>>x;
vector<int> vis(n+1);
for(int i=0;i<x;i++){
int y;
cin>>y;
vis[y] = 1;
}
vector<vector<int>> e(n+1);
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
e[l].push_back(r);
e[r].push_back(l);
}
queue<int> q;
vector<int> ans;
auto bfs=[&](auto bfs)->void{
queue<int> qq;
while(q.size()){
auto p = q.front();
q.pop();
vis[p] = 1;
ans.push_back(p);
for(auto ne:e[p]){
if(!vis[ne]){
qq.push(ne);
vis[ne] = 1;
}
}
}
q=qq;
if(q.size()) bfs(bfs);
};
q.push(1);
bfs(bfs);
cout<<ans.size()<<"/"<<n-x<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
并查集法:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n,m,x;
cin>>n>>m>>x;
map<int,int> xj;
vector<int> f(n+1);
for(int i=1;i<=n;i++) f[i]=i;
function<int(int)> find=[&](int a){
if(f[a]==a) return a;
return f[a]=find(f[a]);
};
for(int i=0;i<x;i++){
int a; cin>>a; xj[a]=1;
}
for(int i=0;i<m;i++){
int a,b; cin>>a>>b;
if(xj[a]||xj[b]) continue;
a=find(a); b=find(b);
if(a==1){
f[b]=f[a];
}
else{
f[a]=f[b];
}
}
int c=0;
for(int i=1;i<=n;i++){
if(find(i)==1) c++;
}
cout<<c<<"/"<<n-x<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
G.月感电（mid)
考点：模拟
题目大意：根据题意描述，计算出一个期望值。
解题思路：观察到，每个角色的面板给出后，接下来贡献值会受到的影响只有暴击率，通过枚举角色是否会暴击的16种可能,根据题意对他们计算此时的月感电伤害以及触发这个事件的可能性，然后再记录到整体期望之中就是答案，记得约束暴击率超出100的部分，这部分是无效暴击。
G代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve() {
double g=2672.0;
double res=0;
vector<array<double,3>> v(4);
for(int i=0;i<4;i++){
cin>>v[i][0]>>v[i][1]>>v[i][2];
v[i][1]/=100;
v[i][2]/=100;
if(v[i][1]>=1) v[i][1]=1;
}
for(int i=0;i<=15;i++){
int t=i;
double may=1,ans=0;
vector<double> a(4);
for(int j=0;j<4;j++){
int f=t&1;
t/=2;
if(f){
may*=v[j][1];
a[j]=g*(1+v[j][0]*0.0028)*(1+v[j][2]);
}else{
may*=(1.0-v[j][1]);
a[j]=g*(1+v[j][0]*0.0028);
}
}
sort(a.begin(),a.end(),greater<double>());
for(int j=0;j<4;j++){
if(j==0) ans+=a[j];
else if(j==1) ans+=a[j]*0.5;
else ans+=a[j]*0.083;
}
res+=ans*may;
}
cout<<int(res+0.5)<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
H.整合时间!(mid)
考点：暴力枚举&前缀和
题目大意：你需要在一个只有0和1的数组中进行操作，每次操作可以置换一个0或者1，你的最终目标是将这个数组变成恰好由2个连续的0子数组以及2个连续的1子数组组成的数组，问你最少操作次数是多少。
解题思路：首先对于每个区间有多少个1进行预处理(即前缀和处理)之后三个点分出四个线段，枚举3个点的位置在哪，对于第一段都为0或者都为1，其余段都与前一段恰好不同的连续段。
随后用前缀和数组得出每个区间需要操作的次数是多少，将所有段全部加起来，然后每次获得最小的,最后输出这个最小值。
H代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
int n; cin>>n;
string s; cin>>s;
int mx=1e9+7;
vector<int> v(n);
if(s[0]=='1') v[0]=1;
for(int i=1;i<n;i++){
v[i]=v[i-1]+(s[i]=='1');
}
for(int l=0;l<n-3;l++){
for(int r=l+1;r<n-2;r++){
for(int k=r+1;k<n-1;k++){
int m1=(l+1-v[l])+(v[r]-v[l])+((k-r)-(v[k]-v[r]))+(v[n-1]-v[k]);//1010
int m0=v[l]+((r-l)-(v[r]-v[l]))+(v[k]-v[r])+((n-1-k)-(v[n-1]-v[k]));//0101
mx=min({mx,m1,m0});
}
}
}
cout<<mx<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
C.盗火行者(mid)
考点：思维&贪心
题目大意：在一个数轴l,r当中，存在一个临界点k，使得当x位于<=k时恰好合理，>k时不合理，且在验算出这个临界点前，你不能使＞k的验算超出两次，想要让最差的可能性最少。
解题思路：最差的结果，从最下面一直往上找，结果最差是n次,但这显然不可能是答案；一种二分优化，开局从中间找，随后如果这就是临界点之和只能从1找到n/2的位置，最好可以不断缩小,最好是logn，最差是（n+1）/2，由于最差结果还是比较高，所以这也不是答案。
继续思考，如果我们想找到初始位置并不位于一半(因为这样我们存在一个瓶颈就是一半，导致左边相对空旷浪费次数多，所以可以考虑将初始索引向左移动来减少浪费)，而是一个更加宽泛的x值的情况，那么如果x不符合，此时我们只需要检查x下面的所有值，这样得到的向下寻找次数为x次(通过新的x突破原来的瓶颈)，而非二分的(n+1)/2次。
那么我们考虑将所有存在不符合的答案都定为x，如果符合由于我们之前存在使用次数cnt，所有我们向上寻找x-cnt的位置，此时如果不符合我们只需要检查与上一个符合区间的中间区域(中间区域数量一定为x-cnt-1)，根据我们的方案这样加起来一定是x，通过这个策略我们在整个过程中只要存在不符合答案一定会在x次数找到。
接下来我们来寻找x的值，我们发现还有一种情况，那就是全符合，直到我们向上寻找的位置x==1时停止，于是我们就得到了x+x-1+…+1,这个次数必须大于给定的n，这样就能做到停止时刚好知道了所有区域的情况，为了使寻找次数最小我们就选择最小的x。
于是x+x-1+…+1=x*(x+1)/2＞=n，于是我们可以反推出答案x。
由于本题数据较小，所以无需二分(最差不超过5e7次可以通过)。
相对的，如果此题扩大题目的数据如1e9则应该使用二分来进行优化。
C代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
ll n,x=0;
cin>>n;
n*=2;
while(x*(x+1)<n){
x++;
}
cout<<x<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1; //cin>>T;
while(T--){
solve();
}
return 0;
}
J.鏖战试炼·荣耀(hard)
考点：二分&贪心
题目大意：初始时具备n点专注度和要完成的爬塔数量m，两个操作：爬塔操作和休息操作。连续执行第i次爬塔操作会消耗i点专注度，休息操作会增加1点专注度以及重置爬塔操作。整个过程中需要保证专注度严格大于0，询问最少操作次数。
解题思路：首先观察到，本题中要想使操作次数最少即使我们的休息次数最少，因为爬塔操作是一个固定的操作次数。
对于如何安排最少的休息操作我们一定是将休息操作分开给一定次数的连续爬塔操作最优：对于休息操作为x次，连续休息x次再爬n层塔消耗专注度为(1+n)*n/2-x,与分开休息等价但消耗更多的专注度（因为连续爬塔层数越高损耗越大，所以考虑均分）。
假设休息操作为x，最优策略为均分连续爬塔数，x次休息可以将其分解为x+1段的连续爬塔，我们先考虑均分操作，将m层塔均等的分给x+1段，每段分得a=m/(x+1)。随后对于多余的部分r=m%（x+1）再次进行均分操作，我们得到最优情况下所需要的最少专注度为（f = a*（a+1）/2*（m+1-r）+（a+1）（a+2）/2r）。
最后我们对答案直接进行二分查找，寻找最少休息需求数，再根据上述公式检查该休息数下能否合法的打完全部的m层塔，如果可以缩小右边界否则扩大左边界。
同时因为最差的情况下我们可以休息爬塔休息爬塔…这样循环去完成所有的爬塔，所以最终休息的最少次数一定不超过爬塔总数，时间复杂度为T*log(m)。
J代码参考.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
void solve(){
int n,m;
cin>>n>>m;
ll l=0,r=1e9;
auto check=[&](ll x)->bool
{
int a=m/(x+1),r=m%(x+1);
ll f=1ll*a*(a+1)/2*(x+1-r)+1ll*(a+1)*(a+2)/2*r;
return (f<=n+x-1);
};
ll ans=-1;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
ans=1ll*mid+m;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T=1; cin>>T;
while (T--){
solve();
}
return 0;
}
京公网安备 11010502036488号