Codeforces Round #627(Div. 3) 문제 해결

C o d e f o r c e s R o u n d 627 (D i v. 3)\mathrm {Codeforces\Round\627 (Div. 3)} Codeforces Round 627 (Div.3) 문제 해결
이 경기를 수속장(인당 A K AK AK장)이라고도 부른다
A   Y e t   A n o t h e r   T e t r i s   P r o b l e m\mathrm{A\Yet\Another\Tetris\Problem} A Yet Another Tetris Problem

한 문제에서 짝짓기를 판정하면 됩니다. 그리고 그 자체가 숫자라면 YE S\mathrm {YES} YES입니다.

C o d e\mathcal{Code} Code

#include 
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

bool rem;
int t,n,s,i,a;

int main()
{
	
	t=read();
	while(t--)
	{
		n=read(),s=read();
		s&=1;
		rem=0;
		for ( int i=2;i<=n;i++ )  
		{
			scanf("%d",&a);
			if(s!=(a&1))rem=1;
		}
		puts((rem&&n>1?"NO":"YES"));
	}
	return 0;
}

B   Y e t   A n o t h e r   P a l i n d r o m e   P r o b l e m\mathrm{B\Yet\Another\Palindrome\Problem} B Yet Another Palindrome Problem

는 또 하나의 문제로 두 개의 같은 수 사이의 간격이 333보다 큰지 판단하고 원열의 길이를 판단하면 된다.

C o d e\mathcal{Code} Code

#include 
using namespace std;
const int N=10000;

int T,n,pos[N],a[N];

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int main()
{
	T=read();
	while (T--)
	{
		n=read();
		memset(pos,0,sizeof(pos));
		bool ww=false;
		for ( int i=1; i<=n; ++i) 
		{
			a[i]=read();
			if (!pos[a[i]]) pos[a[i]]=i;
			else if (i-pos[a[i]]>1) ww=true;
		}
		if(n<3) ww=false;
		if(ww) printf("YES
");
		else printf("NO
");
	}	
	return 0;	
}

C   F r o g   J u m p s\mathrm{C\Frog\Jumps} C Frog Jumps

왜 또 문제야.먼저 c 0 = c n + 1 = R c0=c_{n+1}=R c0=cn+1=R, 그리고 두 R R R R 사이의 최대 거리를 판단하면 됩니다.

C o d e\mathcal{Code} Code

#include 
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

string str;
int t,n,last,d,i;

inline void solve()
{
	cin>>str;
	int n=str.size();
	int last=0,d=0;
	for ( int i=0;i<n;i++ ) 
		if(str[i]=='R')d=max(d,i+1-last),last=i+1;
	printf("%d
",max(d,n+1-last));
}

int main()
{
	t=read();
	while(t--) solve();
	return 0;
}

D   P a i r   o f   T o p i c s\mathrm{D\Pair\of\Topics} D Pair of Topics

하나의 큰 문제

a i + a j > b i + b j a_i+a_j>b_i+b_jai+aj>bi+bj, 그럼 ai-3-bi

C o d e\mathcal{Code} Code

#include 
#define int long long
#define lowbit(x) x&(-x)

using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}


const int N=4e5+5; 

int n,m,ans,a[N],b[N],c[N],d[N],e[N];

inline void add(int x,int val)
{
	while(x<=m)
	{
		c[x]+=val;
		x+=lowbit(x);
	}
}

inline int ask(int x)
{
	int ret=0;
	while(x)
	{
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}

signed main()
{
	n=read();
	for ( int i=1;i<=n;i++ ) a[i]=read();
	for ( int i=1;i<=n;i++ )
	{
		b[i]=read();
		d[i*2-1]=a[i]-b[i];
		d[i*2]=b[i]-a[i];
	}
	sort(d+1,d+2*n+1);
	m=unique(d+1,d+2*n+1)-d-1;
	for ( int i=1;i<=n;i++ ) 
	{
		int p=lower_bound(d+1,d+m+1,b[i]-a[i])-d;
		ans+=i-ask(p)-1;
		p=lower_bound(d+1,d+m+1,a[i]-b[i])-d;
		add(p,1);
	}
	printf("%lld
",ans);
	return 0;
}
		

E   S l e e p i n g   S c h e d u l e\mathrm{E\Sleeping\Schedule} E Sleeping Schedule

무슨 문제야, 직접 G\mathrm {G} GG를 설명하는 예가 없어.사실은 dpdpdp야.

f i , j f_{i, j}fi, j는 i i가 몇 가지 선택인지를 나타냅니다 a i ai ai​

g i , j g_{i, j}gi, j는 ii가 몇 시인지 표시하고 ai-3-1ai-1 ai​−1

그리고 아무데나 옮기는 거야

C o d e\mathcal{Code} Code

#include
using namespace std;

int g[2005],f[2005];
bool vis[2005],bo[2005];

#define mem(i,j) memset(i,j,sizeof i)
#define mec(i,j) memcpy(i,j,sizeof i)

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int n,h,l,r,i,a,j,ans=0;

int main()
{
	
	n=read();
	h=read();
	l=read();
	r=read();
	bo[0]=1;
	while(n--)
	{
		a=read();
		for ( int i=0;i<h;i++ ) 
		if(bo[i])
		{
			j=(i+a)%h;
			g[j]=f[i]+(j>=l&&j<=r);
			vis[j]=1;
		}
		for ( int i=0;i<h;i++ ) 
		if(bo[i])
		{
			j=(i+a-1)%h;
			g[j]=max(g[j],f[i]+(j>=l&&j<=r));
			vis[j]=1;
		}
		mec(f,g);
		mem(g,0);
		mec(bo,vis);
		mem(vis,0);
	}
	for ( int i=0;i<h;i++ ) 
		if(bo[i])
			ans=max(ans,f[i]);
	printf("%d
",ans);
	return 0;
}

F   M a x i m u m   W h i t e   S u b t r e e\mathrm{F\Maximum\White\Subtree} F Maximum White Subtree

이 문제는 정말 지혜롭다.xg c xgc xgc의 원래 말에 따르면: 견본을 보고 멋대로 추측하면 모두 A A A 가 된다.그렇긴 한데.

단순한 트리 D P DP DP

먼저 각 노드를 111로 가장 크게 미리 처리한다.그리고 dfs dfs dfs 다시 한 번 뿌리가 아니고 원래 0 0 0보다 작으면 아버지께 희망을 걸 수 밖에 없습니다.0 0 0 보다 크면 아버지와 크기를 비교하면 좋겠다.구체적으로 실현하려면 코드를 보아라.

C o d e\mathcal{Code} Code

#include 
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=2e5+5;

int n,m,col[N],c[N],f[N];
vector<int> ma[N];

inline void dfs(int u,int fa)
{
	if(col[u]) f[u]=1; else f[u]=-1;
	for ( int i=0;i<ma[u].size();i++ )
	{
		int v=ma[u][i];
		if(v==fa) continue;
		dfs(v,u);
		f[u]=max(f[u],f[v]+f[u]);
	}
}

inline void dfs2(int u,int fa)
{
	if(u!=1) 
	{
		if(f[u]<0) f[u]=max(f[u],f[u]+f[fa]);
		else f[u]=max(f[u],f[fa]);
	}
	for ( int i=0;i<ma[u].size();i++ )
	{
		int v=ma[u][i];
		if(v==fa) continue;
		dfs2(v,u);
	}
}

int main()
{
	n=read();
	for ( int i=1;i<=n;i++ ) col[i]=read();
	for ( int i=1;i<n;i++ )
	{
		int x,y;
		x=read(),y=read();
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	dfs(1,0);
	dfs2(1,0);
	for ( int i=1;i<=n;i++ ) printf("%d ",f[i]);
	return 0;
}
	

E E\mathrm{EE} EE 절차

자신의 손이 빠르지 않은 것을 발견했지만 트럼펫은 149 149 149점

을 받았다.

마치 A-3 E\mathrm {A-E} A-3 E의 모든 코드 마스터 프로그램을 합치면 아직 트리 섹션에 미치지 못하는 것 같다.