10.19 一中S模拟2

· · 题解

T1

题意

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

做法

令 $r_{1},r_{2}$ 分别为 $O_{1},O_{2}$ 的半径，$d$ 为两圆圆心的距离，若 $r_{1} > r_{2} + d$，则满足限制。 $\sqrt x$ 有精度误差，两种解决思路： 1.转化为整数比较。 2.卡精度 $eps = -10^{-8} 
#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

题意

[题目](https://www.luogu.com.cn/problem/P9906) ## 找性质 正难则反，倒着考虑。 不难发现 $n$ 最后一定在序列中，因为他是最后放的；$n-1$ 也一定在序列中，因为他只能放在 $n$ 的旁边；$n-3$ 可以放在 $n$ 下面被覆盖，也可以放在 $n-1$ 旁边显露出来……以此类推，我们发现最后形成的序列一定连续。 设 $f(i,j)$ 表示到了选到第 $i$ 大的点，形成了长度为 $j$ 的序列（也就是 $j$ 个数需要在最终序列出现），钦定当前数出现的序列方案数。 注意到因为从小到大考虑，所以当前出现的数一定在最左或最右边。考虑更新其它数，如果这个数填补左端点的左边，则可以更新 $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-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(n^3)$ 的，发现可以用前缀和记录 前面 $f(2\times k,j)$ 的总方案数，复杂度 $O(n^2)$。 答案统计为$\sum_{i=2}^{n}\sum_{j=2}^{k}f(i,j)\times (k - j + 1)$，因为我们只考虑了每个序列的内部关系，没有考虑序列在 $k$ 中的位置方案，这里是统计最小的出现的数是 $i$，有 $j$ 个数出现的总方案数。 ```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 [题目链接](https://www.luogu.com.cn/problem/P10230) ## 题意 给定 $n$ 个顶点的多边形，$n-3$ 条对角线形成一个三角剖分（顾名思义 $n-3$ 条对角线将多边形分成了一个个三角形）。 有两种操作： 1.删除一条对角线，并添加新的一条（算一次操作）。 2.问此时将所有对角线的一端移到 $x$ 上的最小操作次数和其方案数。 注意三角剖分和操作 $2$ 时不能让当前的对角线有交。 ## 突破点 从 $sub2$ 中受到启发，发现最小操作次数就是端点不在 $x$ 上的对角线条数。 简单证明一下：对于一条对角线 $(p,q)$，它存在于两个三角形中，所对的点分别记为 $x,r$。我们可以删除 $(p,q)$，添加 $x,r$ 使得对角线的一端变为 $x$，而我们每次可以选择不被其他对角线包含的一条操作。至于一端在 $x$ 上的对角线，我们不进行操作显然更优。 ![](https://cdn.luogu.com.cn/upload/image_hosting/a1f96d1v.png) ## 第一步转化 经过最小操作次数的启发，我们可以发现操作的一般顺序。 我们将所有对角线看作不经过 $x$ 的弧的形式，则： 1. 任意两条弧要么不交要么包含（根据三角剖分的性质）。 2. 每次一定选择一条极大的弧（不被其他弧包含的弧），满足操作中对角线无交。 3. 一条弧至多**直接**包含两条弧（无用）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/nvqs0r3o.png) ## 第二步转化 将所有弧看作点，将弧与弧之间的包含关系映射为树上的父子关系（大弧为父亲），就得到了一个二叉树形结构。 ![](https://cdn.luogu.com.cn/upload/image_hosting/xsm0rm6k.png) 结合我们上一步的操作顺序，我们就是每次处理一个父亲节点，然后将它的儿子加入到待处理集合中。这样我们的操作方案数就是一个树上拓扑序数，因为弧与弧之间可能无交，也就是可能有很多棵树形成的森林，操作方案数为森林拓扑序数量。 有个经典结论，森林拓扑序数量为 $\frac{n!}{\prod sz_{i}}$。 **对于这个结论，我的理解是这样的：** 首先将所有点排列起来，共 $n!$ 种。对于每一个点，我们要求它出现在它的子树中的点的前面，其中这个点出现在子树序列最前面的概率是 $\frac{1}{sz_{i}}$，要求每个点出现在各自子树序列的前面，所以总拓扑序数就是 $\frac{n!}{\prod sz_{i}}$。 $n$ 为节点数，$sz_{i}$ 为以 $i$ 为根的子树大小；而这里 $n$ 为不经过 $x$ 的对角线的数量；对于一个点 $p$，$sz_{p}$ 就是这条弧所包含的小弧数量（包括自己）。 设弧为 $(l,r)$，则包含数量就是 $(r - l - 1)$，只需计算所有不经过 $x$ 的弧的弧长-1的乘积。 所以我们记录每个点上连接的对角线条数 $ind[i]$，最小操作次数就是 $n - 3 - ind[x]$，方案数就是不经过 $x$ 的弧的条数除以所有弧的包含总数和。 ## 第三步优化 考虑优化复杂度，用树状数组维护 $mul[i]$，表示不经过 $i$ 号点的对角线/弧包含总数和（也就是 $\prod sz_{i}$ 这部分）。维护对角线就是维护对角线所对的两条弧上的点：具体的，添加一条对角线就是进行区间乘，删除对角线就是区间乘以逆元。 区间修单点查利用差分思想转为单点修前缀查，$[l,r]$ 的区间乘就是 $l$ 上乘，$r+1$ 上乘逆元。 快速幂算逆元，预处理阶乘，树状数组维护，复杂度 $O((n+q)\log n)$。 ## 细节 本题的区间为环形区间，要注意 $l,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; } ```