Educational Codeforces Round 120 (Rated for Div. 2) C，D
C
这个题目大意是给我们n个数，我们可以把ai变成ai-1,或者是把ai变成aj,而我们需要知道最少的操作数把n个数的和小于等于k
对于这些个操作，我们可以知道，我们先进行减法操作还是改变值的操作呢
当然是我们如果需要减法操作的话，我们就先对最小的那个进行减法，然后再把后面的若干个数变成那个后面的a1(如果有需要的话)
首先我们先遍历把后面多少个数变成a1,然后再讨论是否需要进行减法操作t
如果不考虑减法
now=sum[i]+(n-i)a[1],前i面个不变，i到n变成a1
如果now<=k t=0
否则，就需要判断需要几个减法操作
cha=k-now
对于这变化的n-i+1(还须包括a1),每多进行一个减法操作，cha就会减去（n-i+1)个，差值会减少，所以我们t就是cha除以n-i+1,向上取整
那么此时用过的操作数是
cnt=n-i+t
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <cmath>
#define int long long
using namespace std;
int n,k;
int t;
void solve()
{
cin>>n>>k;
vector<int>a(n+1,0);
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
vector<int>sum(n+1,0);
sort(a.begin()+1,a.end());
int ans=1e10;
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for (int i=1;i<=n;i++)
{
int t=0;
if (sum[i]+(n-i)*a[1]<=k) t=0;
else
{
t=ceil((sum[i]+(n-i)*a[1]-k)*1.0/(n-i+1));
}
ans=min(ans,n-i+t);
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这一个题大意是我们有一个长度为n的01串，我们可以对一段子串里面有k个1的子串对这些字符进行重排列，我们需要知道最后有多少种不同的排序
这一个是组合问题
我们首先要知道这k个1的跨度，这个跨度我们是这样判断的
以第一个1的位置作为最左边，以最右边是第k+1的前一个位置
如，对于k=2
011000001 那么此时第一段就是01100000
对于这一段里的重排列有多少不同的排列呢
当然是从这里面字符数量里面选出k个位置来放1（但是对于我们为什么没有减去原来的那一个排序呢，请往后看）
但是对于第i段和i+1段，会有重叠的部分（合集）
这个合集还是比较重要的
然后我们就只需要减去这个交集即可。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=3e5+10,mod=998244353;
#define int long long
int inv[maxn],fac[maxn],ifac[maxn];
int n,k;
int pre[maxn],fix[maxn],pos[maxn];
string s;
void init()
{
inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for (int i=2;i<=n;i++)
{
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
fac[i]=fac[i-1]*i%mod;
ifac[i]=ifac[i-1]*inv[i]%mod;
}
return ;
}
int C(int m,int n)
{
return fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}
void solve()
{
cin>>n>>k;
cin>>s;
init();
s=" "+s;
int last=1;
int cnt=0;
for (int i=1;i<=n;i++)
{
if (s[i]=='1')
{
pre[i]=last;//pre是上一1的后面一个位置，这个用于找最左端
last=i+1;
pos[++cnt]=i;
}
}
last=n;
for (int i=n;i>=1;i--)
{
if (s[i]=='1')//这个是找1后面一个1的前一个，用于找最右端
{
fix[i]=last;
last=i-1;
}
}
if (cnt<k||k==0)
{
cout<<1<<'\n';
return ;
}
int res=0;
for (int i=1;i+k-1<=cnt;i++)
{
int l=pre[pos[i]],r=fix[pos[i+k-1]];
int l1=pre[pos[i+1]],r1=r;
res+=C(r-l+1,k);
if (i!=cnt-k+1)//和下一个k的重叠部分（交集）
{
res-=C(r1-l1+1,k-1);
}
res=(res+mod)%mod;
}
cout<<res<<'\n';
return ;
}
signed main ()
{
int t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}