Educational Codeforces Round 119 (Rated for Div. 2)
我真是越来越菜了，现在竟然连a都做不出来了，o(╥﹏╥)o
A
这个题是对于每一个ai和ai+1,（an和a1)都有一个判断，判断这两个是否相等，N代表着不相同，E代表相同，问我们是否可以找出这样一个数组
我就直接讲解法了吧
我们可以把这一串看成一个环，对于只有一个N的情况，那么一定是不符合条件的
#include <iostream>
#include <string>
using namespace std;
const int maxn=2e5+10;
int t;
string s;
void solve()
{
cin>>s;
int cnt=0;
for (int i=0;i<s.size();i++)
{
if (s[i]=='N') cnt++;
}
if (cnt==1)
{
cout<<"NO\n";
}
else
{
cout<<"YES\n";
}
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这个题目是给予我们一个串，里面有a，是固定的，还有一种字符是*，这种事可以变化的，我们可以变成0到k个b,我们需要找出第x个小的字符
这一个我一开始看到代码，还以为是逆康拓展开，仔细一看，还是不同的
但是还是有一些操作也和逆康拓相似的
对于第一小的，是所有的*都变成0个b
我们要想增加到1,那么我们需要把加上一个b(在最后)，要增加到x,如果这一个*不够（最多只可以变成k个b),那么我们可以往前找，再把此时需要的次序还要更新（到了第二个 * 号，我们的次序增加了（k+1)个）,一直往前找，对于这一个 * 号，需要变成多少个b,就是此时还需要往前找的数量sum%(k+1)，对于k是有多少个连续的 * 号
其实这一个操作过程就好像把x变成是一个k+1进制的数（这个k是连续cnt个 * 号，k=cnt*k,对于每一位，其中的进制中的每一个k有可能是不同的），仔细想想，好像也符合题意。
比如一个二级制，每一位都只能选0或者是1
最小的就是00，第二小的是01，第三小的是10，第四小的是11
就觉得蛮妙的
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int maxn=2e3+10;
int n,k,t,x;
string s;
int idx,idx2;
int a[maxn],b[maxn];
void calc(int n,int k)
{
for (int i=n;i>=0;i--)
{
b[i]=k%(a[i]+1);//就算是0也不怕，索性就直接往前遍历了
k/=(a[i]+1);
}
return ;
}
void solve()
{
cin>>n>>k>>x;
cin>>s;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
idx=0,idx2=0;
for (int i=0;i<n;i++)
{
if (s[i]=='a')
{
if (a[idx])
{
idx++;
}
}
else
{
a[idx]+=k;
}
}
calc(idx,x-1);
for (int i=0;i<n;i++)
{
if (s[i]=='a')
{
if (i&&s[i-1]=='*')
{
for (int j=0;j<b[idx2];j++)
{
cout<<'b';
}
idx2++;
}
cout<<'a';
}
}
if (idx2<=idx)
{
while (idx2<=idx)
{
for (int j=0;j<b[idx2];j++)
{
cout<<'b';
}
idx2++;
}
}
cout<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个大意是有n个数，我们需要用1,2,3这三个数需要总共多少个，可以对于所有的数都可以满足
那么我们可以贪心的来看，我们要尽量的多用3
对于那些必须用的1或者2还有些判断，具体看代码吧
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2e5+10;
int n,a[maxn],t;
void solve()
{
cin>>n;
int t1=0,t2=0,t3=0;
int mx=0,mi=1e9;
for (int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
mi=min(mi,a[i]);
if (a[i]%3==0)
{
t3=max(t3,a[i]);
}
else if (a[i]%3==1)
{
t1=1;
}
else
{
t2=1;
}
}
int ans=0;
if (mx%3==0)//如果最大的数%3==0，那么对于需要2的数，我们可以多出一个2，对于还有需要1的数我们还可以多加一个1，对于既有1，又有2的情况，我们把最大的那一个的需要的3换成2和1，那么我们就只多出一个了
{
ans=mx/3+(t1|t2);
}
else if (mx%3==2)
{
ans=mx/3+1+t1;//对于这一类，2是必须的，如果有需要1，就加一
}
else //对于多出了一个1，对于最后4个，我们有两种选择,但是不管怎样，都会加一
// 1 3
// 2 2
//如果我们需要2 ，那么我们就只能是2 2了，
//如果我们还有一个1，我们就必须还要加一（对于余数为1的，我们也看用2 2的方式转换
//如果第二小的数%3==0，那么我们就必须要t3/3个3，那么我们就只可以用1 3的方式来了，那么我们只能在多出一个1了
{
ans=mx/3+1+(t2&(mi==1||t3+1==mx));
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}