专栏文章

10.19 一中S模拟2

qqdl66666666
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink8csn
此快照首次捕获于
2025/12/02 03:46
3 个月前
此快照最后确认于
2025/12/02 03:46
3 个月前
查看原文

T1

题意

给定 kk 个点，选出互不相等的四个点 a,b,c,da,b,c,d，使得以 aa 为圆心，bb 为圆周上的点的圆 O1O_{1}，和以 cc 为圆心，dd 为圆周上的点的圆 O2O_{2} 呈真包含关系，统计方案数。

做法

k<=40k<=40 枚举每种点的组合，如何 check?
令 r1,r2r_{1},r_{2} 分别为 O1,O2O_{1},O_{2} 的半径，dd 为两圆圆心的距离，若 r1>r2+dr_{1} > r_{2} + d，则满足限制。
x\sqrt x 有精度误差，两种解决思路：
1.转化为整数比较。
2.卡精度 eps=−10−8eps = -10^{-8}
CPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 1010;
const double eps = -1e-8;
template<typename TY>
inline void read(TY &s){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	s = x * f;
}
int n,m,k;
ll ans;
pair<ll,ll> z[N];
double dis(ll x1,ll y1,ll x2,ll y2){
	return sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
}
bool check(ll a,ll b,ll c,ll d){
	if(a == b || a == c || a==d || b == c || b == d || c == d) return false;
	double l = z[a].se, r = m - z[a].se, u = z[a].fi, downs = n - z[a].fi;
	double minn = min({l,r,u,downs});
	double r1 = dis(z[a].fi,z[a].se,z[b].fi,z[b].se);
	if(r1 > minn) return false;
	l = z[c].se, r = m - z[c].se, u = z[c].fi, downs = n - z[c].fi;
	minn = min({l,r,u,downs});
	double r2 = dis(z[c].fi,z[c].se,z[d].fi,z[d].se);
	if(r2 > minn) return false;
	double D = dis(z[a].fi,z[a].se,z[c].fi,z[c].se);
	if(D + r2 - r1 >= eps) return false;
	return true;
}
int main(){
	freopen("circle.in","r",stdin);
	freopen("circle.out","w",stdout);
	read(k); read(n); read(m);
	for(int i=1;i<=k;i++){
		read(z[i].fi); read(z[i].se);
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			if(i != j)
			for(int u=1;u<=k;u++){
				if(u != j && u != i)
				for(int v=1;v<=k;v++){
					if(v == j || v == i || v == u) continue;
					if(check(i,j,u,v)){
//						cerr << i << " " << j << " " << u << " " << v<<"\n"; 
						ans++;
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}

T2

题意

kk 个位置，nn 个数。11 随意放，从 22 开始必须放在与上一个放的数的相邻位置最上层。最后得到的序列每个位置的颜色为（若没有为 00，若有则是最上层的数），问不同序列的方案数。 题目

找性质

正难则反，倒着考虑。
不难发现 nn 最后一定在序列中，因为他是最后放的；n−1n-1 也一定在序列中，因为他只能放在 nn 的旁边；n−3n-3 可以放在 nn 下面被覆盖，也可以放在 n−1n-1 旁边显露出来……以此类推，我们发现最后形成的序列一定连续。
设 f(i,j)f(i,j) 表示到了选到第 ii 大的点，形成了长度为 jj 的序列（也就是 jj 个数需要在最终序列出现），钦定当前数出现的序列方案数。
注意到因为从小到大考虑，所以当前出现的数一定在最左或最右边。考虑更新其它数，如果这个数填补左端点的左边，则可以更新 f((i+1,i+3,...,i+2∗k+1),j+1)f((i+1,i+3,...,i+2*k+1),j+1)；如果这个数填补右端点的右边，则更新 f((i+j,i+j+2,...,i+j+2∗k),j+1)f((i+j,i+j+2,...,i+j+2*k),j+1)。
所以转移方程已出 f((i−1,...,i−1−2×k),j−1)−>f(i,j),f((i−j+1,...,i−j+1−2×k),j−1)−>f(i,j)f((i-1,...,i-1-2\times k),j-1) -> f(i,j),f((i-j+1,...,i-j+1-2\times k),j-1) -> f(i,j)。这样做是 O(n3)O(n^3) 的，发现可以用前缀和记录 前面 f(2×k,j)f(2\times k,j) 的总方案数，复杂度 O(n2)O(n^2)。
答案统计为∑i=2n∑j=2kf(i,j)×(k−j+1)\sum_{i=2}^{n}\sum_{j=2}^{k}f(i,j)\times (k - j + 1)，因为我们只考虑了每个序列的内部关系，没有考虑序列在 kk 中的位置方案，这里是统计最小的出现的数是 ii，有 jj 个数出现的总方案数。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3 + 10;
const int MOD = 1e9 + 7;
template<typename TY>
inline void read(TY &s){
	ll x = 0,f = 1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	s = x * f;
}
ll f[N][N],sum[N][N];
int n,k;
int main(){
//	freopen("sequence.in","r",stdin);
//	freopen("sequence.out","w",stdout);
	read(n); read(k);
	f[1][1] = 1; f[2][2] = 2;
	for(int i=1;i<=n;i++){
		if(i&1) sum[i][1] = 1;
		else sum[i][2] = 2;	
	} 
	for(int i=3;i<=n;i++){
		for(int j=3;j<=k;j++){
			f[i][j] = sum[i-1][j-1];
			if(j < i + 1) f[i][j] = (f[i][j] + sum[i-j+1][j-1]) % MOD;
			sum[i][j] = (f[i][j] + sum[i-2][j]) % MOD;
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=2;j<=k;j++){
//			sum[i][j] = (sum[i][j] + sum[i][j-2]) % MOD;
//			f[i][j] = (f[i][j] + sum[i][j]) % MOD; 
//			sum[i+1][j+1] = (sum[i+1][j+1] + f[i][j]) % MOD; 
//			if(i + j <= n) sum[i+j][j+1] = (sum[i+j][j+1] + f[i][j]) % MOD; 
//		}
//	}
	ll ans = 0;
	for(int i=2;i<=n;i++){
		for(int j=2;j<=k;j++){
//			cerr << f[i][j] << " "; 
			ans += (f[i][j] * (k - j + 1)) % MOD;
			ans %= MOD;
		}
//		cerr << "\n";
	}
	cout << ans;
	return 0;
}

T3

题目链接

题意

给定 nn 个顶点的多边形，n−3n-3 条对角线形成一个三角剖分（顾名思义 n−3n-3 条对角线将多边形分成了一个个三角形）。 有两种操作：
1.删除一条对角线，并添加新的一条（算一次操作）。
2.问此时将所有对角线的一端移到 xx 上的最小操作次数和其方案数。
注意三角剖分和操作 22 时不能让当前的对角线有交。

突破点

从 sub2sub2 中受到启发，发现最小操作次数就是端点不在 xx 上的对角线条数。
简单证明一下：对于一条对角线 (p,q)(p,q)，它存在于两个三角形中，所对的点分别记为 x,rx,r。我们可以删除 (p,q)(p,q)，添加 x,rx,r 使得对角线的一端变为 xx，而我们每次可以选择不被其他对角线包含的一条操作。至于一端在 xx 上的对角线，我们不进行操作显然更优。

第一步转化

经过最小操作次数的启发，我们可以发现操作的一般顺序。
我们将所有对角线看作不经过 xx 的弧的形式，则：
  1. 任意两条弧要么不交要么包含（根据三角剖分的性质）。
  2. 每次一定选择一条极大的弧（不被其他弧包含的弧），满足操作中对角线无交。
  3. 一条弧至多直接包含两条弧（无用）。

第二步转化

将所有弧看作点，将弧与弧之间的包含关系映射为树上的父子关系（大弧为父亲），就得到了一个二叉树形结构。 结合我们上一步的操作顺序，我们就是每次处理一个父亲节点，然后将它的儿子加入到待处理集合中。这样我们的操作方案数就是一个树上拓扑序数，因为弧与弧之间可能无交，也就是可能有很多棵树形成的森林，操作方案数为森林拓扑序数量。
有个经典结论，森林拓扑序数量为 n!∏szi\frac{n!}{\prod sz_{i}}。
对于这个结论，我的理解是这样的：
首先将所有点排列起来，共 n!n! 种。对于每一个点，我们要求它出现在它的子树中的点的前面，其中这个点出现在子树序列最前面的概率是 1szi\frac{1}{sz_{i}}，要求每个点出现在各自子树序列的前面，所以总拓扑序数就是 n!∏szi\frac{n!}{\prod sz_{i}}。
nn 为节点数，szisz_{i} 为以 ii 为根的子树大小；而这里 nn 为不经过 xx 的对角线的数量；对于一个点 pp，szpsz_{p} 就是这条弧所包含的小弧数量（包括自己）。
设弧为 (l,r)(l,r)，则包含数量就是 (r−l−1)(r - l - 1)，只需计算所有不经过 xx 的弧的弧长-1的乘积。
所以我们记录每个点上连接的对角线条数 ind[i]ind[i]，最小操作次数就是 n−3−ind[x]n - 3 - ind[x]，方案数就是不经过 xx 的弧的条数除以所有弧的包含总数和。

第三步优化

考虑优化复杂度，用树状数组维护 mul[i]mul[i]，表示不经过 ii 号点的对角线/弧包含总数和（也就是 ∏szi\prod sz_{i} 这部分）。维护对角线就是维护对角线所对的两条弧上的点：具体的，添加一条对角线就是进行区间乘，删除对角线就是区间乘以逆元。
区间修单点查利用差分思想转为单点修前缀查，[l,r][l,r] 的区间乘就是 ll 上乘，r+1r+1 上乘逆元。
快速幂算逆元，预处理阶乘，树状数组维护，复杂度 O((n+q)log⁡n)O((n+q)\log n)。

细节

本题的区间为环形区间，要注意 l,r,1,nl,r,1,n 的关系。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int MOD =  1e9 + 7;
const int N = 2e5 + 10;
template<typename TY>
inline void read(TY &s){
	ll x = 0,f = 1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	s = x * f;
}
int n,q;
int ind[N];
ll qpow(ll a,ll b,ll p){
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}
inline ll inverse(ll x){
	return qpow(x,MOD-2,MOD);
}
inline int dist(int x,int y){
	if(x < y) return y - x;
	else return y - x + n;
}
ll mul[N],fac[N];
inline void modify(int x,ll v){
	for(int i=x;i<=n;i+=lowbit(i)) mul[i] = mul[i] * v % MOD;
}
inline ll query(int x){
	ll res = 1;
	for(int i=x;i;i-=lowbit(i)) res = res * mul[i] % MOD;
	return res;
}
inline void M(int l,int r,ll v){
	if(l > r) return;
	modify(l,v); modify(r+1,inverse(v));
}
inline void change(int x,int y,ll v){
	if(x < y){
		M(x+1,y-1,v);
	}
	else{
		M(x+1,n,v);
		M(1,y-1,v);
	}
}
int main(){
	read(n); read(q);
	int a,b;
	fac[0] = 1; 
	for(int i=1;i<=n;i++){
		fac[i] = fac[i - 1] * i % MOD;
		mul[i] = 1;
	}
	for(int i=1;i<=n-3;i++){
		read(a); read(b);
		ind[a]++; ind[b]++;
		change(a,b,dist(b,a)-1);
		change(b,a,dist(a,b)-1);
	} 
	int c,d,opt;
	while(q--){
		read(opt);
		if(opt == 1){
			read(a); read(b); read(c); read(d);
			ind[a]--; ind[b]--; ind[c]++; ind[d]++;
			change(a,b,inverse(dist(b,a)-1));
			change(b,a,inverse(dist(a,b)-1));
			change(c,d,dist(d,c)-1);
			change(d,c,dist(c,d)-1);
		}
		else{
			read(a);
			cout << (n - 3 - ind[a]) << " " << (fac[n-3-ind[a]]) * inverse(query(a)) % MOD << "\n";
		} 
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...