문제 해결 - Codeforces Round #637(Div.2, A-E)

C o d e f o r c e s   R o u n d   637   ( D i v . 2   A − E )\mathrm{Codeforces\Round\637\(Div. 2\A-E) } Codeforces Round 637 (Div.2 A−E)
A . N a s t y a   a n d   R i c e\mathrm{A.Nastya\and\Rice } A.Nastya and Rice
난이도:\1000*1000\1000
제목 설명: 전송문
S o l\mathrm{Sol} Sol

간단한 문제, 왜냐하면 ai∈[a-3-b, a+b], ∑ai∈[c-3-d, c+d]ai∈[a-b,a+b],\sum a_i∈[c-d,c+d] ai​∈[a−b,a+b],∑ai​∈[c−d,c+d].그러면 저희는 모든 a, i, a에 대해...iai의 최악과 가장 좋은 상황은 [c-3d, c+d] [c-d, c+d] [c-3d, c+d]와 비교하면 된다.

C o d e\mathrm{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;
}

int n,m,x,y,a,b;

int main()
{
	int Q=read();
	for (;Q--;)
	{
		n=read();
		x=read();
		y=read();
		a=read();
		b=read();
		int low=x-y,high=x+y;
		if(low*n<=a+b&&high*n>=a-b) puts("Yes");
		else puts("No");
	}
	return 0;
}
		 

B . N a s t y a   a n d   D o o r\mathrm{B.Nastya\and\Door } B.Nastya and Door
난이도:\1300*1300\1300
제목 설명: 전송문
S o l\mathrm{Sol} Sol

시뮬레이션 문제, 우리는 P e a k s o f m o u n t a i n s\mathrm {Peaks\of\mountains} Peaks of mountains의 수량의 접두사와 그 다음에 각 길이가 kk인 합법적인 개구간을 열거한 다음에 접두사와 조회를 사용하고 마지막에 하나를 들면 바로 해답을 찾을 수 있다. 그리고 마지막에 111을 추가하는 것을 잊지 마라.

C o d e\mathrm{Code} Code

#include 
#define pb push_back
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 T,n,k,s[N],a[N];

int main()
{
	T=read();
	while(T--)
	{
		n=read(),k=read();
		a[0]=a[n+1]=1e9+5;
		for ( int i=1;i<=n;++i )
			a[i]=read();
		for ( int i=1;i<=n;++i) 
		{ 
			s[i]=s[i-1];
			if(a[i]>a[i-1]&&a[i]>a[i+1])
				s[i]++;
		}
		int pos=0,ans=0;
		for ( int i=k;i<=n;++i )
			if(ans<s[i-1]-s[i-k+1]+1)
			{
				pos=i-k+1;
				ans=s[i-1]-s[i-k+1]+1;
			}
		printf("%d %d
",ans,pos);
	}
	return 0;
}

C . N a s t y a   a n d   S t r a n g e   G e n e r a t o r\mathrm{C.Nastya\and\Strange\Generator } C.Nastya and Strange Generator
난이도:\1500*1500\1500
제목 설명: 전송문
S o l\mathrm{Sol} Sol

결론문제: 만약에 서열 ppp가 여러 소절로 나눌 수 있다면 각 소절이 모두 111을 공차로 하는 점증 등차수열이면 성공적으로 구성할 수 있다.구체적인 증명은 쓰지 않겠습니다(qwq

C o d e\mathrm{Code} Code

#include 
using namespace std;
const int N=2e5+5;

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 a[N];

signed main()
{
	int Q=read();
	for (;Q--;)
	{
		int n=read();
		int flg=0;
		for ( int i=1;i<=n;i++ ) a[i]=read();
		for ( int i=1;i<=n;i++ )
		{
			int j=i;
			while(j+1<=n&&a[j+1]>a[j])  j++ ;
			for ( int k=i;k<j;k++ ) 
				if((a[k]+1)^a[k+1])  
					flg=1;
			i=j;
		}
		if(flg) puts("No");
		else puts("Yes");
	}
	return 0;
}

D . N a s t y a   a n d   S c o r e b o a r d\mathrm{D.Nastya\and\Scoreboard } D.Nastya and Scoreboard
난이도:\1800 * 1800\1800
제목 설명: 전송문
S o l\mathrm{Sol} Sol

DP DP DP 비교 및 욕심

우선 fi, jf 설정{i, j}fi, j는 ii 블록에 jj j개의 추가 나무 막대기로 숫자를 구성할 수 있는지 여부입니다.이동은 간단하다: fi, j∣=[k=0 9] fi - 1, j - c i, k f{i,j}|=[_{k=0}^{9}]f_{i-1,j-c_{i,k}} fi,j​∣=[k=09​]fi−1,j−ci,k​​. c i , j c_{i, j}ci, j는: ii i블록이 숫자 jjj로 변하는 데 필요한 나무 막대기 수(변할 수 없으면 ci, j=i n f c {i, j}=inf ci, j=inf)로 미리 처리할 수 있습니다.

그리고 우리는 gi, jg{i, j}gi, j에서 ii i 블록은 jj j 나무 막대기로 바뀌어야 하는 숫자로 옮길 때 수정하면 됩니다.

우리는 높은 자리에서 낮은 위치로 내려가면 된다는 욕심 전략이 하나 더 있다.

C o d e\mathrm{Code} Code

#include 
#define pb push_back
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=2e3+5;

string s[11]=
	{"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
int n,m,f[N][N],g[N][N],c[N][11],h[N];
string a[N];

inline int calc(int x,int y)
{
	int gs=0;
	for ( int i=0;i<7;i++ ) 
	{
		if(a[x][i]=='1'&&s[y][i]=='0') return 1e9;
		else 
			if(a[x][i]=='0'&&s[y][i]=='1') gs++;
	}
	return gs;
}

int main()
{
	n=read();
	m=read();
	memset(f,-1,sizeof(f));
	int alb=0;
	for ( int i=1;i<=n;i++ ) 
	{
		cin>>a[i];
		for ( int j=0;j<=9;j++ ) 
		{
			int flg=1;
			for ( int k=0;j<7;k++ ) 
				if(a[i][k]!=s[j][k]) 
				{
					flg=0;
					break;
				}
			alb|=flg;
		}
	}
	if(!alb) return puts("-1"),0;
	reverse(a+1,a+n+1);
	for ( int i=1;i<=n;i++ ) 
	{
		for ( int j=0;j<=9;j++ ) 
			c[i][j]=calc(i,j);
		int flg=1;
		for ( int j=0;j<=9;j++ ) 
			if(c[i][j]!=1e9) flg=0;
		if(flg) return puts("-1"),0;
	}
//	for ( int i=1;i<=n;i++,puts("") ) 
//		for ( int j=0;j<=9;j++ ) 
//			printf("c[%d][%d]=%d
",i,j,c[i][j]);
	f[0][0]=1;
	for ( int i=1;i<=n;i++ ) 
		for ( int j=0;j<=m;j++ ) 
			for ( int k=0;k<=9;k++ ) 
			{
				int cost=c[i][k];
				if(j-cost<0||cost==1e9) continue;
				if(~f[i-1][j-cost])
					f[i][j]=1,g[i][j]=k;
			}
	if(!(~f[n][m])) return puts("-1"),0; 
	for ( int i=n;i>=1;i-- ) 
	{
		int x=g[i][m];
//		printf("x=%d c[%d][%d]=%d
",x,i,x,c[i][x]); 
		printf("%d",x);
		m-=c[i][x];
	}
	return 0;
}

E . N a s t y a   a n d   U n e x p e c t e d   G u e s t\mathrm{E.Nastya\and\Unexpected\Guest } E.Nastya and Unexpected Guest
난이도:\2300*2300\2300
제목 설명: 전송문
S o l\mathrm{Sol} Sol

우선 소질 출제자가 did 를i di 정렬

우리 이 문제로 돌아가자. 우리 먼저 fi, jf 를 설정하자.{i, j} fi, j는 d i didi, 그리고 불완전한 한 주기(g+r)(g+r)(g+r)(g+r)는 jj초의 최소 주기수(주기와 주기 사이의 본질이 같기 때문)보다 많다.

그리고 각 관건에 대한 분류 토론(즉 왼쪽, 오른쪽)에 대해 구체적으로 왼쪽으로 이야기합시다.이 시점이 d i d 라고 가정합니다.i di, 그럼 왼쪽은 d i - 1 d{i-1} di-3-1(경계 주의), 그리고 왼쪽으로 가지 않기 전에 jj초가 더 나왔어요.

만약 (d i -3 d i -3 1 + j) < g(d i-d {i-1} + j) (di -3 di -3 1 + j) < g라면 f i -3 1, (d i -3 d i -3 1 + j) = f i, j f{i-1,(d_i-d_{i-1}+j)}=f_{i,j} fi−1,(di​−di−1​+j)​=fi,j​

(d i -3 d i -3 1 + j) = g(d i-d {i-1} + j) = g(di -3 di -3 1 + j) = g이면 f i -3 1, 0 = f i, j + 1 f{i-1,0}=f_{i,j}+1 fi−1,0​=fi,j​+1.주기가 꽉 차서 다시 켜야 한다

여기서 우리는 변경권이 0,10,10,1만 존재하는 것을 발견했다. 그러면 우리는 01bfs01bfs01bfs01bfs만 있으면 된다.구체적으로 양단 대기열을 만들고, 경계가 11인 pu s h b a c k pushback pushback 아님 pu s h f r o n t pushfront pushfront

C o d e\mathrm{Code} Code

#include 
#define pb push_back
#define int long long
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=1e6+5;
const int M=1e4+5;

int n,m,d[M],R,G,dis[M][1005],ans;
deque<pair<int,int> >q;

signed main()
{
	n=read();
	m=read();
	for ( int i=1;i<=m;i++ ) d[i]=read();
	G=read();
	R=read();
	sort(d+1,d+m+1);
	memset(dis,-1,sizeof(dis));
	q.push_front(make_pair(1,0));
	dis[1][0]=0;
	while(!q.empty())
	{
		pair<int,int> v=q.front();
		q.pop_front();
		if(v.first>1) 
		{
			int del=d[v.first]-d[v.first-1]+v.second;
			if(del<G) 
			{
				if(dis[v.first-1][del]<0)
				{
					dis[v.first-1][del]=dis[v.first][v.second];
					q.push_front(make_pair(v.first-1,del));
				}
			}
			if(del==G)
			{
				if(dis[v.first-1][0]<0)
				{
					dis[v.first-1][0]=dis[v.first][v.second]+1;
					q.push_back(make_pair(v.first-1,0));
				}
			}
		}
		if(v.first<m)
		{
			int del=d[v.first+1]-d[v.first]+v.second;
			if(del<G)
			{
				if(dis[v.first+1][del]<0)
				{
					dis[v.first+1][del]=dis[v.first][v.second];
					q.push_front(make_pair(v.first+1,del));
				}
			}
			if(del==G)
			{
				if(dis[v.first+1][0]<0)
				{
					dis[v.first+1][0]=dis[v.first][v.second]+1;
					q.push_back(make_pair(v.first+1,0));
				}
			}
		}
	}
	int ans=-1;
	for ( int i=0;i<G;i++ ) 
	{
		if(dis[m][i]<0) continue;
		int gs=dis[m][i];
		int tim=1ll*gs*(R+G)+i;
		if(!i&&dis[m][i]) tim-=R;
		if(ans<0||ans>tim) ans=tim;
	}
	printf("%lld
",ans);
	return 0;
}