A 古堡中的勇者

求b到c之间的元素个数，遍历即可，题目还贴心的告诉你 $b< a，c>a$，如果在cf，不先判断再swap一下，你就等着WA吧。

void solve(){
    CIN(a);CIN(l);CIN(r);
    CIN(n);ll ans=0;
    while(n--){
        CIN(tmp);
        if(l<tmp&&tmp<r)ans++;
    }
    cout<<ans;
}

B 三星五费

阅读题，看懂了就是概率与统计的问题。如果当前金币小于7，roll一遍商店后就没钱买了。当前金币大于等于7，Vinky才有概率赢：$P(胜)=1-P(输)$，而 $P(输)=(1-0.03)^{最大可roll次数}$。

void solve(){
    CIN(n);
    cout<<setprecision(3)<<fixed;
    if(n<7){cout<<0.0;return;}
    ll cnt=((n-5)>>1);
    cout<<1-powl(1-0.03,cnt);
}

C 我就要不协调

遍历找到最小差值即可，如果遍历过程中发现数组本身就有局部是下降趋势的，那就开个flag记录一下，直接输出0就行。

void solve(){
    CIN(n);
    vector<ll> a;a.push_back(0);
    bool flag=0;ll m=0x3f3f3f3f;
    FOR(i,1,n){
        CIN(tmp);if(flag)continue;
        a.push_back(tmp);
        if(a[i]<a[i-1])flag=1;
        if(i>1)m=min(m,a[i]-a[i-1]);
    }
    if(flag){
        cout<<0<<ET;return;
    }
    cout<<m/2+1<<ET;
}

D 古希腊掌管原神的神

唯 · 一 · 真 · 神

(恭喜原神成为过题数最少的水题，我的评价是CF脑筋急转弯)

我个人用了大量的分类讨论，但是其实只需要知道几个关键讨论即可：

总房间数为1，必然可以，输出0
真神人数大于假神和变化之神的人数时，必然也可以，输出 $2\times (假神与变化之神之和)+1$ 即可。一直问他们原神在哪个房间就行了。
反之则必然不行

void solve(){
    CIN(a);CIN(b);CIN(c);
    if(a+b+c==1){cout<<"YES"<<ET;cout<<0;return;}
    if(c==0){//其实没必要分这么多类，把假神和变化之神归为一类就行了
        if(b==0){
            cout<<"YES"<<ET;
            cout<<1;
            return;
        }
        if(a==0){
            cout<<"YES"<<ET;
            cout<<b-1;
            return;
        }
        if(a+b>2){
            cout<<"YES"<<ET;
            if(a>b)cout<<2*b+1<<ET;
            else cout<<a+b-1;
            return;
        }
        cout<<"YES"<<ET;
        cout<<2;
        return;
    }
    if(a>b+c){
        cout<<"YES"<<ET;
        cout<<(b+c)*2+1;
        return;
    }
    cout<<"NO"<<ET;
}

优化后的代码

void solve(){
    CIN(a);CIN(b);CIN(c);
    if(a+b+c==1){cout<<"YES"<<ET;cout<<0;return;}
    if(a>b+c){cout<<"YES"<<ET<<(b+c)*2+1;return;}
    cout<<"NO"<<ET;
}

E 字母匹配

刚好最近vp cf的时候见到过，所以秒了

直接记录所有字母出现次数，然后

$ans=\sum \min (cnt_i,~CNT_i) +\min (\sum \lfloor \frac{abs(cnt_i-CNT_i)}{2} \rfloor,~k)$

就过了

int a[300];
void solve(){
    CIN(n);CIN(k);
    FOR(i,1,n){
        char c;cin>>c;
        a[c]++;
    }
    ll ans=0,un=0;
    for(char c='a';c<='z';c++){
        ans+=min(a[c],a[c+'A'-'a']);
        un+=(abs(a[c]-a[c+'A'-'a'])>>1);
    }
    cout<<ans+min(k,un);
}

F 数学家的四不要

写四个筛子就行，卡特兰数太少了，直接打表筛。

bool a[100005],prime[100005],vis[100005];
void solve(){
    CIN(n);
    memset(a,1,sizeof a);

    for(int i=2;i<=n;i+=2)a[i]=0;//筛偶数

    for(int i=2;i<=n;i++){//筛质数
        if(!vis[i]){prime[i]=1;vis[i]=1;}
        for(int k=2;i*k<=n;k++){
            vis[i*k]=1;
        }
    }
    FOR(i,1,n){
        if(prime[i])a[i]=0;
    }

    for(int i=1;i*(i+1)/2<=n;i++)a[i*(i+1)/2]=0;//筛三角数

    vector<int> cat={1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786};//筛卡特兰数
    for(auto i:cat)a[i]=0;

    ll ans=0;//统计
    FOR(i,1,n)ans+=a[i];
    cout<<ans;
}

G 旗鼓相当的对手

01背包问题，尽可能填满 $\frac{\sum w_i}{2}$ 这个背包即可，此时相差最小。

(一开始忘一维优化了，被卡掉内存了)

int arra[301];
int n;
int dp[100001];
int minn(){
		int result=0;
		for(int i=0;i<n;i++){
			result+=arra[i];
		}
		int sum=result/2;
		for(int i=1;i<=n;i++){
			for(int j=sum;j>=arra[i-1];j--){
				dp[j]=max(dp[j],dp[j-arra[i-1]]+arra[i-1]);
			}
		}
		return result-dp[sum]*2;
}

H 卷王

先让小D拿到最大分数，然后剩下的人分数高的拿低分，低的拿高分。如果一个人放水只拿当前剩的最小的分数，却还是比小D的分高，那么就“化敌为友”，直接请他拿走剩下的分数中的最高分，不让后面的人拿。（拿少拿多了都比小D高，那不如直接拿走最高的，帮小D清除潜在对手）

void solve(){
    CIN(n);CIN(now);now--;
    vector<int> sc,sc2;
    FOR(i,1,n){
        CIN(tmp);sc.push_back(tmp);
    }
    FOR(i,1,n){
        CIN(tmp);sc2.push_back(tmp);
    }
    if(n==1){cout<<1;return;}
    int get=1,nowsc=0;
    sc[now]+=sc2[0];
    nowsc=sc[now];
    FOR(i,0,n-1){
        if(now==i)get++;
        else {
            if(sc[i]+sc2[n-1-i+get-1]>nowsc)sc[i]+=sc2[get++];
            else sc[i]+=sc2[n-1-i+get-1];
        }
    }
    sort(sc.begin(),sc.end());
    cout<<n-(lower_bound(sc.begin(),sc.end(),nowsc+1)-sc.begin())+1;
    //这里注意，upper_bound和lower_bound()都是针对升序容器的
    //如果sc是降序的，就不能用其获取排名了
}

I 字串比较

数据水了，substr都能爆切

ll l1,l2,r1,r2;
void solve(){
    CIN(n);CIN(m);CIN(q);
    string s1,s2;cin>>s1>>s2;
    while(q--){
        cin>>l1>>r1>>l2>>r2;
        string t1=s1.substr(l1-1,r1-l1+1),t2=s2.substr(l2-1,r2-l2+1);
        if(t1<t2)cout<<"<\n";
        else cout<<"=>"[t1>t2]<<ET;
    }
}

附录：

为了能更好的让读者抓住阅读重点，这里特意将代码头部和main函数与solve()函数分离，一般来说这些部分都是万年不变的：

#include<bits/stdc++.h>//如果编译器不能用这个，你自己看着缺啥补啥吧
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

//======这部分放主要逻辑和自定义类与数据结构======//
void solve(){
    //主要逻辑
}
//=======================================//

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();//预处理函数
    //CIN(t);while(t--)//多重样例的开关
    solve();
    return 0;
}

第十一届"图灵杯"NEUQ-ACM程序设计竞赛