Znzryb's Blog

START197B——Expected Cost 预期成本

Posted on 2025-07-30 Edited on 2026-04-06

思路讲解

精髓在于猜这个你随机跳到其他位置以后，再跳到终点N+1的期望成本，可以设这个东西位S，用这个S算出来的S，我们叫做g(S)。那么 $g(S)=S$ 那是必须的，但是我们猜的不等于怎么办呢？

于是我们就二分。

至于这个二分的收敛方向嘛，我试着推了一下，我的建议是都试试。guess嘛。

这个图把y=x画的太斜了，实际上在y=x的下面， $g(S)<S$ ，需要向左移动（也就是even<mid，r=mid）。

// 从x到N+1的最小期望成本
vdb dp(N+5);
DB l=0,r=accumulate(all(A),0ll)+accumulate(all(B),0ll);
FOR(_,1,100){
    DB mid=(l+r)/2;
    dp[N]=min((DB)A[N-1],mid+B[N-1]);
    ROF(i,N-1,1){
        dp[i]=min(dp[i+1]+A[i-1],mid+B[i-1]);
    }
    DB even=0;
    FOR(i,1,N){
        even+=dp[i];
    }
    // 包含位置 N+1 的 f=0（随机游走位置是包含N+1的）
    even/=(N+1);
    // 如果答案有问题，可以先换一下收敛方向
    // 我们要尽可能的减少这个even与这个mid之间的差
    if(even>mid){
        l=mid;
    }else{
        r=mid;
    }
}

AC代码

源代码

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

2025“钉耙编程”中国大学生算法设计暑期联赛（4）——1007 咖啡的罪恶

Posted on 2025-07-28 Edited on 2026-04-06

思路讲解

AC代码

源代码

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

2025“钉耙编程”中国大学生算法设计暑期联赛（4）——回忆与展望

Posted on 2025-07-28 Edited on 2026-04-06

思路讲解

赛后自己想出来了

核心代码是

FOR(i,1,N){
    if(cnt[i]==0) continue;
    diff[cnt[i]+1]-=1;
    diff[1]+=1;
}
// 这个sum维护的就是出现次数
// Sum[i] 表示出现次数大于等于i的数有Sum[i]个
vll Sum(N+5);
FOR(i,1,N){
    Sum[i]=Sum[i-1]+diff[i];
}
ll ans=jichu;ll lans=jichu;
FOR(i,2,N){     // 枚举分为i条链的情况
    if(Sum[i]<=1) break;
    lans+=(Sum[i]-1)*X;
    lans-=Sum[i]*Y;
    lans+=Z;
    ans=max(lans,ans);
}

AC代码

https://acm.hdu.edu.cn/contest/view-code?cid=1175&rid=12705

源代码

// 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 SZ(a) ((int) 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"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#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 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 vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,Y,Z;

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>>X>>Y>>Z;
	vll P(N),cnt(N+5);
    FOR(i,0,N-1){
        cin>>P[i];
        ++cnt[P[i]];
    }
    if(N==1){
        cout<<X<<"\n";
        return;
    }
    sort(all(P));
    vll diff(N+5);
    ll jichu=0;
    FOR(i,1,N-1){
        if(P[i]==P[i-1]){
            jichu+=Y;
        }else{
            jichu+=X;
        }
    }
    jichu+=X;
    FOR(i,1,N){
        if(cnt[i]==0) continue;
        diff[cnt[i]+1]-=1;
        diff[1]+=1;
    }
    // 这个sum维护的就是出现次数
    // Sum[i] 表示出现次数大于等于i的数有Sum[i]个
    vll Sum(N+5);
    FOR(i,1,N){
        Sum[i]=Sum[i-1]+diff[i];
    }
    ll ans=jichu;ll lans=jichu;
    FOR(i,2,N){     // 枚举分为i条链的情况
        if(Sum[i]<=1) break;
        lans+=(Sum[i]-1)*X;
        lans-=Sum[i]*Y;
        lans+=Z;
        ans=max(lans,ans);
    }
    cout<<ans<<"\n";
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1175&rid=12705

*/

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

Codeforces Round 788 (Div. 2)——C. Where is the Pizza?

Posted on 2025-07-26 Edited on 2026-04-06

思路讲解（gemini翻译的题解）

首先，我们来解决一个简化版的问题，即假设数组 d 中全是 0（换句话-说，对于需要形成的排列 c 没有任何预设的限制）。

我们假设排列 a 为 [1,2,3,4]，排列 b 为 [3,1,2,4]。

假设我们已经选择了数组 c 的第一个元素为数组 a 的第一个元素（即 c[0] = a[0] = 1）。这样一来，我们就不能选择数组 b 的第一个元素了（b[0] = 3）。由于我们希望数组 c 是一个完整的排列，那么数字 3 就必须在 c 中出现，所以我们必须从数组 a 中找到 3 并将其加入到数组 c 中。

我们在数组 a 中寻找 3，发现它在索引 2 的位置（a[2]=3），于是我们选择 c[2] = a[2] = 3。这个选择导致我们不能再选择 b 中对应索引的元素（即 b[2]=2）。因此，我们又必须从 a 中找到 2 并加入 c。我们在 a 中找到 2 在索引 1 的位置（a[1]=2），所以选择 c[1] = a[1] = 2。这次，b 在该索引对应的元素是 1（b[1]=1），而 1 已经因为我们最初的选择被包含在数组 c 中了。这样，我们就不再被强制要求从 a 中选择新的元素了，形成了一个闭环。

我们观察到，我们最初选择的元素 1，以及之后被“强制”选择的元素 2 和 3，即 [1,3,2]（按选择顺序），与它们在 b 数组中对应位置的元素 [3,2,1] 构成了相同元素的排列。这些元素形成了一个“分组”。对于每个大小超过 1 的分组，我们都有 2 个选择：

将这个分组对应的所有元素都从 a 中选取。
将这个分组对应的所有元素都从 b 中选取。

所以，这个简化版问题的答案就是：找出所有这样相互关联的分组，统计其中大小超过 1 的分组数量（我们称之为 p），最终答案就是 2p。

那么，如果数组 `d` 不全是 `0` 该怎么办呢？

这种情况我们只需要在之前的逻辑上增加一个约束。对于我们找到的每一个分组，我们必须检查其所有成员在 d 数组中对应的位置是否全为 0。

如果一个分组对应的所有 d 数组位置上的值都是 0，那么这个分组就有两种选择（要么全选 a，要么全选 b），对最终答案的贡献是乘以 2。
如果一个分组中，哪怕只有一个成员在 d 数组中对应的位置不为 0（意味着这个位置的选择已经被 d 数组固定了），那么整个分组的选择也就被唯一确定了，它只有一种选择方案。这种分组对最终答案的贡献是乘以 1，我们就不需要把它计入 p 中。

这个解法可以通过多种方式实现，但在我看来，**使用并查集（Disjoint Set Union, DSU）**来将每个分组的元素合并在一起，是实现这个逻辑最优雅的方式。

AC代码

https://codeforces.com/contest/1670/submission/330958420

源代码

// Problem: C. Where is the Pizza?C. 披萨在哪里？
// Contest: Codeforces - Codeforces Round 788 (Div. 2)
// URL: https://codeforces.com/contest/1670/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by Gospel_rock
// 
// Powered by CP Editor (https://cpeditor.org)

#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 SZ(a) ((int) 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)

using namespace std;

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 vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e5+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN],B[MAXN],C[MAXN];

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

*/
ll posa[MAXN],posb[MAXN];
bool vis[MAXN];
struct DSU { // 并查集
    vector < int > fa, siz;
    int ln;
    DSU(int n) {
        ln = n;
        fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
        FOR(i, 1, n) {
            fa[i] = i;
            siz[i] = 1;
        }
    }
    int find(int x) {
        while (fa[x] != x) {
            x = fa[x];
            fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
    int countFa() {
        int res = 0;
        FOR(i, 1, ln) {
            if (fa[i] == i) ++res;
        }
        return res;
    }
};
ll binpow(ll a,ll k,const ll &p=mod){	// 迭代快速幂
	ll res=1;
	a%=p;		// 防止a*a溢出
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
inline void __(){
	cin>>N;
	DSU fa(N);
	FOR(i,0,N+5){
		vis[i]=0;
	}
	vector<vector<ll> > g(N+5);
	FOR(i,1,N){
		cin>>A[i];
		posa[A[i]]=i;
	}
	FOR(i,1,N){
		cin>>B[i];
		posb[B[i]]=i;
	}
	FOR(i,1,N){
		cin>>C[i];
	}
	if(N==0){
		cout<<0<<"\n";return;
	}
	FOR(i,1,N){
		if(vis[i]) continue;
		ll idx=posa[i];
		while(!vis[A[idx]]){
			fa.merge(A[idx],B[idx]);
			vis[A[idx]]=true;
			idx=posa[B[idx]];
		}
	}
	vb viss(N+5);
	ll ans=1;
	FOR(i,1,N){
		ll pa=fa.find(i);
		if(viss[pa]) continue;
		viss[pa]=true;
		if(fa.size(i)>=2){
			ans*=2;
			ans%=mod;
		}
	}
	vector<ll> wp;
	FOR(i,1,N){
		if(C[i]==0) continue;
		wp.pb(fa.find(C[i]));
	}
	sort(all(wp));wp.resize(unique(all(wp))-wp.begin());
	ll inv2=binpow(2,mod-2);
	FOR(i,0,SZ(wp)-1){
		ll rt=wp[i];
		if(fa.size(rt)>=2){
			ans*=inv2;
			ans%=mod;
		}
	}
	cout<< ans <<"\n";
}
/*
AC
https://codeforces.com/contest/1670/submission/330958420
*/

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

2025牛客暑期多校训练营4——Problem G. Ghost in the Parentheses

Posted on 2025-07-26 Edited on 2026-04-06

思路讲解

2025“钉耙编程”中国大学生算法设计暑期联赛（3）（2025杭电多校 3）——1009线段染色

和这道题目有点相似，难点都在于这个容斥上面，那么解决都很简单，就是上dp。

AC代码

源代码

思路讲解

AC代码

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

思路讲解

AC代码

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

思路讲解

AC代码

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

思路讲解（gemini翻译的题解）

那么，如果数组 d 不全是 0 该怎么办呢？

AC代码

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

思路讲解

AC代码

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

那么，如果数组 `d` 不全是 `0` 该怎么办呢？