Znzryb's Blog

CF-995-E. Best Price

Posted on 2025-05-11 Edited on 2026-02-16

思路讲解

二分是假的，离散化，差分是真的。

还是有一定难度的，一是要想到离散化+差分快速判断该数是否符合条件。第二是要缩小答案范围，注意到，只有a和b才能成为答案（a+1不就差评了？那为什么不选b？—————a-1不就还好评那？那为什么不选a？）

AC代码

https://codeforces.com/contest/2051/submission/319412463

源代码

// Problem: E. Best Price
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/contest/2051/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T;
ll ans=0;
arr ab[MAXN];
ll diff[MAXN],Sum[MAXN];
/*
不难注意到，我们只要在合法的价格上，求出
*/
inline void solve(){
	cin>>N>>K;
	vector<ll> li,Vals,B;
	FOR(i,0,3*N+5){
		Sum[i]=0;
		diff[i]=0;
	}
	FOR(i,1,N){
		cin>>ab[i][0];
		li.pb(ab[i][0]+1);
		li.pb(ab[i][0]);
		Vals.pb(ab[i][0]);
	}
	FOR(i,1,N){
		cin>>ab[i][1];
		li.pb(ab[i][1]);
		Vals.pb(ab[i][1]);
		B.pb(ab[i][1]);
	}
	sort(all(B));
	uniVec(li);
	uniVec(Vals);
	li.pb(li.back()+1);
	// li.insert(-INF,0);
	FOR(i,1,N){
		// 是从a+1～b这段需要加一
		ll beg=lower_bound(all(li),ab[i][0]+1)-li.begin(),
		ed=lower_bound(all(li),ab[i][1])-li.begin();
		diff[beg]+=1;
		diff[ed+1]-=1;
	}
	Sum[0]=diff[0];
	FOR(i,1,3*N){
		Sum[i]=Sum[i-1]+diff[i];
	}
#ifdef LOCAL
	cerr<<"Sum:";
    FOR(i,0,2*N){
    	cerr<<Sum[i]<<" ";
    }
    cerr<<"\n";
    DEBUG(li);
    DEBUG(B);
#endif
	ans=0;
	FOR(i,0,SZ(Vals)-1){
		ll val=Vals[i];
		ll idx=lower_bound(all(li),val)-li.begin();
#ifdef LOCAL
    if(val==1){
    	debug(Sum[idx]);
    	debug(K);
    }
#endif
		if(Sum[idx]<=K){
			// B中>=val的值有多少个
			ll ind=lower_bound(all(B),val)-B.begin();
			ll num=N-ind;
			ans=max(num*val,ans);
#ifdef LOCAL
    debug(ind);
#endif
		}
	}
	
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2051/submission/319412463
*/

心路历程（WA，TLE，MLE……）

三分做法，WA了

https://codeforces.com/contest/2051/submission/319133918

源代码

// Problem: E. Best Price
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/contest/2051/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN],B[MAXN];
ll ans=0;
/*

*/
inline ll check(ll x){
	ll res=0,neg=0;
#ifdef LOCAL
    debug(x)
#endif
	FOR(i,1,N){
		if(x<=A[i]){
			res+=x;
		}else if(x>A[i] && x<=B[i]){
			neg+=1;
			res+=x;
		}else{
			continue;
		}
	}
#ifdef LOCAL
    debug(neg)debug(res)
#endif
	if(neg>K) return 1;
	else {ans=max(ans,res);return res;}
}
inline void solve(){
	cin>>N>>K;
	FOR(i,1,N){
		cin>>A[i];
	}
	ll maxB=0;
	FOR(i,1,N){
		cin>>B[i];
		maxB=max(maxB,B[i]);
	}
	ll l=0,r=maxB+3;ans=0;
	while(r-l>2){
		ll mid1=l+(r-l)/3,mid2=r-(r-l)/3;
#ifdef LOCAL
    debug(l)debug(r)debug(mid1)debug(mid2)
#endif
		if(check(mid1)>check(mid2)){
			r=mid2;
		}else{
			l=mid1;
		}
#ifdef LOCAL
    cerr << '\n';
#endif
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

后面几次WA是因为清空不够多，sum没加够。

CF-1009-F. Counting Necessary Nodes

Posted on 2025-05-10 Edited on 2026-02-16

思路讲解

那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形。

图中的1，2，3，4对应加粗斜体的dfs部分。

	ROF(i,log2(b-a),0){
		ll b_=b/pow2[i]*pow2[i],a_=ceil(a*1.0/pow2[i])*pow2[i];
		ll d_=d/pow2[i]*pow2[i],c_=ceil(c*1.0/pow2[i])*pow2[i];
		if(b_<=a) continue;
		if(a_>=b) continue;
		if(d_<=c) continue;
		if(c_>=d) continue;
		if(a_+pow2[i]>b_) continue;
		if(c_+pow2[i]>d_) continue;
		ans+=abs(a_-b_)/pow2[i]*(abs(c_-d_)/pow2[i]);
#ifdef LOCAL
    debug(a_)
    debug(b_)
    debug(c_)
    debug(d_)
    debug(pow2[i])
    debug(ans)
    cerr<<"\n";
#endif
		dfs(a,a_,c,d);
		dfs(b_,b,c,d);
		dfs(a_,b_,c,c_);
		dfs(a_,b_,d_,d);
		return;
	}

AC代码

https://codeforces.com/contest/2074/submission/319087712

源代码

// Problem: F. Counting Necessary Nodes
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/F
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
/*
那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形
去分是不大可能的，也不大可能是数学方法。
我认为其实就是
*/
ll ans=0;
ll pow2[40];
void dfs(ll a,ll b,ll c,ll d){
	if(a>=b || c>=d) return;
// #ifdef LOCAL
    // debug(a)debug(b)debug(c)debug(d)
// #endif
	if(b-a>d-c){
		swap(a,c);
		swap(b,d);
	}
#ifdef LOCAL
    debug(a)debug(b)debug(c)debug(d)
#endif
	ROF(i,log2(b-a),0){
		ll b_=b/pow2[i]*pow2[i],a_=ceil(a*1.0/pow2[i])*pow2[i];
		ll d_=d/pow2[i]*pow2[i],c_=ceil(c*1.0/pow2[i])*pow2[i];
		if(b_<=a) continue;
		if(a_>=b) continue;
		if(d_<=c) continue;
		if(c_>=d) continue;
		if(a_+pow2[i]>b_) continue;
		if(c_+pow2[i]>d_) continue;
		ans+=abs(a_-b_)/pow2[i]*(abs(c_-d_)/pow2[i]);
#ifdef LOCAL
    debug(a_)
    debug(b_)
    debug(c_)
    debug(d_)
    debug(pow2[i])
    debug(ans)
    cerr<<"\n";
#endif
		dfs(a,a_,c,d);
		dfs(b_,b,c,d);
		dfs(a_,b_,c,c_);
		dfs(a_,b_,d_,d);
		return;
	}
}
inline void solve(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ans=0;
	dfs(a,b,c,d);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,35){
		pow2[i]=2*pow2[i-1];
	}
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<"-------------"<< '\n';
#endif
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2074/submission/319087712
*/

心路历程（WA，TLE，MLE……）

直接模拟4叉树，TLE

https://codeforces.com/contest/2074/submission/319043232

源代码

// Problem: F. Counting Necessary Nodes
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/F
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
/*
那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形
去分是不大可能的，也不大可能是数学方法。
我认为其实就是
*/
ll ans=0;
ll pow2[40];
void dfs(ll a,ll b,ll c,ll d,ll a1,ll b1,ll c1,ll d1){	// 模拟4叉树的这个过程就行
	if(a>=b || c>=d) return;	// 出现了不合法的表达形式，退出
	if(b<=a1 || a>=b1) return;	// 不可能情况退出
	if(c>=d1 || d<=c1) return;
	ll midAb=(a1+b1)/2,midCd=(c1+d1)/2;
	if(a==a1 && b==b1 && c==c1 && d==d1){
		++ans;
#ifdef LOCAL
    debug(a)debug(b)debug(c)debug(d);
    cerr<<"\n";
#endif
		return;
	}
	// if(a>= midAb && c>=midCd){
		// if(b<=b1 && d<=d1){
			// dfs(a,b,c,d,midAb,b1,midCd,d1);
		// }else if(b>b1 && d<=d1){
			// dfs(a,b1,c,d,midAb,b1,midCd,d1);
		// }
// 		
	// }else if(a>=midAb && d<=midCd){
		// dfs(a,b,c,d,midAb,b1,c1,midCd);
	// }else if(b<=midAb && c>=midCd){
		// dfs(a,b,c,d,a1,midAb,midCd,d1);
	// }else if(b<=midAb && d<=midCd){
		// dfs(a,b,c,d,a1,midAb,c1,midCd);
	// }
	dfs(a,min(b,midAb),c,min(d,midCd),a1,midAb,c1,midCd);
	dfs(max(midAb,a),b,c,min(d,midCd),midAb,b1,c1,midCd);
	dfs(a,min(b,midAb),max(midCd,c),d,a1,midAb,midCd,d1);
	dfs(max(midAb,a),b,max(midCd,c),d,midAb,b1,midCd,d1);
}
inline void solve(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ans=0;
	ll idx=ceil(log2(max(b,d)));
	dfs(a,b,c,d,0,pow2[idx],0,pow2[idx]);	// 1048576 为2的20次方
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,35){
		pow2[i]=2*pow2[i-1];
	}
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<"-------------"<< '\n';
#endif
	}
	// solve();
	return 0;
}
/*

*/

CF-1009-E. Empty Triangle

Posted on 2025-05-09 Edited on 2026-02-16

思路讲解

呃，这题虽然套着一个几何的背景，但我认为考察重点并不在几何上。

正解竟然就是随机化做法？这题的意义是什么那？我也不是很理解。

AC代码

https://codeforces.com/contest/2074/submission/318930035

源代码

// Problem: E. Empty Triangle
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];

inline void solve(){
	cin>>N;
	if(N==3){
		cout<<"! 1 2 3"<<endl;
		return;
	}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	uniform_int_distribution<> distrib(1,N),dis3(0,2);
	vector<ll> quer={distrib(rng),distrib(rng),distrib(rng)};
	while(quer[0]==quer[1] || quer[1]==quer[2] || quer[0]==quer[2]){
		quer={distrib(rng),distrib(rng),distrib(rng)};
	}
	ll idx=0;
	while(true){
		cout<<"? "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
		ll res;
		cin>>res;
		if(res==0){
			cout<<"! "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
			break;
		}else{
			quer[dis3(rng)]=res;
			++idx;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2074/submission/318917809
AC https://codeforces.com/contest/2074/submission/318930035
*/

心路历程（WA，TLE，MLE……）

TLE

https://codeforces.com/contest/2074/submission/318918084

源代码

// Problem: E. Empty Triangle
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];

inline void solve(){
	cin>>N;
	if(N==3){
		cout<<"! 1 2 3"<<endl;
		return;
	}
	vector<ll> quer={1,2,3};
	ll idx=0;
	while(true){
		cout<<"? "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
		ll res;
		cin>>res;
		if(res==0){
			cout<<"! "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
			break;
		}else{
			quer[idx%3]=res;
			++idx;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2074/submission/318917809

*/

CF-1009-D. Counting Points

Posted on 2025-05-09 Edited on 2026-02-16

思路讲解

其实不难，挺简单的。

我的思路是由于限制了半径的大小的总和，所以说可以把每个圆的每个x都扫一遍，扫到这个x了这个圆在这个x上包含了几个点就很容易知道了。然后把x上有多少个点被包含存在Cnt里就好了，最后扫一遍加起来就好。

FOR(i,1,N){
	ll r=xr[i][1],x=xr[i][0];
	FOR(j,x-r,x+r){
		ll len=abs(j-x);
		ll yCanChoose=sqrtl(r*r-len*len);
		yCanChoose*=2,yCanChoose+=1;
		if(Cnt.find(j)==Cnt.end()){
			Cnt[j]=yCanChoose;
		}else{
			Cnt[j]=max(yCanChoose,Cnt[j]);
		}
	}
}
ll ans=0;
for(auto ele:Cnt){
	ans+=ele.se;
}

AC代码

https://codeforces.com/contest/2074/submission/318915158

源代码

// Problem: D. Counting Points
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T; // X[MAXN],R[MAXN];
arr xr[MAXN];
ll rToNum[MAXN];

inline void solve(){
	cin>>N>>M;
	map<ll,ll> Cnt;
	FOR(i,1,N){
		cin>>xr[i][0];
	}
	FOR(i,1,N){
		cin>>xr[i][1];
	}
	// sort(xr+1,xr+1+N);
	// ll ans=0;
	// FOR(i,1,N){
		// ll r=xr[i][1];
		// ans+=r;
	// }
	FOR(i,1,N){
		ll r=xr[i][1],x=xr[i][0];
		FOR(j,x-r,x+r){
			ll len=abs(j-x);
			ll yCanChoose=sqrtl(r*r-len*len);
			yCanChoose*=2,yCanChoose+=1;
			if(Cnt.find(j)==Cnt.end()){
				Cnt[j]=yCanChoose;
			}else{
				Cnt[j]=max(yCanChoose,Cnt[j]);
			}
		}
	}
	ll ans=0;
	for(auto ele:Cnt){
		ans+=ele.se;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	FOR(i,1,MAXN-5){
		
	}
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2074/submission/318915158
*/

心路历程（WA，TLE，MLE……）

CF-1011-D. Serval and Kaitenzushi Buffet

Posted on 2025-05-08 Edited on 2026-02-16

思路讲解

K其实就是吃掉一个寿司所需要花费的时间。
你可以不停拿，但是最后要吃完，拿的时候不能吃。

这个其实是个贪心，这个把题目完全读完就可以得出。

https://www.luogu.com.cn/article/flnzpg4m 这个题解写的很清楚。

总的来说，其实就是这么选一定是合法的，但不一定最优。

而且可以证明所有的O是不能再往后移了，只能往前移。当然，往前移一定是合法的。

具体而言是这样的。

ll idx=0;
ROF(i,N,1){
	++idx;
	if(idx%(K+1)==0){
		spec[i]=true;
	}
}
priority_queue<ll> pq;
ll ans=0;
FOR(i,1,N){
	pq.push(D[i]);
	if(spec[i]){
		ans+=pq.top();
		pq.pop(); // 记得要弹出，不用清空，往前移比较多也是可以接受的。
	}
}

AC代码

https://codeforces.com/contest/2085/submission/319924135

源代码

// Problem: D. Serval and Kaitenzushi Buffet
// Contest: Codeforces - Codeforces Round 1011 (Div. 2)
// URL: https://codeforces.com/contest/2085/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,D[MAXN];
bool spec[MAXN];
/*
K其实就是吃掉一个寿司所需要花费的时间。
你可以不停拿，但是最后要吃完，拿的时候不能吃。

*/
inline void solve(){
	cin>>N>>K;
	FOR(i,0,N+5){
		D[i]=0;
		spec[i]=false;
	}
	FOR(i,1,N){
		cin>>D[i];
	}
	ll idx=0;
	ROF(i,N,1){
		++idx;
		if(idx%(K+1)==0){
			spec[i]=true;
		}
	}
	priority_queue<ll> pq;
	ll ans=0;
	FOR(i,1,N){
		pq.push(D[i]);
		if(spec[i]){
			ans+=pq.top();
			pq.pop();
		}
	}
#ifdef LOCAL
    debugN(spec,N);
#endif
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2085/submission/319924135
*/