Znzryb's Blog

Good Travels｜缩点模版

Posted on 2026-01-09 Edited on 2026-03-14

思路讲解

AC代码

AC
https://www.spoj.com/status/ns=35103793

源代码

// by Gospel_rock
// title: Good Travels scc
// timeLimit: 1000
// url: https://vjudge.net/problem/SPOJ-GOODA#author=GPT_zh
#include <bits/stdc++.h>
#include <vector>
#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())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
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, S, E;

void Solve() {
    cin >> N >> M >> S >> E;
    vector<ll> A(N + 4);
    FOR(i, 1, N) { cin >> A[i]; }
    vector<vector<ll>> g(N + 5);
    FOR(i, 1, M) {
        ll u, v;
        cin >> u >> v;
        g[u].PB(v);
    }
    vector<ll> tin(N + 5), low(N + 5);
    vector<ll> stk;
    vector<char> instk(N + 5);
    vector<ll> scc(N + 5);
    vector<ll> scca(N+5);
    ll idx = 0, sccidx = 0;
    auto dfs1 = [&](auto self, ll u) -> void {
        tin[u] = low[u] = ++idx;
        stk.PB(u);
        instk[u] = 1;
        for (auto v : g[u]) {
            if (!tin[v]) {
                self(self, v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], low[v]);
            }
        }
        if (tin[u] == low[u]) { // u是 scc 的根
            ++sccidx;
            ll y=0;
            do {
                y = stk.back();
                stk.pop_back();
                instk[y] = 0;
                scc[y] = sccidx;
                scca[sccidx]+=A[y];
            } while (y != u);
        }
    };
    FOR(i,1,N){
        if(!tin[i]){
            dfs1(dfs1,i);
        }
    }
    vector<vector<ll> > scg(sccidx+5);
    vector<ll> dp(sccidx+5,-INF);
    vector<ll> in(sccidx+5);
    FOR(u,1,N){
        for(auto v:g[u]){
            if(scc[u]==scc[v]) continue;
            scg[scc[u]].PB(scc[v]);
            in[scc[v]]++;
        }
    }
    // exit(0);
    queue<ll> q;
    FOR(i,1,sccidx){
        if(in[i]==0){
            q.push(i);
        }
    }
    dp[scc[S]]=scca[scc[S]];
    while(!q.empty()){
        auto u=q.front();q.pop();
        for(auto v:scg[u]){
            dp[v]=max(dp[v],dp[u]+scca[v]);
            in[v]--;
            if(in[v]==0){
                q.push(v);
            }
        }
    }
    ll ans=0;
    // FOR(i,1,sccidx){
    //     ans=max(dp[i],ans);
    // }
    cout<<(ll)dp[scc[E]]<<"\n";


// #ifdef LOCAL
//     debug(sccidx);
//     cerr<<"scc:";
//     FOR(i,1,N){
//         cerr<<scc[i]<<" ";
//     }
//     cerr<<"\n";
//     cerr<<"scca:";
//     FOR(i,1,sccidx){
//         cerr<<scca[i]<<" ";
//     }
//     cerr<<"\n";
//     FOR(i,1,sccidx){
//         cerr<<i<<":";
//         FOR(j,0,SZ(scg[i])-1){
//             cerr<<scg[i][j]<<" ";
//         }
//         cerr<<"\n";
//     }
//     cerr<<"dp:";
//     FOR(i,1,sccidx){
//         cerr<<dp[i]<<" ";
//     }
//     cerr<<"\n";
// #endif
   
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // cin >> lT;
    // while (lT--)
        Solve();
    return 0;
}
/*
AC
https://www.spoj.com/status/ns=35103793

*/

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

Starters 213-Mean Difference (easy)

Posted on 2026-01-09 Edited on 2026-02-19

思路讲解

AC代码

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

源代码

// by Gospel_rock
// title: Mean Difference (Easy)
// GROUP_NAME: START213B
// ONLINE_JUDGE_NAME: CodeChef

#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 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)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);

ll lT;

void Solve(){
	ll N;
	cin>>N;
	vector<ll> A(N+5);
    FOR(i,1,N) {
        cin>>A[i];
    }
    if (N==1) {
        cout<<0<<"\n";
        return;
    }
    sort(A.begin()+1,A.begin()+N+1,greater<>());
    function f=[&](ll need_big) {
        if (need_big>=N) return 0ll;
        ll acc=0;
        FOR(i,1,need_big) {
            acc+=A[i];
        }
        acc+=A[N];
        acc/=(need_big+1);
        return abs(acc-A[N]);
    };
    ll l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    ll ans=0;
    FOR(i,l,r) ans=max(ans,f(i));
    sort(A.begin()+1,A.begin()+N+1);
    l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    FOR(i,l,r) ans=max(ans,f(i));
    cout<<ans<<"\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin>>lT;
    while(lT--)
        Solve();
    return 0;
}
/*
AC

*/

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

ABC430-C - Truck Driver

Posted on 2026-01-09 Edited on 2026-02-19

思路讲解

赛时AC的。

        if(cnta>=A && cntb<B) {
// ans+=(cnta-A+1)
            ans+=(*posa.find_by_order(cnta-A)-i+1);

        }

// ans+=(cnta-A+1)
hack数据：

7 2 3
aabbaba

AC代码

https://atcoder.jp/contests/abc430/submissions/70626068

源代码

//  C - Truck Driver  
  
#include <bits/stdc++.h>  
  
#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 all(vec) vec.begin(),vec.end()  
  
using namespace std;  
  
using  ll = long long;using ull = unsigned long long;  
using DB=double;using LD=long double;  
// using i128 = __int128;  
using CD=complex<double>;  
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;  
static constexpr ll mod=(ll)1e9+7; // 998244353;  
static constexpr double eps=1e-8;const double pi=acos(-1.0);  
  
#include <ext/pb_ds/assoc_container.hpp>  
using namespace __gnu_pbds;  
using ordered_set = tree<ll, null_type, less<>, rb_tree_tag,  
tree_order_statistics_node_update>;  
  
ll lT;  
  
void Solve(){  
    ll N,A,B;  
    cin>>N>>A>>B;  
    vector<char> S(N+5);  
    FOR(i,1,N) {  
        cin>>S[i];  
    }  
    ll cnta=0,cntb=0;  
    ll ans=0;  
    ll up=1;  
    ordered_set posa;  
    FOR(i,1,N) {  
        bool isb=false;  
        FOR(j,up,N) {  
            if(S[j]=='b') {  
                ++cntb;  
            }else {  
                posa.insert(j);  
                ++cnta;  
            }  
            if(cnta>=A && cntb<B) {  
// #ifdef LOCAL  
//                 debug(i);  
//                 debug(j);  
//                 debug((cnta-A+1));  
//  
// #endif  
                ans+=(*posa.find_by_order(cnta-A)-i+1);  
// #ifdef LOCAL  
//                 debug(*posa.find_by_order(cnta-A));  
//                 debug(*posa.begin());  
//                 debug((*posa.find_by_order(cnta-A)-i+1));  
//                 cend;  
// #endif  
            }  
            if(cntb>=B) {  
                up=j;  
                if(S[i]=='a') {  
                    posa.erase(i);  
                    --cnta;  
                }else {  
                    --cntb;  
                }  
  
                if(S[j]=='b') {  
  
                    --cntb;  
                }else {  
                    posa.erase(j);  
                    --cnta;  
                }  
                isb=true;  
                break;  
            }  
        }  
        if(!isb) {  
            up=N+1;  
        }  
  
    }  
    cout<<ans<<"\n";  
}  
  
signed main()  
{  
    ios::sync_with_stdio(false);  
    cin.tie(0);cout.tie(0);  
    // cin>>lT;  
    // while(lT--)        Solve();  
    return 0;  
}  
/*  
AC  
https://atcoder.jp/contests/abc430/submissions/70626068  
  
*/

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

ABC429-D - Pop and Insert

Posted on 2026-01-09 Edited on 2026-02-19

题目大意

有一个周长为 $M$ 的池塘，岸边有一个小屋和 $N$ 个人。定义地点 $x$ 为从小屋顺时针走 $x$ 距离的位置（ $0 \leq x < M$ ）。第 $i$ 个人站在地点 $A_i$ 处，多个人可能站在同一位置。

对于 $i = 0, 1, \ldots, M-1$ ，定义 $X_i$ ：

高橋君从地点 $(i+0.5)$ 出发，开始顺时针移动
他会一直移动，直到遇到的人数总计达到 $C$ 人或更多时停止
$X_i$ 是他遇到的总人数（如果停止位置有多人，全部计入，因此 $X_i$ 可能大于 $C$ ）

求所有 $X_i$ 的总和： $\sum_{i=0}^{M-1} X_i$

输入格式：

第一行： $N$ $M$ $C$
第二行： $A_1$ $A_2$ $\ldots$ $A_N$

输出格式：

一个整数，表示 $X_i$ 的总和

思路讲解

AC代码

https://atcoder.jp/contests/abc429/submissions/70464977

源代码

// by Gospel_rock
// title: D - On AtCoder Conference
// timeLimit: 2000
// url: https://atcoder.jp/contests/abc429/tasks/abc429_d
#include <algorithm>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#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())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
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, C;

void Solve() {
    cin >> N >> M >> C;
    vector<ll> A(N);
    // map<ll,ll> freq;
    FOR(i, 1, N) {
        cin >> A[i - 1];
        // freq[A[i]]++;
    }
    vector<ll> sa(all(A));
    sort(all(sa));
    sa.resize(unique(all(sa)) - sa.begin());
    ll sz = SZ(sa);
    vector<ll> freq(SZ(sa) + 1);
    auto findi = [&](ll x) {
        ll idx = lower_bound(all(sa), x) - sa.begin();
        return idx;
    };
    auto caldis = [&](ll l, ll r) {
        l %= sz;
        if (l < 0)
            l += sz;
        l = sa[l];

        r %= sz;
        if (r < 0)
            r += sz;
        r = sa[r];

        ll dis = 0;
        if (r > l) {
            dis = r - l;
        } else {
            dis = M + (r - l);
        }
        // if(dis==0) dis=M;
        return dis;
    };
    FOR(i, 1, N) { freq[findi(A[i - 1])]++; }
    // for(auto it1=freq.begin();it1!=freq.end();++it1){
    //     for(auto it2=freq.begin();it2;){

    //     }
    // }

    ll up = 0;
    ll sum = 0;
    ll ans = 0;
    FOR(i, 0, sz - 1) {
        if (up <= i) {
            sum = 0;
            up = i;
        }
        FOR(j, up, 2 * sz) {
            sum += freq[j % sz];
            if (sum >= C) {
                ans += caldis(i - 1, i) * sum;
#ifdef LOCAL
                debug(sum);
                debug(j);
                debug(caldis(i - 1, i));
#endif
                sum -= freq[j % sz];
                sum -= freq[i];
                up = j;

                break;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // cin>>lT;
    // while(lT--)
    Solve();
    return 0;
}
/*
AC
https://atcoder.jp/contests/abc429/submissions/70464977

*/

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

第 49 届 ICPC区域赛沈阳站——D. Dot Product Game

Posted on 2026-01-09 Edited on 2026-03-26

思路讲解

交换一定使得逆序对数量奇偶性变化，循环移动一格可以看作交换len-1次

（长度为len的）向左（向右）循环移动一次可以看作交换len-1次

第 49 届 ICPC区域赛沈阳站——D. Dot Product Game

FOR(i, 1, N - 1) {
    char ch;
    ll l, r, d;
    cin >> ch >> l >> r >> d;
    ll len = r - l + 1;
    // 向左循环移动一个可以看作交换len-1次，向左循环移动d次，就是交换d*(len-1)次
    if (d != 0)
        inva += (len-1)*d;
    out();
}

然后如何比较快速的求出一个数组中的这个逆序对的奇偶性呢？其实也不难。

众所周知，排列成环，成的环，在环上向左循环移动一次以后就复位了。那么如果说有一个环，（以下说相等，是默认是奇偶性相等），那么逆序对就是N-1，有两个环，逆序对就是N-2。因此只需要知道环的数量即可，会比这个直接用这个树状数组求好写一点。

AC代码

https://qoj.ac/submission/1658154

源代码

// by Gospel_rock
// title: D. Dot Product Game 补题
// timeLimit: 2000
// url: https://codeforces.com/gym/105578/problem/D
#include <array>
#include <bits/stdc++.h>
#include <vector>
#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())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
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;
ll fa[MAXN];
ll find(ll x) {
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
void merge(ll u, ll v) {
    u = find(u), v = find(v);
    fa[u] = v;
}
void Solve() {
    cin >> N;
    // vector<ll> A(N+5),B(N+5);
    vector<array<ll, 2>> A(N + 5);
    FOR(i, 1, N) { cin >> A[i][0]; }
    FOR(i, 1, N) { cin >> A[i][1]; }
    sort(A.begin() + 1, A.begin() + 1 + N);
    FOR(i, 1, N) { fa[i] = i; }
    FOR(i, 1, N) { merge(A[i][1], i); }
    ll invb = 0;
    // 直接计算需要多少次交换得到答案比较困难
    // 其实这道题目没有那么复杂，我们先要知道轮换次数
    FOR(i, 1, N) {
        if (fa[i] == i) {
            invb++;
        }
    }
    invb = (N - invb) % 2;
    // sort(A.begin()+1,A.begin()+1+N,[&](array<ll, 2> &a,array<ll, 2> &b){
    //     return a[1]<b[1];
    // });
    // FOR(i,1,N){
    //     fa[i]=i;
    // }
    // FOR(i,1,N){
    //     merge(A[i][0],i);
    // }
    ll inva = 0;
    // FOR(i,1,N){
    //     if(fa[i]==i){
    //         inva++;
    //     }
    // }
    // inva=(N-inva)%2;
    auto out = [&]() {
        ll c = inva + invb;
        c %= 2;
        if (c) {
            cout << "A";
        } else {
            cout << "B";
        }
    };
    out();
    FOR(i, 1, N - 1) {
        char ch;
        ll l, r, d;
        cin >> ch >> l >> r >> d;
        ll len = r - l + 1;
        // 向左循环移动一个可以看作交换len-1次，向左循环移动d次，就是交换d*(len-1)次
        if (d != 0)
            inva += (len-1)*d;
        out();
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}
/*
 *AC
 *https://qoj.ac/submission/1658154
 *
*/