首页 > 其他分享 >【比赛记录】国庆集训合集

【比赛记录】国庆集训合集

时间：2024-01-17 18:56:55浏览次数：35  
标签：return int res 国庆 ans inline 合集 集训 mod

\(\text{T1}\) GirlFriend区间 3

好题。

先把质数筛了。

考虑将所有区间按照左右端点离散化。将询问离线下来，然后对于每个右端点统计左端点上的贡献。即从小到大扫描 \(r\)，维护每一个后缀的答案。

考虑使用 set 维护区间的并。考虑已处理前 \(r-1\) 的询问，处理位于 \(r\) 上的所有右端点的询问产生的影响。那么对于 \([i,r-1]\) 的区间并，\(r\) 的区间产生的贡献覆盖的是 \([i,r]\) 的并减去 \([i,r-1]\) 的区间。也就是空出来的部分。然后使用树状数组维护。

注意到对于一个之前的区间 \(i\)，它最多被 update 覆盖两次（左端点被覆盖时一次，右端点一次）。所以颜色段均摊 \(O((n+m)\log n)\)。

代码还没写完。

upd：你妈的不写了。

\(\text{T2}\) ABC小精灵

考虑 AB 通过 ABAA->ABABBA->BA 可以变成 BA。同理 BC 可以变成 CB。

那么 A 与 B，C 与 B 可以相互交换。那么 B 就可以随意放置。将 B 扔到最前面，然后 A,C 相对位置无法交换。所以最终序列必然形如 B...BACAACCAA...，对于相邻两个相同的字符再删去，比较最终序列即可判断。

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+6;

int T,n,m,B1,B2,top1,top2;
char s1[N],s2[N],t1[N],t2[N];

inline void solve(){
	B1=B2=top1=top2=0;
	scanf("%s%s",s1+1,s2+1),n=strlen(s1+1),m=strlen(s2+1);
	for(int i=1;i<=n;i++){
		if(s1[i]=='B')B1++;
		else{
			if(s1[i]==t1[top1])top1--;
			else t1[++top1]=s1[i];
		}
	}
	for(int i=1;i<=m;i++){
		if(s2[i]=='B')B2++;
		else{
			if(s2[i]==t2[top2])top2--;
			else t2[++top2]=s2[i];
		}
	}
	if(top1!=top2||(B1-B2)&1){
		puts("NO");
		return;
	}
	for(int i=1;i<=top1;i++)if(t1[i]!=t2[i]){
		puts("NO");
		return;
	}
	puts("YES");
	return;
}

int main(){
	scanf("%d",&T);
	while(T--)solve(); 
}

\(\text{T3}\) 树的计数

显然是个笛卡尔树相关。然后对于多个相同的 min 必定形如一棵二叉树。所以对于一段区间其贡献为相同的 min 的个数。使用卡特兰数计算。然后多个 min 会将一个区间分割为多个区间，那么递归求解。对于区间 min 与 min 的位置使用线段树实现。当然你也可以用 ST表+set 一只 \(\log\)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls p<<1
#define rs p<<1|1
#define pb push_back

const int N=1e6+7;
const int mod=1e9+7;

int n,a[N],fac[N<<1],ifac[N<<1],tr[N<<2],mn;
vector<int>pos[N<<2],mnpos;

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

inline void init(int n){
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	return;
}

inline int C(int n,int m){
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

inline int Cat(int n){
	return (C(2*n,n)-C(2*n,n-1)+mod)%mod;

}

inline void merge(vector<int>&x,int y){
	for(auto i:pos[y])x.pb(i);
	return;
}

inline void pushup(int p){
	tr[p]=min(tr[ls],tr[rs]);
	if(tr[p]==tr[ls])merge(pos[p],ls);
	if(tr[p]==tr[rs])merge(pos[p],rs);
	return;
}

inline void build(int p,int l,int r){
	if(l==r){
		tr[p]=a[l],pos[p].pb(l);
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(p);
	return;
}

inline void query(int p,int l,int r,int s,int t){
	if(s>t)return;
	if(s<=l&&r<=t){
		if(mn>tr[p])mn=tr[p],mnpos=pos[p];
		else if(mn==tr[p])merge(mnpos,p);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(ls,l,mid,s,t);
	if(t>mid)query(rs,mid+1,r,s,t);
	return;
}

inline int solve(int l,int r){
	if(l>=r)return 1;
	mnpos.clear(),mn=LLONG_MAX;
	query(1,1,n,l,r);
	int ans=1,num=0,lst=l;
	vector<pair<int,int> >vec;
	vec.clear();
	for(auto i:mnpos){
		num++;
		vec.push_back(make_pair(lst,i-1));
		lst=i+1;
	}
	for(auto i:vec)ans=ans*solve(i.first,i.second)%mod;
	ans=ans*solve(lst,r)%mod;
	ans=ans*Cat(num)%mod;
	return ans;
}

signed main(){
	scanf("%lld",&n);init(N-1);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	printf("%lld",solve(1,n));
	return 0;
}

\(\text{T4}\) AND=OR

考虑将两个区间独立开然后依次与。那么显然 popcount 是单调不升的。同理对于或的情况单调不减。

所以对于一段区间，按照 popcount 排序，选出的必然是选择一段前缀与后缀。

枚举两边相等数的 popcount \(k\)，查询区间内 popcount 为 \([0,k-1]\) 的或和与 \([k+1,30]\) 的数的与和。注意对于 popcount 为 \(k\) 的数必然全部相同。否则无解。对于每个 \(k\) 使用线段树维护。

#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1

const int N=1e5+6;
const int M=32;

int n,Q,mxpc,And_[M],Or_[M],Cnt_[M],a[N];

struct SegmentTree{
	int And[N<<2],Or[N<<2],tr[N<<2];
	inline void pushup(int p){
		And[p]=And[ls]&And[rs];
		Or[p]=Or[ls]|Or[rs];
		tr[p]=tr[ls]+tr[rs];
		return;
	}
	inline void build(int p,int l,int r){
		if(l==r){
			And[p]=-1,Or[p]=tr[p]=0;
			return;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(p);
	}
	inline void update(int p,int l,int r,int ps,int val){
		if(l==r){
			And[p]=Or[p]=val,tr[p]=1;
			return;
		}
		int mid=(l+r)>>1;
		if(ps<=mid)update(ls,l,mid,ps,val);
		else update(rs,mid+1,r,ps,val);
		pushup(p);
	}
	inline int queryand(int p,int l,int r,int s,int t){
		if(s<=l&&r<=t)return And[p];
		int mid=(l+r)>>1,res=-1;
		if(s<=mid)res&=queryand(ls,l,mid,s,t);
		if(t>mid)res&=queryand(rs,mid+1,r,s,t);
		return res;
	}
	inline int queryor(int p,int l,int r,int s,int t){
		if(s<=l&&r<=t)return Or[p];
		int mid=(l+r)>>1,res=0;
		if(s<=mid)res|=queryor(ls,l,mid,s,t);
		if(t>mid)res|=queryor(rs,mid+1,r,s,t);
		return res;
	}
	inline int query(int p,int l,int r,int s,int t){
		if(s<=l&&r<=t)return tr[p];
		int mid=(l+r)>>1,res=0;
		if(s<=mid)res+=query(ls,l,mid,s,t);
		if(t>mid)res+=query(rs,mid+1,r,s,t);
		return res;
	} 
}ch[M];

inline int pc(int x){
	if(x<0)return 47497;
	int res=0;
	while(x){
		res+=x&1;
		x>>=1;
	}
	return res;
}

int main(){
	scanf("%d%d",&n,&Q);
	for(int i=0;i<=30;i++)ch[i].build(1,1,n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		int x=pc(a[i]);
		mxpc=max(mxpc,x);
		ch[x].update(1,1,n,i,a[i]);
	}
	while(Q--){
		int l,r,flag=0;
		scanf("%d%d",&l,&r);
		for(int i=0;i<=mxpc;i++){
			And_[i]=ch[i].queryand(1,1,n,l,r);
			Or_[i]=ch[i].queryor(1,1,n,l,r);
			Cnt_[i]=ch[i].query(1,1,n,l,r);
		}
		for(int i=0;i<=mxpc;i++){
			int Sor=0,Sand=-1,Cntor=0,Cntand=0;
			for(int j=0;j<i;j++)Sor|=Or_[j],Cntor+=Cnt_[j];
			for(int j=i;j<=mxpc;j++)Sand&=And_[j],Cntand+=Cnt_[j];
			if(Sor==Sand&&Cntor>0&&Cntand>0){
				puts("YES");flag=1;
				break;
			}
			if(pc(And_[i])!=i)continue;
			if(Cnt_[i]>1&&(Sor|And_[i])==(Sand)){
				puts("YES");flag=1;
				break;
			}
		}
		if(!flag)puts("NO");
	}
	return 0;
}

\(\text{T5}\) 数学题

如 FWT 按照 \(2\) 的次幂为合并长度合并答案。然后直接子集 dp。

具体实现请参考：https://codeforces.com/blog/entry/45223

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=6e5+6;
const int mod=1e9+7;
const int lg=20;

int n,a[N],f[N],g[N],sf[N][lg+1],sg[N][lg+1],ans;

signed main(){
	scanf("%lld",&n);
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	for(int i=0;i<n;i++){
		sf[i][lg]=sg[i][lg]=0;
		for(int j=lg-1;~j;j--){
			sf[i][j]=sf[i][j+1],sg[i][j]=sg[i][j+1];
			int s=1<<j;
			if(i&s){
				sf[i][j]=(sf[i][j]+sf[i-s][j])%mod;
				sg[i][j]=(sg[i][j]+sg[i-s][j])%mod;
			}
		}
		f[i]=(a[i]*a[i]%mod+sg[i][0]*sg[i][0]%mod)%mod;
		g[i]=(f[i]*f[i]%mod+sf[i][0])%mod;
		for(int j=lg;~j;j--){
			sf[i][j]=(sf[i][j]+f[i]*f[i]%mod)%mod;
			sg[i][j]=(sg[i][j]+g[i])%mod;
		}
		ans=(ans+f[i]*g[i]%mod*i%mod)%mod;
	}
	printf("%lld",ans);
	return 0;
}

\(\text{T6}\) 考试

先把理论考试全部选择，然后就变为从 \(n\) 个 \(b_i-a_i\) 中至少选择 \(B\) 个的最大代价。显然通过贪心容易。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+6;

int n,A,B,a[N],b[N],ans;

inline bool cmp(int x,int y){return x>y;}

int main(){
	scanf("%d%d%d",&n,&A,&B);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i];
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),b[i]-=a[i];
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=B;i++)ans+=b[i];
	for(int i=B+1;i<=n&&n-i>=A;i++)if(b[i]>0)ans+=b[i];
	printf("%d",ans);
	return 0;
}

\(\text{T7}\) 背包

注意到 \(m\) 很小，考虑状压 dp。\(f_{i,S}\) 表示第 \(i\) 个背包，\(S\) 表示选择的物品集合。这样是 \(O(2^nn^2)\)。考虑优化。令 \(f_{S},g_{S}\)，其中 \(f\) 表示 \(S\) 状态下最少选择的背包数量，\(g\) 表示当前最后加入的这个背包最大还可以留下多少空间。此时 \(O(2^nn)\)，可以通过。

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+7;
const int M=100;

int n,m,a[M],w[M],f[N],g[N],S;

inline bool cmp(int x,int y){return x>y;}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&w[i]);
	sort(w+1,w+m+1,cmp);
	f[0]=1,g[0]=w[1];S=(1<<n)-1;
	for(int i=0;i<=S;i++){
		if(!f[i])continue;
		for(int j=1;j<=n;j++){
			int I=i|(1<<j-1);
			if(i==I)continue;
			if(g[i]>=a[j]){
				if(!f[I]||f[i]<f[I]){
					f[I]=f[i];
					g[I]=g[i]-a[j];
				}
				else if(f[I]==f[i])g[I]=max(g[I],(g[i]-a[j]));
			}
			else if(f[i]!=m){
				int k=f[i]+1;
				if(w[k]>=a[j]){
					if(f[I]>f[i]+1||!f[I]){
						f[I]=f[i]+1;
						g[I]=w[k]-a[j];
					}
					else if(f[I]==f[i]+1)g[I]=max(g[I],w[k]-a[j]);
				}
			}
		}
	}
	if(!f[S])puts("-1");
	else printf("%d",f[S]);
	return 0;
}

\(\text{T8}\) 移动细胞

\(f_{i,j}\) 表示第 \(i\) 列，第 \(i\) 列黑色细胞的上端放在第 \(j\) 行。

\[f_{i,j}=\min_{k=j-len_{i-1}+1}^{j-len_i+1} f_{i-1,k}+|l_i-j| \]

直接 dp \(O(n^2)\)，考虑单调队列优化即可。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+6;

int n,m,l[N],r[N],len[N],ans=INT_MAX,dp[2][N],q[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l[i],&r[i]);
		len[i]=r[i]-l[i]+1;
	}
	for(int i=1;i<=m;i++){
		int I=(i&1),head=1,tail=0;
		for(int j=1;j<len[i];j++){
			while(head<=tail&&dp[I^1][q[tail]]>dp[I^1][j])tail--;
			q[++tail]=j;
		}
		for(int j=1;j<=n-len[i]+1;j++){
			while(head<=tail&&q[head]<j-len[i-1]+1)head++;
			while(head<=tail&&dp[I^1][q[tail]]>dp[I^1][j+len[i]-1])tail--;
			q[++tail]=j+len[i]-1;
			dp[I][j]=min(dp[I^1][q[head]],dp[I^1][j+len[i]-1])+abs(l[i]-j); 
		}
		for(int j=n-len[i]+2;j<=n;j++)dp[I][j]=INT_MAX;
	}
	for(int i=1;i<=n-len[m]+1;i++)ans=min(ans,dp[m&1][i]);
	printf("%d",ans);
	return 0;
}

\(\text{T9}\)

\(\text{T1}\) 经典原题，不讲。

\(\text{T2}\) 雪猫头鹰

直接 dp。记录上个断点与前缀 min 的 pos 集合。使用 st表 \(O(n^2)\)。使用线段树 \(O(n\log n)\)。啥ds都不用 \(O(n)\)。然而我是大怨种。

#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1

const int N=5e5+4;
const int mod=1e9+7;

int n,a[N],tr[N<<2],f[N],mx,mxpos,pos[N<<2],g[N];

inline void pushup(int p){
	tr[p]=max(tr[ls],tr[rs]);
	if(tr[p]==tr[rs])pos[p]=pos[rs];
	if(tr[p]==tr[ls])pos[p]=pos[ls];
	return;
}

inline void build(int p,int l,int r){
	if(l==r){
		tr[p]=a[l],pos[p]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(p);
	return;
}

inline void query(int p,int l,int r,int s,int t){
	if(s>t)return;
	if(s<=l&&r<=t){
		if(mx<tr[p])mx=tr[p],mxpos=pos[p];
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(ls,l,mid,s,t);
	if(t>mid)query(rs,mid+1,r,s,t);
	return;
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);f[0]=1,g[0]=1;
	for(int i=1;i<=n;i++){
		mx=0,mxpos=0;
		query(1,1,n,1,i-1);
		if(mx>a[i])f[i]=g[mxpos-1];
		else f[i]=g[i-1];
		g[i]=g[i-1]+f[i];
		f[i]%=mod,g[i]%=mod;
//		f[i]=g[mxpos]
	}
	printf("%lld",f[n]);
	return 0;
}

\(\text{T3}\) 白头鹰

什么诈骗题。赛时就我过了就离谱。

使用打表容易发现当 \(k\) 至 \(a+1\) 后 \(f\) 恒为 \(1\)。然后 \(a\) 很小。于是做完了。

#include<bits/stdc++.h>
using namespace std;

#define int long long

int b,a,p;

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

inline int f(int x,int y){
	int v=a*b+x*y;
	if(v%p==0)return 1;
	else return (a*x+b*y)%p*qpow(v%p,p-2)%p;
}

inline int F(int a,int b,int p,int k){
	int lst=k;
	for(int i=k-1;i;i--){
		int x=f(lst,i);
		lst=x;
	}
	return lst;
}

signed main(){
	int k;
	cin>>a>>b>>p>>k;int mx=max(a,b);
	if(k>a)cout<<F(a,b,p,a+1);
	else cout<<F(a,b,p,k);
//	for(int i=1;i<=n;i++)
}

//signed main(){
//	srand(time(0));
//	
//	a=2,b=4,p=5;
//	int T;cin>>T;
//	for(int k=T;k;--k) cout<<F(a,b,p,k)<<" "<<k<<endl;
//	cout<<a<<" "<<b<<" "<<p<<"?\n";
////	solved();
//}

\(\text{T4}\) 鸵鸟

发现我们对于每个加号，可以使用后面的 \(i\) 来匹配这里的加号。\(f_{i,j}\) 表示前 \(i\) 个还有 \(j\) 个加号没有匹配。当前位若是减号则匹配之前的加号。

我的评价是：如果想到加号匹配，那么一眼丁真。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e3+4;
const int mod=1e9+7;

int n,dp[N][N],a[N],cnt;
char s[N];

signed main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)a[i]=s[i]=='+';
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		cnt+=a[i];
		for(int j=0;j<=cnt;j++){
			if(a[i])dp[i][j]=(dp[i][j]+dp[i-1][j-1]+j*dp[i-1][j]%mod)%mod;
			else dp[i][j]=(dp[i][j]+dp[i-1][j]*j%mod+dp[i-1][j+1]*(j+1)%mod*(j+1)%mod)%mod;
		}
	}
	printf("%lld",dp[n][0]);
	return 0;
}

\(\text{T5}\) 帝企

注意到最后肯定是每个极长的只含有两种字符的连续段，然后这个连续段的字符不可能移动到前一个或后一个连续段。如 ..PSS|SR..，那么每个极长段由于只包含两种字符（若三种则必然可以拆分或合并），直接冒泡排序。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+7;

int n,k,q[N],a[N],top,res,lst=1,m;
map<char,int>mps;
char s[N],ans[N];

signed main(){
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='R')a[i]=1;
		else if(s[i]=='S')a[i]=2;
		else a[i]=3;
	}
	for(int i=1;i<=n+1;i++){
		if(!mps[a[i]])res++;
		mps[a[i]]++;
		if(res==3){
			mps[a[i]]--,res--;top=0;int o=0;
			if(mps[1]&&mps[2])o=1;
			if(mps[2]&&mps[3])o=2;
			if(mps[3]&&mps[1])o=3;
			for(int j=lst;j<i;j++){
				if(top<k&&a[j]==o)q[++top]=j;
				else ans[++m]=s[j];
			}
			for(int j=1;j<=top;j++)ans[++m]=s[q[j]];
			for(int j=lst;j<i;j++)if(!(--mps[a[j]]))res--;
			if(!mps[a[i]])res++;
			mps[a[i]]++;lst=i;
		}
	}
	for(int i=lst;i<=n;i++)ans[i]=s[i];
	printf("%s",ans+1);
	return 0;
}

\(\text{T1}\) 糖果

发现肯定是见到一对可以消除的就消除。显然消除顺序对于答案无关。所以顺着跑一遍，将能删除的直接删除，或者与栈顶的数配对，若配对失败则也扔到栈中。最后在栈中元素首尾配对来计算反向配对的答案。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+6;

int n,m,a[N],ans,top,stk[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(top&&(stk[top]==a[i]||stk[top]+a[i]==m))top--,ans++;
		else stk[++top]=a[i];
	}
	for(int i=1;i<=top;i++){
		if(stk[i]==stk[top-i+1]||stk[i]+stk[top-i+1]==m)ans++;
		else break;
	}
	printf("%d",ans);
	return 0;
}

\(\text{T2}\) 铜川

考虑给定序列怎么求有多少子区间和 \(≡0\pmod k\)。

记录前缀和为 \([0,k-1]\) 的每种前缀出现次数 \(c\)，那么答案是 \(\binom{c}{2}\)。即对于任意两个同余的前缀，其区间必然整除 \(k\)。

\(f_{i,j,t}\) 表示当前计算前缀和为 \(i\)，放了 \(j\) 个位置，好序列个数为 \(t\)的方案数。

\[f_{i,j,t}\times \binom{n-j}{x}\to f_{i+1,j+x,t+\binom{x}2} \]

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=66;
const int mod=998244353;

int n,k,tt,fac[N],ifac[N],f[N][N][N*N];

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

inline void init(int n){
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	return;
}

inline int C(int n,int m){
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

signed main(){
	init(N-1);
	scanf("%lld%lld%lld",&n,&k,&tt);
	for(int i=0;i<=n;i++)f[0][i][i*(i+1)>>1]=C(n,i);
	for(int i=1;i<k;i++){
		for(int j=0;j<=n;j++){
			for(int t=0;t<=((j+1)*j>>1);t++){
				for(int jj=0;jj<=j;jj++){
					int o=((j-jj)*(j-jj-1)>>1);
					if(t<o)continue;
					f[i][j][t]=(f[i][j][t]+f[i-1][jj][t-o]*C(n-jj,j-jj)%mod)%mod;
				}
			}
		}
	}
	printf("%lld",f[k-1][n][tt]);
	return 0;
}

\(\text{T3}\) 山峰

发现考虑确定最大值的位置不好做。发现最小值的位置唯一，一定在最左或最右。然后考虑将当前的 min 移到一方端点，然后删除 min，因为对答案不可能再产生影响。如此做 \(n\) 次，使用线段树维护当前第 \(i\) 位到第 \(1\) 位与第 \(n\) 位之间还剩下多少数。

#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1
#define int long long

const int N=2e5+6;

int n,lsh[N],a[N],ans,tr[N<<2],pos[N];

inline void pushup(int p){
	tr[p]=tr[ls]+tr[rs];
	return;
}

inline void update(int p,int l,int r,int ps,int val){
	if(l==r){
		tr[p]+=val;
		return;
	}
	int mid=(l+r)>>1;
	if(ps<=mid)update(ls,l,mid,ps,val);
	else update(rs,mid+1,r,ps,val);
	pushup(p);
	return;
}

inline int query(int p,int l,int r,int s,int t){
	if(s>t)return 0;
	if(s<=l&&r<=t)return tr[p];
	int mid=(l+r)>>1,res=0;
	if(s<=mid)res+=query(ls,l,mid,s,t);
	if(t>mid)res+=query(rs,mid+1,r,s,t);
	return res;
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+n+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+n+1,a[i])-lsh;
	for(int i=1;i<=n;i++)update(1,1,n,i,1),pos[a[i]]=i;
	for(int i=1;i<=n;i++){
		int j=pos[i];
		ans+=min(query(1,1,n,1,j-1),query(1,1,n,j+1,n));
		update(1,1,n,j,-1);
	}
	printf("%lld",ans);
	return 0;
}

\(\text{T4}\) 瓦片

注意到 \(k\le 5\)。于是分类讨论。没了。

事实上可以发现答案是关于 \(n,m\) 的多项式，于是暴力跑 \(n,m\) 较小的情况，搜出来后插值。

我的评价：厂。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=998244353;

int n,m,k;

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

inline int C(int n,int m){
	int res=1;
	for(int i=1;i<=m;i++)res=res*(n-i+1)%mod;
	for(int i=1;i<=m;i++)res=res*qpow(i,mod-2)%mod;
	return res;
}

inline int sum(vector<int>vec){
	int ans=0;
	for(auto i:vec)ans=(ans+i)%mod;
	return ans;
}

inline void sub1(){
	puts("1");
	return;
}

inline void sub2(){
	printf("%lld",(n+m-2)%mod);
	return;
}

inline void sub3(){
	int ans=0;
	ans=(C(n-1,2)+C(m-1,2))%mod;
	ans=(ans+(n-1)*(m-1)%mod*4%mod)%mod;
	printf("%lld",ans);
	return;
}

inline void sub4(){
	int ans=0,x=0,y=0;
	ans=(n-1)*(m-1)%mod+(C(n-1,3)+C(m-1,3))%mod;
	x=(C(n-1,2)*(m-1)%mod*3%mod+C(m-1,2)*(n-1)%mod*3%mod);
	y=(n-1)*C(m-1,2)%mod*4%mod+(m-1)*C(n-1,2)%mod*4%mod;y=y*2%mod;y=(y+ans)%mod;
	printf("%lld",(x+y)%mod);
	return;
}

inline void sub5(){
	vector<int>ly={
		C(n-1,2)*C(m-1,2)%mod*2%mod,C(n-1,4),C(m-1,4),
		C(n-1,3)*(m-1)%mod*4%mod,C(m-1,3)*(n-1)%mod*4%mod,
		C(n-1,3)*(m-1)%mod*6%mod,C(m-1,3)*(n-1)%mod*6%mod,
		C(n-1,2)*C(m-1,2)%mod*3%mod*2%mod,C(m-1,2)*C(n-1,2)%mod*3%mod*2%mod,
		C(n-1,2)*(m-1)%mod*3%mod,C(m-1,2)*(n-1)%mod*3%mod,
		C(n-1,2)*C(m-1,2)%mod*3%mod,C(m-1,2)*C(n-1,2)%mod*3%mod,
		C(n-1,2)*C(m-1,2)%mod*8%mod,C(m-1,2)*C(n-1,2)%mod*8%mod,
		C(n-1,3)*(m-1)%mod*4%mod,C(m-1,3)*(n-1)%mod*4%mod,
		C(n-1,3)*(m-1)%mod*4%mod,C(m-1,3)*(n-1)%mod*4%mod,
		C(n-1,2)*C(m-1,2)%mod*6%mod,C(m-1,2)*C(n-1,2)%mod*6%mod,
		C(n-1,3)*(m-1)%mod*2%mod,C(m-1,3)*(n-1)%mod*2%mod,
		C(n-1,3)*(m-1)%mod*6%mod,C(m-1,3)*(n-1)%mod*6%mod,
		C(n-1,2)*(m-1)%mod*4%mod,C(m-1,2)*(n-1)%mod*4%mod,
		C(n-1,2)*C(m-1,2)%mod*8%mod,C(m-1,2)*C(n-1,2)%mod*8%mod
	};
	printf("%lld",sum(ly));
	return;
}

signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	if(k==1)sub1();
	else if(k==2)sub2();
	else if(k==3)sub3();
	else if(k==4)sub4();
	else sub5();
	return 0;
}

\(\text{T5}\) 聊天

首先将区间分为若干个连通块， 对于每个联通块内部必然有 \(r_i\ge l_{i+1}\) 成立。然后考虑让相邻两个连通块之间损失的代价最小，令当前连通块右端点 \(R\) 与下一个连通块左端点 \(L'\) 尽量接近。

按照右端点排序，对于当前的 \(r_{i-1}\ge l_{i}\) 则将区间加入当前连通块；若 \(r_{i-1}<l_{i}\) 则将区间 \(i\) 当作新的连通块。注意到有情况 \(l_j<l_i,j>i\) 时，区间 \(j\) 完全覆盖 \(i\)，那么区间 \(i\) 没有任何作用。

那么先按照 \(l\) 排序后记录每个区间是否大于之前的 \(\max r\)，若不是则必然被之前的某个区间所包含，于是打个标记。

那么上述过程可以通过 deque 实现。加入当前连通块时或者此连通块作为新的连通块的起点则扔到后面，否则扔到最前（即被覆盖的区间）。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e5+6;

int n,lst,mx,ans[N],sum;
struct node{
	int l,r,id,mx;
}q[N];
deque<node>dq;

inline bool cmp1(node a,node b){
	return a.l!=b.l?a.l<b.l:a.r>b.r;
}
inline bool cmp2(node a,node b){
	return a.r!=b.r?a.r<b.r:a.l<b.l;
}

signed main(){
	scanf("%lld%lld",&n,&lst);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+n+1,cmp1);
	for(int i=1;i<=n;i++)if(q[i].r>mx)mx=q[i].r,q[i].mx=1;
	sort(q+1,q+n+1,cmp2);dq.push_back(q[1]);
	for(int i=2;i<=n;i++){
		if(dq.back().r<q[i].l&&!q[i].mx)dq.push_front(q[i]);
		else dq.push_back(q[i]);
	}
	for(int i=1;i<=n;i++){
		node tmp=dq.front();dq.pop_front();
		ans[i]=tmp.id;
		sum+=max(lst-tmp.l,0ll),lst=tmp.r;
	}
	printf("%lld\n",sum);
	for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
	return 0;
}

10.3省选组训练

\(\text{T1}\) Z

当 \(n\) 为偶数构造 \(2\times n,n\)，当 \(n\) 为奇数，枚举质数 \(\min p\) 满足 \(p\) 不是 \(n\) 的因子则构造 \(pn,(p-1)n\)。

#include<bits/stdc++.h>
using namespace std;

#define int long long

int p[30]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97},T,n;

signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		if(n&1){int i;
			for(i=1;i<25;i++)if(n%p[i])break;
			printf("%lld %lld\n",n*p[i],(p[i]-1)*n);
		}
		else printf("%lld %lld\n",n*2,n);
	}
	return 0;
}

国庆联赛模拟赛DAY4

\(\text{T1}\) 区间

同 CF1285E Delete a Segment。

所有区间按照端点离散化。

考虑对于一段新的区间 \([l,r]\)，而此区间属于原来的区间 \([L,R]\)。若 \([l,r]\) 上没有其他的区间覆盖则会贡献答案至区间 \([L,R]\)。注意若 \(l=L\) 或 \(r=R\) 时无贡献。所以用 set 扫描线即可。

#include<bits/stdc++.h>
using namespace std;

const int N=4e5+6;

int T,n,m,ans,cnt[N],mx;
pair<int,int>q[N];
set<int>st;

inline void solve(){
	scanf("%d",&n);ans=m=0;st.clear();mx=-1;
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		q[++m]=make_pair(l,-i);
		q[++m]=make_pair(r,i);
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++){
		int j=q[i].second;
		if(j>0){
			if(st.size()==1)cnt[j]--;
			st.erase(j);
		}
		else{
			if(st.empty())cnt[-j]--;
			st.insert(-j);
		}
		if(st.empty())ans++;
		else if(st.size()==1)cnt[*st.begin()]++;
	}
	for(int i=1;i<=n;i++)mx=max(mx,cnt[i]),cnt[i]=0;
	printf("%d\n",mx+ans);
	return;
}

int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

\(\text{T2}\) 打印机

栈是循环的。否则必定不优。那么可能的栈的类型共 \(6\) 种（ABC,ABC,BAC,BCA,CAB,CBA）。设 \(f_{i,j,t}\) 表示当前第 \(i\) 位，\(j\) 为栈的大小，\(t\) 表示栈的类型。

dp 时根据栈内元素个数分类转移。

#include<bits/stdc++.h>
using namespace std;

const int mps[8][5]={{0,0,0,0},{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}};
const int N=5e3+4;
const int inf=1e9;

int n,dp[2][N][8],a[N],ans=inf;
char s[N];

inline void Min(int &x,int y){
	x=min(x,y);
	return;
} 

int main(){
	scanf("%s",s+1);int len=strlen(s+1);
	for(int i=1;i<=len;i++)if(s[i]!=s[i-1])a[++n]=s[i]-'A'+1;
	memset(dp,0x3f,sizeof(dp));
	dp[1][1][a[1]*2-1]=1;
	for(int i=2;i<=n;i++){
		int p=i&1,q=(i-1)&1;
		for(int j=0;j<=i;j++)for(int k=1;k<=6;k++)dp[p][j][k]=inf;
		for(int j=0;j<=i;j++){
			for(int k=1;k<=6;k++){
//				cout<<k<<" "<<a[i]<<" "<<i<<" "<<(j-1)%3+1<<"?\n";
				if(a[i]!=mps[k][(j-1)%3+1])continue;
				if(j==1){
					if(!(k&1))continue;
					Min(dp[p][j][k],dp[q][j-1][1]+1);
					Min(dp[p][j][k],min(dp[q][j+1][k],dp[q][j+2][k]));
					Min(dp[p][j][k],min(dp[q][j+1][k+1],dp[q][j+2][k+1]));
				}
				else if(j==2){
					Min(dp[p][j][k],min(dp[q][j+1][k],dp[q][j+2][k]));
					if(k&1)Min(dp[p][j][k],dp[q][j-1][k]+1);
					else Min(dp[p][j][k],dp[q][j-1][k-1]+1);
				}
				else{
					Min(dp[p][j][k],min(dp[q][j+1][k],dp[q][j+2][k]));
					Min(dp[p][j][k],dp[q][j-1][k]+1);
				}
//				cout<<dp[p][j][k]<<" ";
			}
		}
	}
	for(int i=0;i<=n;i++)for(int k=1;k<=6;k++)ans=min(ans,dp[n&1][i][k]);
	printf("%d",ans*2+len);
	return 0;
}

\(\text{T3}\) 餐厅

同 CF1369E DeadLee。

考虑每个人都吃了两道菜。然后如果当前对于一个人还有剩下的那他肯定放哪里都没问题。所以扔到后面。

对于剩下的在放到最前面构成一个新的问题。注意此时要将之前扔到后面去的人吃掉的菜吐出来（bushi。如此做子问题即可。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+6;

int n,m,a[N],head[N],tot,top,st[N];
bool vis[N];
queue<int>q;

struct edge{
	int to,nxt,w;
}e[N<<1];

inline void addedge(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].w=w;
	head[u]=tot;
	return;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y,i),addedge(y,x,i);
		a[x]--,a[y]--;
	}
	for(int i=1;i<=n;i++)if(a[i]>=0)q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(vis[e[i].w])continue;
			vis[e[i].w]=true;
			st[++top]=e[i].w;
			a[v]++;
			if(!a[v])q.push(v);
		}
	}
	if(top<m)puts("DEAD");
	else{
		puts("ALIVE");
		while(top)printf("%d ",st[top--]);
	}
	return 0;
}

\(\text{T4}\) 战略游戏

同 P5332 [JSOI2019]精准预测。

一眼发现是 2-sat，发现暴力建图不可接受，考虑对于每个人只保留判定时间。然后图本身就是个 DAG，套路地使用 bitset 优化。

对于空间的限制，使用分块来计算结果。块长取 \(10^4\) 时优秀。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+6;
const int inf=1e9;
const int block=1e4;
const int M=N*3;

int nowt,n,k,ed[N],vis[M],head[M],ans[N],tot;
bitset<block>S,bs[M];
struct node{int op,t,x,y;}q[N];
map<int,int>mps[N];
struct edge{
	int to,nxt;
}e[M<<1];

inline void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	return;
}

inline void add(int u,int v,int op){
	addedge(u+op,v),addedge(v+1,u+!op);
	return;
}

inline void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		dfs(v);
		bs[u]|=bs[v];
	}
	return;
}

int main(){
	scanf("%d%d%d",&nowt,&n,&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d%d",&q[i].op,&q[i].t,&q[i].x,&q[i].y);
		mps[q[i].x][q[i].t]=i*2;
	}
	for(int i=1;i<=n;i++)ed[i]=mps[i][nowt+1]=(k+i)*2;
	for(int i=1;i<=k;i++){
		int u=mps[q[i].x][q[i].t],v=(*mps[q[i].y].lower_bound(q[i].t+!q[i].op)).second;
		add(u,v,q[i].op);
	}
	for(int i=1;i<=n;i++){
		int lst=0;
		for(auto tmp:mps[i]){
			int v=tmp.second;
			if(lst)add(lst,v,0);
			lst=v;
		}
	}
	for(int l=1,r;l<=n;l+=block){
		r=min(l+block-1,n);S.reset();
		for(int i=2;i<=(n+k)*2+1;i++)vis[i]=0,bs[i].reset();
		for(int i=l;i<=r;i++)bs[ed[i]][i-l]=1;
		for(int i=2;i<=(n+k)*2+1;i++)dfs(i);
		for(int i=l;i<=r;i++)if(bs[ed[i]+1][i-l])ans[i]=-inf,S[i-l]=1;
		for(int i=1;i<=n;i++)ans[i]+=(r-l+1)-(S|bs[ed[i]+1]).count();
	}
	for(int i=1;i<=n;i++)printf("%d ",max(ans[i]-1,0));
	return 0;
}

国庆联赛模拟赛DAY5

\(\text{T1}\) Box 不讲。

\(\text{T2}\) Replace

记 \(f_i\) 为考虑前 \(i\) 个数，第 \(i\) 个数不变的最小操作次数。

从 \(j(j>i)\) 能转移到 \(i\) 的充要条件是 \(a_i,a_j\) 之间的 \(b\)
数量 \(\ge j-i-1\)。

使用线段树维护。

#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1

const int N=5e5+6;
const int inf=0x3f3f3f3f;

int n,m,a[N],b[N],pos[N],tr[N<<3],f[N],g[N];

inline void pushup(int p){
	tr[p]=min(tr[ls],tr[rs]);
	return;
}

inline void update(int p,int l,int r,int ps,int val){
	if(l==r){
		tr[p]=min(tr[p],val);
		return;
	}
	int mid=(l+r)>>1;
	if(ps<=mid)update(ls,l,mid,ps,val);
	else update(rs,mid+1,r,ps,val);
	pushup(p);
	return;
}

inline int query(int p,int l,int r,int s,int t){
	if(s<=l&&r<=t)return tr[p];
	int mid=(l+r)>>1,res=inf;
	if(s<=mid)res=min(res,query(ls,l,mid,s,t));
	if(t>mid)res=min(res,query(rs,mid+1,r,s,t));
	return res;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&b[i]);
	sort(b+1,b+m+1);
	a[n+1]=2*n+m-1,b[m+1]=inf;
	for(int i=0;i<=n;i++)pos[i]=lower_bound(b+1,b+m+2,a[i])-b-1;pos[n+1]=m;
	memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g)),memset(tr,0x3f,sizeof(tr));
	f[0]=0;
	update(1,-n,m,1,0);
	for(int i=1;i<=n;i++){
		f[i]=min(f[i],g[i-1]);
		g[i]=query(1,-n,m,-n,pos[i+1]-i+1)+i;
		if(a[i]>a[i-1])f[i]=min(f[i],f[i-1]);
		update(1,-n,m,1+pos[i]-i,f[i]-i);
	}
	if(min(f[n],g[n])==inf)puts("-1");
	else printf("%d",min(f[n],g[n]));
	return 0;
}

\(\text{T3}\) 苦难交易

同 CF1713E Cross Swapping。

从小到大枚举，对于 \(a_{x,y}\) 与 \(a_{y,x}\) 之间的关系容易推出，使用带权并查集维护。

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+4;

int T,n,a[N][N],fa[N<<1];

inline int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}

inline void merge(int x,int y){
	x=find(x),y=find(y);
	if(abs(x-y)%n)fa[x]=y;
	return;
}

inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);	
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
		if(a[i][j]<a[j][i])merge(i,j),merge(i+n,j+n);
		else if(a[i][j]>a[j][i])merge(i,j+n),merge(i+n,j);
	}
	for(int i=1;i<=n;i++){
		if(find(i)>n)continue;
		for(int j=1;j<=n;j++)swap(a[i][j],a[j][i]);	
	}
	for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)printf("%d ",a[i][j]);
	return;
}

int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

\(\text{T4}\) 线性代树

同 P3340 [ZJOI2014]星系调查。

考虑直接大力推式子。式子很容易推，最终结果是 \(S=\dfrac{C+A+\sqrt{(A-C)^2+B^2}}{2}\)，那么维护 \(\sum x,\sum y,\sum x^2,\sum y^2,\sum xy\) 即可。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+6;

int n,m,Q,S,T,X[N],Y[N],dep[N],sx[N],sy[N],sxx[N],syy[N],xy[N],top[N],tot,head[N],sz[N],son[N],fa[N];
double X_,Y_,XX,YY,XY,Dis;

struct edge{
	int to,nxt;
}e[N<<1];

inline void addedge(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	return;
}

inline void dfs1(int u,int faa){
//	cout<<u<<" "<<faa<<"?\n";
	sz[u]=1,fa[u]=faa,dep[u]=dep[faa]+1;
	sx[u]=sx[faa]+X[u],sxx[u]=sxx[faa]+X[u]*X[u];
	sy[u]=sy[faa]+Y[u],syy[u]=syy[faa]+Y[u]*Y[u];
	xy[u]=xy[faa]+X[u]*Y[u];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==faa||sz[v]){
			if(v&&v!=faa)S=u,T=v;
			continue;
		}
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
	return;
}

inline void dfs2(int u,int tp){
	top[u]=tp;
	if(son[u])dfs2(son[u],tp);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(top[v]||v==fa[u]||v==son[u]||(u==S&&v==T)||(u==T&&v==S))continue;
		dfs2(v,v);
	}
	return;
}

inline int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}

inline double dis(int u,int v){
	int o=lca(u,v);
	return dep[u]+dep[v]-dep[o]*2.0+1;
}

inline void query(int u,int v){
	int o=lca(u,v);
	X_+=sx[u]+sx[v]-sx[o]*2+X[o],XX+=sxx[u]+sxx[v]-2*sxx[o]+X[o]*X[o];
	Y_+=sy[u]+sy[v]-sy[o]*2+Y[o],YY+=syy[u]+syy[v]-2*syy[o]+Y[o]*Y[o];
	XY+=xy[u]+xy[v]-xy[o]*2+X[o]*Y[o];
	Dis+=dis(u,v);
	return;
}

inline double F(){
	double D=1.0/Dis,u=XX-D*X_*X_,v=YY-D*Y_*Y_,w=XY-D*X_*Y_;
	double res=(u+v)/2.0-sqrt(w*w+(u-v)/4.0*(u-v));
	X_=XX=Y_=YY=XY=Dis=0;
	return res;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&X[i],&Y[i]);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v),addedge(v,u);
	}
	dfs1(1,0);
//	puts("!");
	dfs2(1,1);
	scanf("%d",&Q);
	while(Q--){
		int u,v,o;double ans;
		scanf("%d%d",&u,&v),o=lca(u,v);
		query(u,v);
		ans=F();
		if(n==m){
			query(u,S),query(v,T);
			ans=min(ans,F());
			query(u,T),query(v,S);
			ans=min(ans,F());
		}
		printf("%.6lf\n",ans);
	}
	return 0;
}

国庆联赛模拟赛DAY6

咕了。

标签：return,int,res,国庆,ans,inline,合集,集训,mod
From： https://www.cnblogs.com/trsins/p/17970749

相关文章

  • 位运算合集
    位运算合集（&、|、^、~、>>、<<）​ 在学习和研究源码过程中，经常遇到使用位运算的逻辑，代码看着简洁，执行效率也高；特此总结和记录位运算的使用方法。1.位运算概述从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫......
  • [国家集训队] 矩阵乘法 整体二分
    [国家集训队]矩阵乘法题目描述给你一个\(n\timesn\)的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第\(k\)小数。输入格式第一行有两个整数，分别表示矩阵大小\(n\)和询问组数\(q\)。第\(2\)到第\((n+1)\)行，每行\(n\)个整数，表示这个矩阵。第\((i+1)\)行......
  • 即时通讯技术文集（第32期）：IM开发综合技术合集(Part5) [共12篇]
    为了更好地分类阅读52im.net总计1000多篇精编文章，我将在每周三推送新的一期技术文集，本次是第32 期。[- 1 -] IM开发干货分享：如何优雅的实现大量离线消息的可靠投递[链接] http://www.52im.net/thread-3069-1-1.html[摘要] 本文作者将以自已IM开发过程中的真实总结，分......
  • P6667 [清华集训2016] 如何优雅地求和
    P6667[清华集训2016]如何优雅地求和Problem给定最高次幂为\(x^{m}\)的多项式函数\(g(x)\)和整数\(n,q\)，其中\(g\)以点值形式给出，即给定\(g(0),g(1),\dots,g(m)\)。求：\[\begin{aligned}Q(g,n,q)=\sum\limits_{k=0}^{n}g(k)\binom{n}{k}q^{k}(1-q)^{n-k......
  • 【专题】2023中国电商营销趋势及增长策略研究报告PDF合集分享（附原数据表）
    全球电商市场在疫情后持续发展，其中，中国市场占据了半壁江山，对全球电商格局产生了重大影响。在中国，三至五线城市的城镇人口众多，约占总城镇人口的65%。随着移动互联网的普及，这些城市构成了纵深市场，其用户规模正在稳步增长。据数据显示，近7.2亿的目标用户占据了整个市场的52%，成为移动互......
  • 【专题】2023年B2B医疗企业营销转型白皮书报告PDF合集分享（附原数据表）
    随着医药企业营销数字化转型的深入，将面临更多的内外数据和数据源。这些问题导致数据断层，难以有效利用，使企业忙于处理数据问题，无暇关注深层业务需求。因此，尽管高呼“数据驱动”，却难以提供切实有效的解决方案和洞察。医疗企业数字化营销的挑战医疗企业在数字化营销过程中面临多方面的......
  • 【专题】2023双碳背景下新型电力系统的应用创新-电网洞察白皮书报告PDF合集分享（附原数
    为实现碳达峰、碳中和目标，构建清洁低碳、安全高效的能源体系成为首要任务。清洁电力作为能源转型的关键，对于保障中国能源安全具有重要意义。为适应新能源的大规模接入，新型电力系统应运而生，以确保电力系统的安全可靠运行。为确保电力系统的稳定运行，提升其灵活性至关重要，这需要各环......
  • 【专题】全球医疗器械报告 2023报告PDF合集分享（附原数据表）
    在全球范围内，医疗器械行业的检验中心和诊断解决方案、牙科、医疗辅助设备等细分领域的企业表现尤为出色。这些企业在新冠疫情期间或是受益于有利的市场环境，或是凭借创新主导的高增长市场策略取得了显著的优势。相反，手术器械细分市场在疫情期间受到了一定的冲击，由于手术量减少，医疗......
  • 寒假集训Day1
    寒假集训Day1主要了解到了两个比较有意义的东西，记录如下质数筛法埃氏筛从二开始，二是一个质数，那么二的倍数就是合数，三同理，利用这样的思想可以把所有质数的倍数做上标记欧拉筛埃氏筛有一个问题，就是同一个合数可能被反复筛选，比如6既是2的倍数又是3的倍数，这样它就会被筛选两遍。......
  • 【专题】保险行业数字化洞察白皮书报告PDF合集分享（附原数据表）
    报告链接：https://tecdat.cn/?p=33203原文出处：拓端数据部落公众号近年来，"养老"、"三胎政策"、"医疗成本"等一系列备受关注的民生话题，使得保险服务备受瞩目，并逐渐渗透到每个人的生活中。自2020年以来，由于多种因素的影响，人们对健康的意识不断提高，这正在重新塑造中国消费者对保险的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99