Znzryb's Blog

重载小于号运算符使min以字符长度返回值

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

思路讲解

AC代码

应该输出bb

源代码

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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 bool comPareLen(const string &a,const string &b){
	return SZ(a)<SZ(b);
}

inline void solve(){
	string s=min({string("aba"),string("bb"),string("aaa")},comPareLen);
	cout<<s<<"\n";
	
}

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

*/

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

P3382 三分

Posted on 2025-05-03 Edited on 2026-04-06

思路讲解

三分模版

注意L=mid，R=mid。

AC代码

源代码

// Problem: P3382 三分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3382
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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 long double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr DB eps=1e-8;

ll N,K,T;
DB fac[18];
DB L,R;

inline DB binpow(DB x,ll k){
	DB res=1;
	while(k){
		if(k&1) res*=x;
		k>>=1;
		x*=x;
	}
	return res;
}

inline DB F(DB x){
	DB res=0;
	FOR(i,0,N){
		res+=fac[i]*binpow(x,i);
	}
	return res;
}

inline void solve(){
	cin>>N>>L>>R;
	ROF(i,N,0){
		cin>>fac[i];
	}
	while(R-L>eps){	// 保证为凸性函数在[l,r]内
		DB mid=L+(R-L)/2;
		if(F(mid-eps)>F(mid+eps)){
			R=mid;
		}else{
			L=mid;
		}
	}
	cout<<setprecision(15)<<L<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/215785806
*/

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

ABC-403-F - Shortest One Formula

Posted on 2025-05-03 Edited on 2026-04-06

思路讲解

竟然每种表达式都能转移

如果是推这个式子的长度，可以这么推

// Problem: F - Shortest One Formula
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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;

ll N,M,K,T,A[MAXN];
// [0]是用加法拼出来的,[1]是用乘法拼出来的，或者不用加括号（这个属性会影响括号）
ll dp[MAXN][2];
ll dx[5]={1,11,111,1111};

// 其实正推还是比较难的，但是可以倒推（记忆化搜索）

// ll dfs(ll x){
	// ll res=0;
// 	
	// FOR(i,2,sqrtl(x)){
		// if(x%i==0){
// 			
		// }
	// }
// }

inline void solve(){
	cin>>N;
	FOR(i,1,N){
		dp[i][1]=INF;
		dp[i][0]=INF;
	}
	// dfs(N);
	dp[1][1]=1;
	dp[1][0]=1;
	dp[11][1]=2;
	dp[11][0]=2;
	dp[111][1]=3;
	dp[111][0]=3;
	dp[1111][1]=4;
	dp[1111][0]=4;
	FOR(i,2,N){
		// dp[i]=dp[i-1]
		FOR(j,2,sqrtl(i)){	// 乘法
			if(i%j==0){
				// 			一个乘号
				dp[i][1]=min({dp[j][1]+dp[i/j][1]+1,dp[i][1],
					// 一个乘号+一对括号                          一个乘号+两对对括号
					dp[j][0]+dp[i/j][1]+3,dp[j][1]+dp[i/j][0]+3,dp[j][0]+dp[i/j][0]+5});
			}
		}
		FOR(j,1,i-1){
			//                     就是一个加号嘛
			dp[i][0]=min({dp[i][0],dp[j][0]+dp[i-j][0]+1,
				dp[j][0]+dp[i-j][1]+1,dp[j][1]+dp[i-j][1]+1,dp[j][1]+dp[i-j][0]+1});
		}
		// ROF(j,N-1,2){
// 			
		// }
	}
	cout<<min(dp[N][0],dp[N][1])<<"\n";
}

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

*/

那么我们异想天开一点，直接转移字符串那

转移字符串的程序

FOR(j,2,sqrtl(i)){	// 乘法
	if(i%j==0){
		// 			一个乘号
		dp[i][1]=min({dp[i][1],dp[j][1]+"*"+dp[i/j][1],           
			"("+dp[j][0]+")"+"*"+dp[i/j][1],
			dp[j][1]+"*"+"("+dp[i/j][0]+")",
			"("+dp[j][0]+")"+"*"+"("+dp[i/j][0]+")"},comPareLen );
	}
}
FOR(j,1,i-1){
	//                     就是一个加号嘛
	dp[i][0]=min({dp[i][0],dp[j][0]+"+"+dp[i-j][0],
		dp[j][0]+"+"+dp[i-j][1],dp[j][1]+"+"+dp[i-j][1],
		dp[j][1]+"+"+dp[i-j][0] },comPareLen);
}
dp[i][1]=min(dp[i][1],"("+dp[i][0]+")",comPareLen);

AC代码

源代码

// Problem: F - Shortest One Formula
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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>(2e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
const string INFstr=string(1003,'a');

ll N,M,K,T;
// [0]是用加法拼出来的,[1]是用乘法拼出来的，或者不用加括号（这个属性会影响括号）
string dp[MAXN][2];
ll dx[5]={1,11,111,1111};

// 其实正推还是比较难的，但是可以倒推（记忆化搜索）

// ll dfs(ll x){
	// ll res=0;
// 	
	// FOR(i,2,sqrtl(x)){
		// if(x%i==0){
// 			
		// }
	// }
// }
inline bool comPareLen(const string &a,const string &b){
	return SZ(a)<SZ(b);
}

inline void solve(){
	cin>>N;
	FOR(i,1,N){
		dp[i][1]=INFstr;
		dp[i][0]=INFstr;
	}
	// dfs(N);
	dp[1][1]="1";
	dp[1][0]="1";
	dp[11][1]="11";
	dp[11][0]="11";
	dp[111][1]="111";
	dp[111][0]="111";
	dp[1111][1]="1111";
	dp[1111][0]="1111";
	FOR(i,2,N){
		if(i==11 || i==111 || i==1111) continue;
		// dp[i]=dp[i-1]
		FOR(j,2,sqrtl(i)){	// 乘法
			if(i%j==0){
				// 			一个乘号
				dp[i][1]=min({dp[i][1],dp[j][1]+"*"+dp[i/j][1],           
					"("+dp[j][0]+")"+"*"+dp[i/j][1],
					dp[j][1]+"*"+"("+dp[i/j][0]+")",
					"("+dp[j][0]+")"+"*"+"("+dp[i/j][0]+")"},comPareLen );
			}
		}
		FOR(j,1,i-1){
			//                     就是一个加号嘛
			dp[i][0]=min({dp[i][0],dp[j][0]+"+"+dp[i-j][0],
				dp[j][0]+"+"+dp[i-j][1],dp[j][1]+"+"+dp[i-j][1],
				dp[j][1]+"+"+dp[i-j][0] },comPareLen);
		}
		dp[i][1]=min(dp[i][1],"("+dp[i][0]+")",comPareLen);
		// ROF(j,N-1,2){
// 			
		// }
#ifdef LOCAL
   	cerr<<"i:"<<i<<" "<<dp[i][0]<<'\n';
   	cerr<<"i:"<<i<<" "<<dp[i][1]<<'\n';
   	cerr<<"\n";
#endif
	}
	cout<<min(dp[N][0],dp[N][1],comPareLen)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://atcoder.jp/contests/abc403/submissions/65417394
(1+1)*(1+1+1)*((1+1)*(1+1+1)*11+1)+1

1+(1+1+1)*(1+11+11+111)
*/

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

ABC-403-E - Forbidden Prefix

Posted on 2025-05-02 Edited on 2026-04-06

思路讲解

也是体验了一把学霸的感觉，一编译就本地AC，然后交上去就一次AC了。

比那个D题还要顺，只能说我的字符串哈希还是比较熟练的。

这个如果Hx里有比该前缀更小的单元，直接放弃。

FOR(i,0,SZ(s)-1){
	hax+=s[i]*Base[i];
	// 如果Hx里有比该前缀更小的单元，直接放弃
	if(Hx.find(hax)!=Hx.end()){
		needOp=false;
		break;
	}
}

AC代码

https://atcoder.jp/contests/abc403/submissions/65404782

源代码

// Problem: E - Forbidden Prefix
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,Q,T;
set<arr> g[MAXN];
bool vis[MAXN];
ll Base[MAXN];

// 自然溢出取模

inline void solve(){
	cin>>Q;
	set<ll> Hx;
	Base[0]=1;
	FOR(i,1,MAXN/2){
		Base[i]=Base[i-1]*131;
	}
	ll ans=0;
	FOR(q,1,Q){
		ll t;string s;
		cin>>t>>s;
		// the number of strings in Y that have no element of X as a prefix
		if(t==1){
			ll hax=0;
			bool needOp=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				// 如果Hx里有比该前缀更小的单元，直接放弃
				if(Hx.find(hax)!=Hx.end()){
					needOp=false;
					break;
				}
			}
			ll len=SZ(s);
			if(needOp){
				auto itb=g[len-1].lower_bound({hax,0});
				auto ite=g[len-1].lower_bound({hax,INF});
				for(auto it=itb;it!=ite;++it){
					ll que=(*it)[1];
					if(vis[que]) continue;
					vis[que]=true;
					--ans;
				}
				Hx.insert(hax);
			}
			cout<<ans<<"\n";
		}else{
			ll hax=0;
			bool needAdd=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				if(Hx.find(hax)!=Hx.end()){
					needAdd=false;
					break;
				}
			}
			if(needAdd){
				++ans;
				ll hax=0;
				FOR(i,0,SZ(s)-1){
					hax+=s[i]*Base[i];
					g[i].insert({hax,q});
				}
			}
			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，TLE，MLE……）

ABC-403-D - Forbidden Difference

Posted on 2025-05-02 Edited on 2026-04-06

思路讲解

这道题目，可以通过转化，变为给你一张链图，问你如何删去权重之和最少的点，使这张链图完全不联通。

这个问题可以通过dp解决。

dp[0][0]=0,dp[0][1]=ls.front();
FOR(j,1,SZ(ls)-1){
	// 当前带着的=之前不带的 之前带着砍掉之前带着的
	dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
	// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
	dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
}
ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);

AC代码

https://atcoder.jp/contests/abc403/submissions/65403420

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	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://atcoder.jp/contests/abc403/submissions/65403420
*/

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

WA，最后发现是循环范围出了问题

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.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)

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>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		// if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1-D;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	cout<<ans<<"\n";
}

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

*/