gjoi 2024.9.12

T1 星天花雨

首先考虑分解 \(k=l\times r\)，然后考虑 \(a/b\) 的前缀和中差分为 \(l/r\) 的对数是多少累加进去就行了，这个是好求的。

#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back

using namespace std;

const int N=100005, P=998244353;

int n, m, k, a[N], b[N], L[N], R[N], Ans, flag=1;

void solve(int l,int r) {
	if(l>a[n]||r>b[m]) return;
	if(flag) {
		(Ans+=1ll*(n-l+1)*(m-r+1)%P)%=P;
		return;
	}
	int cnt1=0, cnt2=0;
	up(i,0,a[n]-l) (cnt1+=1ll*L[i]*L[i+l]%P)%=P;
	up(i,0,b[m]-r) (cnt2+=1ll*R[i]*R[i+r]%P)%=P;
	(Ans+=1ll*cnt1*cnt2%P)%=P;
}

signed main() {
	freopen("rain.in","r",stdin);
	freopen("rain.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k, L[0]=R[0]=1;
	up(i,1,n) cin >> a[i], a[i]+=a[i-1], ++L[a[i]];
	up(i,1,m) cin >> b[i], b[i]+=b[i-1], ++R[b[i]];
	up(i,1,n) if(a[i]!=a[i-1]+1) flag=0;
	up(i,1,m) if(b[i]!=b[i-1]+1) flag=0;
	for(int i=1; i*i<=k; ++i) if(k%i==0) {
		solve(i,k/i);
		if(i*i!=k) solve(k/i,i);
	}
	cout << Ans;
	return 0;
}

T2 野火

Bronya 可爱，多测全塞二元环不可爱（二元环二分上界要给到 \(3\times 10^9\)） /fn

就是先考虑二分，树的情况是简单的，二分之后不够的补上得了。

首先基环树中那一部分无用，只考虑环，我们先补满，然后时刻里面环上可以断一条边，我们考虑怎么断最优，首先会想去拿那个 \(d_i\) 最小的断掉，拿回那 \(mid-d_i\) 的部分，然后发现前面 \(d_i\) 时刻还可以断别的，那就考虑给 \(d_i\) 次小的吃这个贡献，所有可能的贡献这个次小一定能吃满，然后就做完了。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back

using namespace std;

const int N=200005, inf=1ll<<60;

int n, m, sp, in[N], u[N], v[N], d[N], vis[N];
vector<int> to[N]; queue<int> q; 

void solve1() {
	int l=1, r=3e9, Ans;
	while(l<=r) {
		int mid=(l+r)>>1, ret=0;
		up(i,1,m) if(d[i]<mid) ret+=mid-d[i];
		if(ret<=sp) Ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << Ans << '\n';
}

void solve2() {
	up(i,1,n) vis[i]=0;
	up(i,1,n) if(in[i]==1) q.push(i);
	while(q.size()) {
		int x=q.front();
		vis[x]=1, q.pop();
		for(int y:to[x]) if(--in[y]==1) q.push(y);
	}
	int l=1, r=3e9, Ans;
	while(l<=r) {
		int mid=(l+r)>>1, ret=0, fir=inf, sec=inf;
		up(i,1,m) if((vis[u[i]]||vis[v[i]])&&d[i]<mid) ret+=mid-d[i];
		up(i,1,m) if(!vis[u[i]]&&!vis[v[i]]&&d[i]<mid) {
			ret+=mid-d[i];
			if(d[i]<fir) sec=fir, fir=d[i];
			else if(d[i]<sec) sec=d[i];
		}
		if(fir<inf) ret-=mid-fir;
		if(sec<inf) ret-=max(mid-sec,0ll)-max(mid-fir-sec,0ll);
		if(ret<=sp) Ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << Ans << '\n';
}

void mian() {
	cin >> n >> m >> sp;
	up(i,1,n) in[i]=0, to[i].clear();
	up(i,1,m) {
		cin >> u[i] >> v[i] >> d[i];
		++in[u[i]], ++in[v[i]];
		to[u[i]].pb(v[i]), to[v[i]].pb(u[i]);
	} 
	if(m==n-1) solve1(); else solve2();
	
}

signed main() {
	freopen("wildfire.in","r",stdin);
	freopen("wildfire.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int id, T;
	cin >> id >> T;
	while(T--) mian();
	return 0;
}

T3 赤玉琉金

点对能产生贡献当且仅当一个点集 \(S\) 没有被删除（如上图绿色部分），考虑 \(|S|=x\) 的点对的贡献，不难写出 \(Ans_x=\sum_{t=0}^n\binom{n-x}{t}\times t!\times (n-t)!=\frac{(n-x)!}{(n-x-t)!}\times (n-t)!\)，常数 \((n-x)!\) 提出来得到 \(Ans_x=(n-x)!\times \sum_{t=0}^n\frac{(n-t)!}{(n-x-t)!}\)，后面那部分还是不好求，但是补成组合数可以组合意义，\(Ans_x=(n-x)!x!\times \sum_{t=0}^n\binom{n-t}{x}=(n-x)!x!\times \sum_{t=0}^n\binom{t}{x}\)。