Educational Codeforces Round 116 (Rated for Div. 2)

A - AB Balance

分析：

• 思维题，只有 a b ab ab 两个字符，可以发现 a b ab ab， b a ba ba 的差值最大为 1 1 1

  并且，当开头和结尾为同一个字符时，差值必定为 0 0 0

  因此，只需判断一下开头结尾，修改一个字符即可

#include <bits/stdc++.h>
using namespace std;
 
const int N=105;
char s[N];
signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>s+1;
		int n=strlen(s+1);
		if(n>1 && s[1]!=s[n])
		{
			if(s[n]=='a') s[n]='b';
			else s[n]='a';
		}
		cout<<s+1<<endl;
	}
}

B - Update Files

分析：

• 就模拟，先将电脑数增加到大于等于 k k k 的情况，再除 k k k 即可

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int s[N];
signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		if(n==1) cout<<"0"<<endl;
		else 
		{
			s[0]=1;
			for(int i=1;i<=60;i++) s[i]=s[i-1]<<1;
			int p=0;
			int sum=0,ans=0;
			for(int i=1;i<=60;i++)
			{
				if(s[i]>=n) 
				{
					ans=i; break;
				}
				if(s[i]>=k)
				{
					p=i;
					break;
				}
			}
			if(ans) cout<<ans<<endl;
			else 
			{
				n-=s[p];
				ans=p+n/k;
				if(n%k) ans++;
				cout<<ans<<endl;
			}
		}
	}
}

C - Banknotes

分析：

• 模拟题 + + + 贪心，会卡 p o w pow pow（ p o w pow pow 精度很低），每次相邻两位 a a a 的差值，取最多的 9 9 9

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int a[N],b[N];
int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a;
		a=a*a; b>>=1;
	}
	return ans;
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		for(int i=0;i<=12;i++) a[i]=b[i]=0;;
		for(int i=1;i<=n;i++) cin>>a[i];
		k++;
		for(int i=1;i<n;i++)
		{
			int t=ksm(10,a[i+1]-a[i])-1;
			if(t<=k)
			{
				b[i]=t;
				k-=t;
			}
			else 
			{
				b[i]=k;
				k=0;
			}
		}
		b[n]=k;
		int ans=0;
		for(int i=1;i<=n;i++) ans+=ksm(10,a[i])*b[i];
		cout<<ans<<endl;
	}
}