2024 上海CCPC

The 2024 Shanghai Collegiate Programming Contest
补题连接：https://codeforces.com/gym/105229

M. 不共戴天

观察样例2，注意到6个荷叶两两分成一组，共分为3组
（1，2）（3，4）（5，6）
其中对于青蛙的策略是组内全部连接，即：
m = 3：1->2，3->4，5->6
鸟的策略是，相邻组相连，即：
m = 4：1->3，2->4，3->5，4->6

猜想均匀分组（每组荷叶数量相同）是最优解。
设共有n个荷叶，每组包含k个荷叶，则共分为 t = ⌈n / k⌉ 组

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int fk = 0, ff = 0;
    for(int k = 2; k < n; ++ k)
    {
        int t = (n + k - 1) / k; // t blocks
        int l = (n % k == 0 ? k : n % k); // last block
        int frog = (t - 1) * (k - 1) + (l - 1);
        int bird = (t >= 2 ? (t - 2) * k : 0) + l;
        if(bird >= frog) fk = k, ff = frog;
        else break;
    }
    if(fk == 0)
    {
    	cout << 0 << endl;
    	return 0;
	}
    cout << ff << endl;
    // print
    int t = (n + fk - 1) / fk;
    int l = (n % fk == 0 ? fk : n % fk);
    for(int i = 1; i <= t - 1; ++ i)
        for(int j = 1; j < fk; ++ j)
        {
            int fir = (i - 1) * fk + j;
            cout << fir << " " << fir + 1 << endl;
        }
    for(int j = 1; j < l; ++ j)
    {
        int fir = (t - 1) * fk + j;
        cout << fir << " " << fir + 1 << endl;
    }
    
    int cnt = 1;
    for(int i = 1; i <= t - 2 && cnt <= ff; ++ i)
        for(int j = 1; j <= fk && cnt <= ff; ++ j, ++ cnt)
        {
            int fir = (i - 1) * fk + j;
            cout << fir << " " << fir + fk << endl;
        }
    for(int j = 1; j <= l && cnt <= ff; ++ j, ++ cnt)
    {
        int fir = (t - 2) * fk + j;
        cout << fir << " " << fir + fk << endl;
    }
    
    return 0;
}

E. 无线软件日

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    map<char,int> hash;
    for(char hi : s)
    {
        if(hi == 's' || hi == 'S') hash['s']++;
        if(hi == 'h' || hi == 'H') hash['h']++;
        if(hi == 'a' || hi == 'A') hash['a']++;
        if(hi == 'n' || hi == 'N') hash['n']++;
        if(hi == 'g' || hi == 'G') hash['g']++;
        if(hi == 'i' || hi == 'I') hash['i']++;
    }
    int cnt = 9999999;
    for(auto hi : hash)
    {
        if(hi.first == 'h' || hi.first == 'a') cnt = min(cnt,hi.second/2);
        else cnt = min(cnt,hi.second);
    }
    cout << (cnt == 9999999 ? 0 : cnt) << endl;
    return 0;
}

J. 极简合数序列
前缀和暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int arr[N], s[N];
inline bool is_heshu(int x)
{
    if(x <= 2) return false;
    for(int i = 2; i <= x / i; ++ i)
        if(x % i == 0) return true;
    return false;
}
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%d",&arr[i]);
        s[i] = s[i - 1] + arr[i];
    }
    for(int k = 1; k <= n; ++ k)
        for(int i = 1; i <= n - k + 1; ++ i)
            if(is_heshu(s[i + k - 1] - s[i - 1]))
            {
                printf("%d\n",k-1);
                return;
            }
    printf("-1\n");
}
int main()
{
    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}