526互联

AtCoder Regular Contest 165

发布时间 2023-09-26 18:07:32作者: 空気力学の詩

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要阳间的多但就是不想打……