牛客周赛 Round76 (A~E)

A

先算出工作了几个星期，那么小红的工作天数 = 星期数 * 5 + 剩下的天数（超过5天按5天算）

#include<iostream>
using namespace std;
int main()
{
    int n; cin >> n;
    int day = n / 7 * 5;
    n = n % 7;
    if(n > 5) n = 5;
    day += n;
    cout << day * 3;
    return 0;
}

B

如果已经求出了出现次数最多的字串，而长度为1的字串就是该字串的字串，所以只需统计长度为1的字串就好了,也就是求出现次数最多的字母

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;

char s[N];
int st[26];

void solve()
{
	int n; cin >> n;
	cin >> s;
	for(int i=0;i<n;i++) st[s[i] - 'a'] ++;
	int ch = 0 , cnt = 0;
	for(int i=0;i<26;i++)
	{
		if(st[i] > cnt)
		{
			ch = i;
			cnt = st[i]; 
		}
	}
	cout << (char)(ch+'a');
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	while(_--) solve();
	return 0;
}

C

执行任意次操作后，数组所有元素都会等于所有数的最大公约数，所以找出所有数的最大公约数就好了 x * n 可能超出 int 范围，所以要开 long long

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 100010 , INF = 0x3f3f3f3f;

int a[N];

void solve()
{
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	sort(a+1 , a+1+n);
	int x = a[1];
	for(int i=2;i<=n;i++) x = __gcd(x,a[i]);
	cout << x * n;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	while(_--) solve();
	return 0;
}

D

错误理解：要让和尽可能小，所以每次取数组中最大的数将其除以2。维护一个单调的数组，每次取出最大值，若为奇数且 $k>0$ 则将其减去1后放回数组，若为偶数且 $m>0$ 则将其除2后再放回数组。若 $k=0$ （ $m=0$ ）就将该数直接加入结果。若取出的最大值为0，则说明答案已经无法更小了，直接退出即可。（赛时分成了两个单调的奇数和偶数数组）

虽然按照以上方法确实可以过题，但其实这道题是个假题（官方题解里看到的）

hack 数据如下

2 2 1
11 9

按照上述算法结果是14 ，但实际结果是13 ，因为实际上让9变成8后可以利用两次除法操作，而11变成10后只能进行一次除法操作

代码如下，看看就好，我也不知道正确的该怎么写

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> PII;

void solve()
{
	int n , m , k; cin >> n >> m >> k;
    ll sum = 0;
    priority_queue<int> q;
    while(n --)
    {
        int x; cin >> x;
        q.push(x);
    }
    while(q.size())
    {
        int t = q.top(); q.pop();
        if(t == 0) break;
        if(t % 2)
        {
            if(k)
            {
                q.push(t - 1);
                k --;
            }
            else sum += t;
        }
        else
        {
            if(m)
            {
                q.push(t / 2);
                m --;
            }
            else sum += t;
        }
    }
	cout << sum;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	while(_--) solve();
	return 0;
}

~~比赛时丑陋的代码~~

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> PII;
const int N = 200010 , INF = 0x3f3f3f3f;

int a[N];
priority_queue<int> q1 , q2;

void solve()
{
	int n , m , k; cin >> n >> m >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
	ll sum = 0;
	for(int i=1;i<=n;i++) sum += a[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i] % 2) q1.push(a[i]);
		else q2.push(a[i]);
	}
	while(m || k)
	{
		int x1 = 0 , x2 = 0;
		if(!q1.empty()) x1 = q1.top();
		if(!q2.empty()) x2 = q2.top();
		if(m == 0 && q1.empty()) break;
		if(x1 == 0 && x2 == 0) break;
		if(k == 0 && q2.empty()) break;
		// cout << x1 << x2 << '\n';
		if(x1 < x2 && m && !q2.empty())
		{
			m --;
			q2.pop();
			x2 >>= 1;
			sum -= x2;
			if(x2 % 2) q1.push(x2);
			else q2.push(x2);
		}
		else if(k && !q1.empty())
		{
			k --;
			q1.pop();
			x1 -- , sum --;
			q2.push(x1);
		}
		else if(m && !q2.empty())
		{
			m --;
			q2.pop();
			x2 >>= 1;
			sum -= x2;
			if(x2 % 2) q1.push(x2);
			else q2.push(x2);
		}
		else break;
	}
	cout << sum;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	while(_--) solve();
	return 0;
}

E

题目要求 $n-m^k$ 足够小，也就是让 n 和 $m^k$ 足够接近。先考虑 m 取 $\lfloor\sqrt[k]{n}\rfloor$ 的情况，再比较 $m^k$ 和 (m+1)^k哪个与 n 更接近，答案就是哪个
记得开long long

#include<bits/stdc++.h>
using namespace std;

long double n , k;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t; cin >> t;
    while(t --)
    {
        cin >> n >> k;
        long long m = pow(n,(1/k));
        if(n-pow(m,k) > pow(m+1,k)-n) cout << m + 1 << '\n';
        else cout << m << '\n';
    }
    return 0;
}