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

AtCoder Regular Contest 165

时间：2023-09-26 18:11:07浏览次数：40  
标签：AtCoder typedef now int long Regular 165 include define

Preface

这场前三题是上周四写的，今天课有点多本来想着把最近两场CF的博客先写下的

但后面发现还有CCLCC的杂谈没写，写完发现由于晚上要上课没时间了，只能先把这场先写一下

A - Sum equals LCM

设\(n=\prod_{i=1}^k p_i^{c_i}\)，不难发现令\(A_1=p_1^{c_1},A_2=p_2^{c_2},\cdots\)，然后如果剩下的数还有多就补若干个\(1\)，这种构造方式一定是最优的

稍作分析会发现当且仅当\(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;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; int cnt=0;
		for (scanf("%d",&n),i=2;i*i<=n;++i)
		if (n%i==0)
		{
			++cnt; while (n%i==0) n/=i;
		}
		if (n>1) ++cnt;
		puts(cnt>1?"Yes":"No");
	}
	return 0;
}

B - Sliding Window Sort 2

刚开始铸币了看到题目是滑动窗口就真写了个类似于滑动窗口的东西，然后WA到怀疑人生

首先由于排序一定不会使区间内的字典序变大，因此一个贪心的想法就是尽量排后面区间，即把左端点取成\(pos=n-k+1\)

但这样有个问题就是我们可以适当把区间左移，当\([pos,n-k]\)这段区间内元素单调递增，且所有元素均小于\([n-k+1,pos+k-1]\)中的最小值时，这个区间就比原来的更优

因此找一个最靠左的满足要求的区间即可，判断的话可以用ST表维护区间最小值

#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 n,k,a[N],mi[N][20],lg[N];
inline int query(CI l,CI r)
{
	int k=lg[r-l+1]; return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
	int cur=0,flag=0; for (i=1;i<=n;++i)
	{
		if (a[i]>a[i-1]) ++cur; else cur=1;
		if (cur>=k) flag=1;
	}
	if (flag)
	{
		for (i=1;i<=n;++i) printf("%d ",a[i]); return 0;
	}
	for (i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
	for (i=1;i<=n;++i) mi[i][0]=a[i];
	for (j=1;(1<<j)<=n;++j) for (i=1;i+(1<<j)-1<=n;++i)
	mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
	int pos=n-k+1; for (i=n-k;i>=max(1,n-k*2+2);--i)
	{
		if (a[i]>a[i+1]) break;
		if (a[i]<query(i+1,i+k-1)) pos=i;
	}
	for (sort(a+pos,a+pos+k),i=1;i<=n;++i) printf("%d ",a[i]);
	return 0;
}

C - Social Distance on Graph

最小值最大，一眼二分答案，考虑如何check(x)

首先我们可以找到所有\(w_i<x\)的边，显然这些边的两端点一定是不同的颜色，因此可以变成一个染色问题先跑一跑，如果发现冲突那么显然无解

否则考虑在剩下的图中，由于图中没有边直接相连的两点要么本来就没有边，要么之间有\(w_i\ge x\)的边，而后者这种边显然只要走了就一定符合要求所以可以不管

那么我们要考虑的就是同色点之间的最小距离是否\(\ge x\)了，很容易发现最小的距离的两个同色点一定同为某个点的邻居

因此对于每个点求出与它相连的点对应边权的最小值与次小值，最后检验下即可

总复杂度\(O(n\log w_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=200005,INF=1e9;
int n,m,x[N],y[N],z[N],col[N],mi[N],smi[N]; vector <int> v[N];
inline bool DFS(CI now,CI c)
{
	col[now]=c; for (auto to:v[now])
	if (!~col[to])
	{
		if (!DFS(to,c^1)) return 0;
	} else if (col[to]==c) return 0;
	return 1;
}
inline bool check(CI lim)
{
	RI i; for (i=1;i<=n;++i) col[i]=-1,mi[i]=smi[i]=INF,v[i].clear();
	for (i=1;i<=m;++i) if (z[i]<lim) v[x[i]].push_back(y[i]),v[y[i]].push_back(x[i]);
	for (i=1;i<=n;++i) if (!~col[i]) if (!DFS(i,0)) return 0;
	auto update=[&](CI x,CI y)
	{
		if (y<mi[x]) smi[x]=mi[x],mi[x]=y; else	if (y<smi[x]) smi[x]=y;
	};
	for (i=1;i<=m;++i) if (z[i]<lim) update(x[i],z[i]),update(y[i],z[i]);
	for (i=1;i<=n;++i) if (mi[i]+smi[i]<lim) return 0; return 1;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%d",&x[i],&y[i],&z[i]);
	int l=0,r=2e9,mid,ret; while (l<=r)
	if (check(mid=l+(r-l)/2)) ret=mid,l=mid+1; else r=mid-1;
	return printf("%d",ret),0;
}

D - Substring Comparison

好题，启发了我对于这一类多约束的问题，可以考虑从强到弱依次加入约束来处理

考虑对于一组约束\((A_i,B_i,C_i,D_i)\)，直接考虑它的字典序大小因为涉及到前缀相等的情况，所以搞不清楚在哪一位确定大小关系，因此也就不好表示

我们不妨从中抽取出最强的一个限制，即\(X[A_i]\le X[C_i]\)，然后将每个约束连\(A_i\to C_i\)的边建图

然后我们发现如果此时图中没有环的话那我们就已经得到了一组解了，否则考虑图中有环的情况

很显然根据约束关系，此时同一个强连通分量内的点都只能取相同的数值，我们可以用并查集维护所有取值相同的位置

然后不妨再次考虑一组约束\((A_i,B_i,C_i,D_i)\)，若它对应的\(A_i\)和\(C_i\)不在同一个强连通分量里，那显然不用管这个约束了直接扔掉就好

否则说明\(X[A_i]=X[C_i]\)必须成立，那我们不妨将\(A_i,C_i\)同时向右移动，以此来构建新的限制即可

不难发现移动过程的次数上限是\(O(n)\)的，而每次建新图后有跑Tarjan的复杂度\(O(n+m)\)，因此总复杂度为\(O(n\times (n+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 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=2005;
struct ifo
{
	int a,b,c,d;
}o[N]; vector <int> v[N]; int n,m,fa[N],dfn[N],low[N],stk[N],col[N],idx,scc,top; bool vis[N],flag;
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void Tarjan(CI now)
{
	dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
	for (int to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
	else if (vis[to]) low[now]=min(low[now],dfn[to]);
	if (low[now]==dfn[now])
	{
		col[now]=++scc; vis[now]=0; while (stk[top]!=now)
		flag=1,fa[getfa(stk[top])]=getfa(now),col[stk[top]]=scc,vis[stk[top--]]=0; --top;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%d%d",&o[i].a,&o[i].b,&o[i].c,&o[i].d);
	for (i=1;i<=n;++i) fa[i]=i;
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=n;++j) dfn[j]=0,v[j].clear(); idx=scc=0; flag=0;
		for (j=1;j<=m;++j)
		{
			while (getfa(o[j].a)==getfa(o[j].c)&&o[j].a<=o[j].b&&o[j].c<=o[j].d) ++o[j].a,++o[j].c;
			if (o[j].c>o[j].d) return puts("No"),0;
			if (o[j].a<=o[j].b) v[getfa(o[j].a)].push_back(getfa(o[j].c));
		}
		for (j=1;j<=n;++j) if (!dfn[j]) Tarjan(j);
		if (!flag) return puts("Yes"),0;
	}
	return 0;
}

Postscript

感觉好久没有现场打过Atcoder了的说，明明时间相比CF要阳间的多但就是不想打……

标签：AtCoder,typedef,now,int,long,Regular,165,include,define
From： https://www.cnblogs.com/cjjsb/p/17730866.html

相关文章

  • Some Recent Thoughts Wrritten By NiuJiawen-2019141490165
    Recently,manystudentswhoarejunioryeararetakingpartininterviewsforexemptstudents.Somehaveobtainedsatisfactoryoffers,whereas,othersthinkitistoohardtogetawonderfuloffer. Andthereisnodoubtthatthelatterwillbefrustrated......
  • AtCoder Beginner Contest 321
    A-321-likeChecker(abc321A)题目大意给定一个数，问从高位到低位，数字是不是递减的。解题思路可以以字符串读入，然后依次判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);......
  • 题解 ARC165F【Make Adjacent】
    区间排序问题，主席树优化建图，最小字典序拓扑排序（priority_queue）problem给定一个长度为\(n*2\)的序列，其中每种元素恰好出现了2次。允许每次选择任意两个相邻的元素交换。那么必定存在一个最小\(k\)：使得\(k\)次交换以后所有相同的元素都是相邻的。问恰好操作\(k\)次后，......
  • [ARC165D] Substring Comparison
    ProblemStatementForanintegersequence$X=(X_1,X_2,\dots,X_n)$,let$X[L,R]$denotetheintegersequence$(X_L,X_{L+1},\dots,X_{R})$.Youaregivenintegers$N$and$M$,and$M$quadruplesofintegers$(A_i,B_i,C_i,D_i)$.Determineifthereisaninte......
  • 题解 AtCoder Beginner Contest 267 A~H
    ABC267solutionhttps://atcoder.jp/contests/abc267/ProblemA.Saturday题目描述输入一个表示星期的英文字符串，输出：还有多少天到星期六？solution依题意模拟。\(O(1)\)。ProblemB.Split?题目描述Robin有十个小球，如图排列成这样，然后Robin将一些球击飞了，他告诉你哪些......
  • AtCoder Beginner Contest 318 ABCDE
    AtCoderBeginnerContest318A-FullMoon思路：等差数列求项数//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;intmain(){ios::sync_with_stdio(false);......
  • AtCoder Beginner Contest 320 ABCDE
    AtCoderBeginnerContest320A-LeylandNumber思路：直接快速幂//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;llqmi(lla,llb){llans=1;whil......
  • AtCoder Beginner Contest 253 E
    AtCoderBeginnerContest253E-DistanceSequence思路：前缀和优化DP要求$|a[i]-a[i+1]|>=k\(定于\)dp[i][j]:\(前\)i\(个数以\)j\(结尾的合法序列数列\)dp[i][j]+=dp[i-1][1～(j-k)]+dp[i-1][(j+k)～m]$直接写的话复杂度是\(O(nm^2)\)的会TLE，我们发现可以做一个前缀和优化......
  • AtCoder Beginner Contest 313 Ex Group Photo
    洛谷传送门AtCoder传送门考虑若重排好了\(a\)，如何判断可不可行。显然只用把\(b\)排序，把\(\min(a_{i-1},a_i)\)也排序（定义\(a_0=a_{n+1}=+\infty\)），按顺序逐个判断是否大于即可。这启示我们将\(\min(a_{i-1},a_i)\)排序考虑。考虑从大到小加入\(a_i\)，那么......
  • arc165F
    arc165F题目描述：给定\(n\)和一个长度为\(2n\)的序列\(a\)，满足\([1,n]\)每个数恰好出现两次。每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列\(a\)满足\(\foralli\in[1,n]\a_{2\timesi}=a_{2\timesi+1}\)。在保证为最小操作次数的前提下，输出所有......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99