Znzryb's Blog

P3128 [USACO15DEC] Max Flow P（打印）

Posted on 2025-01-22 Edited on 2026-02-15

思路讲解

用的tarjan方法求的LCA（倍增我不太会）

参考讲解（树上差分）

AC代码

AC
https://www.luogu.com.cn/record/199856000

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e5)+10;
ll N,K;
vector<ll> g[MAXN];
ll fa[MAXN],par[MAXN];
bool vis[MAXN],done[MAXN],vis2[MAXN];
vector<pll> route[MAXN];
ll diff[MAXN];	// 树上差分数组
ll ans[MAXN];	// 原数组
// https://www.luogu.com.cn/problem/P3128
// LCA+树上差分
ll find(int x) {
	if(fa[x]==x) return fa[x];
	fa[x]=find(fa[x]);
	return fa[x];
}
void dfs(int x,int pa) {  // 求LCA以及进行树上差分
	vis[x]=true;fa[x]=x;	// 一开始并查集要指向自己
	par[x]=pa;	// 另外的一个专门记录父节点的数组
	for(int i=0;i<g[x].size();++i) {
		if(vis[g[x][i]]) continue;	// 走过的我们不走了
		dfs(g[x][i],x);
		fa[g[x][i]]=x;	// 并查集指向自己父亲
	}
	for(int i=0;i<route[x].size();++i) {
		ll t=route[x][i].first,idx=route[x][i].second;
		if(vis[t] && !done[idx]) {	// 树上差分操作
			done[idx]=true;	// 避免重复树上差分
			diff[find(t)]-=1;	// 这里-1是因为最近公共祖先会被记两次
			diff[x]+=1;
			diff[t]+=1;			// 在区间开头+1
			diff[par[find(t)]]-=1; // 在区间结束-1
		}
	}
}
// 还原差分数组为原数组
void restorDiff(int x) {
	vis2[x]=true;
	for(int i=0;i<g[x].size();++i) {
		if(vis2[g[x][i]]) continue;	// 走过的我们不走了
		restorDiff(g[x][i]);
		ans[x]+=ans[g[x][i]];
	}
	ans[x]+=diff[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i=1;i<=N-1;++i) {
		ll u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=K;++i) {
		ll s,t;
		cin>>s>>t;
		route[s].push_back({t,i});
		route[t].push_back({s,i});
	}
	// 应当认为1的根节点是0或者是无，而不是自己
	dfs(1,0);
	restorDiff(1);
	ll Ans=0;
	for(int i=1;i<=N;++i) {
		Ans=max(Ans,ans[i]);
	}
	cout<<Ans<<endl;
	// for(int i=1;i<=N;++i) {	// debug
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/199856000
*/

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

这道题数据范围好像是有点问题，需要开到5e5+10才行，反正有点离谱，也不知道是我0数错了还是什么，反正有点离谱

2025牛客WC1-J-硝基甲苯之袭

Posted on 2025-01-21 Edited on 2026-02-15

思路讲解

赛时最后30min过了，通过网上搜到的结论，

gcd(a,b)=a\ xor\ b=a-b（结论，下面是推理过程）

a-b<=a\ xor\ b=gcd(a,b)

gcd(a,b)*x=a,\ gcd(a,b)*y=b\xrightarrow{可得}a-b=(x-y)*gcd(a,b)\xrightarrow{可得}\\a-b<=gcd(a,b)\xrightarrow{又因为a-b>=gcd(a,b)}gcd(a,b)=a-b

当然不可能每题都用结论嘛，所以看看枚举可不可以过

搞半天发现和我的赛时代码也差不多，jiangly差不多也是我这个做法

最重要的其实就是更换枚举尺度，枚举a太慢了，可以枚举g，进而枚举a时只用枚举g的倍数就行了

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74967799

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,A[MAXN];
ll Cnt[MAXN];
ll gcd(ll a,ll b) {
	if(b==0) return a;
	return gcd(b,a%b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		Cnt[A[i]]+=1;
	}
	// sort(&A[1],&A[N+1]);
	ll ans=0;ll m=*max_element(&A[1],&A[N+1]);
	for(int g=1;g<=m;++g) {
	// 枚举公因数g
		for(int a=g;a<=m;a+=g) {
		// 枚举a
			ll b=a^g;// 判断a，b，g是否符合条件
			if(a<b && gcd(a,b)==g && b<=m) {
				ans+=Cnt[a]*Cnt[b];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
15
1 1 4 6 6 9 9 8 8 6 7 6 22 26 28

*/

赛时AC记录

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74946535

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,T,A[MAXN];
ll gcd(ll a,ll b) {
	if(b==0) return a;
	return gcd(b,a%b);
}
inline ll lowbit(ll x) {
	return x&(-x);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
	}
	sort(&A[1],&A[N+1]);
	ll ans=0;
	for(int i=1;i<=A[N];++i) {
		for(int j=i;j<=A[N]-i;j+=i) {
			if((j^(j+i))!=i) continue;
			ans+=(upper_bound(&A[1],&A[N+1],j)-&A[0]-(lower_bound(&A[1],&A[N+1],j)-&A[0])) *
				(upper_bound(&A[1],&A[N+1],j+i)-&A[0]-(lower_bound(&A[1],&A[N+1],j+i)-&A[0]));
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
7
1 2 3 4 5 6 7

5
2 6 2 3 4
AC
*/

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

2025牛客WC1-M-数值膨胀之美

Posted on 2025-01-21 Edited on 2026-02-15

思路讲解

https://ac.nowcoder.com/discuss/1452662

主要就是他的思路，赛时实际上就AC了，只不过赛后数据加强了，前面AI乱写的过不去了。

这个思路就是贪心，先把最小的吃掉，再吃次小的，再吃次次小的。。。。以此类推

AC代码

AC

https://ac.nowcoder.com/acm/contest/95323/M

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10,maxval=static_cast<ll>(1e18)+3;
ll N,T,A[MAXN];
multiset<ll> st;
vector<pll> Apos;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll maxA=0,minA=maxval;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		st.insert(A[i]);
		Apos.push_back({A[i],i});
	}
	sort(Apos.begin(),Apos.end());
	st.insert(*st.begin()*2);
	st.erase(st.begin());
	ll ans=*st.rbegin()-*st.begin();
	ll l=Apos[0].second,r=Apos[0].second;
	for(int i=1;i<N;++i) {
		ll pos=Apos[i].second,key=Apos[i].first;
		if(l<=pos && pos<=r) continue;
		if(pos<l) {
			ll l1=pos;
			for(int j=l1;j<l;++j) {
				auto it=st.lower_bound(A[j]);
				st.insert(*it*2);
				st.erase(it);
			}
			l=l1;
		}else {
			ll r1=pos;
			for(int j=r+1;j<=r1;++j) {
				auto it=st.lower_bound(A[j]);
				st.insert(*it*2);
				st.erase(it);
			}
			r=r1;
		}
		ans=min(ans,*st.rbegin()-*st.begin());
	}
	cout<<ans<<endl;
	return 0;
}
/*
5
9 3 5 3 9

*/

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

2025牛客WC1-E-双生双宿之错

Posted on 2025-01-21 Edited on 2026-02-15

思路讲解

参考题解：

https://ac.nowcoder.com/discuss/1452661

https://ac.nowcoder.com/discuss/1452662（这个题解好）

中位数定理，其实类似于树的重心（以该点为根，最大子树最小），都是不能牺牲大我

只有一个点左边也有n个点，右边也有n个点，到达该点距离之和最短

其实数轴就是一种特殊的树嘛～～

AC代码

AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74961575

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
ll N,T,A[MAXN];
void solve() {
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    sort(&A[1],&A[N+1]);
    // 中位数定理
    ll mid1,mid2;
    if(N%4==0) mid1=A[N/4]+A[N/4+1]>>1,mid2=A[3*N/4]+A[3*N/4+1]>>1;
    else mid1=A[N/4+1],mid2=A[3*N/4+1];	// 是不是严格在中间是不重要的
    if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }
    ll dis=0;
    for(int i=1;i<=N;++i) {
        if(i<=N/2) {
            dis+=abs(A[i]-mid1);
        }else {
            dis+=abs(A[i]-mid2);
        }
    }
    cout<<dis<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
3
4
1 1 3 1
4
6 6 6 6
6
1 1 4 4 1 4

*/

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

前面一直有点问题，结果是因为这个特判mid1-=1和mid2+=1都要算

if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }

P6136 【模板】普通平衡树（数据加强版）

Posted on 2025-01-21 Edited on 2026-02-15

思路讲解

FHQ-Treap

https://www.luogu.com.cn/article/vj041eul

AC代码

AC

https://www.luogu.com.cn/record/200519720

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
const ll MAXN = static_cast<ll>(4e6) + 10;
ll N, M, idx, root, last, ans;
mt19937 rng(time(0));
//                          值         随机值
ll son[MAXN][2], size[MAXN], key[MAXN], rad[MAXN];
inline void resize(ll k) { size[k] = size[son[k][0]] + size[son[k][1]] + 1; }
// split函数返回的是分裂出来的左子树和右子树的编号
//          根与按值分裂的值
pll split(ll u, ll k) {
    // 这里按值分裂,分裂为左子树<k，右子树>=k;
    if (!u)
        return {0, 0}; // 递归终止条件
    if (key[u] < k) {
        // 继续分裂右子树（左子树全部<k，也都符合条件）
        pll t = split(son[u][1], k);
        son[u][1] = t.first;
        resize(u); // 重新计算树大小
        // 进入到了这个节点，就是来找左子树中有没有>=k的值的
        return {u, t.second};
    } else {
        // 继续分裂左子树（右子树全部>=k，都符合条件）
        pll t = split(son[u][0], k);
        son[u][0] = t.second;
        resize(u);
        // 进入到了这个节点，就是来找右子树中有没有<k的值的，右子树中<k的值的就是在左子树
        return {t.first, u};
    }
}
// merge函数接受两个参数，为两棵树的根；返回合并后的根。
ll merge(ll u, ll v) {
    if (!u | !v)
        return u + v; // 如果任何一棵树为空，返回另一棵树
    if (rad[u] < rad[v]) {
        // 小根堆，我们让随机值小的u当根，merge左子树
        son[u][1] = merge(son[u][1], v);
        resize(u);
        return u;
    } else {
        // u值比较大，当v的右边
        son[v][0] = merge(u, son[v][0]);
        resize(v);
        return v;
    }
}
inline void insert(ll k) {
    key[++idx] = k;
    rad[idx] = rng();
    size[idx] = 1;
    pll t = split(root, k);
    root = merge(merge(t.first, idx), t.second);
}
inline void eraser(ll k) {
    pll x = split(root, k);
    // x.second 是所有>=k的，所以y就分成了=k的和>k的
    pll y = split(x.second, k + 1);
    // 把=k的根节点吃掉了
    y.first = merge(son[y.first][0], son[y.first][1]);
    // 依次合并起来，更新根
    root = merge(x.first, merge(y.first, y.second));
}
// 查询k的排名
inline ll find1(ll k) {
    pll t = split(root, k);
    ll rank = size[t.first] + 1;
    root = merge(t.first, t.second);
    return rank;
}
// 根据排名找数
inline ll find2(ll rank) {
    ll pos = root;
    while (pos) {
        if (rank == size[son[pos][0]] + 1)
            return key[pos];
        else if (size[son[pos][0]] + 1 > rank)
            pos = son[pos][0];
        else
            rank -= size[son[pos][0]] + 1, pos = son[pos][1];
    }
    return 0;
}
// 查询前驱
inline ll lst(ll k) { return find2(find1(k) - 1); }
// 直接find1(k+1)，查询的值+1，避免了值相同的问题
inline ll nxt(ll k) { return find2(find1(k + 1)); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        insert(a);
    }
    // cout<<"debug "<<0<<" :\n";
    // cout<<root<<'\n';
    // for(int j=1;j<=N;++j) {
    //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
 // }
 for(int i=1;i<=M;i++){
  ll o,x;
  cin>>o>>x;
  // x^=last;
  if(o==1) insert(x^last);
  if(o==2) eraser(x^last);
  if(o==3) { last=find1(x^last); ans^=last; }
  if(o==4) { last=find2(x^last); ans^=last; }
  if(o==5) { last=lst(x^last); ans^=last; }
  if(o==6) { last=nxt(x^last); ans^=last; }
  // cout<<"debug "<<i<<" :\n";
  // for(int j=1;j<=N;++j) {
  //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
  // }
 }
 cout<<ans<<endl;
 return 0;
}
/*
AC https://www.luogu.com.cn/record/200519720
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4

*/

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

各种奇怪的地方吧，导致WA了。