Znzryb's Blog

Edu-180-E. Tree Colorings

Posted on 2025-06-29 Edited on 2026-02-17

思路讲解

AC代码

源代码

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

P3812 【模板】线性基

Posted on 2025-06-29 Edited on 2026-02-17

思路讲解

AC代码

源代码

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

BD202429 毕业照(binary lift facilitate the calculation)

Posted on 2025-06-28 Edited on 2026-02-17

思路讲解

前两问用二分，贪心解决。

最后一问需要使用双指针+倍增法。

AC代码

https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD

源代码

// https://www.matiji.net/exam/brushquestion/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,lT,H[MAXN],D;
/*

*/
inline void init(){
	
}
struct cmpda{
	bool operator()(ll a,ll b){
		return H[a]<H[b];
	}
};
struct cmpxiao{
	bool operator()(ll a,ll b){
		return H[a]>H[b];
	}
};
inline void solve(){
	cin>>N>>K>>D;
	init();
	FOR(i,1,N){
		cin>>H[i];
	}
	ll lans2=0;
	auto check1=[&](ll mid)->bool{
		ll bp=1,res=0;
		while(bp<=N){
			ll i=bp;
			ll mn=H[i],mx=H[i];
			bool isB=false;
			FOR(j,i,N){
// #ifdef LOCAL
    // debug(H[j]-mn);
    // debug(H[j]-mx);
// #endif
				if(abs(H[j]-mn)<=mid && abs(H[j]-mx)<=mid){
// #ifdef LOCAL
    // cerr<<"OKAY\n";
// #endif
					mn=min(H[j],mn);
					mx=max(H[j],mx);
				}else{
					bp=j;
					++res;
					isB=true;
					break;
				}
				
			}
			if(!isB){
				++res;
				break;
			}
		}
// #ifdef LOCAL
	// debug(mid);
    // debug(res);
// #endif
		lans2=res;
		if(res>K){
			return false;
		}
		return true;
	};
	ll l=0,r=mod;
	while(l<r){
		ll mid=l+r>>1;
		if(check1(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
	check1(D);
	cout<<lans2<<"\n";
	vector<ll> nextPos(N+5,0);
	auto cal=[&]()->void{
		ll bp=1,res=0;
		priority_queue<ll,vector<ll>,cmpda> da;
		priority_queue<ll,vector<ll>,cmpxiao> xiao;
		FOR(i,1,N){
			bool isB=false;
			FOR(j,bp,N){
				while(da.empty()==false && (da.top()<i || da.top()>j) ){
					da.pop();
				}
				while(xiao.empty()==false && (xiao.top()<i || xiao.top()>j)){
					xiao.pop();
				}
				ll mx=da.empty()?H[j]:H[da.top()],mn=xiao.empty()?H[j]:H[xiao.top()];
				if(abs(H[j]-mx)<=D && abs(H[j]-mn)<=D){
					xiao.push(j);
					da.push(j);
				}else{
					bp=j;
					nextPos[i]=j-1;
// #ifdef LOCAL
    // debug(i);
// #endif
					isB=true;
					break;
				}
			}
			if(!isB){
				nextPos[i]=N;
				bp=N+1;
			}
		}
	};
	cal();
	ll mx_k=ceil(log2(K+1))+1;
	bitset<32> bik(K);
	vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
	ROF(i,N+1,1){
		jump[i][0]=i<=N?nextPos[i]+1:N+1;
		// if(i==N){
			// FOR(j,0,mx_k) jump[i][j]=N+1;
			// continue;
		// }
		FOR(j,1,mx_k){
			jump[i][j]=jump[jump[i][j-1]][j-1];
			// if(jump[i][j]==0) jump[i][j]=N+1;
		}
	}
	// FOR(t,0,mx_k){
		// FOR(i,1,N){
			// if(t==0) {jump[i][t]=nextPos[i]+1;continue;}
			// jump[i][t]=jump[jump[i][t-1]][t-1];
		// }
	// }
	ll ans=0;
// #ifdef LOCAL
    // FOR(i,1,N+1){
    	// FOR(j,0,mx_k){
    		// cerr<<jump[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // FOR(i,1,N){
    	// cerr<<nextPos[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	FOR(i,1,N){
		ll lans=0,idx=i;
		FOR(j,0,mx_k){
			if(bik[j]){
				idx=jump[idx][j];
			}
// #ifdef LOCAL
   	// debug(i);debug(idx);
// #endif
		}
		lans=idx-i;
		ans=max(ans,lans);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
*/

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

调了比较久，最后终于是调出来了。最重要的就是这个倍增的板子，需要从N+1开始遍历。

vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
	ROF(i,N+1,1){
		jump[i][0]=i<=N?nextPos[i]+1:N+1;
		FOR(j,1,mx_k){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}

2025北京市赛-G. 萤火虫难题（转换状态设计思路，以倍数为核心）

Posted on 2025-06-27 Edited on 2026-02-17

思路讲解

那么首先相邻，状态转移只需要考虑最后一个（前缀dp）。

AC代码

https://qoj.ac/submission/1125813

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,lT,C[MAXN],W[MAXN];
/*

*/
ll dp[MAXN];
inline void init(){
	
}
//  minp[i] 存储的是i的最小素因数
vector<ll> minp,primes;
void sieve(ll n){
	minp.assign(n+5,0);
	for(int i=2;i<=n;++i){
		if(minp[i]==0){		// 是素数
			minp[i]=i;
			primes.push_back(i);
		}
		for(auto p:primes){
			if(i*p>n){	// 超范围了
				break;
			}
			minp[i*p]=p;
			// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
			// i * p_next = (p * k) * p_next 最小的应该是p
			if(p==minp[i]){
				break;
			}
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>W[i];
	}
	FOR(i,1,N){
		cin>>C[i];
	}
	ll mxw=*max_element(W+1,W+1+N);
	sieve(mxw);
	// 并按它们在路边的顺序排成一列（这样就不必考虑后效性了）
	//        最大值       次大值
	vector<ll> dp(mxw+5,0),dp2(mxw+5,0),col(mxw+5,0);
	for(int i=1;i<=N;++i){
		vector<ll> prs;
		for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
			ll p=minp[j];
			prs.pb(p);
		}
		sort(all(prs));
		prs.resize(unique(all(prs))-prs.begin());
		// 需要这个max是因为这个转移只关心最后一位
		//	所以应该将素因数状态更新为最大
		ll mx=0;	
		for(auto p:prs){
			if(col[p]!=C[i]){
				mx=max(mx,dp[p]+1);
			}else{
				mx=max(mx,dp2[p]+1);
			}
		}
		for(auto p:prs){
			if(col[p]!=C[i]){
				if(mx>dp[p]){
					dp2[p]=dp[p];
					dp[p]=mx;
					col[p]=C[i];
				}else if(mx>dp2[p]){
					dp2[p]=mx;
				}
			}else{
				if(mx>dp[p]) dp[p]=mx;
			}
		}
	}
	// 不需要考虑1，因为1和任何数都互素
	ll ans=1;
	for(int i=2;i<=mxw;++i){
		ans=max({ans,dp[i],dp2[i]});
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
WA 
https://qoj.ac/submission/1125736

*/

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

https://qoj.ac/submission/1125736

//        最大值       次大值
vector<ll> dp(mxw+5,0),dp2(mxw+5,0),col(mxw+5,0);
for(int i=1;i<=N;++i){
	vector<ll> prs;
	for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
		ll p=minp[j];
		prs.pb(p);
	}
	sort(all(prs));
	prs.resize(unique(all(prs))-prs.begin());
	for(auto p:prs){
		if(col[p]!=C[i]){
			dp2[p]=dp[p];
			dp[p]+=1;
			col[p]=C[i];
		}else{
			dp2[p]+=1;
		}
	}
}

2025北京市赛-E. 布置 WAP

Posted on 2025-06-26 Edited on 2026-02-17

思路讲解

这种方式更稳定，精度更高（其实就是用这种方式过了）

      // 方案二：使用固定迭代次数（100次）进行三分搜索。
      // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
for(int i=0; i<100; ++i){
	DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
	DB mid2 = r - (r-l)/3.0;
	if(fx(mid1) > fx(mid2)){
		l=mid1;
	}else{
		r=mid2;
	}
}
printf("%.11f\n",fx(l));

AC代码

https://codeforces.com/gym/105851/my#

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
// 采用固定迭代次数的方案，不再需要eps常量
// constexpr double eps=1e-10;

ll N,M,Q,X[MAXN],Y[MAXN],K,lT,A[MAXN];
/*

*/
inline void init(){
	// 根据需要可以清空X和Y数组，但在您的框架中，每次N都会被重置，
    // 旧数据不会被访问，所以这里为空也可以。
}

inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>X[i]>>Y[i];
	}
	ll a,b,c;
	cin>>a>>b>>c;

	auto fx=[&](DB mid)->DB{
		DB x=mid,y=-(DB)a*x/b-(DB)c/b; // 显式转换一下类型，避免整数除法
		DB mx=0;
		FOR(i,1,N){
            // 直接计算距离的平方，最后再开方，可以减少sqrt的调用次数，稍微快一点
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	auto fy=[&](DB mid)->DB{
		DB y=mid,x=-(DB)b*y/a-(DB)c/a; // 显式转换
		DB mx=0;
		FOR(i,1,N){
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	DB l=-2e8,r=2e8; // 搜索范围，根据题目数据范围可能需要调整

    // a, b, c 是 ll, 在除法中最好转成 DB
	if(b!=0){
        // 方案二：使用固定迭代次数（100次）进行三分搜索。
        // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
			DB mid2 = r - (r-l)/3.0;
			if(fx(mid1) > fx(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fx(l));
	}else{
        // 同理，处理直线垂直的情况
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0;
			DB mid2 = r - (r-l)/3.0;
			if(fy(mid1) > fy(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fy(l));
	}
	
}

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