526互联

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

发布时间 2023-12-06 11:14:21作者: 空気力学の詩

Preface

补题，经典不会F，看了会题解发现看不懂，索性直接开摆

A. Jagged Swaps

判断\(a_1\)是否为\(1\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=15;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		puts(a[1]==1?"YES":"NO");
	}
	return 0;
}

B. AB Flipping

不难发现除了开头的一段B和结尾的一段A之外所有的位置都可以被操作

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s",&n,s+1); int L=1,R=n;
		while (L<=n&&s[L]=='B') ++L;
		while (R>=1&&s[R]=='A') --R;
		if (L>R) puts("0"); else printf("%d\n",R-L);
	}
	return 0;
}

C. Matching Arrays

考虑最优策略，一定是取出\(b\)中前\(x\)小的元素，以及\(a\)中前\(x\)大的元素，尝试用这\(2x\)个数组合出\(x\)的beauty值

同时再将剩下的\(b\)中前\(n-x\)大的元素，以及\(a\)中前\(n-x\)小的元素，尝试用这\(2(n-x)\)个数不组出任何beauty值

而组合的最优策略手玩一下会发现一定是排序后对应匹配

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,x,ans[N]; pi a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i].fi),a[i].se=i;
		for (i=1;i<=n;++i) scanf("%d",&b[i].fi),b[i].se=i;
		sort(a+1,a+n+1); sort(b+1,b+n+1);
		vector <pi> AL,AG,BL,BG; bool flag=1;
		for (i=1;i<=x;++i) BL.push_back(b[i]),AG.push_back(a[n-i+1]);
		for (i=1;i<=n-x;++i) BG.push_back(b[n-i+1]),AL.push_back(a[i]);
		sort(AL.begin(),AL.end()); sort(AG.begin(),AG.end());
		sort(BL.begin(),BL.end()); sort(BG.begin(),BG.end());
		for (i=0;i<BL.size()&&flag;++i) if (AG[i].fi<=BL[i].fi) flag=0;
		for (i=0;i<BG.size()&&flag;++i) if (AL[i].fi>BG[i].fi) flag=0;
		if (!flag) { puts("NO"); continue; }
		for (i=0;i<BL.size();++i) ans[AG[i].se]=BL[i].fi;
		for (i=0;i<BG.size();++i) ans[AL[i].se]=BG[i].fi;
		for (puts("YES"),i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

D. Ones and Twos

类似思想的题在今年桂林H中见过，所以看一眼就会了

首先不难发现对于某个区间\([l,r]\)，设其区间和为\(sum\)，则\(sum-2,sum-4,\cdots\)这些数都能被表出

证明的话也很简单，考虑两个端点的数，如果其中存在\(2\)就拿走它使得和减少\(2\)；否则就存在两个\(1\)，直接都拿走即可

有了这个结论我们会发现可以先求出\([1,n]\)的和，不妨记为\(S\)，则对于询问的\(s\)，分情况讨论：

  • \(s\)和\(S\)奇偶性相同，则直接比较\(s\)和\(S\)的大小关系
  • \(s\)和\(S\)奇偶性不同，考虑找出某个区间使得其和的奇偶性和\(S\)不同且和的值尽量大

后者稍作思考会发现其实就是维护整个序列最靠前和最靠后的\(1\)的位置，不妨记为\(L,R\)，则只要验证\([L+1,n],[1,R-1]\)的和的大小关系即可

用set和树状数组来维护，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,q,a[N],opt,x,y;
class Tree_Array
{
	private:
		int bit[N];
	public:
		inline void init(CI n)
		{
			for (RI i=1;i<=n;++i) bit[i]=0;
		}
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=n;x+=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; set <int> s; scanf("%d%d",&n,&q); BIT.init(n);
		for (i=1;i<=n;++i) if (scanf("%d",&a[i]),BIT.add(i,a[i]),a[i]==1) s.insert(i);
		for (i=1;i<=q;++i)
		{
			scanf("%d%d",&opt,&x); if (opt==1)
			{
				int sum=BIT.get(n);
				if (sum%2==x%2)
				{
					puts(x<=sum?"YES":"NO"); continue;
				}
				if (s.empty()) { puts("NO"); continue; }
				int L=*s.begin(),R=*s.rbegin();
				puts(x<=max(BIT.get(R-1),sum-BIT.get(L))?"YES":"NO");
			} else
			{
				scanf("%d",&y); if (a[x]==y) continue;
				if (a[x]==1) s.erase(x);
				BIT.add(x,y-a[x]); a[x]=y;
				if (a[x]==1) s.insert(x);
			}
		}
	}
	return 0;
}

E. Permutation Sorting

首先设\(p_i\)为数\(i\)在\({a_i}\)中出现的次数，则我们可以把一个移动过程看作区间\([p_i,i]\)

当然由于整个数组是循环的，因此需要把原数组倍长

如果每个数的移动互不影响则每个区间的移动次数就是\(i-p_i\)，但不难发现先回到目标位置的数会对本来要经过它的数的移动产生影响

手玩一下会发现某个区间的答案还要减去它所包含的区间的个数

这个东西很经典，把所有区间按照右端点排序后跑个扫描线维护即可

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
int t,n,a[N],p[N],ans[N]; vector <int> v[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		inline void init(CI n)
		{
			for (RI i=1;i<=n;++i) bit[i]=0;
		}
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x<=2*n;x+=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),p[a[i]]=i;
		for (i=1;i<=2*n;++i) v[i].clear();
		for (i=1;i<=n;++i)
		{
			int l=p[i],r=i; if (l>r) r+=n;
			ans[i]=r-l; v[r].push_back(l);
			if (r<=n) v[r+n].push_back(l+n);
		}
		for (BIT.init(2*n),i=1;i<=2*n;++i)
		{
			if (i<=n&&p[i]<=i) ans[i]-=BIT.get(p[i]);
			if (i>n&&p[i-n]>i-n) ans[i-n]-=BIT.get(p[i-n]);
			for (auto j:v[i]) BIT.add(j,1);
		}
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

期末考临近，但眼下还有重庆市赛以及不知道能不能去的ECFinal，还在纠结是滚回去复习比较好还是全力冲刺，给这个赛季画一个圆满的结尾（貌似已经圆满了）