A - Notelock

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=0,last=-1e9;
        for(int i=0;s[i];i++)
            if(s[i]=='1'){
                if(i-last>=k) ans++;
                last=i;
            }
        cout<<ans<<'\n';
    }
    return 0;
}

B - Make it Zigzag

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],mx[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            mx[i]=max(mx[i-1],a[i]);
        }
        int ans=0;
        for(int i=2;i<=n;i+=2){
            if(a[i-1]>=mx[i]) ans+=a[i-1]-mx[i]+1;
            if(i+1<=n&&a[i+1]>=mx[i]){
                ans+=a[i+1]-mx[i]+1;
                a[i+1]=mx[i]-1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

C1 - No Cost Too Great (Easy Version)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
vector<int> v[N+1];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    //类似埃氏筛 质因数
    for(int i=2;i<=N;i++){
        if(v[i].size()) continue ;
        for(int j=i;j<=N;j+=i){
            v[j].push_back(i);
        }
    }
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        map<int,int> mp;
        int ans=2;
        for(int i=1;i<=n;i++){
            for(int x:v[a[i]]){
                if(mp[x]>0) ans=0;
                mp[x]++;
            }
        }
        for(int i=1;i<=n;i++){
            for(int x:v[a[i]]) mp[x]--;
            for(int x:v[a[i]+1]){
                if(mp[x]>0) ans=min<long long>(ans,1);
            }
            for(int x:v[a[i]]) mp[x]++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

C2 - No Cost Too Great (Hard Version)

#include <bits/stdc++.h>
#define int long long
#define fi first 
#define se second
using namespace std;
const int N=2e5+10;
pair<int,int> p[N];
vector<int> v[N+1];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    //类似埃氏筛 质因数
    for(int i=2;i<=N;i++){
        if(v[i].size()) continue ;
        for(int j=i;j<=N;j+=i){
            v[j].push_back(i);
        }
    }
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>p[i].fi;
        for(int i=1;i<=n;i++) cin>>p[i].se;
        map<int,int> mp;
        sort(p+1,p+n+1,[&](pair<int,int> a,pair<int,int> b){return a.se<b.se;});
        int ans=p[1].se+p[2].se;
        for(int i=1;i<=n;i++){
            for(int x:v[p[i].fi]){
                if(mp[x]>0) ans=0;
                mp[x]++;
            }
        }
        for(int i=1;i<=n;i++){
            for(int x:v[p[i].fi]) mp[x]--;
            for(int x:v[p[i].fi+1]){
                if(mp[x]>0) ans=min<long long>(ans,p[i].se);
            }
            for(int x:v[p[i].fi]) mp[x]++;
        }
        int mn=1e9;
        set<int> s;
        for(int i=2;i<=n;i++){
            for(int x:v[p[i].fi])
                s.insert(x);
        }
        for(int x:s)
            ans=min(ans,(x-p[1].fi%x)*p[1].se);
        cout<<ans<<'\n';
    }
    return 0;
}

D - Catshock

有一只猫住在一棵有 n个节点的树上。猫最初位于节点 1，而你位于节点 n。你打算给猫留下一个用“跑酷语言（parkour language）”写成的指令序列，让它能顺利找到你。

1. 1
   表示猫应当移动到与它当前所在节点相邻的任意一个节点。

   • 如果有多个相邻节点，它会随机选择其中一个；
   • 如果当前节点没有相邻节点（即孤立），猫就不移动。

2. 2 u
   表示销毁节点 u 以及与其相连的所有边。

   • 如果猫正好在节点 u 上，那么它会死亡（必须避免这种情况）；
   • 如果节点 u已经被销毁，则该指令不产生任何效果。

指令序列中不能有两个连续的 2 类型指令（即不能连续销毁节点）。
由于“跑酷语言”具有随机性（每次执行 1 时猫可能走不同的路），
你的目标是：

构造一个长度 不超过 (3n) 的指令序列，
使得无论猫在每次执行 1 时如何选择路径，
最终都会到达节点 (n)。

💡 可以证明：对于任意一棵树，这样的指令序列总是存在。