题解 | #SYUCT 结训赛题解#

整体难度：
简单:H、A、B
中等:C、D、E、F
偏难：G、I

A.空哥复习记

仔细读题后可以观察到，操作2一定是最优的，而且每次操作可能将某种字符全部变成b
所以即求出字符串中有多少个不是b字符

#include <iostream>
using namespace std;
int cnt[30];

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] != 'b') cnt[s[i] - 'a'] ++;
    }
    int ans = 0;
    for(int i = 0; i < 26; i ++)
    {
        if(cnt[i] > 0) ans ++;
    }
    cout << ans << "\n";
    return 0;
}

B.空哥的质数(Easy)

此题为easy版， 暴力即可

#include <iostream>
using namespace std;

bool is_prime(int x)
{
    if(x <= 1) return false;
    
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0) return false;
    }
    return true;
}
int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        int ans = 0;
        
        int l, r;
        cin >> l >> r;
        
        for(int j = l; j <= r; j ++)
        {
            if(is_prime(j)) ans ++;
        }
        cout << ans << "\n";
    }
    return 0;
}

C.空哥的质数(Hard)

本题考查素数筛模板
将1e7范围内的质数全部筛出来
最后用sum数组记录，前缀和即可

#include <iostream>
using namespace std;
const int N = 1e7 + 10;

int n;
// primes数组里存放质数  cnt 是最后质数的个数
int st[N], primes[N], cnt;
int sum[N];
void init(int x = N - 10) // 质数筛模板
{
    for(int i = 2; i <= x; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= x; j ++)
        {
            st[primes[j] * i] = 1;
            if(primes[j] % i == 0) break;
        }
    }
}

int main()
{
    init();
    cin >> n;
    for(int i = 2; i <= N - 10; i ++)
    {
        if(!st[i]) sum[i] = 1;
        sum[i] += sum[i - 1];
    }
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l - 1] << "\n"; 
    }
    return 0;
}

D.空哥的数学领域

考察3的倍数的性质：若x为3的倍数，则x的各个数位上的和是3的倍数
根据性质，我们统计出领域中每个数字数位和，再对3取余，统计个数。
答案就是 +

#include <iostream>
#include <algorithm>
using namespace std;
int get(int x) //获得x的数位和
{
    int sum = 0;
    while(x)
    {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int cnt[3];
int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        cnt[get(x) % 3] ++;
    }
    cout << cnt[0] / 2 + min(cnt[1], cnt[2]);
    return 0;
}

E.自律的空哥

经典BFS
看到题意最优策略即为最短路
所以直接BFS 最后遍历调到哪步最短路最大即可

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;

int d[N];
int n, k;
void bfs()
{
    memset(d, -1, sizeof d);
    queue<int> q;
    d[0] = 0;
    q.push(0);
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        int t1 = (t + 1) % n;
        int t2 = (t + k) % n;
        
        if(d[t1] == -1)
        {
            d[t1] = d[t] + 1;
            q.push(t1);
        }
        if(d[t2] == -1)
        {
            d[t2] = d[t] + 1;
            q.push(t2);
        }
    }
}

int main()
{
    cin >> n >> k;
    bfs();
    int ans = 0;
    for(int i = 0; i <= n - 1; i ++)
    {
        ans = max(ans, d[i]);
    }
    cout << ans << "\n";
    return 0;
}

F.空哥的项链

思维
找最长的一段0的个数即可
答案即为 总长 - 最长的0的个数 - 1的个数，就是要操作的个数
考虑到特殊情况即可，这里我采用破环成链，即再复制一遍字符串接在原串后
ps:注意全0的情况

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s = s + s; // 复制一遍
    
    int cnt0 = 0, sum = 0; // 最长0的个数
    int cnt1 = 0; // 1的个数
    for(int i = 0; i < n * 2; i ++)
    {
        if(s[i] == '0')
        {
            cnt0 ++;
        }
        else
        {
            cnt0 = 0;
            cnt1 ++;
        }
        sum = max(sum, cnt0);
    }
    // 因为复制了一遍所以 cnt1 = cnt1 / 2;
    // 判断全0
    cout << max(0, n - (cnt1 / 2) - sum) << "\n";
    return 0;
}

第二种解法 ：暴力 记录每一种情况最左边1和最右边1中间0的个数，取最小值即可

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e6 + 10;
int sum[N];
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s = s + s;
    s = " " + s;
    int cnt = 0, cnt1 = 0;
    vector<int> p; // 记录1的位置
    for(int i = 1; i <= n * 2; i ++)
    {
        cnt1 += s[i] == '1';
        if(s[i] == '0') sum[i] = 1;
        else p.push_back(i);
        if(i <= n) cnt = std :: max(cnt, cnt1);
        sum[i] += sum[i - 1];
    }
    if(p.size() == 0)
    {
        cout << 0 << "\n";
        return 0;
    }
    int ans = 1e9;
    for(int i = 0; i < cnt; i ++)
    {
        int l = p[i], r = p[i + cnt - 1];
        // l 是当前最左1的位置， r 是当前最右1的位置
        ans = min(ans, sum[r] - sum[l - 1]);
    }
    cout << ans << "\n";
    return 0;
}

G.空哥的愉快午餐

乘法原理\

对于某种方案，比如选了1 4 5：那么这种答案的贡献就是
可以观察到2、3没选，相当于×1\

所以本题答案公式：
例如 n = 2时候：
同理 n = 3、n = 4.......\

ps: 解决本题 还需了解快速幂

#include <iostream>
using namespace std;
const int mod = 998244353;

int qmi(int a, int b) // 快速幂模板
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * (long long)a % mod;
        a = a * (long long)a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int n, p = 114514;
    cin >> n;

    long long ans = 1;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        ans = (ans * (qmi(p, x) % mod + 1)) % mod;
    }
    cout << ans << "\n";
    return 0;
}

H.空哥的疑惑

输出 wo bu xiang jie xun 即可

#include <iostream>
using namespace std;

int main()
{
    puts("wo bu xiang jie xun");
    return 0;
}

I.空哥的幻想

反悔贪心
我们维护当前有的钱 和 一个大根堆，堆里存我买幻想值花的
贪心思想，当我们钱够买当前月的幻想值时，我们就选择买，即当时，此时将插入进堆中
当我们钱不够买当前月幻想值时，我们考虑这个月的是否可以替换掉，我前面某个月买幻想值的花费，由于我们使用的是大根堆，那么堆顶就是我们前面某个月买幻想值花费的最大消费，如果用本月替换掉那个月的花费，我们便可以让我们维护的加上一些差值，体现了贪心思想。

在每个月的末尾，我们使 +

最终堆的大小即为答案

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<int, vector<int>> q;
    long long s = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        if(s >= x) // 可以放直接放
        {
            q.push(x);
            s -= x;
        }
        else if(q.size() && x < q.top()) // 不可以放，看看能否让sum多些差值
        {
            s += q.top() - x;
            q.pop();
            q.push(x);
        }
        s += m; // 每个月 + 月薪
    }
    cout << q.size() << "\n";
    return 0;
}