Codefoece Educational Codeforces Round 83(Rated for Div. 2) 문제 풀이(ABCDE)

경기 링크 A 문제: 사고방식: 출석 문제.코드:

#include
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int t,n,m;
int arr[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		if(n<=4)
		{
			cout<<"NO"<<endl;
		}
		else
		{
			if(n%m) cout<<"NO"<<endl;
			else cout<<"YES"<<endl;
		}
	}
	return 0;
}

B문제: 사고방식: 문제에 서명하고 제목이 요구하는 부등식 항목을 옮긴 다음에 수조를 큰 것에서 작은 것까지 정렬하면 조건에 부합된다는 것을 발견한다.코드:

#include
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int t,n,m;
int arr[maxn];
bool comp(int a,int b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>arr[i];
		}
		sort(arr+1,arr+1+n,comp);
		for(int i=1;i<=n;i++)
		{
			if(i==1) cout<<arr[i];
			else cout<<" "<<arr[i];
		}
		cout<<endl;
	}
	return 0;
}

C문제: 사고방식: 2진법 1100110과 같이 모든 사람이 하나를 가져올 필요가 있는지 살펴보고 시뮬레이션을 하면 된다. 최종적으로 k의 i차원이 한 번 이상 사용된 것은 합법적이지 않다.코드:

#include
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
ll t,n,m;
ll arr[maxn];
int rec[105];
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
		memset(rec,0,sizeof(rec));
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>arr[i];
		}
		int flag=1;
		for(int i=1;i<=n;i++)
		{
			if(arr[i]==0) continue;
			if(arr[i]==1)
			{
				rec[0]++;continue;
			}
			ll z=arr[i];
			ll tmp=1;int num=0;
			while(tmp<=z)
			{
				tmp=tmp*m;num++;
			}
			tmp=tmp/m;num--;
			while(z)
			{
				while(z>=tmp)
				{
					z=z-tmp;
					rec[num]++;
				}
				tmp=tmp/m;num--;
			}
		}
		for(int i=0;i<=103;i++)
		{
			if(rec[i]>1)
			{
				flag=0;break;
			}
		}
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

D문제: 사고방식: 분명히 추식이 필요하다. 총 m명, 수열 총 n개수, 서로 다른 숫자 n-1개가 필요하다. 따라서 m에서 n-1개의 다른 숫자를 먼저 골라야 한다. C(m, n-1), 그리고 n-1개의 숫자 중 가장 큰 숫자는 반드시 중전점이다. 중전점은 두 번 나오는 그 숫자가 될 수 없기 때문에 나머지 n-2개의 숫자에서 두 번 나오는 숫자를 찾아야 한다. 따라서 하나를 곱해야 한다(n-2).나머지 n-3개의 숫자는 중전점에서 왼쪽이든 오른쪽이든 두 번 나오는 숫자는 고려할 필요가 없다. 남은 n-3개의 숫자는 왼쪽에서 오른쪽으로 갈 수 있기 때문에 2의 (n-3) 차원을 곱해야 한다.루카스와 스피드 멱을 끼워서 답을 계산할 수 있다.주의해야 할 것은 n이 2일 때 쾌속멱 중의 횟수는 -1이어서 끊겨 죽는다.따라서 2면 특판, n은 2일 때 바로 0을 출력한다.판자는 인터넷에서 찾은 세트이다.
코드:

#include 
#include 
#include 
using namespace std;

typedef long long LL;

LL fast_power(LL a,LL b,LL p){
    LL ans=1;
    a%=p;
    while(b){
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

LL C(LL a,LL b,LL p){
    if(b>a) return 0;
    if(a==b) return 1;
    LL ans1=1,ans2=1;
    for(LL i=1;i<=b;i++){
        ans1=ans1*(a-i+1)%p;
        ans2=ans2*i%p;
    }
    return ans1*fast_power(ans2,p-2,p)%p;
}

LL Lucas(LL a,LL b,LL p){
    if(b==0) return 1;
    return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;
}

int main(){
    int t;
        LL n,m,p;
        cin>>n>>m;
        p=998244353;
        LL fin=0;
        if(n==2)
        {
        	cout<<"0"<<endl;
        	return 0;
		}
		LL zz=(Lucas(m,n-1,p)*fast_power(2,n-3,p))%p;
		fin=zz;
        cout<<(fin*(n-2))%p<<endl;
    return 0;
}

E문항:
사고방식: n의 크기는 500이고 이동은 하나의 구간의 이동을 관찰하기 때문에 기본적으로 구간 dp를 확정한다.주의해야 할 것은 이동 과정에서 각 구간의 왼쪽 오른쪽의 값을 기록하여 이동을 보조해야 한다는 것이다.코드는 기억화된 검색형의 구간 DP를 썼다.
코드:

#include
using namespace std;
const int maxn=550;
int dp[maxn][maxn];
int t,n,m;
int arr[maxn];
int ll[maxn][maxn],rr[maxn][maxn];
int solve(int l,int r)
{
	if(l==r)
	{
		dp[l][r]=1;ll[l][r]=rr[l][r]=arr[l];
		return 1;
	}
	if(dp[l][r]<=n) return dp[l][r];
	for(int i=l;i<r;i++)
	{
		if(dp[l][r]>(solve(l,i)+solve(i+1,r)-(rr[l][i]==ll[i+1][r])))
		{
			dp[l][r]=dp[l][i]+dp[i+1][r]-(rr[l][i]==ll[i+1][r]);
			ll[l][r]=ll[l][i];rr[l][r]=rr[i+1][r];
			if(rr[l][i]==ll[i+1][r])
			{
				if(dp[l][i]==1) ll[l][r]++;
				if(dp[i+1][r]==1) rr[l][r]++;
			}
		}
	}
	return dp[l][r];
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	int fin=n;
	memset(dp,0x3f,sizeof(dp));
	fin=min(fin,solve(1,n));
	cout<<fin<<endl;
	return 0;
}

휴, 퇴근했어.