JZTXT

Educational Codeforces Round 116 (Rated for Div. 2)

发布时间 2023-03-23 16:53:49作者: 努力的德华

题目链接

A

核心思路

这个题目相当的玄学，所以如果遇到实在不会的题目。那么直接从样例入手吧，我们可以从样例发现每次改的都是开头或者最后的一个。于是大胆的猜测啊。会不会只要改动开头或者是结尾的呢。

结论：如果开头和结尾相同就不需要改，如果需要就要改。

数学归纳法：

  1. n=3,aba这种情况显然成立。
  2. n=n+1,这个的话如果我们肯定总可以找到一个点使得二者相同，然后以这个点为分界线划为的两个字串肯定也相同。如果找不到这么一个点，那就是abbb...bba的情况，很显然也是相同的。
// Problem: A. AB Balance
// Contest: Codeforces - Educational Codeforces Round 116 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1606/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

void solve()
{
	string s;
	cin>>s;
	int len=s.size();
	int pos=len-1;
	if(s[0]==s[pos])
	cout<<s<<endl;
	else
	{
		if(s[0]=='a')
		s[0]='b';
		else
		s[0]='a';
		cout<<s<<endl;
	}
}


signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
return 0;
}

B

核心思路

这个显然就是从局部的构造入手就好了。

node:1 2 4 8 16...

liner:1 2 4 8 16..

这是一个很神奇的规律可以说。

// Problem: B. Update Files
// Contest: Codeforces - Educational Codeforces Round 116 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1606/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

void solve()
{
	int n,k;
	cin>>n>>k;
	int ans=0,cur=1;
	while(cur<k)
	{
		cur*=2;
		++ans;
	}
	if(cur<n)
	ans+=(n-cur+k-1)/k;
	cout<<ans<<endl;
}


signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
}

C

核心思路

这个题目更加的简单，其实完全可以根据样例模拟出来，就是一个贪心，先从小的开始拿但是有一个需要注意的点就是我们最大拿的数量是\(a[i+1]/a[i]-1\).至于为什么其实也比较好理解，因为一旦超过这个数量了，那就可以使用一张a[i+1]的替换了。

// Problem: C. Banknotes
// Contest: Codeforces - Educational Codeforces Round 116 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1606/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}

void solve()
{
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++)
	cin>>a[i];
	k++;
	vector<int> p;
	for(int i=0;i<n;i++)
	p.push_back((int)qmi(10,a[i]));
	// for(int i=0;i<n;i++)
	// cout<<p[i]<<" ";
	// cout<<endl;
	int ans=0;
	for(int i=0;i<n;i++)
	{
		int cnt=k;
		if (i<n-1)
		cnt=min(cnt,p[i+1]/p[i]-1);
		ans+=cnt*p[i];
		k-=cnt;
	}
	cout<<ans<<endl;
	
}



signed main()
{
int t;
cin>>t;
while(t--)
{
	solve();
}
}

E

核心思路

这个题目其实并不是很好想，我们需要想把题目抽象出来就是假设有n为勇士还活着那么每一位勇士需要减去n-1的生命值。因为每个勇士会受到其实n-1位勇士的攻击。

首先看下数据范围500，所以我们会想这可以使用dp来做吧，但是首先有一个很重要的地方是我们怎么去设计他的状态呢，我们看哪些状态可以随着时间的变化而变化，并且根据这个范围我们可以知道的是我们设立含有两个状态的集合。

我们可以知道的是存活的勇士的数量，和他们的生命值的范围这个是会变化的。

集合定义

\(f[i][j]表示的是还存活着i个人，血量的范围是j的方案数\)

集合划分

我们可以由淘汰的人数来对我们的集合进行划分：假设淘汰了k个人。因为这一轮扣除的血量是n-1,这里我们的大集合是\(dp[n][x]\).所以划分的小集合是\(dp[n-k][x-n+1]\).总共有k个人的血量是\(1\sim n-1\)的。我们可以把\(1\sim n-1\)的血量分配给k个人。所以也就是\((n-1)^k\).然后我们还要从n个人里面选出来k个人啊。所以也就是\(C_{n}^{k}\).

状态转移方程

\(dp[n][x]+=\sum_{k=0}^{n-2}(n-1)^k*C_{n}^{k}*dp[n-k][x-n+1]\).

这里我们采用记忆化来做的，所以我们需要对于一轮就淘汰的情况进行讨论下。因为数学归纳法嘛，一轮就淘汰了，那就是说明全部人的血量都是\(1 \sim n-1\)然后我们分配给这么多个人就好了。

// Problem: E. Arena
// Contest: Codeforces - Educational Codeforces Round 116 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1606/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 
const int N=550;
int c[N][N],dp[N][N];
const int mod= 998244353;

void Init()
{
for(int i=0;i<N;i++)
{
	for(int j=0;j<=i;j++)
	{
		if(i==0||j==0)
		c[i][j]=1;
		else
		{
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
}	
	
}
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}
LL dfs(int n, int x) {
    if (dp[n][x]) return dp[n][x];
    dp[n][x] = qmi(min(x, n - 1), n);
    if (x <= n - 1) return dp[n][x];
    for (int i = 0; i <= n - 2; i ++ ) dp[n][x] = (dp[n][x] + qmi(n - 1, i) * dfs(n - i, x - n + 1) % mod * c[n][i] % mod) % mod;
    return dp[n][x];//这里之所以是n-2是因为如果存活了一个人那么就不是合法的方案了。
}


signed main()
{
	IOS;
Init();
int n,m;
cin>>n>>m;
cout<<dfs(n,m)<<endl;
return 0;

}