icontofig | 发布于 2019-08-05 22:56:27 | 阅读量 341 | 思维题
发布于 2019-08-05 22:56:27 | 思维题

题目大意

给出n个二元组(ai,bi),求出Σni=1|aix-bi| = c 的所有解,并用最简分数形式表示,若有无穷多解输出-1

题解

这道题卡我常……比赛的时候被卡常卡到心态炸裂

赛后发现我被排序用的cmp函数给卡了,真TM没想到啊……

首先我们不能直接求绝对值方程式的解,我们通常的想法是把绝对值号拿掉,然后再做。

但是这题一共有n个绝对值式,不是很好办。

我们想一下,每一个绝对值式都有一个对应的变号点,我们可以先把这些变号点求出来,然后根据变号点对每个式子排一遍序。

然后很明显的这些变号点把整个数轴分成了n+1个区间。每个区间对应了一个去掉绝对值后的方程式,也对应着一个合法的解区间。

然后我们对于每一个解区间所对应的无绝对值方程式,可以解出确切的一个解x’,或者解出无数组解。如果解出确切的一个解x‘,我们只需要判断x’是否在当前的合法解区间内即可。

至于解区间间的方程式变换,由于我们已经对式子排了序,也就是确定了每个式子变号点的前后顺序,所以可以做到O(1)变换方程式。

总复杂度O(T*(nlogn + n))

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int p[maxn],q[maxn];
int tot = 0;
struct funct{
    int a,b;
    double k;
}f[maxn];
const double eps = 1e-5;
bool cmp(funct x,funct y){
    return x.k - y.k >= eps;
}
int T;
int n;
int suma,sumb;
int c;
int x,y,g;
bool flag;
double xx,yy;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&c);
        tot = 0;
        suma = 0;
        sumb = 0;
        for(int i = 1;i <= n;++i){
            scanf("%d%d",&f[i].a,&f[i].b);
            suma += f[i].a;
            sumb += f[i].b;
            f[i].k = double(-f[i].b) / double(f[i].a);
        }
        sort(f+1,f+n+1,cmp);
        int j = 1;
        flag = false;
        for(int j = 1;j <= n;++j){
            if(suma == 0 && sumb == c){
                printf("-1\n");
                flag = true;
                break;
            }
            else{
                if(suma != 0){
                    x = c - sumb;
                    y = suma;
                    xx = x;
                    yy = y;
                    if(j == 1){
                        if(xx / yy - f[j].k >= eps){
                            tot++;
                            p[tot] = x;q[tot] = y;
                        }
                    }
                    else{
                        if(xx / yy - f[j].k >= eps && xx / yy - f[j-1].k < eps){
                            tot++;
                            p[tot] = x;q[tot] = y;
                        }
                    }
                }
                suma -= 2*f[j].a;
                sumb -= 2*f[j].b;
            }
        }
        x = c - sumb;
        y = suma;
        if(y == 0 && x == 0 && !flag){
            printf("-1\n");
            flag = true;
        }
        if(flag)continue;
        xx = x;
        yy = y;
        if(xx / yy - f[n].k < eps){
            tot++;
            p[tot] = x;q[tot] = y;
        }
        printf("%d",tot);
        for(int i = tot;i >= 1;--i){
            if(p[i] == 0){
                printf(" 0/1");
            }
            else{
                g = __gcd(p[i],q[i]);
                p[i] /= g;q[i] /= g;
                if(q[i] < 0){
                    q[i] = -q[i];
                    p[i] = -p[i];
                }
                printf(" %d/%d",p[i],q[i]);
            }
        }
        printf("\n");
    }
    return 0;
}



内容更新于: 2019-08-05 22:56:27
链接地址: http://blog.leanote.com/post/icontofig/fa2ce26007aa

上一篇: 2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题

下一篇: SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置

341 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航