Znzryb's Blog

CF-1024-D. Quartet Swapping（四重交换）

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

思路讲解

那么注意到，在该操作过程中，一个数下标的的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是偶数下标的反转数和奇数下标的反转数是相同的，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标，反之亦然。

那么要用到我们观察出来的第二个性质，就是偶数下标的反转数和奇数下标的反转数是相同的，那么如果说偶数下标序列和奇数下标序列的逆序对数量的奇偶性不相同（逆序对数量其实也就是需交换操作数量，因为本道题目是只能相邻交换，相当于冒泡排序），那么就说明必须要牺牲一个不反转（或者有时是在有序的基础上，再多反转一个，反正无论是 $+1$ 还是 $-1$ 以后奇偶性一定就相同了）。

那么应该反转哪个最优呢？不难发现这样交换最优。

1
2
3

if((revOdd-revEven)%2!=0){
	swap(Ans[N],Ans[N-2]);
}

AC代码

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

源代码

// Problem: B. Quartet Swapping
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/B
// Memory Limit: 256 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)

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 Ans[MAXN];
/*
交换ai和ai+2，交换ai+1和ai+3
输出通过该操作能够达到的字典序最小的数组
其实就是把两个数当成一块然后换个位置

那么注意到，在该操作过程中，一个数位置的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是反转数的奇偶性，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标。
然后呢，这个其实除了最后的3个位置，其实前面的位置按照奇偶性排序输出即可。

那么最后的问题。最后三个元素的位置是什么？那么其实就是要么就是一奇二偶，要么就是一偶二奇。
奇偶之间亦无需多言，那么就是偶偶奇奇之间如何判断的问题。
*/
struct BIT {  // 普通的单点修改区间查询树状数组，含有查找第K个空位的功能
  vector<ll> tr;
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    tr.resize(n+5,0);
  }
  inline void add(int p, int x) {
  	if(p==0) return;
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx + 1;  // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};
inline void solve(){
	cin>>N;
	priority_queue<ll,vector<ll>,greater<ll>> pqOdd,pqEven;
	BIT oddTree(N),evenTree(N);
	ll revOdd=0,revEven=0;
	FOR(i,1,N){
		cin>>A[i];
		if(i%2==0){
			pqEven.push(A[i]);
			revEven+=evenTree.query(A[i]+1,N);
			evenTree.add(A[i],1);
		}else{
			pqOdd.push(A[i]);
			revOdd+=oddTree.query(A[i]+1,N);
			oddTree.add(A[i],1);
		}
	}
	FOR(i,1,N){
		if(i%2==0){
			Ans[i]=pqEven.top();
			pqEven.pop();
		}else{
			Ans[i]=pqOdd.top();
			pqOdd.pop();
		}
	}
	if((revOdd-revEven)%2!=0){
		swap(Ans[N],Ans[N-2]);
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

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

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

CF-1024-C. Mex in the Grid（蛇形构造转圈矩阵）

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

思路讲解

从外往里转会好很多。

AC代码

https://codeforces.com/contest/2102/submission/319351416

源代码

// Problem: C. Mex in the Grid
// Contest: Codeforces - Codeforces Round 1024 (Div. 2)
// URL: https://codeforces.com/contest/2102/problem/C
// Memory Limit: 256 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)

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>(1e3)+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;
ll maze[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
/*
678  0->1->2->3,...,->8
501
432
从外往里转会好很多。
*/
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		FOR(j,0,N+5){
			maze[i][j]=-1;
		}
	}
	ll idx=N*N-1;
	ll x=N,y=N,dir=3;
	while(idx>=0){
#ifdef LOCAL
    if(idx==1){
		debug(dir)
	}
#endif
		maze[x][y]=idx;
		--idx;
#ifdef LOCAL
    FOR(i,1,N){
		FOR(j,1,N){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
		if(x+dx[dir]>N || x+dx[dir]<1){
			dir--;
		}else if(y+dy[dir]>N || y+dy[dir]<1){
			--dir;
		}else if(maze[x+dx[dir]][y+dy[dir]]!=-1){
			--dir;
		}
		dir%=4;
		if(dir<0) dir+=4;
		x+=dx[dir];
		y+=dy[dir];
	}
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<maze[i][j]<<" ";
		}
		cout<<"\n";
	}
#ifdef LOCAL
    FOR(i,0,N+5){
		FOR(j,0,N+5){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
}

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;
}
/*

*/

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

从里往外转比较烦。

源代码

// Problem: C. Mex in the Grid
// Contest: Codeforces - Codeforces Round 1024 (Div. 2)
// URL: https://codeforces.com/contest/2102/problem/C
// Memory Limit: 256 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)

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>(1e3)+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;
ll maze[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
/*
678  0->1->2->3,...,->8
501
432
*/
ll idx=0;
void dfs(ll x,ll y,ll step,ll cnt,ll dir){
	if(idx>N*N-1){
		return;
	}
	dir%=4;
	if(cnt>3){
		cnt=1;
		step+=1;
		ll dir_1=(dir-1)%4;
		if(dir_1<0) dir_1+=4;
		maze[x][y]=idx;
		++idx;
		x+=dx[dir_1];
		y+=dy[dir_1];
	}
	
	if(dir==0){
		FOR(i,y,y+step-2){
			maze[x][i]=idx;
			++idx;
		}
		dfs(x,y+step-1,step,cnt+1,dir+1);
	}else if(dir==1){
		FOR(i,x,x+step-2){
			maze[i][y]=idx;
			++idx;
		}
		dfs(x+step-1,y,step,cnt+1,dir+1);
	}else if(dir==2){
		ROF(i,y,y-step+2){
			maze[x][i]=idx;
			++idx;
		}
		dfs(x,y-step+1,step,cnt+1,dir+1);
	}else{
		ROF(i,x,x-step+2){
			maze[i][y]=idx;
			++idx;
		}
		dfs(x-step+1,y,step,cnt+1,dir+1);
	}
	
}
inline void solve(){
	cin>>N;
	ll n2=ceil(N*1.0/2);
	FOR(i,0,N+5){
		FOR(j,0,N+5){
			maze[i][j]=-1;
			vis[i][j]=false;
		}
	}
	idx=0;
	dfs(n2,n2,2,1,0);
#ifdef LOCAL
    FOR(i,0,N+5){
		FOR(j,0,N+5){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<maze[i][j]<<" ";
		}
		cout<<"\n";
	}
}

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

*/

CF-995-E. Best Price

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

思路讲解

二分是假的，离散化，差分是真的。

还是有一定难度的，一是要想到离散化+差分快速判断该数是否符合条件。第二是要缩小答案范围，注意到，只有a和b才能成为答案（a+1不就差评了？那为什么不选b？—————a-1不就还好评那？那为什么不选a？）

AC代码

https://codeforces.com/contest/2051/submission/319412463

源代码

// Problem: E. Best Price
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/contest/2051/problem/E
// Memory Limit: 256 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)

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

ll N,M,K,T;
ll ans=0;
arr ab[MAXN];
ll diff[MAXN],Sum[MAXN];
/*
不难注意到，我们只要在合法的价格上，求出
*/
inline void solve(){
	cin>>N>>K;
	vector<ll> li,Vals,B;
	FOR(i,0,3*N+5){
		Sum[i]=0;
		diff[i]=0;
	}
	FOR(i,1,N){
		cin>>ab[i][0];
		li.pb(ab[i][0]+1);
		li.pb(ab[i][0]);
		Vals.pb(ab[i][0]);
	}
	FOR(i,1,N){
		cin>>ab[i][1];
		li.pb(ab[i][1]);
		Vals.pb(ab[i][1]);
		B.pb(ab[i][1]);
	}
	sort(all(B));
	uniVec(li);
	uniVec(Vals);
	li.pb(li.back()+1);
	// li.insert(-INF,0);
	FOR(i,1,N){
		// 是从a+1～b这段需要加一
		ll beg=lower_bound(all(li),ab[i][0]+1)-li.begin(),
		ed=lower_bound(all(li),ab[i][1])-li.begin();
		diff[beg]+=1;
		diff[ed+1]-=1;
	}
	Sum[0]=diff[0];
	FOR(i,1,3*N){
		Sum[i]=Sum[i-1]+diff[i];
	}
#ifdef LOCAL
	cerr<<"Sum:";
    FOR(i,0,2*N){
    	cerr<<Sum[i]<<" ";
    }
    cerr<<"\n";
    DEBUG(li);
    DEBUG(B);
#endif
	ans=0;
	FOR(i,0,SZ(Vals)-1){
		ll val=Vals[i];
		ll idx=lower_bound(all(li),val)-li.begin();
#ifdef LOCAL
    if(val==1){
    	debug(Sum[idx]);
    	debug(K);
    }
#endif
		if(Sum[idx]<=K){
			// B中>=val的值有多少个
			ll ind=lower_bound(all(B),val)-B.begin();
			ll num=N-ind;
			ans=max(num*val,ans);
#ifdef LOCAL
    debug(ind);
#endif
		}
	}
	
	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://codeforces.com/contest/2051/submission/319412463
*/

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

三分做法，WA了

https://codeforces.com/contest/2051/submission/319133918

源代码

// Problem: E. Best Price
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/contest/2051/problem/E
// Memory Limit: 256 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)

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],B[MAXN];
ll ans=0;
/*

*/
inline ll check(ll x){
	ll res=0,neg=0;
#ifdef LOCAL
    debug(x)
#endif
	FOR(i,1,N){
		if(x<=A[i]){
			res+=x;
		}else if(x>A[i] && x<=B[i]){
			neg+=1;
			res+=x;
		}else{
			continue;
		}
	}
#ifdef LOCAL
    debug(neg)debug(res)
#endif
	if(neg>K) return 1;
	else {ans=max(ans,res);return res;}
}
inline void solve(){
	cin>>N>>K;
	FOR(i,1,N){
		cin>>A[i];
	}
	ll maxB=0;
	FOR(i,1,N){
		cin>>B[i];
		maxB=max(maxB,B[i]);
	}
	ll l=0,r=maxB+3;ans=0;
	while(r-l>2){
		ll mid1=l+(r-l)/3,mid2=r-(r-l)/3;
#ifdef LOCAL
    debug(l)debug(r)debug(mid1)debug(mid2)
#endif
		if(check(mid1)>check(mid2)){
			r=mid2;
		}else{
			l=mid1;
		}
#ifdef LOCAL
    cerr << '\n';
#endif
	}
	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是因为清空不够多，sum没加够。

CF-1009-F. Counting Necessary Nodes

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

思路讲解

那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形。

图中的1，2，3，4对应加粗斜体的dfs部分。

	ROF(i,log2(b-a),0){
		ll b_=b/pow2[i]*pow2[i],a_=ceil(a*1.0/pow2[i])*pow2[i];
		ll d_=d/pow2[i]*pow2[i],c_=ceil(c*1.0/pow2[i])*pow2[i];
		if(b_<=a) continue;
		if(a_>=b) continue;
		if(d_<=c) continue;
		if(c_>=d) continue;
		if(a_+pow2[i]>b_) continue;
		if(c_+pow2[i]>d_) continue;
		ans+=abs(a_-b_)/pow2[i]*(abs(c_-d_)/pow2[i]);
#ifdef LOCAL
    debug(a_)
    debug(b_)
    debug(c_)
    debug(d_)
    debug(pow2[i])
    debug(ans)
    cerr<<"\n";
#endif
		dfs(a,a_,c,d);
		dfs(b_,b,c,d);
		dfs(a_,b_,c,c_);
		dfs(a_,b_,d_,d);
		return;
	}

AC代码

https://codeforces.com/contest/2074/submission/319087712

源代码

// Problem: F. Counting Necessary Nodes
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/F
// Memory Limit: 512 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)

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];
/*
那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形
去分是不大可能的，也不大可能是数学方法。
我认为其实就是
*/
ll ans=0;
ll pow2[40];
void dfs(ll a,ll b,ll c,ll d){
	if(a>=b || c>=d) return;
// #ifdef LOCAL
    // debug(a)debug(b)debug(c)debug(d)
// #endif
	if(b-a>d-c){
		swap(a,c);
		swap(b,d);
	}
#ifdef LOCAL
    debug(a)debug(b)debug(c)debug(d)
#endif
	ROF(i,log2(b-a),0){
		ll b_=b/pow2[i]*pow2[i],a_=ceil(a*1.0/pow2[i])*pow2[i];
		ll d_=d/pow2[i]*pow2[i],c_=ceil(c*1.0/pow2[i])*pow2[i];
		if(b_<=a) continue;
		if(a_>=b) continue;
		if(d_<=c) continue;
		if(c_>=d) continue;
		if(a_+pow2[i]>b_) continue;
		if(c_+pow2[i]>d_) continue;
		ans+=abs(a_-b_)/pow2[i]*(abs(c_-d_)/pow2[i]);
#ifdef LOCAL
    debug(a_)
    debug(b_)
    debug(c_)
    debug(d_)
    debug(pow2[i])
    debug(ans)
    cerr<<"\n";
#endif
		dfs(a,a_,c,d);
		dfs(b_,b,c,d);
		dfs(a_,b_,c,c_);
		dfs(a_,b_,d_,d);
		return;
	}
}
inline void solve(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ans=0;
	dfs(a,b,c,d);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,35){
		pow2[i]=2*pow2[i-1];
	}
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<"-------------"<< '\n';
#endif
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2074/submission/319087712
*/

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

直接模拟4叉树，TLE

https://codeforces.com/contest/2074/submission/319043232

源代码

// Problem: F. Counting Necessary Nodes
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/F
// Memory Limit: 512 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)

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];
/*
那个公式的意思其实就是只有0，2，4，8，。。才能有边长为2的正方形。
0，4，8，12，。。。才能有边长为4的正方形
去分是不大可能的，也不大可能是数学方法。
我认为其实就是
*/
ll ans=0;
ll pow2[40];
void dfs(ll a,ll b,ll c,ll d,ll a1,ll b1,ll c1,ll d1){	// 模拟4叉树的这个过程就行
	if(a>=b || c>=d) return;	// 出现了不合法的表达形式，退出
	if(b<=a1 || a>=b1) return;	// 不可能情况退出
	if(c>=d1 || d<=c1) return;
	ll midAb=(a1+b1)/2,midCd=(c1+d1)/2;
	if(a==a1 && b==b1 && c==c1 && d==d1){
		++ans;
#ifdef LOCAL
    debug(a)debug(b)debug(c)debug(d);
    cerr<<"\n";
#endif
		return;
	}
	// if(a>= midAb && c>=midCd){
		// if(b<=b1 && d<=d1){
			// dfs(a,b,c,d,midAb,b1,midCd,d1);
		// }else if(b>b1 && d<=d1){
			// dfs(a,b1,c,d,midAb,b1,midCd,d1);
		// }
// 		
	// }else if(a>=midAb && d<=midCd){
		// dfs(a,b,c,d,midAb,b1,c1,midCd);
	// }else if(b<=midAb && c>=midCd){
		// dfs(a,b,c,d,a1,midAb,midCd,d1);
	// }else if(b<=midAb && d<=midCd){
		// dfs(a,b,c,d,a1,midAb,c1,midCd);
	// }
	dfs(a,min(b,midAb),c,min(d,midCd),a1,midAb,c1,midCd);
	dfs(max(midAb,a),b,c,min(d,midCd),midAb,b1,c1,midCd);
	dfs(a,min(b,midAb),max(midCd,c),d,a1,midAb,midCd,d1);
	dfs(max(midAb,a),b,max(midCd,c),d,midAb,b1,midCd,d1);
}
inline void solve(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ans=0;
	ll idx=ceil(log2(max(b,d)));
	dfs(a,b,c,d,0,pow2[idx],0,pow2[idx]);	// 1048576 为2的20次方
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,35){
		pow2[i]=2*pow2[i-1];
	}
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<"-------------"<< '\n';
#endif
	}
	// solve();
	return 0;
}
/*

*/

CF-1009-E. Empty Triangle

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

思路讲解

呃，这题虽然套着一个几何的背景，但我认为考察重点并不在几何上。

正解竟然就是随机化做法？这题的意义是什么那？我也不是很理解。

AC代码

https://codeforces.com/contest/2074/submission/318930035

源代码

// Problem: E. Empty Triangle
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/E
// Memory Limit: 512 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)

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 void solve(){
	cin>>N;
	if(N==3){
		cout<<"! 1 2 3"<<endl;
		return;
	}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	uniform_int_distribution<> distrib(1,N),dis3(0,2);
	vector<ll> quer={distrib(rng),distrib(rng),distrib(rng)};
	while(quer[0]==quer[1] || quer[1]==quer[2] || quer[0]==quer[2]){
		quer={distrib(rng),distrib(rng),distrib(rng)};
	}
	ll idx=0;
	while(true){
		cout<<"? "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
		ll res;
		cin>>res;
		if(res==0){
			cout<<"! "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
			break;
		}else{
			quer[dis3(rng)]=res;
			++idx;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2074/submission/318917809
AC https://codeforces.com/contest/2074/submission/318930035
*/

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

TLE

https://codeforces.com/contest/2074/submission/318918084

源代码

// Problem: E. Empty Triangle
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/E
// Memory Limit: 512 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)

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 void solve(){
	cin>>N;
	if(N==3){
		cout<<"! 1 2 3"<<endl;
		return;
	}
	vector<ll> quer={1,2,3};
	ll idx=0;
	while(true){
		cout<<"? "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
		ll res;
		cin>>res;
		if(res==0){
			cout<<"! "<<quer[0]<<" "<<quer[1]<<" "<<quer[2]<<endl;
			break;
		}else{
			quer[idx%3]=res;
			++idx;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2074/submission/318917809

*/