首页 > 其他 > 详细

CF2

时间:2020-01-21 22:48:35      阅读:34      评论:0      收藏:0      [点我收藏+]

标签:注意   har   esp   clas   是否   细节   

热烈庆祝我马力大进步能调出计算几何了……

A

A

阅读理解+\(map\)

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define y1 qwq
#define int long long
#define eps (1e-6)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    int n,maxn,tot,x[1010];
    string win,s[1010];
    map<string,int> q,q1;
    inline void main()
    {
        n=read();
        for(int i=1;i<=n;++i)
        {
            cin>>s[i]>>x[i];
            q[s[i]]+=x[i];
        }
        for(int i=1;i<=n;++i)
        {
            if(q[s[i]]==maxn) ++tot;
            if(q[s[i]]>maxn) maxn=q[s[i]],tot=1,win=s[i];
        }
        if(tot==1)
        {
            cout<<win<<endl;
            return;
        }
        for(int i=1;i<=n;++i)
        {
            q1[s[i]]+=x[i];
            if(q1[s[i]]>=maxn&&q[s[i]]>=maxn)
            {
                cout<<s[i]<<endl;
                return;
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;
}

B

B

一眼考虑\(f[i][j][k]\)表示到\(i,j\),乘积末尾为\(k\)的最少\(0\)

发现被卡空间了

考虑\(0\)只能由\(2*5\)得到,记录\(f[i][j][0/1]\)表示到\(i,j\)最少的\(2/5\)的数量,最后取\(min(f[n][n][0],f[n][n][1])\)

注意如果矩阵中有\(0\),可以强制让答案变为\(1\)

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define y1 qwq
#define eps (1e-6)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=1005;
    int n,ans;
    int f[N][N][2];
    int g[N][N][2];
    int a[N][N][2];
    bool flag;
    int tx,ty;
    inline void dfs(int x,int y,int opt)
    {
        if(x==1&&y==1) return;
        
        if(g[x][y][opt])
        {
            dfs(x-1,y,opt);
            putchar('D');
        }
        else
        {
            dfs(x,y-1,opt);
            putchar('R');
        }
    }
    inline void main()
    {
        n=read();
        for(int x,y,i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                x=y=read();
                if(!x)
                {
                    tx=i,ty=j;
                    flag=1;
                    x=y=10;//变为10防止必须遇到这个0但答案仍然为0的情况
                }
                while(x%2==0) ++a[i][j][0],x/=2;
                while(y%5==0) ++a[i][j][1],y/=5;
            }
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i==1)
                {
                    g[i][j][0]=g[i][j][1]=0;
                    f[i][j][0]=f[i][j-1][0]+a[i][j][0];
                    f[i][j][1]=f[i][j-1][1]+a[i][j][1];
                }
                else if(j==1)
                {
                    g[i][j][0]=g[i][j][1]=1;
                    f[i][j][0]=f[i-1][j][0]+a[i][j][0];
                    f[i][j][1]=f[i-1][j][1]+a[i][j][1];
                }
                else
                {
                    if(f[i][j-1][0]<f[i-1][j][0]) g[i][j][0]=0,f[i][j][0]=f[i][j-1][0]+a[i][j][0];
                    else g[i][j][0]=1,f[i][j][0]=f[i-1][j][0]+a[i][j][0];
                    
                    if(f[i][j-1][1]<f[i-1][j][1]) g[i][j][1]=0,f[i][j][1]=f[i][j-1][1]+a[i][j][1];
                    else g[i][j][1]=1,f[i][j][1]=f[i-1][j][1]+a[i][j][1];
                }
            }
        }
        ans=min(f[n][n][0],f[n][n][1]);
        if(ans>1&&flag)
        {
            puts("1");
            for(int i=1;i<tx;++i) putchar('D');
            for(int i=1;i<ty;++i) putchar('R');
            for(int i=tx+1;i<=n;++i) putchar('D');
            for(int i=ty+1;i<=n;++i) putchar('R');
            return;
        }
        printf("%d\n",ans);
        ans=f[n][n][0]<f[n][n][1]?0:1;
        dfs(n,n,ans);
    }
}
signed main()
{
    red::main();
    return 0;
}
/*
3 
0 1 1 
1 1 1 
1 1 1 

*/

C

C

怎么又是计算几何草,超级码力+必修二大复习

设答案点为\(T\),与圆的切点为\(A1,A2\)

那么\(\frac{r_A}{dis(A,T)}=sin(\frac{∠A1TA2}{2})\)

由于三个圆角度应该相等,所以

\(\frac{r_A}{dis(A,T)}=\frac{r_B}{dis(B,T)}=\frac{r_C}{dis(C,T)}\)

我们设\(\frac{r_A}{r_B}=k\)

把坐标代入\(r_A,r_B\)

\(k^2=\frac{(x_T-x_A)^2+(y_T-y_A)^2}{(x_T-x_B)^2+(x_T-x_A)^2}\)

移项

\(k^2((x_T-x_B)^2+(x_T-x_A)^2)-(x_T-x_A)^2+(y_T-y_A)^2=0\)

然后把未知数\(x_T,y_T\)分离出来得到

\((k^2-1)x_T^2 + (k^2-1)y_T^2 - 2(k^2y_B - y_A)y_T - 2(k^2x_B - x_A)x_T+k^2x_B^2 - x_A^2 + k^2y_B^2 - y_A^2 = 0\)

我们把常数项代替一下

\(A=k^2-1,C=-2(k^2y_B-x_A),D=-2(k^2y_B-y_A),E=k^2x^2_B-x^2_A+k^2y^2_B-y^2_A\)

原式等于\(Ax^2+Ay^2+Cx+Dy+E=0\)

我们发现,当\(A\)不为\(0\)时,交点集合是个圆,当\(A\)\(0\)时,交点集合是直线

\(A=0\)时,\(k^2-1=0\),即\(r_A=r_B\)

然后大力分类讨论一下直线交直线交点,直线交圆交点,圆交圆交点

算出交点后还要判断一下是否满足对于第三个圆也满足\(\frac{r_A}{r_C}=\frac{dis(A,T)}{dis(C,T)}\)

一些细节加在代码里

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define y1 qwq
#define int long long
#define eps (1e-6)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    struct circle
    {
        double x,y,r;
    }a[4];
    struct node
    {
        double a,c,d,e;
        double x,y,r;
        double k,b;
        bool v;
    }d[3];
    inline void getline(int i,int j,int id)
    {
        double k=a[i].r/a[j].r;
        double c=-2*(k*k*a[j].x-a[i].x);
        double dd=-2*(k*k*a[j].y-a[i].y);
        double e=k*k*a[j].x*a[j].x-a[i].x*a[i].x+k*k*a[j].y*a[j].y-a[i].y*a[i].y;
        d[id].k=-c/dd;
        d[id].b=-e/dd;
        d[id].v=1;
    }
    inline void getcir(int i,int j,int id)
    {
        double k=a[i].r/a[j].r;
        d[id].a=k*k-1;
        d[id].c=-2*(k*k*a[j].x-a[i].x)/d[id].a;
        d[id].d=-2*(k*k*a[j].y-a[i].y)/d[id].a;
        d[id].e=k*k*a[j].x*a[j].x-a[i].x*a[i].x+k*k*a[j].y*a[j].y-a[i].y*a[i].y;
        d[id].e/=d[id].a;
        d[id].x=-d[id].c/2;
        d[id].y=-d[id].d/2;
        d[id].r=sqrt(d[id].d*d[id].d+d[id].c*d[id].c-4*d[id].e)/2;
    }
    inline double dis(double x1,double y1,double x2,double y2)
    {
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    inline void solve1()//直线交点
    {
        double x=(d[2].b-d[1].b)/(d[1].k-d[2].k);
        double y=(d[1].k*x+d[1].b);
        if(fabs(a[1].r/a[3].r-dis(a[1].x,a[1].y,x,y)/dis(a[3].x,a[3].y,x,y))>eps) return;
        printf("%.5lf %.5lf\n",x,y);
    }
    inline void solve2()//直线交圆
    {
        
        double aa=1+(d[1].k*d[1].k);
        double b=d[2].c+2*d[1].k*d[1].b+d[2].d*d[1].k;
        double c=d[1].b*d[1].b+d[1].b*d[2].d+d[2].e;
        
        double tmp=b*b-4*aa*c;
        
        if(tmp<-eps) return;
        
        double x1=(-b+sqrt(tmp))/(2*aa),y1=d[1].k*x1+d[1].b;
        double x2=(-b-sqrt(tmp))/(2*aa),y2=d[1].k*x2+d[1].b;
        
        
        
        if(fabs(a[1].r/a[3].r-dis(a[1].x,a[1].y,x1,y1)/dis(a[3].x,a[3].y,x1,y1))>eps) x1=y1=1000000;//对于第三个圆不满足
        if(fabs(a[1].r/a[3].r-dis(a[1].x,a[1].y,x2,y2)/dis(a[3].x,a[3].y,x2,y2))>eps) x2=y2=1000000;
        
        
        
        if(x1==1000000&&x2==1000000) return;
        if(x1==1000000) {printf("%.5lf %.5lf\n",x2,y2);return;}
        if(x2==1000000) {printf("%.5lf %.5lf\n",x1,y1);return;}
        //判断哪个点的sin值更大
        if(sin(a[1].r/dis(a[1].x,a[1].y,x1,y1))>sin(a[1].r/dis(a[1].x,a[1].y,x2,y2))) printf("%.5lf %.5lf\n",x1,y1);
        else printf("%.5lf %.5lf\n",x2,y2);
        
    }
    inline void solve3()
    {
        double c=d[2].c-d[1].c,dd=d[2].d-d[1].d,e=d[2].e-d[1].e;
        d[1].k=-c/dd;
        d[1].b=-e/dd;//两圆相减得到交点所在直线
        solve2();
    }
    inline void main()
    {
        for(int i=1;i<=3;++i) a[i].x=read(),a[i].y=read(),a[i].r=read();
        if(a[1].r==a[3].r) swap(a[2],a[3]);
        else if(a[2].r==a[3].r) swap(a[1],a[3]);//如果有直线,放在第一个
        if(a[1].r==a[2].r) getline(1,2,1);
        else getcir(1,2,1);
        if(a[2].r==a[3].r) getline(2,3,2);
        else getcir(2,3,2);
        
        if(d[1].v&&d[2].v) solve1();//直线直线
        else if(d[1].v&&!d[2].v) solve2();//直线圆
        else solve3();//圆圆
    }
}
signed main()
{
    red::main();
    return 0;
}
/*
50 60 70
70 80 90
100 120 130

*/

CF2

标签:注意   har   esp   clas   是否   细节   

原文:https://www.cnblogs.com/knife-rose/p/12227210.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号