A
核心思路
这个题目相当的玄学，所以如果遇到实在不会的题目。那么直接从样例入手吧，我们可以从样例发现每次改的都是开头或者最后的一个。于是大胆的猜测啊。会不会只要改动开头或者是结尾的呢。
结论：如果开头和结尾相同就不需要改，如果需要就要改。
数学归纳法：
- n=3,aba这种情况显然成立。
- 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;
}