qbxt 10 月模拟赛 Day7

Author： RainAir
发布时间：October 7, 2020
810views
No comments
359 words
Categories：题解

A

贪心删除出现次数最少的数。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
int n,a[MAXN],b[MAXN],k;

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i),b[a[i]]++;
    int t = 0;FOR(i,1,n) t += (b[i] != 0);
    std::sort(b+1,b+n+1);
    int ans = 0;
    FOR(i,1,n){
        if(t <= k) break;
        if(!b[i]) continue;
        ans +=  b[i];t--;
    }
    printf("%d\n",ans);
    return 0;
}

B

逆序对期望，根据期望的线性性转成考虑每一对数的期望，由于权值是 $0/1$，现在变成了对于一对数 $(x,y)$，计算是一对逆序对的概率。

我们设 $x<y$，那么一定是先共同经过若干轮都没有被选中，然后在第 $i$ 轮选中了 $y$ 但没有选中 $x$，之后若干轮后选了 $x$；我们枚举 $i$ 可以得到概率：

$$ \begin{aligned} \sum_{i=1}^{\infty} (1-p)^{i-1}p (1-p)^i &= p(1-p)\sum_{i=0}^{\infty}(1-p)^{2i}\\ &= p(1-p)\frac{1}{1-(1-p)^2} \end{aligned} $$

注意到对数有 $\binom n 2$ 个，所以答案是 $\binom n 2 p(1-p)\frac{1}{1-(1-p)^2}$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 998244353;
const int inv2 = 499122177;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int main(){
    int n,x,y;scanf("%d%d%d",&n,&x,&y);
    int p = 1ll*x*qpow(y)%ha;
    int ans = 1ll*n*(n-1)%ha*inv2%ha;
    int t = (1+ha-p)%ha;t = 1ll*t*t%ha;
    t = (1+ha-t)%ha;t = qpow(t);
    ans = 1ll*ans*t%ha;
    ans = 1ll*ans*(1+ha-p)%ha;
    ans = 1ll*ans*p%ha;
    printf("%d\n",ans);
    return 0;
}

C

提供我考场的思路和标程思路，我的思路应该是正规 NOIP 思路（（虽然代码本质是一样的

首先我们考虑有以下恒等式：

$$ x^k = \sum_{i_1=1}^x \sum_{i_2=1}^x \cdots\sum_{i_k=1}^x 1 $$

所以对于一条路径的 $x^k$ 可以理解成有序可重地选出 $k$ 条边，所以一个暴力dp的思想就是设 $f_{v,i}$ 表示从 $1$ 到 $v$ 选了 $i$ 个边的方案数，每次转移 $O(k)$ 枚举当前边被选了 $j$ 次，系数是 $\binom{k-i}{j}$，这样复杂度是 $O(mk^2)$ 的。

优化：我们可以考虑每条路径的系数只和选了多少条不同的边有关，假设选了 $m$ 条不同的边，系数和大概是这样的一个东西：

$$ \sum_{x_1 + x_2 + \ldots + x_m = k} \binom{k}{x_1,x_2,\ldots,x_m} $$

这个东西我考试的时候写了 $k^3$ dp 出来的，但是可以发现实际上它是将 $k$ 个有标号小球放进 $m$ 个有标号小球，要求非空的方案数，也就是 $\left\{^k_m\right\}m!$。

所以我们 dp 的时候只需要求出 $f_{v,i}$ 到 $v$ 点，选了 $i$ 条边的方案数，转移直接枚举当前边是否选，$O(mk + k^2)$。

题解做法（一点点省选知识）：考虑恒等式：

$$ x^k = \sum_{i=0}^k \left\{^k_i\right\}x^{\underline k} = \sum_{i=0}^k \left\{^k_i\right\}\binom x k k! $$

所以我们只需要求出 $f_{v,i}$ 表示到 $v$ 点，所有路径的 $\binom x k$ 的和即可，注意到有 $\binom n m = \binom {n-1}{m} + \binom {n-1}{m-1}$，转移的时候只要枚举当前边是否选就行了。

对于这种只能从一个点出发的 DAG 游走，只需要初始化起点然后正常拓扑排序即可。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int MAXK = 500 + 5;
const int ha = 998244353;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

struct Edge{
    int to,nxt;
}e[MAXN<<1];
bool vis[MAXN];
int head[MAXN],cnt,deg[MAXN];

inline void adde(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    deg[v]++;
}

inline void add(int &x,int y){
    (x += y);if(x >= ha) x -= ha;
}

int f[MAXN][MAXK];
int n,m,k;
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int g[MAXK][MAXK];
// i个变量,和为 j

int main(){
    prework();
    read(n);read(m);read(k);
    g[0][0] = 1;
    FOR(i,1,k){
        FOR(j,i,k){
            FOR(x,1,j){
                add(g[i][j],1ll*g[i-1][j-x]*C(k-(j-x),x)%ha);
            }
        }
    }
    FOR(i,1,m){
        int u,v;read(u);read(v);
        adde(u,v);
    }
    std::queue<int> q;
    q.push(1);vis[1] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(vis[e[i].to]) continue;
            q.push(e[i].to);vis[e[i].to] = 1;
        }
    }
    FOR(v,1,n){
        if(!vis[v]){
            for(int i = head[v];i;i = e[i].nxt){
                deg[e[i].to]--;
            }
        }
    }
    q.push(1);
    f[1][0] = 1;
//    assert(deg[1]==0);
    FOR(i,1,n) vis[i] = 0;
    while(!q.empty()){
        int v = q.front();q.pop();vis[v] = 1;
        for(int i = head[v];i;i = e[i].nxt){
            FOR(x,0,k){
                if(!f[v][x]) continue;
                FOR(y,0,std::min(1,k-x)){
                    add(f[e[i].to][x+y],f[v][x]);
                }
            }
            if(!--deg[e[i].to]) q.push(e[i].to);
        }
    }
    FOR(i,1,n){
        int ans = 0;
        FOR(j,1,k){
            add(ans,1ll*f[i][j]*g[j][k]%ha);
        }
        printf("%d\n",ans);
    }
    return 0;
}

D

曼哈顿距离两维独立考虑，一维上给你若干个点，求一个点满足曼哈顿距离和最小是经典问题：只需要取中位数即可。

那么对于这个题我们肯定要二分中位数 $x$，然后变成了计算有多少个交点满足横坐标 $\leq x$（求纵坐标的时候只需要求一下反函数即可）。

赛时思路：

按照斜率排序，考虑 $i,j$ 两条直线（$i < j$）的交点横坐标是 $\frac{b_i-b_j}{k_j-k_i}$，也就是要判断是否 $\frac{b_i-b_j}{k_j-k_i} \leq x \Rightarrow b_i+k_ix \leq k_jx+b_j$，离散化+树状数组或者归并排序求顺序对都可以。

题解思路：

考虑我们按照 $-\infty$ 的值排序，观察走到 $x$ 的变化：如果有交点就会产生一对逆序对。

所以我们只需要一开始按照 $-\infty$ 的值编号，每次 check 的时候按照 $x$ 的位置的 $y$ 值排序，逆序对就是答案。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 40000+5;
const int EPS = 1e-9;

inline int sgn(double x){
    if(std::fabs(x) <= EPS) return 0;
    if(x < 0) return -1;
    return 1;
}

int n;
int aa[MAXN],bb[MAXN],cc[MAXN];
std::pair<double,double> seg[MAXN];
double a[MAXN];
int c[MAXN];

struct BIT{
    int tree[MAXN];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        while(pos < MAXN){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

inline bool chk(double x){ // <=x 的交点个数是否超过一半
    LL ans = 0;
    std::sort(seg+1,seg+n+1);
    FOR(i,1,n) a[i] = seg[i].se+x*seg[i].fi;
    std::vector<double> S;
    FOR(i,1,n) S.pb(a[i]);
    std::sort(all(S));S.erase(std::unique(all(S)),S.end());
    FOR(i,1,n) c[i] = std::lower_bound(all(S),a[i])-S.begin()+1;
    CLR(bit.tree,0);
    FOR(i,1,n){
        ans += bit.query(c[i]);
        bit.add(c[i],1);
    }
    LL lim = 1ll*n*(n-1)/2;
//    DEBUG(ans);
    return ans >= lim - ans;
}

inline double work(){
    std::sort(seg+1,seg+n+1);
    double l = -1e9,r = 1e9,ans=0;
    FOR(i,1,70){
        double mid = (l + r)/2.0;
        if(chk(mid)) ans = mid,r = mid;
        else l = mid;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%d%d%d",aa+i,bb+i,cc+i);
        seg[i] = MP(-1.0*(1.0*aa[i]/bb[i]),1.0*cc[i]/bb[i]);
    }
    printf("%.6f ",work());
    FOR(i,1,n){
        seg[i] = MP(-1.0*(1.0*bb[i]/aa[i]),1.0*cc[i]/aa[i]);
    }
 //   DEBUG(chk(-4905.877264));
 //   exit(0);
    printf("%.6f\n",work());
    return 0;
}

Last modification：October 8th, 2020 at 11:03 am

如果觉得我的文章对你有用，请随意赞赏

qbxt 10 月模拟赛 Day7

RainAir • 2020 年 10 月 07 日

A

贪心删除出现次数最少的数。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
int n,a[MAXN],b[MAXN],k;

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i),b[a[i]]++;
    int t = 0;FOR(i,1,n) t += (b[i] != 0);
    std::sort(b+1,b+n+1);
    int ans = 0;
    FOR(i,1,n){
        if(t <= k) break;
        if(!b[i]) continue;
        ans +=  b[i];t--;
    }
    printf("%d\n",ans);
    return 0;
}

B

逆序对期望，根据期望的线性性转成考虑每一对数的期望，由于权值是 $0/1$，现在变成了对于一对数 $(x,y)$，计算是一对逆序对的概率。

$$ \begin{aligned} \sum_{i=1}^{\infty} (1-p)^{i-1}p (1-p)^i &= p(1-p)\sum_{i=0}^{\infty}(1-p)^{2i}\\ &= p(1-p)\frac{1}{1-(1-p)^2} \end{aligned} $$

注意到对数有 $\binom n 2$ 个，所以答案是 $\binom n 2 p(1-p)\frac{1}{1-(1-p)^2}$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 998244353;
const int inv2 = 499122177;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int main(){
    int n,x,y;scanf("%d%d%d",&n,&x,&y);
    int p = 1ll*x*qpow(y)%ha;
    int ans = 1ll*n*(n-1)%ha*inv2%ha;
    int t = (1+ha-p)%ha;t = 1ll*t*t%ha;
    t = (1+ha-t)%ha;t = qpow(t);
    ans = 1ll*ans*t%ha;
    ans = 1ll*ans*(1+ha-p)%ha;
    ans = 1ll*ans*p%ha;
    printf("%d\n",ans);
    return 0;
}

C

提供我考场的思路和标程思路，我的思路应该是正规 NOIP 思路（（虽然代码本质是一样的

首先我们考虑有以下恒等式：

$$ x^k = \sum_{i_1=1}^x \sum_{i_2=1}^x \cdots\sum_{i_k=1}^x 1 $$

优化：我们可以考虑每条路径的系数只和选了多少条不同的边有关，假设选了 $m$ 条不同的边，系数和大概是这样的一个东西：

$$ \sum_{x_1 + x_2 + \ldots + x_m = k} \binom{k}{x_1,x_2,\ldots,x_m} $$

所以我们 dp 的时候只需要求出 $f_{v,i}$ 到 $v$ 点，选了 $i$ 条边的方案数，转移直接枚举当前边是否选，$O(mk + k^2)$。

题解做法（一点点省选知识）：考虑恒等式：

$$ x^k = \sum_{i=0}^k \left\{^k_i\right\}x^{\underline k} = \sum_{i=0}^k \left\{^k_i\right\}\binom x k k! $$

对于这种只能从一个点出发的 DAG 游走，只需要初始化起点然后正常拓扑排序即可。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int MAXK = 500 + 5;
const int ha = 998244353;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

struct Edge{
    int to,nxt;
}e[MAXN<<1];
bool vis[MAXN];
int head[MAXN],cnt,deg[MAXN];

inline void adde(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    deg[v]++;
}

inline void add(int &x,int y){
    (x += y);if(x >= ha) x -= ha;
}

int f[MAXN][MAXK];
int n,m,k;
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int g[MAXK][MAXK];
// i个变量,和为 j

int main(){
    prework();
    read(n);read(m);read(k);
    g[0][0] = 1;
    FOR(i,1,k){
        FOR(j,i,k){
            FOR(x,1,j){
                add(g[i][j],1ll*g[i-1][j-x]*C(k-(j-x),x)%ha);
            }
        }
    }
    FOR(i,1,m){
        int u,v;read(u);read(v);
        adde(u,v);
    }
    std::queue<int> q;
    q.push(1);vis[1] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(vis[e[i].to]) continue;
            q.push(e[i].to);vis[e[i].to] = 1;
        }
    }
    FOR(v,1,n){
        if(!vis[v]){
            for(int i = head[v];i;i = e[i].nxt){
                deg[e[i].to]--;
            }
        }
    }
    q.push(1);
    f[1][0] = 1;
//    assert(deg[1]==0);
    FOR(i,1,n) vis[i] = 0;
    while(!q.empty()){
        int v = q.front();q.pop();vis[v] = 1;
        for(int i = head[v];i;i = e[i].nxt){
            FOR(x,0,k){
                if(!f[v][x]) continue;
                FOR(y,0,std::min(1,k-x)){
                    add(f[e[i].to][x+y],f[v][x]);
                }
            }
            if(!--deg[e[i].to]) q.push(e[i].to);
        }
    }
    FOR(i,1,n){
        int ans = 0;
        FOR(j,1,k){
            add(ans,1ll*f[i][j]*g[j][k]%ha);
        }
        printf("%d\n",ans);
    }
    return 0;
}

D

曼哈顿距离两维独立考虑，一维上给你若干个点，求一个点满足曼哈顿距离和最小是经典问题：只需要取中位数即可。

那么对于这个题我们肯定要二分中位数 $x$，然后变成了计算有多少个交点满足横坐标 $\leq x$（求纵坐标的时候只需要求一下反函数即可）。

赛时思路：

题解思路：

考虑我们按照 $-\infty$ 的值排序，观察走到 $x$ 的变化：如果有交点就会产生一对逆序对。

所以我们只需要一开始按照 $-\infty$ 的值编号，每次 check 的时候按照 $x$ 的位置的 $y$ 值排序，逆序对就是答案。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 40000+5;
const int EPS = 1e-9;

inline int sgn(double x){
    if(std::fabs(x) <= EPS) return 0;
    if(x < 0) return -1;
    return 1;
}

int n;
int aa[MAXN],bb[MAXN],cc[MAXN];
std::pair<double,double> seg[MAXN];
double a[MAXN];
int c[MAXN];

struct BIT{
    int tree[MAXN];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        while(pos < MAXN){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

inline bool chk(double x){ // <=x 的交点个数是否超过一半
    LL ans = 0;
    std::sort(seg+1,seg+n+1);
    FOR(i,1,n) a[i] = seg[i].se+x*seg[i].fi;
    std::vector<double> S;
    FOR(i,1,n) S.pb(a[i]);
    std::sort(all(S));S.erase(std::unique(all(S)),S.end());
    FOR(i,1,n) c[i] = std::lower_bound(all(S),a[i])-S.begin()+1;
    CLR(bit.tree,0);
    FOR(i,1,n){
        ans += bit.query(c[i]);
        bit.add(c[i],1);
    }
    LL lim = 1ll*n*(n-1)/2;
//    DEBUG(ans);
    return ans >= lim - ans;
}

inline double work(){
    std::sort(seg+1,seg+n+1);
    double l = -1e9,r = 1e9,ans=0;
    FOR(i,1,70){
        double mid = (l + r)/2.0;
        if(chk(mid)) ans = mid,r = mid;
        else l = mid;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%d%d%d",aa+i,bb+i,cc+i);
        seg[i] = MP(-1.0*(1.0*aa[i]/bb[i]),1.0*cc[i]/bb[i]);
    }
    printf("%.6f ",work());
    FOR(i,1,n){
        seg[i] = MP(-1.0*(1.0*bb[i]/aa[i]),1.0*cc[i]/aa[i]);
    }
 //   DEBUG(chk(-4905.877264));
 //   exit(0);
    printf("%.6f\n",work());
    return 0;
}

qbxt 10 月模拟赛 Day7

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「UOJ191」Unknown

「BZOJ2788」Poi2012Festival

Topcoder UniqueMST

「BZOJ3600」没有人的算术

「CF1110H」Modest Substrings

qbxt 10 月模拟赛 Day7

A

B

C

D