2021牛客暑期多校训练营2

比赛地址

C题 Draw Grids 题目地址

题目大意:给定一个 的点阵,每次选两个相邻点连线。两个人轮流操作,不能连出封闭图形,不能操作者输。

不是封闭图形,就是最小生成树,计算点的奇偶。
代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if((a*b)%2)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}

D题 Er Ba Game 题目地址

题目大意:模拟题。

代码

#include <bits/stdc++.h>
using namespace std;
int t,a1,b1,a2,b2;
int sum1,sum2;
int main()
{
   cin>>t;
   while(t--)
   {
       cin>>a1>>b1>>a2>>b2;
       sum1=a1+b1;
       sum2=a2+b2;
       int l=max(a1,b1);
       int l1=min(a1,b1);
       int l2=max(a2,b2);
       int l3=min(a2,b2);
       a1=l1;b1=l;a2=l3;b2=l2;
       if(a1==2&&b1==8)
       {
           if(a2==2&&b2==8)
            printf("tie\n");
           else
            printf("first\n");
       }
       else if(a1==b1)
       {
           if(a2==2&&b2==8)
            printf("second\n");
           else if(a2==b2)
           {
               if(a1>a2)
                printf("first\n");
               else if(a1==a2)
                printf("tie\n");
               else if(a1<a2)
                printf("second\n");
           }
           else if(a2!=b2)
            printf("first\n");
       }
       else if(a1!=b1)
       {
           if(a2==2&&b2==8)
            printf("second\n");
           else if(a2==b2)
            printf("second\n");
           else if((sum1%10)>(sum2%10))
            printf("first\n");
           else if((sum1%10)==(sum2%10))
           {
               if(b1>b2)
                printf("first\n");
               else if(b1==b2)
                printf("tie\n");
               else if(b1<b2)
                printf("second\n");
           }
           else if((sum1%10)<(sum2%10))
            printf("second\n");
       }
   }
    return 0;
}

F题 Girlfriend 题目地址

题目大意:空间内有六个点,满足 。求 各自轨迹围成的空间体的体积交。

阿波罗尼斯圆,求两个球的体积交。
代码

#include <bits/stdc++.h>
using namespace std;
int t;
double pi=acos(-1);
double a[4],b[4],c[4],d[4];
double k1,k2;
int main()
{
    cin >>t;
    while(t--)
    {
        cin>>a[1]>>a[2]>>a[3];
        cin>>b[1]>>b[2]>>b[3];
        cin>>c[1]>>c[2]>>c[3];
        cin>>d[1]>>d[2]>>d[3];
    cin>>k1>>k2;
    double aa=sqrt((a[1]-b[1])*(a[1]-b[1])+(a[2]-b[2])*(a[2]-b[2])+(a[3]-b[3])*(a[3]-b[3]));
    double an1=aa*fabs(k1/(k1+1)-k1/(k1-1))/2;
    double  x1=a[1]+(b[1]-a[1])*(k1/(k1+1)+k1/(k1-1))/2;
        double y1=a[2]+(b[2]-a[2])*(k1/(k1+1)+k1/(k1-1))/2;
        double z1=a[3]+(b[3]-a[3])*(k1/(k1+1)+k1/(k1-1))/2;
    double bb=sqrt((c[1]-d[1])*(c[1]-d[1])+(c[2]-d[2])*(c[2]-d[2])+(c[3]-d[3])*(c[3]-d[3]));
    double an2=bb*fabs(k2/(k2+1)-k2/(k2-1))/2;
        double x2=c[1]+(d[1]-c[1])*(k2/(k2+1)+k2/(k2-1))/2;
        double y2=c[2]+(d[2]-c[2])*(k2/(k2+1)+k2/(k2-1))/2;
        double z2=c[3]+(d[3]-c[3])*(k2/(k2+1)+k2/(k2-1))/2;
    double ans=0;
    double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
            if (d>=an1+an2) {

            }
            else if (d+an1<=an2) {

                ans=(4.0/3.0)*pi*an1*an1*an1;
            }
            else if(d+an2<=an1)
            {
                ans=(4.0/3.0)*pi*an2*an2*an2;
            }
            else {
                double h1=an1-an1*((an1*an1+d*d-an2*an2)/(2.0*an1*d));
                double h2=an2-an2*((an2*an2+d*d-an1*an1)/(2.0*an2*d));

            ans=pi*(an1*3.0-h1)*h1*h1/3.0+pi*(an2*3.0-h2)*h2*h2/3.0;
            }
            printf("%.3lf\n",ans);
        }
}

K题 Stack 题目地址

题目大意:已知若干时刻的单调栈大小,构造一个合法序列。

思路:

拓扑排序没弄明白,直接从后面构造,貌似也可以。
代码:

#include <bits/stdc++.h>
using namespace std;
int b[1000100];
set<int> a;
int n,k;
struct aa
{
    int a,b,c;
}c[1000100];
bool cmp(aa a,aa b)
{
    return a.a<b.a;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d",&c[i].a,&c[i].b);
    }
    sort(c+1,c+1+k,cmp);
    for(int i=1;i<=n;i++)
    {
        a.insert(i);
    }
    int num=c[k].b;
    int nn=0;
    int f=0;
    int maxx=0;
    for(int i=k;i>=1;i--)
    {
        if(c[i-1].a-c[i-1].b<0)
        {
            f=1;
            break;
        }
    //    cout<<"qq"<<endl; 
        if(c[i].a-c[i].b<0)
        {
            f=1;
            break;
        }
    //    cout<<"qqq"<<endl;
        int pp=c[i].a-c[i].b-(c[i-1].a-c[i-1].b);
        if(pp<0)
        {
            f=1;
            break;
        }
    //    cout<<"qqaq"<<endl;
        if(b[c[i].a])
        {
            f=1;
            break;
        }

    //    cout<<"qqqaa"<<endl;
        if(c[i].b==c[i+1].b) 
        {
            b[c[i].a]=*(a.upper_bound(b[c[i+1].a]-1));
            a.erase(b[c[i].a]);
        }
        else
        {
            b[c[i].a]=*(a.upper_bound(c[i].b-1));
            a.erase(b[c[i].a]);

        }
        maxx=max(maxx,b[c[i].a]);
        int nn=b[c[i].a];
        if(i!=k)
        for(int j=c[i].a+1;j<c[i+1].a&&j<=n;j++)
        {
            if(b[j]==0)
            {
                nn++;
                if(nn<b[c[i+1].a])
                {
                    b[j]=nn;
                    a.erase(nn);
                    maxx=max(maxx,nn);
                }
                else break;
            }
        }
        if(f==1)
        break;
    /*    for(int j=1;j<=n;j++)
        {
                cout<<b[j]<<" ";
        }    
        cout<<endl;*/
    }
    if(f==0)
    {
        for(int i=1;i<=c[1].a;i++)
        {
            if(i<c[1].b)
            {
                b[i]=i;
                maxx=max(maxx,i);
            }
        }
    }

    if(f==0)
    {
        for(int i=1;i<=n;i++)
        {
            if(b[i]==0)
            {
                maxx++;
                b[i]=maxx;
                if(maxx>n)
                {
                    f=1;
                }
            }
        }
    }

    if(f==1)
    {
        cout<<-1<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
                cout<<b[i]<<" ";
        }    
        cout<<endl;
    }


}