思路:
用较少的那个字符去间隔更多的那个.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n,r,b;
cin>>n>>r>>b;
string ans;
if(r==b)
{
char head='R';r--;
ans+='R';
for(int i=1;i<=r+b;i++)
{
if(head=='R')ans+='B',head='B';
else ans+='R',head='R';
}
}else
{
if(r>b)
{
int res1=r/(b+1),res2=r%(b+1);
char head='B';
for(int i=1;i<=2*b+1;i++)
{
if(head=='B')
{
for(int i=1;i<=res1;i++)cout<<"R";
if(res2)cout<<"R",res2--;
head='R';
}else cout<<'B',head='B';
}
}else
{
int res1=b/(r+1),res2=b%(r+1);
char head='R';
for(int i=1;i<=r*2+1;i++)
{
if(head=='R')
{
for(int i=1;i<=res1;i++)cout<<"B";
if(res2)cout<<"B",res2--;
head='B';
}else cout<<"R",head='R';
}
}
}
cout<<endl;
return ;
}
//CCCC
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
思路:
由于之前出过一样的.思路是一致的.
对于同一个位置操作两次.等价于在不影响局面的情况下.凭空减少两次操作.
对于不同操作位置而言有三种情况:
$(1,0)$对于而言相当于交换$1$和$0$
$(0,0)$相当于让两个$0$变成两个$1$
$(1,1)$相当于让两个$1$变成两个$0$.
由此当$k$为奇数的时候只需要考虑如何交换使得前面的$0$尽可能多即可.因为是奇数所以一定有翻转.
当$k$为偶数的时候只需要考虑如何交换使得前面$1$尽可能多即可.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n,k;
cin>>n>>k;
string s;cin>>s;
vector<int>ans(n+1,0);
if(k%2!=0)
{
int l=0;
while(l<n&&k>1)
{
while(l<n&&s[l]=='0')l++;
int r=l+1;
while(r<n&&s[r]=='0')r++;
if(r>=n)break;
else
{
s[l]=s[r]='0';
ans[l+1]++,ans[r+1]++;
k-=2;
l=r+1;//更新指针
}
}
while(l<n&&k>1)
{
while(l<n&&s[l]=='0')l++;
int r=n-1;
while(r>l&&s[r]=='1')r--;
if(r<=l)break;
else
{
swap(s[l],s[r]);
ans[l+1]++,ans[r+1]++;
k-=2;
l=r+1;
}
}
if(k>1)ans[1]+=k-1,k=1;//在第一个位置上把操作用到只有1
while(l<n&&s[l]=='0')l++;
if(l==n)l--;
ans[l+1]++;
for(int i=0;i<n;i++)
if(i!=l)
{
if(s[i]=='0')s[i]='1';
else s[i]='0';
}
cout<<s<<endl;
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
}else//偶数
{
int l=0;
while(l<n&&k>0)
{
while(s[l]=='1'&&l<n)l++;
int st=l+1;
while(s[st]=='1'&&st<n)st++;
if(st>=n)break;
else
{
s[l]='1',s[st]='1';
ans[l+1]++,ans[st+1]++,k-=2;
l=st+1;
}
}//每次可以增加两个1
int r=n-1;
while(l<r&&k>0)
{
while(s[r]=='0'&&r>l)r--;
while(s[l]=='1'&&r>l)l++;
if(r>=l)
{
swap(s[r],s[l]);
ans[l+1]++,ans[r+1]++,k-=2;
}
}//考虑是否可以交换在前面产生一个1
if(k)ans[1]+=k;//剩余操作
cout<<s<<endl;
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
思路:贪心.
和之前牛客月赛某题类似.
由于只有可能不断向右扩展,且必须扩展才可以移动.
因此每次考虑的就是对于之后的操作,是考虑移动到下一个已经占领的位置,还是不移动来的更优.
对于两种局面进行一个比较即可.
Code：
ll res1=a*(d[i]-cur);
ll res2=b*(d[i]-cur)*(n-i);
if(res1<res2)ans+=res1,cur=d[i];//移到下一个点更合适
AC Cde：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
ll n,a,b;
cin>>n>>a>>b;
vector<ll>d(n+1);
ll ans=0;
for(int i=1;i<=n;i++)cin>>d[i];
int cur=0;
for(int i=1;i<=n;i++)
{
ans+=b*(d[i]-cur);
ll res1=a*(d[i]-cur);
ll res2=b*(d[i]-cur)*(n-i);
if(res1<res2)ans+=res1,cur=d[i];//移到下一个点更合适
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
思路:
首先对于任意一种情况的$B$而言其$0$和$1$的数量都是一样的.
因此先求总和$sum$
每一个$B_i$中$1$的数量就是$\frac{sum}{n}$
考虑从后往前构造每一位$ans_i$
由于对于最后一位而言,前$1$到$n-1$个$B$最后一位是一样的.
因为只有$B_n$才会对第$n$位进行一个$sort$操作.
那么我们就可以知道$C_n$的值一定是固定的几种可能.
$C_n=0$.此时每一种$B$在最后一位都是0.因此$ans_n = 0$
$C_n=n$.此时每一种$B$都必然在最后一位是1.因此$ans_n=1$
$C_n=1$.此时这个$1$必然是在$B_n$的最后一位上.因为前面的$B$在最后一位上是一样的
如果有一个是$1$,全部就都在该为上是$1$了,那么$C_n=n$
而且$C_n$因此我们就考虑完了所有$C_n$的情况.
那么如何构造其他位呢?
很简单,每次只需要从$C$中扣掉$B_n$的贡献就可以了.
因为$B_n$是全排序的.所以前面是全$0$,后面是当前还有几个没有分配掉的$1$.
这样我们就很容易的将$n-1$变成了一个前面一样的局面.重复上述过程即可构造出$A$
实际上这个过程就是区间修改,单点查询.因为每次需要知道$C_i$在更新完以后是多少.
这个可以用树状数组来维护,,因为不需要知道之前的是什么所以也可以用一个后缀差分数组来维护.
差分 Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
ll sum=0;
vector<int>c(n+1);
vector<int>t(n+1,0);//构造差分维护动态修改前缀以及求和
for(int i=1;i<=n;i++)cin>>c[i],sum+=c[i];
t[n]=c[n];//构造差分后缀
for(int i=n-1;i>=1;i--)t[i]=c[i]-c[i+1];
ll k=sum/n;//A中应该要有几个1
vector<int>ans(n+1);
int cnt=0;//
for(int i=n;i>=1;i--)
{
c[i]=cnt+t[i];//得到c[i]的实际值
if(c[i]==i)
{
ans[i]=1;
int x=i-k+1;
t[i]-=1;
t[x-1]+=1;
cnt+=t[i];k--;
}
else
{
ans[i]=0;
int x=i-k+1;
t[i]-=1;
t[x-1]+=1;
cnt+=t[i];
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(N)$
树状数组 Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n;
int tr[N];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
int query(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void solve()
{
cin>>n;
ll sum=0;
vector<int>c(n+1);
for(int i=1;i<=n;i++)cin>>c[i],sum+=c[i];
ll k=sum/n;//A中应该要有几个1
vector<int>ans(n+1);
int cnt=0;//
for(int i=n;i>=1;i--)
{
c[i]=c[i]+query(i);
if(c[i]==i)
{
ans[i]=1;
int x=i-k+1;
add(x,-1);
k--;
}
else
{
ans[i]=0;
int x=i-k+1;
add(x,-1);
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
for(int i=1;i<=n;i++)tr[i]=0;//初始化
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(N*\log N)$
