[hdu-6627]equation 分段函数 2019多校5

野性酷女 2021-10-23 17:24 189阅读 0赞

题目：http://acm.hdu.edu.cn/showproblem.php?pid=6627

题意：给c 和n个a，b 求出所有可以满足下面方程的x（可能有无数个，输出-1），

![1606447-20190806231704318-1128753251.png][]

题解：每个 ai \* x + bi = 0 可以解出一个xi，在xi左侧 去绝对值 为 ai \* x + bi，右侧为-（ ai \* x + bi ）

然后这样解出n个x就分成了n+1个区间，对每个区间都可以去括号解出x，看x在不在这个区间内，在的话就是一个可行解，把分子分母丢到set里

特判：如果在一个区间内 suma=0，sumb=c，则有无穷解

ps：xi 有相同的 可能区间重合为一个点，特判（这里直接判double型的相等居然没有精度差）

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 int const maxn=1e6+7;
      4 typedef long long ll;
      5 int n,m,c,tot;
      6 ll suma,sumb;
      7 struct node{
      8     double g;
      9     int a,b;
     10 }no[maxn];
     11 struct     ANS{
     12     ll a,b;
     13     double v;
     14 }ans[maxn];
     15 set <pair<ll,ll>>s;
     16 inline int get_num(){
     17     char ch;
     18     bool flag=false;
     19     int num=0;
     20     ch=getchar();
     21     while(ch<'0'||ch>'9'){
        if(ch=='-')flag=true;ch=getchar();}
     22     while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+ch-'0';ch=getchar();}
     23     if(flag)return -1*num;
     24     return num;
     25 }
     26 ll gcd(ll a,ll b)//最大公约数，辗转相除 
     27 {
     28     return b?gcd(b,a%b):a;
     29 }
     30 bool cmp(node x,node y){
     31     return x.g<y.g;
     32 }
     33 bool cmp1(ANS x,ANS y){
     34     return x.v<y.v;
     35 }
     36 void work(){
     37     bool flag=0;
     38     long long u,zi,mu;
     39     double nowa;
     40     suma=-suma,sumb=-sumb;
     41     for(int i=1;i<=n;i++){
     42         nowa=(c-sumb)*1.0/suma;
     43         zi=abs(c-sumb),mu=abs(suma);u=__gcd(zi,mu);//stl自带求gcd
     44         if(suma==0&&sumb==c){
     45             flag=1;break;
     46         }
     47         if(i==1){
     48             if(nowa<=no[1].g){
     49             if((c-sumb)*suma>=0)s.insert(make_pair(zi/u,mu/u));
     50             else s.insert(make_pair(-zi/u,mu/u));}
     51         }
     52         else if(nowa<=no[i].g&&nowa>=no[i-1].g){
     53             if((c-sumb)*suma>=0)s.insert(make_pair(zi/u,mu/u));
     54             else s.insert(make_pair(-zi/u,mu/u));
     55         }
     56         suma+=2*no[i].a,sumb+=2*no[i].b;
     57         while(i<n&&no[i].g==no[i+1].g){
     58             i++;suma+=2*no[i].a,sumb+=2*no[i].b;
     59         }
     60     }
     61     nowa=(c-sumb)*1.0/suma;
     62     if(suma==0&&sumb==c)flag=1;
     63     else {
     64         zi=abs(c-sumb),mu=abs(suma);u=__gcd(zi,mu);
     65         if(nowa>=no[n].g){
     66             if((c-sumb)*suma>=0)s.insert(make_pair(zi/u,mu/u));
     67             else s.insert(make_pair(-zi/u,mu/u));
     68         }
     69     }
     70     if(flag){
     71         printf("-1\n");return ;
     72     }
     73     cout<<s.size();
     74     set< pair<ll,ll>> :: iterator it=s.begin();
     75     for(;it!=s.end();it++){
     76         ans[++tot].a=it->first;ans[tot].b=it->second;
     77         ans[tot].v=ans[tot].a*1.0/ans[tot].b;
     78     }
     79     sort(ans+1,ans+1+tot,cmp1);
     80     for(int i=1;i<=tot;i++){
     81         printf(" %lld/%lld",ans[i].a,ans[i].b);
     82     }
     83     cout<<endl;
     84 }
     85 int main(){
     86     int t;
     87     scanf("%d",&t);
     88     while(t--){
     89         n=get_num(),c=get_num();
     90         suma=0ll,sumb=0ll;tot=0;s.clear();
     91         for(int i=1;i<=n;i++){
     92             no[i].a=get_num(),no[i].b=get_num(),no[i].g=-1.0*no[i].b/no[i].a;
     93             suma+=no[i].a;sumb+=no[i].b;
     94         }
     95         sort(no+1,no+1+n,cmp);
     96         
     97         work();
     98     }    
     99     return 0;
    100 }

转载于:https://www.cnblogs.com/conver/p/11312567.html

[1606447-20190806231704318-1128753251.png]: /images/20211023/0298dca164874a1f9b5a6fcc8a214157.png