首页 > 其他分享 >CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

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

时间：2023-12-06 11:24:03浏览次数：32  
标签：typedef Rated const int long Prizes Div include define

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，还在纠结是滚回去复习比较好还是全力冲刺，给这个赛季画一个圆满的结尾（貌似已经圆满了）

标签：typedef,Rated,const,int,long,Prizes,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17879085.html

相关文章

  • CodeForces 1497E2 Square-free division (hard version)
    洛谷传送门CF传送门感觉和CF1889C2Doremy'sDryingPlan(HardVersion)有异曲同工之妙。显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。那么我们设\(f_{i,j}\)为\([1,i]\)......
  • Codeforces Round 805 (Div. 3)
    CodeforcesRound805(Div.3)基本情况A、B、C题秒了。D题一开始读错题了，以为是DP，后面发现是简单贪心，拖了点时间才AC。不过无所谓，因为E题没思路了。但是总感觉C做的太不优雅。C.TrainandQueries我的做法就纯用STL无脑模拟。跑了\(701ms\)#include<iostream>#inclu......
  • [Codeforces Round 855 (Div. 3)](https://codeforces.com/contest/1800)
    CodeforcesRound855(Div.3)A.IsItaCat?为什么这个A这么麻烦#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;strings;cin>>n>>s;s=""+s;......
  • [ARC141D] Non-divisible Set 题解
    题目链接点击打开链接题目解法很思维的题，需要用好所有的特殊性质暴力的做法是建出图，然后求包含点\(i\)的最长反链，但这明显过不了上面的做法没用到\(a_i<2m\)的性质如何用？把\(a_i\)拆分成\(q\times2^k\;(k\)为奇数\()\)的形式，那么对于同一个\(q\)，只能在其中选一个......
  • Codeforces Beta Round 18 (Div. 2 Only) E
    111感觉写的好多都是2000分dp+路径这个dp很明显发现只和行相关然后我们发现每行最多俩个那么肯定就是ababab这种交叉dpiab就是我们第i行选了ab交叉的min转移也是26*26预处理costiab作为每行的转移代价即可最后要注意就是m==1的情况然后初始化一定要把所......
  • [Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/con
    EducationalCodeforcesRound159(RatedforDiv.2)好困，差点没打A-BinaryImbalance#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){ strings; intn; cin>>n; cin>>s; if(n==......
  • Codeforces Round 800 (Div. 2)
    CodeforcesRound800(Div.2)基本情况A题秒了。B题写了个递推，但是T了，这种构造题还是得多练。B.ParanoidString我的解法#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingll=longlong;constintN=2e5+10;intt,n;char......
  • Codeforces Round 912 (Div. 2) - sol
    CodeforcesRound912(Div.2)-solCodeforcesRound912(Div.2)一直是因为晚上打太晚了就没有打过cf，所以只能vp了。/kk四道题有关位运算——不好评价。A.HalloumiBoxes给出\(n\)个数\(a_1,\dots,a_n\)，和一个数\(k\)。问是否能通过任意次翻转\(\lek\)的连......
  • Codeforces Round 910 (Div. 2)
    CodeforcesRound910(Div.2)A.MilicaandStringwa麻了，，，不知道自己在干什么#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intk,n;strings;cin>>n>>k>>s;in......
  • Codeforces Round 909 (Div. 3)
    CodeforcesRound909(Div.3)A#include<bits/stdc++.h>#defineintlonglong#defineendl'\n';usingnamespacestd;intn;voidsolve(){cin>>n;for(inti=1;i<=10;i++){if(i&1){if(n%3==0)n++;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99