random fact：难度预期：

A

K L

B C I J

F G H

D E，

好像预期的相对顺序没有太大问题，但BCIJ这档比出题人想象的要难很多就是了（

random fact：DEL出题人：Wildfire032；其它题出题人：fried-chicken。

random fact：本场的 gpt-o3-mini-high 战绩是 9/12，没做出来的是 D(-1)E(-4)H(-4) 三题。在AC的题目中，gpt在F题有两发罚时、J题有一发罚时（但gpt写的是可以做 x,y≤109x,y\leq 10^9x,y≤109 的做法）、L题有一发罚时，此外所有题都是一发过。我们AI真是太牛了。

A. 复制鸡

[h(https://ac.nowcoder.com/acm/contest/95338/Attps://ac.nowcoder.com/acm/contest/95338/A]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int cnt=0;
    for(int i=1;i<=n;)
    {
        cnt++;
        int j=i;
        while(j<=n&&a[j]==a[i])
        {
            j++;
        }
        i=j;
    } 
    cout<<cnt<<"\n";   
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

K. 鸡翻题

https://ac.nowcoder.com/acm/contest/95338/K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int x,y;
    cin>>x>>y;
    if(x&1)
    {
        if(y%4==3||y==0)cout<<"YES\n";
        else cout<<"NO\n";
    }    
    else 
    {
        if(y%4==1||y==0)cout<<"YES\n";
        else cout<<"NO\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

L. 变鸡器

https://ac.nowcoder.com/acm/contest/95338/L

首先最终得到的字符串是由原字符串删去偶数个字符所得到的，因此“chicken”必然是原串的一个子序列，且原字符串的长度为奇数。考虑删去的字符，字符集合是一定的，==不难证明将这些字符能够删去的一个充要条件是出现次数最多的字符小于等于总需要删去字符数量的1/2==(必要性：对于一种字符，每次操作最多删去一个；充分性：用一个大根堆维护即可)。因此判断原串是否满足这些条件即可，时间复杂度O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
string s="CHICKEN";
void solve(){
    int n;
    cin>>n;
    string t;
    cin>>t;
    if(n<7||n%2==0)return cout<<"NO\n",void();
    int i=0,j=0;
    map<char,int>mp;
    while(i<7&&j<n)
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
        }
        else {
            mp[t[j]]++;
            j++;
        }
    }
    while(j<n)
    {
        mp[t[j]]++;
        j++;
    }
    if(i!=7)cout<<"NO\n";
    else 
    {
        for(auto [x,y]:mp)  
        {
            if(y>(n-7)/2)return cout<<"NO\n",void();
        }
        cout<<"YES\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

C. 数列之和

https://ac.nowcoder.com/acm/contest/95338/C

作者：FriedChicken
链接：https://ac.nowcoder.com/discuss/1455225
来源：牛客网

为了防止被出题人骗着输出 4k−24k-24k−2 获得WA（嘻嘻），我们最好先计算一下。

根据初高中数学知识，可以算出第 l个数到第 r个数的和为 sum=al+ar2(r−l+1)=(r+l−2)(r−l+1)sum=\frac{a_l+a_r}{2}(r-l+1)=(r+l-2)(r-l+1)sum=2al+ar(r−l+1)=(r+l−2)(r−l+1)

样例提醒我们从奇偶性角度分析这个式子：若 l,rl,rl,r 都为奇数或都为偶数，则第一项为偶数、第二项为奇数；若 l,r 一个是奇数一个是偶数，则第一项为奇数、第二项为偶数。即 sumsumsum 总是一个奇数乘以偶数，哪些数字不能分解成奇数乘以偶数的形式？形如 2p2^p2p 的整数都不可以。唯一一个例外是样例中的 222，因为此时奇数可以取111 （这对应了 r−l+1=1r-l+1=1r−l+1=1），可以验证其它 2p2^p2p 都不能像这样拆成 2p2^p2p 和 111 相乘。

综上，结论是：除了形如 2^p^ (p>1) 的整数不能表示，其他数字都可以表示。

代码实现上，相当于要找第 k 个非 2^p^ (p>1)形式的偶数。这里写法比较多、也不乏 O(1) 的式子，为了减少动脑，出题人的写法是二分答案为第 x 个偶数，检查

x - (不超过 x 的 2^p^ 数) ≤输入的 k）

是否成立。

random fact：本题抄袭自 2024 海淀高三 10 月月考 21 题。

1