sgn和S(x)的trick

以你之姓@ 2024-03-29 16:00 28阅读 0赞

就是一些小trick，学一下就好了

sgn就是高精度地看这个数是不是等于0，也可以高精度地比较两个数，把x变成a-b就好了

S(x)就是哈希，哈希什么都可以

int S(x)

#include <bits/stdc++.h>
    const int mxn=1e6+10;
    using namespace std;
    struct ty{
        int to,next;
    }edge[mxn];
    queue<int> q;
    int n,res=0,cnt=0,idx=0;
    int head[mxn],inc[mxn];
    void add(int u,int v){
        edge[cnt].to=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    map<string,int> mp;
    int S(string x){
        if(mp[x]) return mp[x];
        else return mp[x]=++idx;
    }
    string u,v;
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        memset(head,-1,sizeof(head));
        res=0,cnt=0;
        for(int i=1;i<=n;i++){
            cin>>u>>v;
            int a=S(u),b=S(v);
            add(a,b);
            //cout<<a<<" "<<b<<'\n';
            inc[b]++;
        }
            for(int i=1;i<=idx;i++){
                if(!inc[i]) q.push(i);
            }
            while(!q.empty()){
                int tmp=q.front();
                q.pop();
                res++;
                for(int i=head[tmp];~i;i=edge[i].next){
                    inc[edge[i].to]--;
                    if(!inc[edge[i].to]) q.push(edge[i].to);
                }
            }
            //cout<<res<<'\n';
            if(res==idx) cout<<"Yes"<<'\n';
            else cout<<"No"<<'\n';
        return 0;
    }

sgn

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define y1 Y1
    const int mxn=1e3+10,mod=1e9+7;
    const double eps=1e-4;
    int x,y,x1,y1;
    double ans;
    int sgn(double x){
        if(fabs(x)<eps) return 0;
        return x<0?-1:1;
    }
    void solve(){
        cin>>x>>y>>x1>>y1;
        if(x1<=x&&y1<=y){
            int Sb=max(max(x1*y1,x1*(y-y1)),max((x-x1)*y1,(x-x1)*(y-y1)));
            int Sh=x*y;
            ans=(double)Sb/(double)Sh;
        }else if(x1<=x&&y1>y){
            int Sb1=x1*y;
            int Sb2=(x-x1)*y;
            int Sh1=x1*y1+x*y-Sb1;
            int Sh2=(x-x1)*y1+x*y-Sb2;
            //cout<<Sb2<<" "<<Sh2<<'\n';
            double ans1=(double)Sb1/(double)Sh1;
            double ans2=(double)Sb2/(double)Sh2;
            if(sgn(ans1-ans2)==1) ans=ans1;
            else ans=ans2;
        }else if(x1>x&&y1<=y){
            int Sb1=x*y1;
            int Sb2=x*(y-y1);
            int Sh1=x*y+x1*y1-Sb1;
            int Sh2=x*y+x1*(y-y1)-Sb2;
            double ans1=(double)Sb1/(double)Sh1;
            double ans2=(double)Sb2/(double)Sh2;
            if(sgn(ans1-ans2)==1) ans=ans1;
            else ans=ans2;
        }else{
            int Sb=x*y;
            int Sh=x1*y1;
            ans=(double)Sb/(double)Sh;
        }
        cout<<fixed<<setprecision(9)<<ans<<'\n';
    }
    signed main(){
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }