牛客周赛39

title: 牛客周赛39
date: 2024-04-07 21:42:57
tags: 赛后思考与总结
categories: 比赛

A

思路

a[1] * 30 < sum 即可

代码

int a[7];
void solve()
{
	int sum = 0;
	for(int i = 1; i <= 6; i ++) cin >> a[i],sum += a[i];
	
	if(a[1] * 30 <	sum) cout << "Yes" << endl;
	else cout << "No" << endl;
}

B

思路

贪心，从最小的开始取，最后不满足k的有多少组就是答案

代码

void solve()
{
	int n,k;
	cin >> n >> k;
    vector<int> a(n + 1);
	ll sum = 0;
	for(int i = 1; i <= n ; i++){
		cin >> a[i];
        sum += a[i];
	}
	if(sum % k == 0){
        cout << 0 << endl;
        return;
    }
    sort(a.begin() + 1,a.end());
    
    ll ans = 0;
    int cnt = 0;
    for(int i = 1; i <= n ; i++){
    	ans += a[i];
        cnt ++;
        if(ans >= k){
            ans %= k;
            if(ans) cnt = 1;
            else cnt = 0;
        }
       
    }
	cout << cnt << endl;
}

C

思路

将每个数模3，那么问题就转化成能够构成3的倍数，每个组合求一下,{1,1,1},{1,2},{0}。

代码

void solve()
{
	int n,p;
	cin >> n >> p;
	map<int,int> mp;
	vector<int> a(n + 1);
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
		a[i] %= p;
		mp[a[i]] ++;
	}
	
	if(mp[0]) cout << 1 << endl;
	else if(mp[1] && mp[2]) cout << 2 << endl;
	else if(mp[1] >= 3) cout << 3 << endl;
	else if(mp[2] >= 3) cout << 3 << endl;
	
}

D

思路

最短路算法，同样也是取模，问题就转化成寻找 (x + a[i]) % p == 0的最短路径，最先出现的肯定是最短的

代码

ll n,p,cnt,ans,a[N],f[N],d[N];

queue<PII> q;

void solve()
{
	cin >> n >> p;
	for(int i = 1; i <= n; i ++){
		int x; cin >> x;
		x %= p;
		if(d[x] == 0){
			d[x] = 1;
			a[++cnt] = x;
			q.push({x,1});
		}
	}
	
	n = cnt;
	while(q.size()){
		auto [x,y] = q.front();
		q.pop();
		
		for(int i = 1; i <= n ; i++){
			ll nx = (x + a[i]) % p;
			if(d[nx] == 0){
				q.push({nx,y + 1});
				d[nx] = y + 1;
			}
		}
		
		if(d[0]){
			ans = d[0];
			break;
		}
	}
	
	cout << ans << endl;
}

E

思路

n * m * p肯定超时，优化一下，根据面积公式 (i * j + 2 * k * (i + j))可以转化为，在枚举每一个长和宽的时候，他对应的合法高度为多少，将合法高度累加即是答案

代码

void solve()
{
    int n,m,p;
    cin >> n >> m >> p;
    int x; cin >> x;
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int sum = x - i * j;
            if(sum > 0 && sum % (2 * (i + j)) == 0){
                int k = sum / (2 * (i + j));
                if(k <= p) ans ++;
                //cout << i << ' ' << j << ' ' << k << endl;
            }
        }
    }
     
    cout << ans << endl;
     
}

F

思路

不能理解 $n^2$ 能够过，但是暴力是真牛逼

代码

void solve()
{
    int n; cin >> n;
    string a,b;
    cin >> a >> b;
    a = " " + a;
    b = " " + b;
    int ans = 0;
    for(int i = 1;  i<= n ; i++) if(a[i] == b[i] && a[i] == '1') ans ++;
    int q; cin >> q;
    while(q --){
        char op[2];
        int l,r;
        cin >> *op >> l >> r;
        if(*op == 'A'){
            for(int i = l;  i<= r ; i++) {
                if(a[i] == '0' && b[i] == '1') ans ++;
                a[i] = '1';
            }
        }
        else {
            for(int i = l; i <= r; i ++) {
                if(a[i] == '1' && b[i] == '0') ans ++;
                b[i] = '1';
            }
             
        }
         
         
         
        cout << ans << endl;
    }
     
     
}