526互联

Pinely Round 2 (Div. 1 + Div. 2)

发布时间 2023-09-02 19:31:44作者: 空気力学の詩

Preface

唉懒狗了这把比赛的时候突然不想打了跑去看AIR了，所以就没打了，后面补题的时候发现前面题挺合我口味的如果打了大概率能上橙

不过这种第二天早上有早八的时间还是很难打的，苦路西苦路西

A. Channel

统计当存在某个时刻在线人数为\(n\)时就是YES

否则把所有的+加起来看看是否大于等于\(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_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=105;
int t,n,a,q; 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%d%d%s",&n,&a,&q,s+1);
		bool flag=a==n; int b=a;
		for (i=1;i<=q;++i)
		{
			if (s[i]=='+') ++a,++b; else --a; flag|=a==n;
		}
		if (flag) { puts("YES"); continue; }
		if (b>=n) puts("MAYBE"); else puts("NO");
	}
	return 0;
}

B. Split Sort

考虑按序进行\(2\sim n\)这些操作一定能将整个序列排序，考虑什么时候能节省下一些操作

手玩下发现对于每对\(i,i+1\)，若\(pos(i+1)>pos(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_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=100005;
int t,n,a[N],pos[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]),pos[a[i]]=i;
		int ans=n-1; for (i=1;i<n;++i) ans-=(pos[i+1]>pos[i]);
		printf("%d\n",ans);
	}
	return 0;
}

C. MEX Repetition

手玩找下规律会发现每次操作就是在开头补上缺少的那个数，然后删除序列末尾的元素

发现操作\(n+1\)次后序列会复原，因此把\(k\)向\(n+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_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=100005;
int t,n,k,x,w,vis[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,&k),i=0;i<=n;++i) vis[i]=0;
		deque <int> q; for (i=1;i<=n;++i) scanf("%d",&x),vis[x]=1,q.push_back(x);
		for (i=0;i<=n;++i) if (!vis[i]) { w=i; break; }
		for (k%=n+1,i=1;i<=k;++i) q.push_front(w),w=q.back(),q.pop_back();
		for (auto x:q) printf("%d ",x); putchar('\n');
	}
	return 0;
}

D. Two-Colored Dominoes

好简单的D题啊

考虑横着的这种牌，不难发现它对行没有影响，只要考虑它对列的影响即可

统计出每列牌的数量，如果是奇数就显然无解，否则我们按列的顺序随便染即可，不难发现这样总有解

处理完后考虑竖着的牌即可，做法是相同的

#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_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=505;
int t,n,m,col[N][N],wr[N],wc[N]; char s[N][N]; vector <int> R[N],C[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",s[i]+1);
		for (i=1;i<=n;++i) R[i].clear(),wr[i]=0;
		for (i=1;i<=m;++i) C[i].clear(),wc[i]=0;
		for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		{
			col[i][j]=-1;
			if (s[i][j]=='L') C[j].push_back(i),C[j+1].push_back(i);
			if (s[i][j]=='U') R[i].push_back(j),R[i+1].push_back(j);
		}
		bool flag=1; for (i=1;i<=n&&flag;++i)
		{
			if (R[i].size()&1) flag=0;
			for (auto j:R[i])
			{
				if (~col[i][j]) continue;
				int c=wr[i]*2<R[i].size(); col[i][j]=c; wr[i]+=c;
				if (s[i][j]=='U') col[i+1][j]=c^1,wr[i+1]+=c^1;
			}
		}
		for (j=1;j<=m&&flag;++j)
		{
			if (C[j].size()&1) flag=0;
			for (auto i:C[j])
			{
				if (~col[i][j]) continue;
				int c=wc[j]*2<C[j].size(); col[i][j]=c; wc[j]+=c;
				if (s[i][j]=='L') col[i][j+1]=c^1,wc[j+1]+=c^1;
			}
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i,putchar('\n')) for (j=1;j<=m;++j)
		if (s[i][j]=='.') putchar('.'); else putchar(col[i][j]?'W':'B');
	}
	return 0;
}

E. Speedrun

首先考虑答案的计算形式，我们需要确定起始时刻，然后跑一个拓扑排序就能得到结束时刻了

因此一个很自然的想法就是给DAG的零入度点排序，然后按顺序枚举某个作为起始时刻，不难发现其实就是不断地把前一个起始时刻加上\(k\)的过程

考虑修改某个点的值后会影响它后面的点的值，乍一看复杂度很爆炸，但仔细一想最后至多每个数都比原来大\(k\)，因此每个点最多被松弛一次，复杂度是对的

#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_map>
#define int 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 t,n,m,k,h[N],x,y,deg[N],f[N],mx[N],ret; vector <int> v[N];
inline int calc(CI x,CI y)
{
	int d=x/k,r=x%k; return (d+(y<r))*k+y;
}
inline void reset(CI now)
{
	if (calc(mx[now],h[now])<=f[now]) return;
	ret=max(ret,f[now]=calc(mx[now],h[now]));
	for (auto to:v[now]) mx[to]=max(mx[to],f[now]),reset(to);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld%lld",&n,&m,&k),i=1;i<=n;++i)
		mx[i]=deg[i]=0,v[i].clear(),scanf("%d",&h[i]);
		for (i=1;i<=m;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),++deg[y];
		queue <int> q; vector <pi> st;
		for (i=1;i<=n;++i) if (!deg[i]) mx[i]=h[i],q.push(i),st.push_back(pi(h[i],i));
		sort(st.begin(),st.end()); ret=0; while (!q.empty())
		{
			int now=q.front(); q.pop(); ret=max(ret,f[now]=calc(mx[now],h[now]));
			for (auto to:v[now])
			{
				mx[to]=max(mx[to],f[now]); if (!--deg[to]) q.push(to);
			}
		}
		int ans=ret-st[0].fi; for (i=0;i<st.size()-1;++i)
		mx[st[i].se]+=k,reset(st[i].se),ans=min(ans,ret-st[i+1].fi);
		printf("%lld\n",ans);
	}
	return 0;
}

F. Divide, XOR, and Conquer

妙妙题

考虑对于某个能得到区间\([l,r]\)，记\(s=\bigoplus_{i=l}^r a_i\)，考虑若\(s=0\)则对于其任意一个前缀或者后缀区间都可以得到

否则若\(s\ne 0\)，则对于每个前缀\([l,k]\)，记\(x=\bigoplus_{i=l}^k a_i\)，显然当且仅当\(s\)的最高位和\(x\)的最高位相同时，区间\([l,k]\)可以被表示

直接利用这个性质做有很多种做法，但都是\(O(n^2\log a_i)\)的复杂度，由于\(n=10000\)无法通过

考虑怎么把状态的转移做到\(O(1)\)，可以利用状压，用\(sl_i,sr_i\)表示以\(i\)为左端点/右端点时，区间最高位的集合（状压）

那么考虑若当前区间\([l',r']\)，其\(s'=\bigoplus_{i=l'}^{r'} a_i\)，则如果\(s'\and sl_{l'}>0\)或者\(s'\and sr_{r'}>0\)这个区间就可以得到，这样就可以\(O(1)\)转移了

注意下当\(s=0\)时需要给\(sl_l,sr_r\)赋上全\(1\)的值，总复杂度\(O(n^2)\)

#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_map>
#define int 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=10005,S=(1LL<<61)-1;
int t,n,a[N],pfx[N],sl[N],sr[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i)
		scanf("%lld",&a[i]),pfx[i]=pfx[i-1]^a[i],sl[i]=sr[i]=0;
		auto high=[&](CI x)
		{
			if (!x) return S; return 1LL<<(63-__builtin_clzll(x));
		};
		for (i=1;i<=n;++i) for (j=n;j>=i;--j)
		{
			int flag=(i==1&&j==n),s=pfx[j]^pfx[i-1];
			flag|=(sl[i]&s)>0||(sr[j]&s)>0;
			if (sl[i]==S||sr[j]==S) flag=1;
			if (flag) sl[i]|=high(s),sr[j]|=high(s);
			if (i==j) putchar(flag?'1':'0');
		}
		putchar('\n');
	}
	return 0;
}

Postscript

最近训练态度很不积极啊感觉，马上要第一次出战区域赛了得赶紧加训加训