D. Orac and Medians

Description

给定一个序列，每次可以把序列上的一个区间的值变成区间的中位数

这里中位数的定义有所不同

如果长度为奇数，那么就是中间值

如果长度为偶数，那么直接是中间较小的那个数

求是不是可以把一个序列转成一个给定的数 \(k\)

Solution

直接给结论吧……

首先判掉没有满足 \(k\) 的情况

设 \(b_i\) 表示 \(a_i\) 和 \(k\) 的大小关系

大于为 \(2\)

小于为 \(0\)

等于为 \(1\)

如果一个长度为 \(3\) 的子区间中有 \(2\) 个数大于等于 \(k\) ，那么就能行

简单理解一下这个结论：

与 \(1\) 相邻有 \(2\) 那么就可以改掉它

\(1.\) 如果我们两个 \(1\) 就显然可以改掉一个数，同理别的直接改就好了

\(2.\) \(\{0,1,2\}\) 直接中位数

\(3.\) \(\{0,2,2\}\) 我们改掉 \(0\) 变成 \(2\) 然后对于每个 \(0\) 我们都可以把它改 成 \(2\)，直到找到 \(1\)

时间复杂度 \(O(n)\)

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=1e5+10;
	int a[N],n,k,b[N];
	inline bool work()
	{
		n=read(); k=read(); bool fl=0;
		for(int i=1;i<=n;++i)
		{
			a[i]=read();
			if(a[i]>k) b[i]=2; 
			else if(a[i]==k) b[i]=1,fl=1;
			else b[i]=0;
		}
		if(!fl) return 0; if(n==1) return 1;
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j-i<=2&&j<=n;++j)
			{
				if(b[i]&&b[j]) return 1;
			}
		} return 0;
	}
	signed main()
	{
		int T=read(); while(T--) puts(work()?"Yes":"No");
		return 0;
	}
}
signed main(){return yspm::main();}

E.Orac and Game of Life

Description

link

Solution

这个是一道普及题好吧

和那个\(CSP2019-J\) 真的太像了吧……

我们先用 \(bfs\) 求出每个点最少多少次就开始连续变色了

然后就看奇偶性即可

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=1010;
	const int inf=1e15+10;
	bool fl[N][N],g[N][N];
	int n,m,f[N][N],T;
	char s;
	inline bool in(int x,int y)
	{
		return x>=1&&x<=n&&y>=1&&y<=m;
	}
	int dx[4]={1,0,-1,0};
	int dy[4]={0,1,0,-1};
	queue<pair<int,int> > q; 
	inline void work()
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
			{
				for(int k=0;k<4;++k)
				{
					int tx=dx[k]+i,ty=dy[k]+j;
					if(in(tx,ty)) 
					{
						if(g[i][j]==g[tx][ty]) 
						{
							fl[i][j]=1;
							f[i][j]=0;
							q.push(make_pair(i,j));
							break;
						}
					}
				}	
			}
		}
		while(!q.empty())
		{
			pair<int,int> fr=q.front(); q.pop();
			int x=fr.first,y=fr.second;
			for(int i=0;i<4;++i)
			{
				int tx=x+dx[i],ty=y+dy[i];
				if(fl[tx][ty]||!in(tx,ty)) continue;
				f[tx][ty]=f[x][y]+1; fl[tx][ty]=1;
				q.push(make_pair(tx,ty));
			}
		} return ;
	}
	signed main()
	{
		n=read(); m=read(); T=read();
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
			{
				while(!isdigit(s=getchar())); 
				g[i][j]=s-‘0‘;
			}
		} 
		work();
		while(T--)
		{
			int i=read(),j=read(),r=read();
			int c=max(r-f[i][j],0ll);
			if(!fl[i][j]){printf("%d\n",g[i][j]); continue;} 
			if(c&1) printf("%d\n",!g[i][j]);
			else printf("%d\n",g[i][j]);
		}
		return 0;
	}
}
signed main(){return yspm::main();}

Codeforces Round #641 Div2 补题

原文：https://www.cnblogs.com/yspm/p/12880071.html