Znzryb's Blog

2025金马高校联赛-B战术单元协同训练

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

思路讲解

AC代码

源代码

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

ABC-405-E - Fruit Lineup

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

思路讲解

像这种题目，一般要把一对有关系的留到最后，这样子状态就唯一了。

1
2
3

|----A----|     |--D--|
|-------B------|
           |-----C----|

可以先枚举A的边界，然后再把C填好，B，D之间因为有位置关系，所以状态唯一。

// 显然是要枚举水果的边界
ll ans=0;
FOR(i,a,a+b){
	// 在i-1个空位中选a-1个空位(因为第i个位置已经钦定了A（苹果）)
	ll res=comb.C(i-1,a-1);
	res*=comb.C(N-i,c);
	res%=mod;
	ans+=res;
}

AC代码

https://atcoder.jp/contests/abc405/submissions/66027443

源代码

// Problem: E - Fruit Lineup
// Contest: AtCoder - AtCoder Beginner Contest 405
// URL: https://atcoder.jp/contests/abc405/tasks/abc405_e
// Memory Limit: 1024 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=998244353;
constexpr double eps=1e-8;

ll N,M,K,T;
/*

*/
struct Comb{
	vector<ll> frac,infrac;
	int ln=1;
	Comb(int n){
		ln=n;
		frac.resize(n+5,1);
		infrac.resize(n+5,1);
		for(int i=1;i<=ln;++i){
			frac[i]=frac[i-1]*i;
			frac[i]%=mod;
		}
		for(int i=1;i<=ln;++i){
			infrac[i]=binpow(frac[i],mod-2);
		}
	}
	inline ll binpow(ll a,ll k){
		ll res=1;
		while(k){
			if(k&1) res*=a;
			a*=a;
			a%=mod;
			res%=mod;
			k>>=1;
		}
		return res;
	}
	inline ll C(ll n,ll k){
		ll res=frac[n]*infrac[n-k];
		res%=mod;
		res*=infrac[k];
		res%=mod;
		return res;
	}
	inline ll P(ll n,ll k){
		ll res=frac[n]*infrac[n-k];
		res%=mod;
		return res;
	}
};
inline void solve(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	N=a+b+c+d;
	Comb comb(a+b+c+d);
	// 显然是要枚举水果的边界
	ll ans=0;
	FOR(i,a,a+b){
		// 在i-1个空位中选a-1个空位(因为第i个位置已经钦定了A（苹果）)
		ll res=comb.C(i-1,a-1);
		res*=comb.C(N-i,c);
		res%=mod;
		ans+=res;
	}
	ans%=mod;
	if(ans<0) ans+=mod;
	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/abc405/submissions/66027443
*/

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

一些常见的trick

Posted on 2025-05-15 Edited on 2026-03-14

思路讲解

【Codeforces Round 1024 (Div. 2) 题目讲解 ABCDE (CF2102)】【精准空降到 16:30】 https://www.bilibili.com/video/BV1CFELzVExf/?p=5&share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=990

这场的E题，用到了一个技巧，就是2，2，3，4 → 1，2，3，4 这如何利用set就能做到（维护一个序列，要求 $a_i≥ i$ ，然后给你一堆数，要求你能够最长化这个序列）？其实可以换个思路，初始的 set 里有 1，2，3，4，5 然后删。

具体见CF-1024-E. 23 Kingdom。

CF-1028-D. Gellyfish and Camellia Japonica（直接构造等于难，构造最小的大于等于）

https://www.luogu.com.cn/article/rae0b6wl

总结的话，主要的启发就是把 构造使得与目标相等 转换成 最小的构造使得大于等于目标。

方法论之解决后效性的方法

Posted on 2025-05-13 Edited on 2026-03-14

介绍

消除后效性，狭义上指的是dp，但广义上来说，贪心做法等也有时需要考虑后效性问题。

总体而言，只要你是想要把一个问题拆开来分析求解，那么合起来的时候，就要考虑后效性了。

案例分析

CF-1024-D. Quartet Swapping（四重交换）这个是解决了交换数量要保持相同，但是最优情况可能无法保持相同，如何找到次优情况呢？或者说什么发现该情况只适用于次优情况呢？涉及冒泡排序以及逆序对。

2025金马高校联赛-B战术单元协同训练利用链表来消除后效性

Edu-179-E. Changing the String 在线处理比较难，需要考虑对后续操作的影响，可以采用离线方法处理，因为下标小的。

CF-1024-E. 23 Kingdom

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

思路讲解

不难注意到，你所选择的区间之中，不允许出现两个区间相离的情况。

因为这两个区间如果变为相交的话，贡献的答案值一定更大。

由这个结论，那么新加入的区间的 $右端点>以前的所有左端点$ ，并且 $左端点<以前的所有右端点$ ，因此，所有的左右端点就会分居两端，因为起始的 $右端点>左端点$ ，新加入的 $右端点>以前的所有左端点$ ，左端点反之亦然。

那么贪心地，我们其实就是想让 $\sum{i_l}$ 最小， $\sum{i_r}$ 最大，那么左端点只要贪心地选择下标小的，右端点我们只要贪心地选择下标大的。

最后一个问题，就是当我们拿到一个序列，如 $2，2，3，4$ ，我们如何知道他是否可以映射到 $1，2，3，4$ 只通过减法。

那么这个其实有一个小的 trick，如果说用加入元素的方法判断，大抵是要用到树状数组或者线段树，但如果使用删除的方法，就可以只用 set 实现。

set<ll> st;
auto init=[&](){  // 初始化函数
	st.clear();
	FOR(i,0,N+1){
		st.insert(i);
	}
};
auto proc=[&](ll x){  // 处理函数
	auto it=st.upper_bound(x);
	--it;
	if(*it==0){
		return false;
	}else{
		st.erase(it);
		return true;
	}
};

AC代码

https://codeforces.com/contest/2101/submission/319792559

源代码

// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 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,A[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/

ll Pre[MAXN],Suf[MAXN],sufSum[MAXN],preSum[MAXN];
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		Pre[i]=0;
		Suf[i]=0;
		sufSum[i]=0;
		preSum[i]=0;
	}
	set<ll> st;
	auto init=[&](){
		st.clear();
		FOR(i,0,N+1){
			st.insert(i);
		}
	};
	auto proc=[&](ll x){
		auto it=st.upper_bound(x);
		--it;
		if(*it==0){
			return false;
		}else{
			st.erase(it);
			return true;
		}
	};
	init();
	ll ind=0;
	vector<ll> mp(N+5,0),mp2(N+5,0);
	FOR(i,1,N){
		cin>>A[i];
		if(proc(A[i])){
			++ind;
			mp[ind]=mp[ind-1]+i;
		}
		Pre[i]=ind;
	}
	mp[0]=0;
	ind=0;
	init();
	ROF(i,N,1){
		if(proc(A[i])){
			++ind;
			mp2[ind]=mp2[ind-1]+i;
		}
		Suf[i]=ind;
	}
	
	
#ifdef LOCAL
    debugN(preSum,N);
    debugN(sufSum,N);
    debugN(Pre,N);
    debugN(Suf,N);
    DEBUG(mp);
    DEBUG(mp2);
#endif
	ll ans=0,up=0;
	
	FOR(i,1,N-1){
		up=max(up,min(Pre[i],Suf[i+1]));
	}
#ifdef LOCAL
    debug(up);
#endif
	FOR(i,1,up){
		ans=max(ans,mp2[i]-mp[i]);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr << "---------------" << '\n';
#endif
	}
	// solve();
	return 0;
}
/*
hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18

AC https://codeforces.com/contest/2101/submission/319792559
*/

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

其实我们的要求是没有任意两个区间相离，这个用线段树判断是有点问题的。

一个比较好的近似解

hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18

https://codeforces.com/contest/2101/submission/319732582

源代码

// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 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 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,A[MAXN];
ll posMatch[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/
vector<ll> pos[MAXN];
struct Tree{
	ll l,r,sum,add;
}tr[MAXN];

void build(ll node,ll l,ll r){
	tr[node].sum=0,tr[node].add=0;
	tr[node].l=l,tr[node].r=r;
	if(tr[node].l>=tr[node].r) return;
	tr[lson(node)].l=l;
	tr[lson(node)].r=l+(r-l)/2;
	tr[rson(node)].r=r;
	tr[rson(node)].l=tr[lson(node)].r+1;
	build(lson(node),tr[lson(node)].l,tr[lson(node)].r);
	build(rson(node),tr[rson(node)].l,tr[rson(node)].r);
}

inline void pushdown(ll node){
	if(tr[node].l==tr[node].r) return;
	tr[lson(node)].sum+=tr[node].add*(tr[lson(node)].r-tr[lson(node)].l+1);
	tr[rson(node)].sum+=tr[node].add*(tr[rson(node)].r-tr[rson(node)].l+1);
	tr[lson(node)].add+=tr[node].add;
	tr[rson(node)].add+=tr[node].add;
	tr[node].add=0;
}
inline void pushup(ll node,ll val){
	node>>=1;
	while(node){
		tr[node].sum+=val;
		node>>=1;
	}
}
inline bool isInter(ll l,ll r,ll l1,ll r2){
	if(l>r2) return false;
	if(r<l1) return false;
	return true;
}
void add(ll node,ll l,ll r,ll val){
	pushdown(node);
	if(tr[node].l>=l && tr[node].r<=r){
		ll num=tr[node].r-tr[node].l+1;
		tr[node].sum+=val*num;
		tr[node].add+=val;
		pushup(node,val*num);
		return;
	}
	if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) add(lson(node),l,r,val);
	if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) add(rson(node),l,r,val);
}
ll query(ll node,ll l,ll r){
	pushdown(node);
	if(tr[node].l>=l && tr[node].r<=r){
		return tr[node].sum;
	}
	ll res=0;
	if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) res+=query(lson(node),l,r);
	if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) res+=query(rson(node),l,r);
	return res;
}
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		posMatch[i]=0;
	}
	FOR(i,1,N){
		pos[i].clear();
	}
	FOR(i,1,N){
		cin>>A[i];
		pos[A[i]].pb(i);
	}
	build(1,1,N);
	set<ll> st,stEd;	// st保存的是现在可用的，stEd是已经用过的。
	ll ans=0;
	ROF(i,N,1){
		st.insert(pos[i].begin(),pos[i].end());
		if(SZ(st)>=2){
			ll beg=*st.begin(),ed=*st.rbegin();
			ll res=query(1,beg,ed);
			if(res>0){	// 只要有区间相交，那么就取用最大区间即可
				add(1,beg,ed,1);
				ans+=ed-beg;
				stEd.insert(beg);	// 已经用过，在已经用过中增加
				stEd.insert(ed);
				posMatch[beg]=ed;
				posMatch[ed]=beg;
				st.erase(st.begin());	// 已经用过了，在可用中删除
				st.erase(--st.end());
			}else{	// 没有与其他区间相交，那么就需要上一点手段了
				if(SZ(stEd)>=2){	// 理论上来说stEd不是空的就是
					// stEd不是空的，那我们就需要让区间们相交
					ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
					ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
					oldLen2=mxEd-posMatch[mxEd];
					ll eff1=len1-oldLen1,eff2=len2-oldLen2;
					if(eff1>eff2 && eff1>0){
						add(1,mnEd,ed,1);
						st.erase(ed);
						ans+=eff1;
						stEd.erase(posMatch[mnEd]);
						st.insert(posMatch[mnEd]);
						posMatch[mnEd]=ed;
						posMatch[ed]=mnEd;
						stEd.insert(ed);
					}else if(eff2>0){
						// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
						add(1,beg,mxEd,1);
						st.erase(beg);
						ans+=eff2;
						stEd.erase(posMatch[mxEd]);
						st.insert(posMatch[mxEd]);
						posMatch[mxEd]=beg;
						posMatch[beg]=mxEd;
						stEd.insert(beg);
					}
				}else{	// stEd是空的，和res>0一样处理
					add(1,beg,ed,1);
					ans+=ed-beg;
					stEd.insert(beg);	// 已经用过，在已经用过中增加
					stEd.insert(ed);
					posMatch[beg]=ed;
					posMatch[ed]=beg;
					st.erase(st.begin());	// 已经用过了，在可用中删除
					st.erase(--st.end());
				}
			}
		}else if(SZ(st)==1){
			ll ed=*st.begin(),beg=*st.begin();
			if(SZ(stEd)>=2){	// 理论上来说stEd不是空的就是
					// stEd不是空的，那我们就需要让区间们相交
					ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
					ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
					oldLen2=mxEd-posMatch[mxEd];
					ll eff1=len1-oldLen1,eff2=len2-oldLen2;
					if(eff1>eff2 && eff1>0){
						add(1,mnEd,ed,1);
						st.erase(ed);
						ans+=eff1;
						stEd.erase(posMatch[mnEd]);
						st.insert(posMatch[mnEd]);
						posMatch[mnEd]=ed;
						posMatch[ed]=mnEd;
						stEd.insert(ed);
					}else if(eff2>0){
						// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
						add(1,beg,mxEd,1);
						st.erase(beg);
						ans+=eff2;
						stEd.erase(posMatch[mxEd]);
						st.insert(posMatch[mxEd]);
						posMatch[mxEd]=beg;
						posMatch[beg]=mxEd;
						stEd.insert(beg);
					}
				}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr << "---------------" << '\n';
#endif
	}
	// solve();
	return 0;
}
/*

*/