Znzryb's Blog

Starter190-ORSUBSORT

Posted on 2025-06-13 Edited on 2026-04-06

思路讲解

codeChef题目可以看viewsolution，就是下面这个链接

inline ll diff(ll a,ll b){
	if(a<=b) return 0;
	bitset<32> ba(a);		// 存储是正序的
	bitset<32> bb(b);
	ROF(i,31,0){
		ll bai=ba[i],bbi=bb[i];
		if(bai-bbi==1){
			return 1<<i;
		}
	}
}

AC代码

https://www.codechef.com/viewsolution/1165814370

源代码

// Problem: Subsequence Sort
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/ORSUBSORT
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// 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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

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

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

*/
inline void init(){
	
}
inline ll diff(ll a,ll b){
	if(a<=b) return 0;
	bitset<32> ba(a);		// 存储是正序的
	bitset<32> bb(b);
	ROF(i,31,0){
		ll bai=ba[i],bbi=bb[i];
		if(bai-bbi==1){
			return 1<<i;
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	bool isSort=true;
	FOR(i,2,N){
		if(A[i-1]>A[i]){isSort=false;break;}
	}
	if(isSort){cout<<0<<"\n";return;}
	ll mxD=0,mx=A[1];
	FOR(i,2,N){
		mxD=max(mxD,diff(mx,A[i]));
		mx=max(mx,A[i]);
	}
	cout<<mxD<<"\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.codechef.com/viewsolution/1165814370
*/

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

CF-1030-B. Make It Permutation

Posted on 2025-06-12 Edited on 2026-04-06

思路讲解

行上面反转，使列上面为排列。

注意到，可以对称的操作，反转1，i，使得 i 为首，再反转N-i+1，N，

// 第一阶段操作
// 对行 i = 1 到 n-1, 翻转子数组 [i, n]
for (int i = 1; i < n; ++i) {
    std::cout << i << " " << i << " " << n << std::endl;
}

// 第二阶段操作
// 对行 j = 2 到 n, 翻转子数组 [1, j-1]
// 为了让最终矩阵和上面推导的一致，我们倒序循环
for (int i = 1; i < n; ++i) {
    // 操作第 n-i+1 行， 翻转 [1, n-i]
    std::cout << (n - i + 1) << " " << 1 << " " << (n - i) << std::endl;
}

AC代码

源代码

#include <iostream>
#include <vector>
#include <numeric>

// 函数用于解决单个测试用例
void solve() {
    int n;
    std::cin >> n;

    // 总操作数是 (n-1) + (n-1) = 2n-2
    std::cout << 2 * n - 2 << std::endl;

    // 第一阶段操作
    // 对行 i = 1 到 n-1, 翻转子数组 [i, n]
    for (int i = 1; i < n; ++i) {
        std::cout << i << " " << i << " " << n << std::endl;
    }

    // 第二阶段操作
    // 对行 j = 2 到 n, 翻转子数组 [1, j-1]
    // 为了让最终矩阵和上面推导的一致，我们倒序循环
    for (int i = 1; i < n; ++i) {
        // 操作第 n-i+1 行， 翻转 [1, n-i]
        std::cout << (n - i + 1) << " " << 1 << " " << (n - i) << std::endl;
    }
}

int main() {
    // 优化输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

// AC

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

P1347 排序

Posted on 2025-06-12 Edited on 2026-04-06

思路讲解

图论建模，拓扑排序。

拓扑排序的代码（使用BFS kahn‘s算法），通过判断q的大小可以知道其是不是严格的（该题目要求严格的顺序）。

ll trop(const vector<ll> &a,ll siz){
	vector<ll> op=a;
	Ans.clear();
	queue<ll> q;
	ll ret=3;	// 3成功 2不能确定 1冲突
	FOR(i,'A','Z'){
		if(vis[i] && op[i]==0) q.push(i),Ans.pb(i);
	}
	if(SZ(q)>1) ret=2;
	while(!q.empty()){
		if(SZ(q)>1) ret=2;
		ll node=q.front();q.pop();
		ll cnt=0;
		FOR(i,0,SZ(g[node])-1){
			ll lnode=g[node][i];
			op[lnode]-=1;
			if(op[lnode]==0){
				q.push(lnode);
				Ans.pb(lnode);
			}
		}
	}
	if(SZ(Ans)==siz){
		if(SZ(Ans)<N){	// 还没完全确定
			return 2;
		}else{
			return ret;
		}
	}else{	// 说明有环
		return 1;
	}
}

AC代码

https://www.luogu.com.cn/record/220236107

源代码

// Problem: P1347 排序
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1347
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// 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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

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

ll N,M,Q,X,K,lT,A[MAXN];
vector<ll> g[MAXN];		// 记得要清空
bitset<MAXN> vis;
/*

*/
vector<ll> Ans;
inline void init(){
	
}

ll trop(const vector<ll> &a,ll siz){
	vector<ll> op=a;
	Ans.clear();
	queue<ll> q;
	ll ret=3;	// 3成功 2不能确定 1冲突
	FOR(i,'A','Z'){
		if(vis[i] && op[i]==0) q.push(i),Ans.pb(i);
	}
	if(SZ(q)>1) ret=2;
	while(!q.empty()){
		if(SZ(q)>1) ret=2;
		ll node=q.front();q.pop();
		ll cnt=0;
		FOR(i,0,SZ(g[node])-1){
			ll lnode=g[node][i];
			op[lnode]-=1;
			if(op[lnode]==0){
				q.push(lnode);
				Ans.pb(lnode);
			}
		}
	}
	if(SZ(Ans)==siz){
		if(SZ(Ans)<N){	// 还没完全确定
			return 2;
		}else{
			return ret;
		}
	}else{	// 说明有环
		return 1;
	}
}
inline void solve(){
	cin>>N>>M;
	init();
	// Inconsistency found after 2 relations.
	// Sorted sequence determined after 4 relations: ABCD.
	vector<ll> inde(300,0);
	set<char> occ;
	FOR(_,1,M){
		string s;
		cin>>s;
		g[s[0]].pb(s[2]);
		vis[s[0]]=true,vis[s[2]]=true;
		occ.insert(s[0]),occ.insert(s[2]);
		inde[s[2]]+=1;
		ll ret=trop(inde,SZ(occ));
		if(ret==1){
			cout<<"Inconsistency found after "<<_<<" relations.\n";
			return;
		}else if(ret==3){
			cout<<"Sorted sequence determined after "<<_<<" relations: ";
			FOR(i,0,SZ(Ans)-1){
				cout<<char(Ans[i]);
			}
			cout<<".\n";
			return;
		}
	}
	cout<<"Sorted sequence cannot be determined.\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.luogu.com.cn/record/220236107
*/

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

CF-1026-D. Fewer Batteries

Posted on 2025-06-11 Edited on 2026-04-06

思路讲解

检查点之间共有 $m$ 条单向通道。第 $i$ 条通道允许从点 $s_i$ 移动到点 $t_i$ （ $s_i < t_i$ ），但不允许反方向移动。此外，只有当机器人至少拥有 $w_i$ 个充电电池时，才能使用第 $i$ 条通道；否则，它将在途中耗尽电量。

这个 $s_i < t_i$ 尤为关键，这说明了这张图是有向无环图（DAG）。

那么二分做法不用多说，使用天然的拓扑排序以及类似dp做法解决，然后注意斜体加粗部分。

inline bool check(ll mid){
	FOR(i,0,N+5){Mxb[i]=0;}
	FOR(i,1,N){
		if(i!=1 && Mxb[i]==0) continue;
		FOR(j,0,SZ(g[i])-1){
			ll v=g[i][j][0],w=g[i][j][1];
			if(min(mid,Mxb[i]+B[i])>=w){
				Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
				Mxb[v]=min(Mxb[v],mid);
			}
		}
	}
	if(Mxb[N]==0) return false;
	return true;
}

AC代码

https://codeforces.com/contest/2110/submission/324044393

源代码

// Problem: D. Fewer Batteries  D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// 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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

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

ll N,M,Q,X,K,lT,B[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
ll Mxb[MAXN];
// bitset<MAXN> vis;
/*

*/
inline void init(){
	FOR(i,0,N+5){g[i].clear();}
}
inline bool check(ll mid){
	FOR(i,0,N+5){Mxb[i]=0;}
	FOR(i,1,N){
		if(i!=1 && Mxb[i]==0) continue;
		FOR(j,0,SZ(g[i])-1){
			ll v=g[i][j][0],w=g[i][j][1];
// #ifdef LOCAL
    // if(w==10){
    	// debug(Mxb[i]+B[i]);
    // }
// #endif
			if(min(mid,Mxb[i]+B[i])>=w){
				Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
				Mxb[v]=min(Mxb[v],mid);
			}
			// assert(Mxb[i]+B[i]>=w);
		}
	}
#ifdef LOCAL
	debug(mid);
    FOR(i,1,N){debug(i);debug(Mxb[i]);}
    cerr<<"\n";
#endif
	if(Mxb[N]==0) return false;
	return true;
}
inline void solve(){
	cin>>N>>M;
	init();
	FOR(i,1,N){
		cin>>B[i];
	}
	ll mxw=0;
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		// 把g反过来
		// g[v].pb({u,w});
		g[u].pb({v,w});
		mxw=max(mxw,w);
	}
	ll l=1;ll r=mxw;
	if(!check(r)){cout<<-1<<"\n";return;}
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
}

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

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

TLE，该代码一个点被访问多次，那么其所有边都将重新遍历一次。

源代码

// Problem: D. Fewer Batteries  D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// 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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

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

ll N,M,Q,X,K,lT,B[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
ll Mx[MAXN];
bitset<MAXN> vis;
/*

*/
inline void init(){
	FOR(i,0,N+5){vis[i]=false;Mx[i]=INF;g[i].clear();}
}
void dfs(ll node,ll mx,ll ba){
	// vis[node]=true;
#ifdef LOCAL
    debug(node);
    debug(mx);
    debug(ba);
    cerr<<"\n";
#endif
	Mx[node]=min(Mx[node],mx);
	ba+=B[node];
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i][0],w=g[node][i][1];
		// if(vis[lnode]) continue;
		if(ba<w) continue;
		dfs(lnode,max(mx,w),ba);
	}
}
inline void solve(){
	cin>>N>>M;
	init();
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		// 把g反过来
		// g[v].pb({u,w});
		g[u].pb({v,w});
	}
	dfs(1,0,0);
	// dfsn(N,0);
	if(Mx[N]==INF){	// 未联通
		cout<<-1<<"\n";
		return;
	}
	cout<<Mx[N]<<"\n";
}

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

*/

CF-1026-C. Racing （让无人机上升还是保持不变以通过障碍）

Posted on 2025-06-11 Edited on 2026-04-06

思路讲解

题目总结

这是一道关于无人机通过障碍门的问题。有 N 道门，每道门都有高度范围 [l_i, r_i]。无人机初始高度为 0，每次可以选择保持高度不变或上升 1 个单位。部分门的操作已经固定（0 表示保持不变，1 表示上升），部分门的操作待定（-1 表示可以自由选择）。需要判断是否存在合法方案使无人机能通过所有门，如果存在则输出一种方案，否则输出 -1。

虽然这种题不是不可能dp，但dp不太可能。

容易想到一种贪心，在每一道门前尽量增加高度，

但是要注意这个高度的上界是什么。

// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
ROF(i,N,1){
	ll r=lr[i][1];
	if(D[i]==1){	
	// 这里-1是因为这里当然不会判断，但是当mnR[i-1]来读这个mnR[i]的时候
	// 我们希望mnR[i-1]的上界不能是mnR[i]，因为+1就超了
	// 连续操作与传递同理
		mnR[i]=min(r-1,mnR[i+1]-1);
	}else{
		mnR[i]=min(r,mnR[i+1]);
	}
}

这个上界不仅会受到后续最小 r 的影响，还会收到固定操作的影响

AC代码

https://codeforces.com/contest/2110/submission/323871174

源代码

// Problem: C. Racing
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)
// URL: https://codeforces.com/contest/2110/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// 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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

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

ll N,M,Q,X,K,lT,D[MAXN];
arr2 lr[MAXN];
ll mnR[MAXN];
/*

*/
inline void init(){
	FOR(i,0,N+5){mnR[i]=INF;}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){cin>>D[i];}
	FOR(i,1,N){
		ll l,r;cin>>l>>r;
		lr[i]={l,r};
	}
	// li>rj  i<j 时必定无解。
	ll mxl=0;
	FOR(i,1,N){
		ll l=lr[i][0],r=lr[i][1];
		if(r<mxl){
			cout<<-1<<"\n";
			return;
		}
		mxl=max(l,mxl);
	}
	// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
	ROF(i,N,1){
		ll r=lr[i][1];
		if(D[i]==1){
			mnR[i]=min(r-1,mnR[i+1]-1);
		}else{
			mnR[i]=min(r,mnR[i+1]);
		}
	}
	ll cnt1=0,curh=0;
	FOR(i,1,N){
		ll l=lr[i][0],r=lr[i][1];
		if(D[i]==0){
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}else if(D[i]==1){
			curh+=1;
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}else{
			if(curh+1<=mnR[i]){
				curh+=1;
				D[i]=1;
			}else{
				D[i]=0;
			}
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}
	}
	FOR(i,1,N){cout<<D[i]<<" ";}
	cout<<"\n";
}

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