多校 2009 2-白红宇

多校 2009 2

阅读量：4467 次

发布时间：2019-06-08

本文共 5727 字，大约阅读时间需要 19 分钟。

n 然后 n 个点然后n个点

问 2个多边形是不是相似的

1 极角排序 2 判断边长度成比例 3 对应的角度好像没来卡精度

#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std ;#define ll __int64#define MAXN 310#define inf  1000000007#define exp  1e-8struct point{    public:        int x,y;        int operator ^ (point b)        {            return x*b.y-y*b.x;        }        point operator -(point b)        {            point c;            c.x=x-b.x;            c.y=y-b.y;            return c;        }}s1[MAXN],s2[MAXN];double dis(point a,point b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool cmp1(point a,point b){    int tmp=((a-s1[1])^(b-s1[1]));    if(tmp>0)        return 1;    if(tmp==0&&dis(a,s1[1])
           
            0) return 1; if(tmp==0&&dis(a,s2[1])
            
             exp) ok=1; } for(int i=1;i<=n;i++) { double a1,a2,a3,b1,b2,b3,c1,c2; a1=dis(s1[i],s1[i-1]); a2=dis(s1[i],s1[i+1]); a3=dis(s1[i-1],s1[i+1]); c1=(a1*a1+a2*a2-a3*a3)/(2*a1*a2); b1=dis(s2[i],s2[i-1]); b2=dis(s2[i],s2[i+1]); b3=dis(s2[i-1],s2[i+1]); c2=(b1*b1+b2*b2-b3*b3)/(2*b1*b2); if(fabs(c1-c2)>exp) ok=1; } if(ok==1) printf("No\n"); else printf("Yes\n"); } } return 0;}

View Code

给你n*m 的 0 1 矩阵可以交换任意2列

求最大子矩阵矩阵内部都是1

1 num[i] 第i列连续下来的1的个数

0 num[i]=0 具体看代码

#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std ;#define ll __int64#define MAXN 1010#define inf  1000000007#define exp  1e-8char z[MAXN][MAXN];int num[MAXN],sum[MAXN];bool cmp(int a,int b){    return a>b;}int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=1;i<=n;i++)            scanf("%s",z[i]+1);        memset(num,0,sizeof(num));        memset(sum,0,sizeof(sum));        int ans=0;        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                if(z[i][j]=='1')                    num[j]++;                else                    num[j]=0;  //不能连续就清零                sum[j]=num[j];            }            sort(sum+1,sum+m+1,cmp);            for(int j=1;j<=m;j++)                 ans=max(ans,j*sum[j]);  //前面的都比这个长  而且是上面连续下来的        }        printf("%d\n",ans);    }    return 0;}

View Code

n个僵尸豌豆的cd

然后僵尸的时间 hp

打hp的时间就能打死一排只能放一个豌豆

按剩下的时间排序走的时间-hp 其他不对

#include 
      
       #include
       
        #include
        
         #include
         
          using namespace std ;#define ll __int64#define MAXN 30100#define mod 200907struct node{    int v,hp,ind;}z[MAXN];bool cmp(node a,node b){    int a1,b1;    a1=a.v-a.hp;    b1=b.v-b.hp;    return a1
          
           z[i].v)                ok=1;        }        if(ok==1)            printf("The zombies eat your brains!\n");        else        {            for(int i=1;i

View Code

长度为 100cm

一只蜗牛每秒走 k cm 走完了1s 人就会把跑道拉长100cm 但是终点和当前蜗牛的位子的比例不变然后继续上面的操作问什时候走到终点卡精度

调和级数n 1/1+1/2 + 1/3 ... +1/n = ln(n)+c + 1/(2*n) n >10000 c=0.57721566490153286060651209 好像叫欧拉常数

反正卡精度了

#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std ;#define ll __int64#define MAXN 30100#define c  0.57721566490153286060651209#define inf  1000000007int main(){    int k;    while(scanf("%d",&k)!=EOF)    {        if(k<=10)        {            int l=1,r=inf,ans;            ans=inf;            while(l<=r)            {                int mid=(l+r)>>1;                if(k*(log(mid)+c+1.0/(2*mid))/100>=1)                {                    r=mid-1;                    ans=min(ans,mid);                }                else                    l=mid+1;            }            printf("%d\n",ans);        }        else        {            int i=1;            double ans=0;            while(1)            {                ans=ans+1.0*k/i;                if(ans>=100)                    break;                i++;            }            printf("%d\n",i);        }    }    return 0;}

View Code

n个点 m条无向边

u v w

然后起点1 终点1 起点2 终点2

问起点1 -> 终点1 起点2->终点2

他们的最短路径中相同的点最多有多少个

相同的点的是连续的可以去画一画

然后floyd 求最短路z[i][j] 然后求出 dp[i][j] i 到j 经历最多点的数目

最后呢列举 i j

s1 - > i -> j -> e1 s2->i ->j ->e2

只要是最短路的那么ans =min(ans,dp[i][j]);

#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std ;#define ll __int64#define MAXN 1010#define inf  1000000007#define exp  1e-8int  z[MAXN][MAXN];int dp[MAXN][MAXN];// 给定一个无向图，和两对起点终点，求两条最短路上的最多公共交点数。int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0&&m==0)            break;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)            {                 if(i==j)                {                    dp[i][j]=1;                    z[i][j]=0;                }                else                {                    dp[i][j]=2;                    z[i][j]=inf;                }            }        for(int i=1;i<=m;i++)        {            int a,b,c;            scanf("%d%d%d",&a,&b,&c);            z[a][b]=z[b][a]=min(z[a][b],c);        }        for(int k=1;k<=n;k++)        {            for(int i=1;i<=n;i++)            {                for(int j=1;j<=n;j++)                {                    if(z[i][j]>z[i][k]+z[k][j])                    {                        z[i][j]=z[i][k]+z[k][j];                        dp[i][j]=dp[i][k]+dp[k][j]-1;                    }                    else if(z[i][j]==z[i][k]+z[k][j]&&dp[i][j]