首页 > 其他分享 >AtCoder Regular Contest 166

AtCoder Regular Contest 166

时间：2023-10-12 19:35:27浏览次数：33  
标签：AtCoder typedef int CI long Regular 166 include define

Preface

上周末因为上课而且这天下午还有CF要打，所以就没现场打这场ARC了

这两天事情也特别多导致写题的时间很少，摸了好久总算是补了四个题

A - Replace C or Swap AB

感觉是我做法复杂了，怎么A题码量好大

首先我们找到所有\(Y\)中为\(C\)的位置，显然对应的\(X\)中的位置也必须为\(C\)，然后我们把\(C\)看作分隔符把序列划分成若干段，其中每段的\(Y\)串不含\(C\)

仅考虑第三个操作，其实就是一个把\(X\)串中的\(B\)前移的过程，因此假设\(X\)串中没有\(C\)，我们只要比较一下每个\(B\)出现位置的先后即可

考虑\(X\)串有\(C\)的话我们肯定是贪心地把后面的先变成\(B\)，直到两个部分\(B\)的个数相同即可

#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 A[N],B[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s%s",&n,A+1,B+1); vector <int> posC;
		for (posC.push_back(0),i=1;i<=n;++i) if (B[i]=='C') posC.push_back(i);
		posC.push_back(n+1); bool flag=1;
		for (i=1;i<=n;++i) if (B[i]=='C'&&A[i]!='C') flag=0;
		auto solve=[&](CI l,CI r)
		{
			if (l>r) return true; int A_A=0,A_B=0,B_A=0,B_B=0;
			RI i; for (i=l;i<=r;++i)
			{
				if (A[i]=='A') ++A_A; else if (A[i]=='B') ++A_B;
				if (B[i]=='A') ++B_A; else if (B[i]=='B') ++B_B;
			}
			if (A_A>B_A||A_B>B_B) return false;
			for (i=l;i<=r;++i) if (A[i]=='C'&&A_A<B_A) A[i]='A',++A_A;
			for (i=r;i>=l;--i) if (A[i]=='C'&&A_B<B_B) A[i]='B',++A_B;
			static int posA[N],posB[N]; int cntA=0,cntB=0;
			for (i=l;i<=r;++i) if (A[i]=='B') posA[++cntA]=i;
			for (i=l;i<=r;++i) if (B[i]=='B') posB[++cntB]=i;
			for (i=1;i<=cntA;++i) if (posA[i]<posB[i]) return false;
			return true;
		};
		for (i=0;i<posC.size()-1&&flag;++i) flag&=solve(posC[i]+1,posC[i+1]-1);
		puts(flag?"Yes":"No");
	}
	return 0;
}

B - Make Multiples

感觉比A题简单，只要考虑清楚所有情况即可

由于可能会出现某些数变成其中\(2/3\)个数的倍数的情况，因此我们定义函数solve(...)，参数个数\(m\)表示最后要选出来的位置数

则只要遍历solve(a,b,c),solve(LCM(a,b),c),solve(LCM(a,c),b),solve(LCM(b,c),a),solve(LCM(a,b,c))这些情形即可

我们枚举要变成哪个数的倍数，显然有意义的只有操作次数最小的\(m\)个数，把这些数找出来然后爆搜一下即可

#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 int unsigned long long
#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 n,A,B,C,a[N],vis[N],ans=2e18; vector <pi> w[5];
inline int LCM(CI x,CI y)
{
	return x/__gcd(x,y)*y;
}
inline void DFS(CI m,CI now=0,CI sum=0)
{
	if (now>=m) return (void)(ans=min(ans,sum));
	for (RI i=0;i<min(n,m);++i) if (!vis[w[now][i].se])
	vis[w[now][i].se]=1,DFS(m,now+1,sum+w[now][i].fi),vis[w[now][i].se]=0;
}
inline void solve(VI d)
{
	RI i,j; int m=d.size();
	for (i=0;i<m;++i)
	{
		for (w[i].clear(),j=1;j<=n;++j) w[i].push_back(pi((a[j]+d[i]-1)/d[i]*d[i]-a[j],j));
		nth_element(w[i].begin(),w[i].begin()+min(n,m)-1,w[i].end());
		w[i].erase(w[i].begin()+min(n,m)-1,w[i].end());
	}
	DFS(m);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%llu%llu%llu%llu",&n,&A,&B,&C),i=1;i<=n;++i) scanf("%llu",&a[i]);
	solve(VI{LCM(LCM(A,B),C)}); solve(VI{A,B,C});
	solve(VI{LCM(A,B),C}); solve(VI{LCM(A,C),B}); solve(VI{LCM(B,C),A}); 
	return printf("%llu",ans),0;
}

C - LU / RD Marking

好久没有遇到有思路的计数题了，这题恰好比较合胃口，上数电的时候随便画画就画出来了

考虑把图中的每个方格斜着切开变成两个三角形，涂黑左上方的三角形就等价于操作一，涂黑右下方的三角形就等价于操作二

不难发现不合法的情形就是存在两个相邻的直角三角形，它们有公共的直角边，而拥有公共斜边的三角形依然是合法的

我们发现沿着图示蓝色方向把矩形分开，则不合法的图形只会在每一部分内部产生

那么很容易发现合法的方案数只和每一部分的三角形个数有关了，不妨设\(f_i\)表示\(i\)个三角形对应的方案数

转移的话就是讨论新加的位置放或不放，写出来就是\(f_i=f_{i-1}+f_{i-2}\)，其实就是个斐波那契数列，不过要注意下边界

最后答案的构成稍微手玩下其实就是（令\(n\le m\)）：

\[(f_1f_3f_5\cdots f_{2n-1})^2\times (f_{2n})^{m-n} \]

预处理\(f_i\)以及其所有奇数项的前缀积即可快速求解

#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,mod=998244353;
int t,n,m,fib[N],prod[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fib[1]=2,fib[2]=3,i=3;i<=n;++i) fib[i]=(fib[i-1]+fib[i-2])%mod;
	for (prod[1]=fib[1],i=3;i<=n;i+=2) prod[i]=1LL*prod[i-2]*fib[i]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(2e6);t;--t)
	{
		scanf("%d%d",&n,&m); if (n>m) swap(n,m);
		printf("%d\n",1LL*prod[2*n-1]*prod[2*n-1]%mod*quick_pow(fib[2*n],m-n)%mod);
	}
	return 0;
}

D - Interval Counts

很有意思的一个题，但被二分的固化思维卡的太死了，导致没做出来，后面看了题解恍然大悟我是个傻逼

首先很容易观察到的一点是，如果我们要覆盖区间\(x_l\sim x_r\)，那么最优的放法就是\([x_{l-1}+1,x_{r+1}-1]\)

考虑直接贪心构造答案，不妨使用增量法，假设我们已经构造了一些区间满足了\(x_1,x_2,\cdots,x_{i-1}\)的限制

而使用的区间有些是两个端点都固定的，有些则是右端点未固定的，现在考虑加入\(x_i\)后带来的新情况：

  • \(y_{i-1}=y_i\)，此时直接把之前右端点未定的区间都向右延长即可，对答案没有影响
  • \(y_{i-1}<y_i\)，需要新加入\(y_i-y_{i-1}\)个区间，它们的左端点为\(x_{i-1}+1\)，右端点不定
  • \(y_{i-1}>y_i\)，需要将\(y_{i-1}-y_i\)个之前的右端点未固定的区间的右端点固定为\(x_i-1\)，为了使最小值最大我们优先选择左端点较小的区间

维护的话我们可以用二元组\((a,b)\)来存储区间的左端点以及其个数，不难发现在操作的过程中\(a\)是单调的，因此可以直接用一个队列来维护所有右端点不定的区间

总复杂度\(O(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,INF=1e9;
int n,x[N],y[N],ans=INF;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x[i]);
	for (i=1;i<=n;++i) scanf("%d",&y[i]); x[0]=-INF;
	queue <pi> q; for (i=1;i<=n;++i)
	{
		if (y[i]==y[i-1]) continue;
		if (y[i]>y[i-1]) q.push(pi(x[i-1]+1,y[i]-y[i-1])); else
		{
			int left=y[i-1]-y[i];
			while (!q.empty()&&left)
			{
				int dlt=min(q.front().se,left);
				q.front().se-=dlt; left-=dlt;
				ans=min(ans,x[i]-1-q.front().fi);
				if (!q.front().se) q.pop();
			}
		}
	}
	return printf("%d",ans!=INF?ans:-1),0;
}

Postscript

发现我已经好久没有现场打过Atcoder的比赛了，看来是越来越怠惰了

标签：AtCoder,typedef,int,CI,long,Regular,166,include,define
From： https://www.cnblogs.com/cjjsb/p/17760370.html

相关文章

  • 题解 AtCoder wtf22_day1_b【Non-Overlapping Swaps】
    题解AtCoderwtf22_day1_b【Non-OverlappingSwaps】problem给定一个排列，要求交换最多\(n-1\)对元素，使得这个排列变成[1,2,...,n]的有序排列。当然没有那么简单，对于交换还是有限制的，对于相邻的两次交换，不妨叫做\((l_i,r_i)\)和\((l_{i+1},r_{i+1})\)，必须满足这两个交......
  • Atcoder Grand Contest 016 E - Poor Turkeys
    先思考这样一个问题：对于一只火鸡\(i\)，我们应该如何判断它最后是否能活下来。如果我们正着判断，我们其实并没有足够的证据表明每一次操作我们应该保留哪只火鸡，也就没法判断最终的答案。但是如果我们倒着考虑，我们发现，如果最后一次操作的两个火鸡都不是\(i\)，那么这次操作选啥对答案......
  • AtCoder Regular Contest 166——A - Replace C or Swap AB
    题目描述  中文题目描述每个字符串的长度为N，由A,B和C组成。通过对X执行以下三种操作任意次数(可能为零)，确定是否有可能使X与y重合。 操作(1):选择X中的字符C替换为字符A。操作(2):在X中选择字符C替换为字符B。操作(3):选择X中的子字符串AB，替换为BA。更正式地说，选择......
  • ARC166E Fizz Buzz Difference
    题面传送门首先一个观察是随着\(n\)的增大，最长的区间肯定是增大的，因此可以直接把等式放缩成\(\leqn\)。另一个观察使为了使区间长度最大，左右端点肯定是顶着两个\(a\)的，不妨设其为\(al+1\)和\(ar-1\)。将\(a,b\)先搞成互质的，那么现在的问题是我们需要最大化区间内\(......
  • P1667 数列
    原题可能更好的阅读体验区间操作的维护看起来很麻烦，考虑转为点操作的维护。题目中的\(\sum_{i=l}^ra_i\)启发我们用前缀和。那么我们考虑每次操作会对前缀和数组\(s\)造成怎样的变化。设操作区间为\([l,r]\)，按照题意，会把\(a_{l-1}\)和\(a_{r+1}\)加上\(S\)，\(a_l\)和......
  • AtCoder Beginner Contest 323 (ABC 323) D、E、F 题解
    AtCoderBeginnerContest323(ABC323)D、E、F题解D题目大意给\(n\)种数\(s_i\)，每一种数有\(c_i\)个，每次可以把两个相同的数合并为一个数，问最后会剩下多少数？分析对于每一个数\(s_i\)，它最多被分解\(log_2c_i\)次，并且合并出来最大的数的大小小于\(s_i\timesc_i......
  • AtCoder Beginner Contest 323
    E-Playlist首先需要算出第x+0.5秒后，第一首歌播放的概率1.要在x+0.5秒后播放第一首，需要在x，x-1,x-2,...,x-t[1]+1，时就要开始播放第一首，并且概率是1/n，概率之和除以n2.概率dp，dp[i]表示播放i的概率，那么可以转换成，dp[i]+=dp[i-j]/n%mod（i>=t[j]）3.答案就是x，x-1，...,x-t[1]+1概率之和......
  • UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323)
    UNIQUEVISIONProgrammingContest2023Autumn(AtCoderBeginnerContest323)A.WeakBeats解题思路:按题意模拟即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){strings;cin>>s;intn=s.size();......
  • Programming abstractions in C阅读笔记：p166-p175
    《ProgrammingAbstractionsInC》学习第58天，p166-p175总结。一、技术总结1.斐波那契数列(FibonacciSequenc)(1)斐波那契数列来源斐波那契数列来自于《LiberAbaci》一书里兔子繁殖问题，相关资料很多，这里不赘述。(2)关于《LiberAbaci》一书《LiberAbaci》——Liber：abook......
  • AtCoder Beginner Contest 323
    有的人边上课边打abcA-WeakBeats(abc323A)题目大意给定一个\(01\)字符串，问偶数位（从\(1\)开始）是否全为\(0\)。解题思路遍历判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99