526互联

Educational Codeforces Round 120

发布时间 2023-08-25 10:20:07作者: gan_coder

传送门
今天依然是4题
B题就是猜结论，其实证明应该也不难，分类讨论一下就行

C题肯定是让最小的减，然后从大到小用set操作
那么我们枚举set了多少个数，算一下至少要减多少，
需要注意的是，如果要减到的数x大于a1，那么减的这部分代价为0，直接减会减出负数导致WA

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef long long ll;
const int N=2e5+5;
ll s[N],k,n,ans,a[N],j,res,x;
int main() {

//    freopen("data.in","r",stdin);
	
	int T;
	scanf("%d",&T);
	while (T--) {
		scanf("%lld %lld",&n,&k);
		
		fo(i,1,n) scanf("%lld",&a[i]);
		sort(a+1,a+n+1);
		fo(i,1,n) s[i]=s[i-1]+a[i];
		
		if (s[n]<=k) {
			puts("0"); continue;
		}
		ans=s[n]-k;
		
		fo(i,2,n) {
			res=s[i-1]-a[1];
			j=n-i+1;
			
			x=(k-res)/(j+1);
			
			if (x*(j+1) + res > k) x--;
			
			if (x>=a[1]) ans=min(ans,j);
			else ans=min(ans, j + a[1]-x);
		}
		printf("%lld\n",ans);
	}	
	
	return 0;
}

D题很像之前做过的一道题，C. 0689
一样的，我们强制左端点一定要改变，否则的话，贡献会在后面计算
然后对于从后往前第k个1，后面已经不会在计算了，所以一次性在此处算完后面的贡献即可，也就是这个位置可以不改变。
复杂度O(n)，当时看着5000的数据范围，还以为做法假了

忘记注释文件操作，又WA一发。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mo=998244353;
ll n,k,f[N],inv[N],ans,c0,c1,j;
char s[N];
void add(ll &x,ll y){
	x=(x+y)%mo;
}
ll power(ll a,ll b){
	ll t=1,y=a;
	while (b){
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
ll F(ll n,ll m){
	return f[n+m]*inv[n]%mo*inv[m]%mo;
}
int main() {

//    freopen("data.in","r",stdin);

	f[0]=1;
	for (ll i=1;i<=5000;i++) f[i]=f[i-1]*i%mo;
	inv[5000]=power(f[5000],mo-2);
	for (ll i=4999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mo;
	
	scanf("%lld %lld",&n,&k);
	scanf("%s",s+1);
	
	int tot=0;
	fo(i,1,n) if (s[i]=='1') tot++;
	
	if (!k) {
		if (tot==n) puts("1");
		else puts("1");
		return 0;
	}
	
	if (tot<k) {
		puts("1");
		return 0;
	}
	
		
	c0=c1=0;
	j=0;
	fo(i,1,n) {
		while (j<n && (c1!=k || s[j+1]=='0')) {
			if (s[j+1]=='1') c1++; 
			else c0++;
				
			j++;
		}
			
		if (c1!=k) break;
		if (j==n && s[i]=='1') {
			add(ans, F(c0,c1));
			break;
		}
		
		if (s[i]=='1') {
			if (c0) add(ans, F(c0-1,c1));
		}
		else{
			if (c1) add(ans, F(c0,c1-1));
		}
			
		if (s[i]=='0') c0--;
		else c1--;
		
//		printf("%lld\n",ans);
	}

	printf("%lld\n",ans);
	
	
	return 0;
}