Znzryb's Blog

Minimum OR Path

Posted on 2025-09-06 Edited on 2026-04-06

思路讲解

AC代码

源代码

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

START202——Equalize Juice

Posted on 2025-09-04 Edited on 2026-04-06

思路讲解

START202——Min-Max Deque

和该问题一样，直接解决这个问题比较难，我们可以解决一些更简单的问题。

比如说就是让果汁恰好为X？

那么考虑我们要选 $i_1,i_2,...i_k$ 个，那么这些 i 要满足什么条件那？

这个问题其实也比较复杂，我们不妨只看 $...i_1...i_2...$ 这两个之间的情况。

我们发现， $A[1]+\cdots+A[i_1]+\cdots+A[i_2-1]≥X$ ，是必要条件。

而且 $A[i_1+1]+\cdots+A[i_2-1]$ 的加多了的部分还可以回馈给 $A[i_2]$

那么我们就会形成一种感觉，就是说前面的部分其实不重要，越少越好，后面的部分要越多越好，因为还可以回馈给下一个。（抱歉，官解也没有证明，所以说只能这样讲了）

当然，我们需要将这种思维拓展到每一个相邻元素之间，那么我们发现，前面一个元素的后面下面一个元素的前面，因此我们要恰好，就是需要删的元素不能多（这个还是很容易发现的）。

于是我们不难写出程序。

AC代码

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

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#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 ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;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<ld>;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;
}
/*

*/
inline void __(){
    cin>>N;
    vll A(N+5);
    FOR(i,1,N){
        cin>>A[i];
    }
    vll li(A.begin()+1,A.begin()+N+1);
    sort(all(li));li.resize(unique(all(li))-li.begin());
    ll ans=INF;
// #ifdef LOCAL
//     cerr<<"OK\n";
// #endif
    for(auto x:li){
        auto findi1=[&](ll st)->pll {
            ll sum=0;
            FOR(i,st,N){
                if(A[i]<=x){
                    return {i,sum};
                }
                sum+=A[i];
            }
            return {N+1,sum};
        };
        auto [st,sum]=findi1(1);
        ll need=0;
        ll lans=N;
        while (st<=N) {
            need=x-A[st]-sum;
            ll ost=st;
            if(need>0){
                while (need>0 && st<=N) {
                    ll add=0;
                    if(st!=ost) add=A[st];
                    tie(st,sum)=findi1(st+1);
                    sum+=add;
                    need-=sum;
                }
                sum=abs(need);
            }else{
                tie(st,sum)=findi1(st+1);
            }
            if(need<=0) lans--;
        }
        ans=min(lans,ans);
#ifdef LOCAL
    debug(x);
#endif
    }
    cout<<ans<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1188472477
*/

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

START202——Min-Max Deque

Posted on 2025-09-04 Edited on 2026-04-06

思路讲解

首先，做这道题目，需要有简单版的基础，简单版就是一个简单的贪心。以下是简单版的代码。

FOR(i,2,N){
    if(i&1){
        if(q.back()>=q.front()){
            q.EF(A[i]);
        }else{
            q.EB(A[i]);
            tr.update(i,i);
        }
    }else{
        if(q.back()<=q.front()){
            q.EF(A[i]);
        }else{
            q.EB(A[i]);
            tr.update(i,i);
        }
    }
}
ll ans=min(q.back(),q.front());

那复杂版就是多了一个在线修改+询问，一个询问就是把 $A[p]:=x$ ，然后 naive 的想法就是再跑一遍简单版的程序，当然，不难发现，时间复杂度肯定有问题。

经过简单尝试，我们发现这个贪心算法不是很好优化，因此我们可以想办法改进一下我们的这个贪心做法。

我们发现比较难优化，是因为我们想通过一种方法直接在 $O(\log n)$ 的时间复杂度内得到答案，这无疑有一定的难度。

那么，我们能不能在 $O(\log n)$ 的时间复杂度内判断一个答案可不可行那？

这肯定是比之前的问题简单多了，但也没有那么简单。

假设答案为 $X$ ，将原数组 $A$ 表示为 $0101...$ ， $0$ 代表 $<X$ ， $1$ 代表 $≥X$ 。
我们不难发现（在题设保证 N 为奇数的情况下）：

越后出现越重要。
$10101$ 为相持阶段，得到的 $B$ 是 $11$ 类型，或维持原类型（即不能抵消 00）。
出现 $11$ 即使得 $B$ 变为 $11$ 类型（抵消一个 00）。
同理，出现 $00$ 即使得 $B$ 变为 $00$ 类型（抵消一个 11）。

那么通过上面发现的性质，那么我们其实就是要找到 $11$ & $00$ 的最靠右出现位置，这个可以使用二分答案+线段树二分 or 二分答案+二分+线段树解决。

具体来说是这样：

  auto check=[&](int mid){
      int pos00=tr.closer00(N,mid);
      int pos11=tr.closer11(N,mid);   // 使用线段树上二分实现
// pos00==-1 &&  pos11==-1 说明为1010结构，合法
      return pos11>=pos00;
  };
  auto cal=[&](){
      int l=1,r=N;
      while (l<r) {
          int mid=l+r+1>>1;
          if(check(mid)){
              l=mid;
          }else{
              r=mid-1;
          }
      }
      return l;
  };

代码：
https://www.codechef.com/viewsolution/1188151973

时间复杂度 $O(n\log^2n)$ 。

AC代码

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

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#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 ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;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<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)2e5+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 __();
ll A[MAXN];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
struct SEG{
    int n;vll tro,tre;
    SEG(int n):n(n),tro(n*4+5,INF),tre(4*n+5,-INF) {}
    void pushup(int o){
        tro[o]=min(tro[lson(o)],tro[rson(o)]);
        tre[o]=max(tre[lson(o)],tre[rson(o)]);
    }
    void update(int o,int p,ll x,int l,int r){
        if(l==r && r==p){
            if(l&1) tro[o]=x;
            else tre[o]=x;
            return;
        }
        int mid=l+r>>1;
        if(p<=mid && p>=l){
            update(lson(o), p, x, l, mid);
            pushup(o);
        }else{
            update(rson(o), p, x, mid+1, r);
            pushup(o);
        }
    }
    void update(int p,ll x){
        update(1,p,x,1,n);
    }
    // odd=0
    int closer00(int o,int R,int X,int l,int r){
        if(l==r){
            if(tro[o]<X){
                return l;
            }
            return -1;
        }
        int pos=-1;
        int mid=l+r>>1;
        if(R>=mid+1 && tro[rson(o)]<X){
            pos=closer00(rson(o),R,X,mid+1,r);
        }
        if(pos!=-1) return pos;
        if(R>=l && tro[lson(o)]<X){
            pos=closer00(lson(o),R,X,l,mid);
        }
        return pos;
    }  
    int closer00(int R,ll X){
        return closer00(1,R,X,1,n);
    }
    int closer11(int o,int R,int X,int l,int r){
        if(l==r){
            if(tre[o]>=X){
                return l;
            }
            return -1;
        }
        int pos=-1;
        int mid=l+r>>1;
        if(R>=mid+1 && tre[rson(o)]>=X){
            pos=closer11(rson(o),R,X,mid+1,r);
        }
        if(pos!=-1) return pos;
        if(R>=l && tre[lson(o)]>=X){
            pos=closer11(lson(o),R,X,l,mid);
        }
        return pos;
    }
    int closer11(int R,ll X){
        return closer11(1,R,X,1,n);
    }
}; 
inline void __(){
    cin>>N>>Q;
    SEG tr(N);
// #ifdef LOCAL
//     cerr<<"OK\n";
// #endif
    FOR(i,1,N){
        cin>>A[i];
        tr.update(i,A[i]);
    }
// #ifdef LOCAL
//     cerr<<"OK2\n";
// #endif
    auto check=[&](int mid){
        int pos00=tr.closer00(N,mid);
        int pos11=tr.closer11(N,mid);
#ifdef LOCAL
    debug(pos00);
    debug(pos11);
#endif
        return pos11>=pos00;
    };
    auto cal=[&](){
        int l=1,r=N;
        while (l<r) {
            int mid=l+r+1>>1;
            if(check(mid)){
                l=mid;
            }else{
                r=mid-1;
            }
// #ifdef LOCAL
//     debug(l);
// #endif
        }
        return l;
    };
    cout<<cal()<<" ";
// #ifdef LOCAL
//     cerr<<"OK3\n";
// #endif
    FOR(i,1,Q){
        ll p,x;cin>>p>>x;
        tr.update(p,x);
        cout<<cal()<<" ";
    }
    cout<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1188151973  
*/

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

START202——Counting Graphs

Posted on 2025-09-04 Edited on 2026-04-06

思路讲解

（现在看起来，这个题目有一点难了，超出了我的理解范围）

说实话，看这道题目，真一点思路都没有，连图都没有，我怎么动态规划？

那么一个联通块作为一个大块是非常难做的，那有没有可能分成好几个小块那？可以的兄弟，可以的，把 1 删除以后，就形成了一个个的小块。这些小块的访问顺序就是

$A[l_i],A[l_i+1]…,A[r_i]$

注意到，我们可以要求这些小块互不连通，那你说联通的情况怎么办呢？怎么统计那？

哈哈，这就用到了一个小巧思，把这个看作为联向 1 的回边，这样我们就能保证小块之间不联通（指的是删除点 1 后）。

想到这个了，我们就会发现，在保持现有联通块及其访问顺序的情况下，哪些点可以连回 1 那？这个其实也很简单，大于 $A[l_i]$ 即可。

然后题目说，我们现在已经成功的把一个大问题分解为小问题了，那不妨用 dp 继续。

Observe that we’ve really just broken the original problem down into smaller problems of the same nature - which naturally suggests dynamic programming.

呃，其实我觉得和分治思想差不多，就是继续把 $A[l_i]$ 当根。

然后我们不难发现，这个重点就在于怎么样求这个块的划分方法那？

其实这个递推式子是不难的，是符合直觉的，但是确实比较难绷。

因为整了两个数组，dp（dp[i][j] 表示从 i 到 j 的答案）和 split（split[i][j] 表示从 i 到 j 有多少种划分方法）实际上是一个东西（忽略联向根的回边），就是有一个差一，即：

$split[i+1][j]=dp[i][j]$

那么我们怎么递推得到 $split$ 那？其实也简单，不难发现（忽略联向根的回边）：

dp[L][R]=split[L+1][R]=\sum^{R}_{x=L+1}dp[L+1][x]\cdot split[x+1][R]\cdot \\ [A_{L+1}<A_{x+1}]（为真时是1，反之为0）

这个式子看起来非常天外飞仙，其实很简单，就是把所有的分块都尝试一遍。

之所以分为两个，是为了避免差一错误。

你可能还会想，为什么一开始是 $dp[L+1][x]$ 那？首先不用 split 是为了避免 $split[L+2][L+1]$ 这种诡异的情况出现，然后 $A[L+1]$ 是一定要为根的，因此用dp[L+1][x]。

那为什么后面一个代码是 $split[x+1][R]$ ，而不是 $dp[x+1][R]$ ？我也想了一会儿，不难发现 $split[x+1][R]$ 可以保证 x+1 一定是根，但是不保证 x+2 一定是根，而采用 $dp[x+1][R]$ 会导致不仅 x+1 一定是根，x+2 也一定是根。

好，那么现在问题就来到了我们怎么样实现了。题解给了一种比较好的实现方法，就是先枚举长度，再枚举起始点，因为不难发现长的区间是从短的区间转移过来的。

我感觉题解给的式子有点麻烦了，而且有点奇怪。

AC代码

源代码

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

Codeforces Round 933 (Div. 3)——G. Rudolf and Subway

Posted on 2025-09-03 Edited on 2026-04-06

思路讲解

https://acm.hdu.edu.cn/contest/problem?cid=1172&pid=1005

这个题目的思路还是比较简单的，建虚拟点，

传送门

while (!pq.empty()) {
    auto [node,dis]=pq.front();
    pq.pop_front();
    if(dis>Dis[node]) continue;
    Dis[node]=dis;
    for(auto&v:g[node]){
        if(node<=N){
            if(dis+1>=Dis[v]) continue;
            Dis[v]=dis+1;
            pq.PB({v,dis+1});
        }else{
            if(dis>=Dis[v]) continue;
            Dis[v]=dis;
            pq.PF({v,dis});
        }
    }
}

AC代码

https://codeforces.com/contest/1941/submission/336750153

源代码

// by Gospel_rock
// https://codeforces.com/problemset/problem/1941/G
#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
#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 (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#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 ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;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<ld>;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;
}
/*

*/
struct odis{
    ll o,dis;
    // odis(ll o,ll dis):o(o),dis(dis) {}
    // odis(){}
    bool operator<(const odis& other)const{
        return dis>other.dis;
    }
};
inline void __(){
    cin>>N>>M;
    vector<pair<ll,ll>> li;
    vector<tll> edge;
    FOR(i,1,M){
        ll u,v,c;
        cin>>u>>v>>c;
        li.EB(u,c);
        li.EB(v,c);
        edge.EB(u,v,c);
    }
    priority_queue<odis> pq;
    ll st=1,ed=N;
    cin>>st>>ed;
    // li.EB(st,0);
    sort(all(li));
    li.resize(unique(all(li))-li.begin());
    auto get=[&](pll a){
        return lower_bound(all(li),a)-li.begin();
    };
    vector<vector<int> > g(SZ(li)+N+5);
    for(auto&[u,v,c]:edge){
        int idx=get({u,c})+N+1,idx2=get({v,c})+N+1;
        g[idx].EB(idx2);
        g[idx2].EB(idx);
        // g[v].EB(idx);
        g[u].EB(idx);
        g[idx].EB(v);
        // g[u].EB(idx2);
        g[v].EB(idx2);
        g[idx2].EB(u);
    }
    vll Dis(SZ(li)+N+5,INF);
    // vb vis(SZ(li)+N+5);
    pq.push({st,0});
    while (!pq.empty()) {
        auto [node,dis]=pq.top();
        pq.pop();
        if(Dis[node]!=INF) continue;
        Dis[node]=dis;
        for(auto&v:g[node]){
            if(node<=N){
                pq.push({v,dis+1});
            }else{
                pq.push({v,dis});
            }
            // if(v>=N+1){
            //     ll col=li[v-N-1].SE;
            //     if(col==c){
            //         pq.push({v,dis});
            //     }else{
                    
            //     }
            // }else{
            //     pq.push({v,dis});
            // }
        }
    } 
	cout<<Dis[ed]<<"\n";
}
/*
AC
https://codeforces.com/contest/1941/submission/336750153
AC  不保证联通
https://vjudge.net/solution/63392276
1
4 3
1 2 1
1 3 1
4 1 1
2 3

5
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 3
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 6
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
6 6
4 3
1 2 1
1 3 1
4 1 1
2 3
6 7
1 2 43
1 3 34
4 6 43
6 3 43
2 3 43
5 3 43
4 5 43
1 6

1
2
0
1
1

*/