Znzryb's Blog

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 H P12597 穿睡衣军训

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

思路讲解

子序列自动机，最重要的是next数组，可以找到从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)

struct seqAuto{	// 子序列自动机 subsequence automaton 
	// 可以处理大小写字母，数字，但是可能要改一下base以及next
	vector<vector<int>> next;
	// 从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)
	char base='a';
	seqAuto(const string &s){
		next.assign(SZ(s)+5,vector<int>(28,-1));
		ROF(i,SZ(s)-1,0){
			FOR(j,0,26){
				next[i][j]=next[i+1][j];
			}
			next[i][s[i]-base]=i;
		}
	}
	inline bool isFind(const string &s){	// 传入substr时，必须为const属性
		ll idx=0;
		FOR(i,0,SZ(s)-1){
			if(next[idx][s[i]-base]!=-1){
				idx=next[idx][s[i]-base]+1;
			}else{
				return false;
			}
		}
		return true;
	}
};

然后用双指针方式枚举子串

FOR(i,0,SZ(S)-1){	// 双指针
	FOR(j,bp,SZ(S)){
		assert(j>=i);
		ll len=j-i;
		if(!sat.isFind(S.substr(i,len))){	// pos,len
			bp=j;
			if(ans.empty() || len-1>SZ(ans.back())){
				ans.clear();
				ans.pb(S.substr(i,len-1));
			}else if(len-1==SZ(ans.back()) ){
				ans.pb(S.substr(i,len-1));
			}
			break;
		}
	}
}

AC代码

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

源代码

// Problem: P12597 穿睡衣军训
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P12597
// Memory Limit: 512 MB
// Time Limit: 1000 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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
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,Q,X,K,lT,A[MAXN];
/*

*/
struct seqAuto{	// 子序列自动机 subsequence automaton 
	// 可以处理大小写字母，数字，但是可能要改一下base以及next
	vector<vector<int>> next;
	// 从i位置开始，字符下一次出现在哪个位置（下标）(包括i位置)
	char base='a';
	seqAuto(const string &s){
		next.assign(SZ(s)+5,vector<int>(28,-1));
		ROF(i,SZ(s)-1,0){
			FOR(j,0,26){
				next[i][j]=next[i+1][j];
			}
			next[i][s[i]-base]=i;
		}
	}
	inline bool isFind(const string &s){	// 传入substr时，必须为const属性
		ll idx=0;
		FOR(i,0,SZ(s)-1){
			if(next[idx][s[i]-base]!=-1){
				idx=next[idx][s[i]-base]+1;
			}else{
				return false;
			}
		}
		return true;
	}
};

inline void solve(){
	string S,T;
	cin>>S>>T;
	seqAuto sat(T);
	ll bp=0;
	vector<string> ans;
	S+=('z'+1);
	FOR(i,0,SZ(S)-1){	// 双指针
		FOR(j,bp,SZ(S)){
			assert(j>=i);
			ll len=j-i;
			if(!sat.isFind(S.substr(i,len))){	// pos,len
				bp=j;
				if(ans.empty() || len-1>SZ(ans.back())){
					ans.clear();
					ans.pb(S.substr(i,len-1));
				}else if(len-1==SZ(ans.back()) ){
					ans.pb(S.substr(i,len-1));
				}
				break;
			}
		}
	}
	sort(all(ans));
	cout<<ans[0]<<"\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/218545015
*/

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

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 F P12595 出生于驾校（线段树加减乘除懒标记思想）

Posted on 2025-05-25 Edited on 2026-02-17

思路讲解

使用递推方法加快Sum预处理速度。

递推代码。

ROF(k,log2(N)-1,0){  // 
	FOR(i,0,pow2[k]-1){
		// assert(pow2[k]+i<SZ(Sum[k+1]));
		Sum[k][i]=Sum[k+1][i]+Sum[k+1][pow2[k]+i];
		Sum[k][i]%=mod;
		Cnt[k][i]=Cnt[k+1][i]+Cnt[k+1][pow2[k]+i];
	}
}

AC代码

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

源代码

// Problem: T610807 出生于驾校
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T610807?contestId=245376
// Memory Limit: 2 MB
// Time Limit: 5000 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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(4e7)+10,INF=static_cast<ll>(1e18)+3;
constexpr int mod=998244353;
constexpr double eps=1e-8;

ll N,M,Q,K,T;
int minK, maxK;
/*

*/
typedef uint32_t ui;
ui X, Y, Z;

inline ui nextInt(ui &x = X, ui &y = Y, ui &z = Z) {
  x ^= y << (z & 31);
  y ^= z >> (x & 31);
  z ^= x << (y & 31);
  x ^= x >> 5; y ^= y << 17; z ^= z >> 6;
  return x;
}

const int lim = 998244353;
// inline std::vector<int> genArr(int n) {
  // std::vector<int> ret(n);
  // for (int i = 0; i < n; ++i) ret[i] = nextInt() % lim;
  // return ret;
// }
ll pow2[90];
vector<int> Sum[32],Cnt[32];
ll A[MAXN];

inline void solve(){
	cin>>N>>Q>> minK >> maxK;
	cin>>X>>Y>>Z;
	// A=genArr(N);	// 这样子效率其实会慢一点，直接上静态数组会快一点
	FOR(i,0,N-1){
		A[i]=nextInt() % lim;
	}
	FOR(i,0,log2(N)){	
		Sum[i].resize(pow2[i]+5,0);
		Cnt[i].resize(pow2[i]+5,0);
	}
	// 我们需要讲这个优化到 O(n+logn) 那么其实也就是O(n)
	ll mxk=log2(N);
	FOR(idx,0,N-1){		
		ll midx=idx%pow2[mxk];
		if(midx<0) midx+=pow2[mxk];
		Sum[mxk][midx]+=A[idx];
		Sum[mxk][midx]%=mod;
		++Cnt[mxk][midx];
	}
	ROF(k,log2(N)-1,0){
		FOR(i,0,pow2[k]-1){
			// assert(pow2[k]+i<SZ(Sum[k+1]));
			Sum[k][i]=Sum[k+1][i]+Sum[k+1][pow2[k]+i];
			Sum[k][i]%=mod;
			Cnt[k][i]=Cnt[k+1][i]+Cnt[k+1][pow2[k]+i];
		}
	}
	
	ll ans=0,addRec=0,mulRec=1;
	FOR(_,1,Q){
		int op = nextInt() % 3 + 1;
		if(op==1){
			int x = nextInt() % lim;
			addRec+=x;addRec%=mod;
		}else if(op==2){
			int x = nextInt() % lim;
			mulRec*=x;mulRec%=mod;
			addRec*=x;addRec%=mod;
		}else{
			int k = nextInt() % (maxK - minK + 1) + minK;
      		int p = nextInt() % (1 << k);
      		ll lans=0;
      		lans=(Sum[k][p]*mulRec+addRec*Cnt[k][p])%mod;
      		ans^=lans;
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	pow2[0]=1;
	FOR(i,1,40){
		pow2[i]=2*pow2[i-1];
	}
	solve();
	return 0;
}
/*
AC https://www.luogu.com.cn/record/218505364
*/

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

赛时因为没有采用递推所以代码比较慢。

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 G P12596 测速仪惊吓

Posted on 2025-05-24 Edited on 2026-02-17

思路讲解

赛时稍微有点暴力，其实这个是增长的，递增的（不要从代数上想，从几何的角度想就容易很多）。

那么二分或者是双指针都行，那我们就写一个双指针吧，好久没写了。

// 双指针做法
FOR(i,1,N-1){
	FOR(j,bp,N){
		ll curArea=Sum[j-1]-Sum[i-1];
		ll ldiff=Sum[N]-curArea*2;  // ldiff不能加abs，只要ldiff变为负数了，继续加j一定会变大
		if(ldiff>=0){
			ans=min(ans,abs(ldiff));
		}else{
			ans=min(ans,abs(ldiff));
			bp=j;
			break;
		}
	}
}

核心做法如上，最重要的就是ldiff不能加abs，只要 ldiff 变为负数了，继续加 j 一定会变大（绝对值）。

AC代码

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

源代码

// Problem: T610809 测速仪惊吓
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T610809?contestId=245376
// Memory Limit: 1 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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

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

ll N,M,Q,X,K,T,A[MAXN];
arr2 xy[MAXN];
inline ll Cross(ll a,ll b,ll c,ll d){	// 记得多边形面积要除以2
	return a*d-b*c;
}
/*

*/
inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
ll Sum[MAXN];
inline void solve(){
	N=read();
	FOR(i,1,N){
		ll x=read(),y=read();
		xy[i][0]=x;xy[i][1]=y;
	}
	ll px=read(),py=read();
	// Sum的逻辑变为三角形面积的前缀和了（以P和边的顶点组成的三角形）严格来说是其面积的两倍
	FOR(i,1,N){
		ll x1=xy[i][0],y1=xy[i][1],x2=xy[(i+1)<=N?i+1:1][0],y2=xy[(i+1)<=N?i+1:1][1];
		Sum[i]=Sum[max(i-1,0)]+abs(Cross(x1-px,y1-py,x2-px,y2-py));
	}
	// 我们面积就不除以2了
	ll ans=INF;
	ll bp=2;
	// 双指针做法
	FOR(i,1,N-1){
		FOR(j,bp,N){
			ll curArea=Sum[j-1]-Sum[i-1];
			ll ldiff=Sum[N]-curArea*2;
			if(ldiff>=0){
				ans=min(ans,abs(ldiff));
			}else{
				ans=min(ans,abs(ldiff));
				bp=j;
				break;
			}
		}
	}
	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://www.luogu.com.cn/record/218460139
*/

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

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

赛时TLE，也骗到了80分，可以了可以了。

源代码

// Problem: T610809 测速仪惊吓
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T610809?contestId=245376
// Memory Limit: 1 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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

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

ll N,M,Q,X,K,T,A[MAXN];
arr2 xy[MAXN];
inline ll Cross(ll a,ll b,ll c,ll d){	// 记得多边形面积要除以2
	return a*d-b*c;
}
/*

*/
inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
ll Sum[MAXN];
inline void solve(){
	N=read();
	FOR(i,1,N){
		ll x=read(),y=read();
		xy[i][0]=x;xy[i][1]=y;
	}
	ll px=read(),py=read();
	FOR(i,1,N-1){
		Sum[i]=Sum[i-1]+Cross(xy[i][0],xy[i][1],xy[i+1][0],xy[i+1][1]);
	}
	// 我们面积就不除以2了
	ll diff=INF;
	FOR(i,1,N){
		FOR(j,i+1,N){
			ll Crosspi=Cross(xy[i][0],xy[i][1],px,py);
			ll Crosspj=Cross(xy[j][0],xy[j][1],px,py);
			ll areaD1=Sum[N-1]-Sum[j-1]+Sum[i-1]+Cross(xy[N][0],xy[N][1],xy[1][0],xy[1][1])
			+Cross(px,py,xy[j][0],xy[j][1])+Cross(xy[i][0],xy[i][1],px,py);
			ll areaD2=Sum[j-1]-Sum[i-1]+Cross(px,py,xy[i][0],xy[i][1])+
			Cross(xy[j][0],xy[j][1],px,py);
			areaD1=abs(areaD1);areaD2=abs(areaD2);
			diff=min(diff,abs(areaD1-areaD2));
		}
	}
	cout<<diff<<"\n";
}

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

*/

ABC-407-E - Most Valuable Parentheses（最有价值的括号）

Posted on 2025-05-24 Edited on 2026-02-17

思路讲解

和这道题目比较像，但又不完全一样。

CF-1011-D. Serval and Kaitenzushi Buffet

套路那比较像，但不完全一样。

其实最重要的就是要找到一个贪心结构，我们这边发现，倒过来遍历，然后一直选左括号，一旦右括号不够了，这个时候就要选一个左括号变为右括号。又因为前面的左括号

	ROF(i,N-1,1){
		ans+=A[i];
		pq.push(i);
		balance--;
		if(balance<0){	// 倒过来遍历，结果发现右括号数量不够了，这个时候必须牺牲一个左括号了
			ans-=A[pq.top()];
// #ifdef LOCAL
	// debug(pq.top());
    // debug(A[pq.top()]);
// #endif
			pq.pop();
			balance+=2;
		}
	}

AC代码

https://atcoder.jp/contests/abc407/submissions/66140638

源代码

// Problem: E - Most Valuable Parentheses
// Contest: AtCoder - AtCoder Beginner Contest 407
// URL: https://atcoder.jp/contests/abc407/tasks/abc407_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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
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,Q,X,K,lT,A[MAXN];
struct cmp{
	bool operator()(ll a,ll b){
		return A[a]>A[b];
	}
};
/*

*/
inline void solve(){
	cin>>N;
	N=2*N;
	FOR(i,1,N){
		cin>>A[i];
	}
	ll ans=0,balance=1;
	priority_queue<ll,vector<ll>,cmp> pq;
	ROF(i,N-1,1){
		ans+=A[i];
		pq.push(i);
		balance--;
		if(balance<0){	// 倒过来遍历，结果发现右括号数量不够了，这个时候必须牺牲一个左括号了
			ans-=A[pq.top()];
// #ifdef LOCAL
	// debug(pq.top());
    // debug(A[pq.top()]);
// #endif
			pq.pop();
			balance+=2;
		}
	}
	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://atcoder.jp/contests/abc407/submissions/66140638
*/

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

ABC-407-D - Domino Covering XOR（dfs优化）

Posted on 2025-05-24 Edited on 2026-02-17

思路讲解

其实还是比较简单的，就是如果说最后的答案不涉及这个顺序问题，其实是可以不用管这个顺序的。

当然，所有选择的可能都是要管的。

// 选择1：不放多米诺骨牌，跳过当前格子
vis[i][j] = true;
dfs(covered_xor);
vis[i][j] = false;

// 选择2：尝试垂直放置多米诺骨牌 (向下)
if (i + 1 <= N && !vis[i + 1][j]) {
    vis[i][j] = vis[i + 1][j] = true;
    dfs(covered_xor ^ A[i][j] ^ A[i + 1][j]);
    vis[i][j] = vis[i + 1][j] = false;
}

// 选择3：尝试水平放置多米诺骨牌 (向右)
if (j + 1 <= M && !vis[i][j + 1]) {
    vis[i][j] = vis[i][j + 1] = true;
    dfs(covered_xor ^ A[i][j] ^ A[i][j + 1]);
    vis[i][j] = vis[i][j + 1] = false;
}

AC代码

https://atcoder.jp/contests/abc407/submissions/66113167

源代码

// Problem: D - Domino Covering XOR
// Contest: AtCoder - AtCoder Beginner Contest 407AtCoder 初学者竞赛 407
// URL: https://atcoder.jp/contests/abc407/tasks/abc407_d
// 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)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
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,Q,X,K,lT,A[25][25];
bool vis[25][25];
ll ans, total_xor;

inline void solve(){
    cin >> N >> M;
    total_xor = 0;
    ans = 0;
    CLR(vis, false);
    
    FOR(i, 1, N) {
        FOR(j, 1, M) {
            cin >> A[i][j];
            total_xor ^= A[i][j];
        }
    }
    
    function<void(ll)> dfs = [&](ll covered_xor) {
        // 找到第一个未被覆盖的格子
        ll next_i = -1, next_j = -1;
        FOR(i, 1, N) {
            FOR(j, 1, M) {
                if (!vis[i][j]) {
                    next_i = i;
                    next_j = j;
                    goto found;
                }
            }
        }
        found:
        
        // 如果所有格子都处理完了，计算得分
        if (next_i == -1) {
            ll score = total_xor ^ covered_xor;
            ans = max(ans, score);
            return;
        }
        
        ll i = next_i, j = next_j;
        
        // 选择1：不放多米诺骨牌，跳过当前格子
        vis[i][j] = true;
        dfs(covered_xor);
        vis[i][j] = false;
        
        // 选择2：尝试垂直放置多米诺骨牌 (向下)
        if (i + 1 <= N && !vis[i + 1][j]) {
            vis[i][j] = vis[i + 1][j] = true;
            dfs(covered_xor ^ A[i][j] ^ A[i + 1][j]);
            vis[i][j] = vis[i + 1][j] = false;
        }
        
        // 选择3：尝试水平放置多米诺骨牌 (向右)
        if (j + 1 <= M && !vis[i][j + 1]) {
            vis[i][j] = vis[i][j + 1] = true;
            dfs(covered_xor ^ A[i][j] ^ A[i][j + 1]);
            vis[i][j] = vis[i][j + 1] = false;
        }
    };
    
    dfs(0);
    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://atcoder.jp/contests/abc407/submissions/66113167
*/