Znzryb's Blog

START199——Perfect Ranges

Posted on 2025-08-22 Edited on 2026-02-18

思路讲解

只要想到dp，那么写起来还是挺简单的。

这个dp的定义还是挺简单的，我的dp[i]的定义是以 i 的 mx 为结尾，所能得到的区间长度（计数），dp2[i] 的定义是以 i 的 mn 为结尾，所能得到的区间长度（计数）。

然后下划线部分注意初始化。

inline void __(){
    cin>>N;
    vll A(N+5),B(N+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    FOR(i,1,N){
        cin>>B[i];
    }
    vll dp(N+5),dp2(N+5);
    FOR(i,1,N){
        ll mx=max(A[i],B[i]),mn=min(A[i],B[i]);
        dp[i]=1;
        if(mx>max(A[i-1],B[i-1])){
            dp[i]=dp[i-1]+1;
        }
        if(mx>min(A[i-1],B[i-1])){
            dp[i]=max(dp[i],dp2[i-1]+1);
        }
        dp2[i]=1;
        if(mn>max(A[i-1],B[i-1])){
            dp2[i]=dp[i-1]+1;
        }
        if(mn>min(A[i-1],B[i-1])){
            dp2[i]=max(dp2[i],dp2[i-1]+1);
        }
    }
    ll ans=0;
#ifdef LOCAL
    _print(dp);
    _print(dp2);
    cend;
#endif
    FOR(i,1,N){
        ans+=max(dp2[i],dp[i]);
    }
    cout<<ans<<"\n";
}

AC代码

https://www.codechef.com/viewsolution/1184464744

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*
那么说实话那，我看见这个，第一反应是双指针。
不过一尝试书写，就发现不对，应该是dp。
*/
inline void __(){
    cin>>N;
    vll A(N+5),B(N+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    FOR(i,1,N){
        cin>>B[i];
    }
    vll dp(N+5),dp2(N+5);
    FOR(i,1,N){
        ll mx=max(A[i],B[i]),mn=min(A[i],B[i]);
        dp[i]=1;
        if(mx>max(A[i-1],B[i-1])){
            dp[i]=dp[i-1]+1;
        }
        if(mx>min(A[i-1],B[i-1])){
            dp[i]=max(dp[i],dp2[i-1]+1);
        }
        dp2[i]=1;
        if(mn>max(A[i-1],B[i-1])){
            dp2[i]=dp[i-1]+1;
        }
        if(mn>min(A[i-1],B[i-1])){
            dp2[i]=max(dp2[i],dp2[i-1]+1);
        }
    }
    ll ans=0;
#ifdef LOCAL
    _print(dp);
    _print(dp2);
    cend;
#endif
    FOR(i,1,N){
        ans+=max(dp2[i],dp[i]);
    }
    cout<<ans<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1184464744
*/
// 那么说实话那，我看见这个，第一反应是双指针。
// 不过一尝试书写，就发现不对，应该是dp。
    // ll st=1;
    // FOR(i,st,N){
    //     ll las=min(A[i],B[i]);
    //     FOR(j,i+1,N){
    //         ll mn=min(A[j],B[j]);
    //         ll mx=max(A[j],B[j]);
    //         if(mn>las){
    //             las=mn;
    //             continue;
    //         }
    //         if(mx>las){
    //             las=mx;
    //             continue;
    //         }

    //     }

    // }

心路历程（WA，TLE，MLE……）

汉诺塔问题的第M步

Posted on 2025-08-22 Edited on 2026-02-18

思路讲解

https://www.hello-algo.com/chapter_divide_and_conquer/hanota_problem/#2

主要dfs代码。

void dfs(ll rem,vll &src,vll &buf,vll &tar,char s,char b,char t){
    if(ok) return;
    if(rem==1){
        move(src,tar);
        if(tot==M){
            cout<<s<<"--"<<t<<"\n";
            ok=true;
            return;
        }
        return;
    }
    // 利用B，将A移动至C
    dfs(rem-1,src,tar,buf,s,t,b);
    move(src,tar);
    if(tot==M){
        cout<<s<<"--"<<t<<"\n";
        ok=true;
        return;
    }
    dfs(rem-1,buf,src,tar,b,s,t);
}

AC代码

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <utility>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    while(cin>>N>>M)
        __();
    return 0;
}
/*

*/
ll tot=0;
bool ok=false;
void move(vll &a,vll &b){
    b.EB(a.back());
    a.pop_back();
    ++tot;
}
void dfs(ll rem,vll &src,vll &buf,vll &tar,char s,char b,char t){
    if(ok) return;
    if(rem==1){
        move(src,tar);
        if(tot==M){
            cout<<s<<"--"<<t<<"\n";
            ok=true;
            return;
        }
        return;
    }
    dfs(rem-1,src,tar,buf,s,t,b);
    move(src,tar);
    if(tot==M){
        cout<<s<<"--"<<t<<"\n";
        ok=true;
        return;
    }
    dfs(rem-1,buf,src,tar,b,s,t);
}
inline void __(){
    // cin>>N;
    tot=0;
    vll a,b,c;
    ok=false;
    ROF(i,N,1){
        a.EB(i);
    }
    dfs(N,a,b,c,'A','B','C');
    if(!ok){
        cout<<"none\n";
    }
}
/*

*/

心路历程（WA，TLE，MLE……）

START200——Permutation Counting (Easy)

Posted on 2025-08-21 Edited on 2026-02-18

思路讲解

题意就是计数问题，求满足 $\forall i\in[2,N],\ \ P_{i-1}+P_i\not\equiv0\pmod K$ 的排列有几个？

首先，看题面，我们发现 $∑_{i=1}^{T}N_i≤2e5$ ，因此最终算法是 $O(n\log n)$ 或者 $O(n)$ 。

然后我们猛然发现， $K=3$ ，确实，我们觉得束手无策是对的，因为如果没有这个条件，是3000+的题目。

那么看着这个数据，我们容易想到dp， $dp[i]$ 表示 $1\cdots i$ 这个排列有可能的总数量（状态定义与答案保持一致）。

但是我们发现这个转移还是比较难的，因为我们用插入一个数字的想法的话，不仅就是说这个原来的合法序列上能够插入，原来的非法序列上也能够插入，变为合法序列，这就导致dp数组存储的信息没有什么意义。

因此，我们还是回到组合数学上，可以令除以3之后余数为0，1，2的分别为 $r_0,r_1,r_2$ 。

不难发现， $r_0$ 和 $r_0$ 不能放在一起， $r_1$ 和 $r_2$ 也不能放在一起。那么总体结构类似于 $r_1|r_0|r_2$ 或者 $r_2|r_0|r_1$ 。

不难发现，如果我们直接固定 $r_0$ ，接着去填充 $r_1$ 和 $r_2 $，这相当于解决：

有 $r_0+1$ 个盒子，其中有 $r_0-1$ 个必须装有球，且一个盒子装的球必须为同一种（一共只有两种），注意，可以理解为球带有编号，且放入盒子的顺序是重要的，盒子也是不同的。

这个问题是比较难解决的，不如我们先确定 $r_1$ 和 $r_2$ ，然后填充 $r_0$ 这样会简单很多。

// 我们按照交替进行分类，就是1-0-2-0-1是可以的，1-0-1-0-2，我们按照1-0-2处理。
// 为什么那？说多了都是泪，详细可以看下面的踩坑代码。
FOR(i,2,r0+1){
    if(i&1){
        for(int j=i/2;j<=i/2+1;++j){
            ll other=i-j;
            // stars and bars
            ll lans=CC(r1-1,j-1)*CC(r2-1,other-1)%mod;
            // 多余0的摆放
            // 一共有r1+r2+1个位置，有i-1个位置被用掉了，剩余r0-i+1个0
            lans*=CC(r1+r2+1-i+1,r0-i+1);lans%=mod;
            ans+=lans;
            ans%=mod;
        }
    }else{
        for(int j=i/2;j<=i/2;j++){
            ll other=i-j;
            // stars and bars
            ll lans=CC(r1-1,j-1)*CC(r2-1,other-1)%mod;
            if(j==i/2) lans*=2;
            lans*=CC(r1+r2+1-i+1,r0-i+1);lans%=mod;
            ans+=lans;
            ans%=mod;
        }
    }
}

将1-0-1-0-2和1-0-1-0-2视为相同（r1的位置可以重新排列，但这属于重复计数）的缺点。实际上，如果我们在最后乘以P(r1,r1)，我们就将r1的块视为相同。当然，r2也是相同的。

AC代码

源代码

心路历程（WA，TLE，MLE……）

START200——Random NIM

Posted on 2025-08-20 Edited on 2026-03-23

思路讲解

就是特判一下全部为1的情况（比较类似于反常nim），这个时候是可以分出胜负的。其他情况的胜率都是1/2。

AC代码

https://www.codechef.com/viewsolution/1183760784

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
ll binpow(ll a,ll k,const ll &p=mod){
    ll res=1;
    a%=p;
    while(k>0){
        if((k&1)==1) res=a*res%p;
        a=a*a%p;
        k>>=1;
    }
    return res;
}
inline void __(){
    cin>>N;
    vll A(N+5);
    ll sum=0;
    bool all1=true;
    FOR(i,1,N){
        cin>>A[i];
        if(A[i]!=1) all1=false;
    }
    if(all1){
        if(N%2==0)cout<<0<<"\n";
        else cout<<1<<"\n";
        return;
    }
    ll ans=binpow(2, mod-2);
    cout<<ans<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1183760784
*/

心路历程（WA，TLE，MLE……）

START200——Minimum Set

Posted on 2025-08-20 Edited on 2026-02-18

思路讲解

不难发现，可以把原来的问题转化为图论问题，就是要联通嘛，然后搞一个mst。

不难发现， $num\oplus (num-lowbit(num))$ 是最小的，因为这个数是比你小的数里面，和你重叠程度最大的。

通过打表等手段，我们可以得到如下程序。

ll ans=0;
ll wei=__lg(N);
ll cnt=0;
FOR(i,2,wei){
    ans+=1ll<<i;
    ++cnt;
}
for(ll i=2;i<=N;i<<=1){
    ll num=min(N,2*i-1)-i+1;
    for(ll j=2;(1ll<<j)<num;++j){
        ll val=(1ll<<(j));
        ans+=(num-1)/val*(val/2);
    }
    // ans+=num/2*2;
}
ans+=N/2;
ans+=(N/2-cnt)*2;
if(N%2==0 && N!=(1ll<<__lg(N))){
    ans--;
}
cout<<ans<<"\n";

唯一就是这一部分不是很优雅。我不太喜欢。至少我们要搞搞清楚为什么要-1吧？

其实要回答这个问题也简单，就是一开始我们写程序的时候假设都是奇数，使用的都是奇数的方法进行计数的，但是不是2的幂次的偶数比较特殊，不能和奇数直接互相转化，需要-1（比如说6，7-6代价是1，但是没有7的时候，就没有这个代价，所以要-1），而2的幂次因为和1相连代价+1（原来1-4，代价为5，但是改为5-1，代价为4，4-5，代价为1，正好抵消）。

AC代码

https://www.codechef.com/viewsolution/1183885336

源代码