A. Dual Trigger

贪心

大概思路

如果是奇数个1,那么免谈;如果是偶数个1,只需要两边从最外侧往内一个个开就行

注意: 当1的个数等于2时,要注意这两个1是不是相邻的,是的话就没办法了,输出NO; 当1的个数大于2时,考虑个数为4的情况,这时候就算它们四个都挤在一起,也有解:按照13、24这样打开就行;当个数大于4时,显然可以多次操作,回到个数为4的情况,依然可解。

因此当1的个数为2时比较特殊,需要特判。

参考代码

void solve() {
    cin(n);
    scin(s);
    ll cnt=0;
    for(auto &c:s)cnt+=(c=='1');
    bool NO=0;
    if(cnt==2)rep(i,0,n-2){
        if(s[i]=='1'&&s[i+1]=='1'){
            NO=1;break;
        }
    }
    if(NO){CN;return;}
    cout<<ANS[cnt%2==0];
}

B. Battle Cows

贪心,模拟

大概思路

思路挺清晰的,就是分类讨论比较麻烦。

当前面没有牛比自己rating大时,直接和第一头牛swap。

当位置k的前面只有一头rating比自己大的牛存在时,显然一把都赢不了,所以这时候你有两个选择

  • 让自己和从左到右第一头rating比自己大的牛换位置
  • 让自己和第一头牛换位置

这时候就要权衡选哪个的收益会更高了,设那头牛位置为 $j$,这里我们直接比较 $j-1$ 和 $m-j$ 即可。

当位置k的前面有两头及以上的牛比自己rating大时,也有同样的两个选择,不过这时候权衡的式子要调整,设两头牛位置分别为 $i,j(i<j)$,只需要比较 $i-1$ 和 $j-i$ 即可。

参考代码

void solve() {
    cin(n);cin(m);
    vector<int> a(n+1);
    rep(i,1,n)cin>>a[i];

    int flag[2]={-1,-1};
    rep(i,1,m-1){
        if(flag[0]==-1&&a[i]>a[m]){
            flag[0]=i;
        }else if(flag[0]!=-1&&a[i]>a[m]){
            flag[1]=i;
            break;
        }
    }
    if(flag[0]==-1){
        swap(a[1],a[m]);
        m=1;
    }else if(flag[1]==-1){
        if(flag[0]-1>m-flag[0]){
            swap(a[1],a[m]);
            m=1;
        }else{
            swap(a[flag[0]],a[m]);
            m=flag[0];
        }
    }else{
        if(flag[0]-1>flag[1]-flag[0]){
            swap(a[1],a[m]);
            m=1;
        }else{
            swap(a[flag[0]],a[m]);
            m=flag[0];
        }
    }
    ll cnt=0;
    rep(i,max(1,m-1),n){
        //cout<<i<<"]";
        if(a[i]>a[m])break;
        if(a[i]<a[m])cnt++;
    }
    cout<<cnt<<et;
}

C - Ticket Hoarding

排序,贪心,模拟

大概思路

从小到大分配每天购买的票数,然后跑模拟即可。

参考代码

struct P{
    int v,i,rnk;
};

void solve() {
    cin(n);cin(m);cin(k);
    int have=0;
    vector<P> a(n+1);
    rep(i,1,n){cin>>a[i].v;a[i].i=i;}

    sort(a.begin()+1,a.end(),[&](P a,P b){//按值大小排序
        return a.v<b.v;
    });
    rep(i,1,n)a[i].rnk=i;//标记rank
    sort(a.begin()+1,a.end(),[&](P a,P b){//按原下标排序回去
        return a.i<b.i;
    });

    ll cost=0;//开始模拟
    rep(i,1,n){
        if(a[i].rnk<=k/m){
            cost+=(a[i].v+have)*m;
            have+=m;
        }
        if(k%m&&a[i].rnk==k/m+1){
            cost+=(a[i].v+have)*(k%m);
            have+=(k%m);
        }
    }
    cout<<cost<<et;
}

D - Buying Jewels

贪心,数学,找规律

大概思路

你手画一个表格,穷举一下 $n,k\in(1,9)$ 的情况,结合一下常识就会发现结论:

  • 当 $n=k$ 时,显然可行,设单价为 $1$ 就行了
  • 当 $\lfloor \frac{n+1}{2} \rfloor \ge k$ 时,也可行,开两家商铺,第一家单价为 $n-k+1$,让她只买到一个,剩 $k-1$ 元,然后第二家单价为 $1$ 即可。
  • 当 $k>n$ 时,显然不行,你单价设成 $1$ 都不够她买的。
  • 当 $k<n$ 且 $k>\lfloor \frac{n+1}{2} \rfloor$ 时,不可行,因为如果第一家单价为 $1$,那么她显然会买超了;如果单价为 $2$,那么也不行,因为此时你的最大购买力就是 $\lfloor \frac{n+1}{2} \rfloor$,购买力赶不上 $k$ 值,显然不够买;如果单价为 $3$ 或者更多,显然也是不够买的(不用算都知道单价开的越高,同样的钱买到的东西数越少)

综上,只需要特判出 $n=k$ 和 $\lfloor \frac{n+1}{2} \rfloor \ge k$ 剩下的直接输出NO就行了

参考代码

void solve() {
    cin(n);cin(k);
    if(n==k){
        CY;
        cout<<1<<et<<1<<et;
        return;
    }
    if(((n+1)>>1)>=k){
        CY;
        cout<<2<<et<<n-k+1<<" "<<1<<et;
        return;
    }
    CN;
}

E - No Palindromes

马拉车,暴力

大概思路

直接上马拉车预处理出回文半径(用于快速判断字符串子串是否为回文串),如果其本身已经是回文,直接输出即可;如果不是,就暴力遍历该往哪切一刀,使得两个串均为非回文串即可。

(要被自己蠢si了,最后10分钟放弃debug了,赛后发现是子串判回文写笨了,果然只了解板子是没用的,还要多练,写熟了,下次比赛中才不会去调细节)

参考代码

vector<int> manacher(string s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}
vector<int> PR;
inline bool PAL(int l,int r){
    return PR[r+l-1]-1==(r-l+1);//就这玩意让我调了半天没过
}
void solve() {
    scin(s);
    PR = manacher(s);
    if(!PAL(1,s.length())){
        CY;
        cout<<1<<et<<s<<et;
        return;
    }
    rep(i,2,s.length()-1){
        if(!PAL(1,i)&&!PAL(i+1, s.length())) {
            CY;
            cout<<2<<et<<s.substr(0,i)<<" "<<s.substr(i)<<et;
            return;
        }
    }
    CN;
}

附录

这里放上用到的文件头和main函数

#include<iostream>
#include<vector>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
//不要用#define,使用using可以用ll格式转换,但是#define不行
#define et '\n'
//慎用register和inline
#define reg register
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rrep(i,a,b) for(int i=(a);i>=(b);i--)
#define cin(a) ll a;cin>>a
#define dcin(a) ld a;cin>>a
#define scin(a) string a;cin>>a
#define CA cout<<ans<<et
#define CY cout<<"YES"<<et
#define CN cout<<"NO"<<et
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};
int M=1e9+7;
//inline ll MO(ll x){return (x%M+M)%M;}

void solve(){

}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    cin(t);while(t--)
    solve();
    return 0;
}