2021牛客暑期多校训练营2

C

给你n*m的网格，每一次可以横的或者竖的连接两个相邻的两个格点，轮流操作，连接的过程中不能有封闭图形，问最后先手赢还是后手赢

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;cin>>n>>m;
    if(n>m){int x=n;n=m;m=x;}
    int ans=m*n-1;
    if(ans%2)puts("YES");
    else puts("NO");
}

数据其实可以出的大一点。

D

比牌的大小，(2,8)最大，a=b仅次，两个人的两张牌都相等，比较(a+b)%10的大小，
如果还是相等，比较b的大小，a,b可以交换，即a为小的那个牌，b为更大的牌。问第一个赢还是第二个。

if,else语句。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a1,b1,a2,b2;
    int t;
    cin>>t;
    while(t--){
        cin>>a1>>b1>>a2>>b2;
        if(a1>b1) swap(a1,b1);
        if(a2>b2) swap(a2,b2);
        if(a1==2&&b1==8&&a2==2&&b2==8) cout<<"tie"<<endl;
        else{
            if(a1==2&&b1==8) cout<<"first"<<endl;
            else if(a2==2&&b2==8) cout<<"second"<<endl;
            else{
                if(a1==b1&&a2==b2){
                    if(a1==a2) cout<<"tie"<<endl;
                    if(a1>a2) cout<<"first"<<endl;
                    if(a1<a2)  cout<<"second"<<endl;
                }
                else if(a1==b1) cout<<"first"<<endl;
                else if(a2==b2) cout<<"second"<<endl;
                else {
                    int a=(a1+b1)%10;
                    int b=(a2+b2)%10;
                    if(a>b) cout<<"first"<<endl;
                    else if(a<b) cout<<"second"<<endl;
                    else {
                        if(b1>b2) cout<<"first"<<endl;
                        else if(b1<b2) cout<<"second"<<endl;
                        else cout<<"tie"<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

E

求两个球相交的部分的体积

题解参考大佬大哥

推一波式子：

对于第一个圆，设P的坐标为 $(x,y,z)$ ;

A,B,C,D坐标分别为 $(x1,y1),(x2,y2),(x3,y3),(x4,y4)$ ;

那么就有：
$图片说明$

移项，合并，之后：

$图片说明$

球的一般方程：

$图片说明$

球的标准方程：

$图片说明$

圆心 $O(-a,-b,-c)$

半径: $图片说明$

那有了这些之后我们又该如何求相交部分的体积呢?
来源于：https://blog.csdn.net/ouyangcheese/article/details/115421270

当然也可以自己推，（懒）

图片说明

公式：
$图片说明$

比赛时候以为是二重积分啥的，想了半天高数公式，发现不会，坐牢一下午，还不如百度一下公式。（bushi）

啥也不是

代码：

#include<bits/stdc++.h>
using namespace std;

const double pi = acos(-1);//圆周率

double x[10],y[10],z[10];
double k1,k2;

int main(){
    //freopen("in.txt", "r", stdin);
     //freopen("test.txt", "w", stdout);
    int T;
    cin>>T;
    while(T--){
        for(int i=1;i<=4;i++){
            cin>>x[i]>>y[i]>>z[i];
        }
        cin>>k1>>k2;
        //计算第一个圆 
        double xx1=k1*k1-1;
        double c1x,c1y,c1z,c1r,d;
        c1x=(k1*k1*x[2]-x[1])/xx1;//求圆心
        c1y=(k1*k1*y[2]-y[1])/xx1;
        c1z=(k1*k1*z[2]-z[1])/xx1;
        d=k1*k1*(x[2]*x[2]+y[2]*y[2]+z[2]*z[2])-x[1]*x[1]-y[1]*y[1]-z[1]*z[1];
        d/=xx1;
        c1r=sqrt(c1x*c1x+c1y*c1y+c1z*c1z-d);//求半径
        //cout<<c1x<<" "<<c1y<<" "<<c1z<<" "<<d<<" "<<c1r<<endl;
        //计算第二个圆 
        double xx2=k2*k2-1;
        double c2x,c2y,c2z,c2r,dd;
        c2x=(k2*k2*x[4]-x[3])/xx2;
        c2y=(k2*k2*y[4]-y[3])/xx2;
        c2z=(k2*k2*z[4]-z[3])/xx2;
        dd=k2*k2*(x[4]*x[4]+y[4]*y[4]+z[4]*z[4])-x[3]*x[3]-y[3]*y[3]-z[3]*z[3];
        dd/=xx2;
        c2r=sqrt(c2x*c2x+c2y*c2y+c2z*c2z-dd);
        //cout<<c2x<<" "<<c2y<<" "<<c2z<<" "<<dd<<" "<<c2r<<endl;
        //求答案
        double ans=0;
        double dis=sqrt((c1x-c2x)*(c1x-c2x)+(c1y-c2y)*(c1y-c2y)+(c1z-c2z)*(c1z-c2z));
        if(dis>=c1r+c2r){//外切或者相离，0
            ans=0;
        }
        else if(c1r+dis<=c2r){//内含，两种情况，答案为体积小的那个球
            ans=(4.00/3.00)*pi*c1r*c1r*c1r;
        }
        else if(c2r+dis<=c1r){
            ans=(4.00/3.00)*pi*c2r*c2r*c2r;
        }
        else{//相交
            double cal=(c1r*c1r+dis*dis-c2r*c2r)/(2.00*dis*c1r);
            double h=c1r*(1-cal);
            ans+=(1.00/3.00)*pi*(3.00*c1r-h)*h*h;
            cal=(c2r*c2r+dis*dis-c1r*c1r)/(2.00*dis*c2r);
            h=c2r*(1.00-cal);
            ans+=(1.00/3.00)*pi*(3.00*c2r-h)*h*h;
        }
        printf("%.3f\n",ans);
    }
}

K

给定一段伪代码，

Stk is an empty stack
for i = 1 to n :
    while ( Stk is not empty ) and ( Stk's top > a[i] ) : 
        pop Stk
    push a[i]
    b[i]=Stk's size

当栈顶的元素大于 $a[i]$ ,则弹出栈顶元素， $b[i]$ 等于当前栈的大小。
现在给你若干个b数组的几个数，构造一个数组a，数组a只能是 $1-n$ 中的数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
#define debug(x) cout << #x << ": " << x << endl;
int a[N],b[N]; 
stack<int> st;
int main(){
    int n,k;
    cin>>n>>k;
    int x;
    for(int i=0;i<k;i++){
        cin>>x>>b[x];
    }//先构造b数组，
    for(int i=1;i<=n;i++){
        if(!b[i]) b[i]=b[i-1]+1;
        if(b[i]>b[i-1]+1){//一次只能push进去一个元素，所以最多，b[i]<=b[i-1]+1;
            puts("-1");
            return 0;
        }
    }
    int cnt=1;
//通过B数组，反过来模拟构造a数组。
//从后面开始填
    for(int i=n;i>=1;i--){
        while(b[i]>st.size()) st.push(cnt++);//构造没有pop之前的数组，有pop停止，最后的数就是数组a后面的数
        a[i]=st.top();
        st.pop();
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

I

两个企鹅，一个在左边的地图，一个在右边的图，两只企鹅同时走，左边的企鹅往左，右边的企鹅往右，左往右，右往左，但是上下移动时，两边都一样。一只企鹅不能走，另一只能走，则一只停下，另一只继续往前。一只到了终点，如果另一个动了，到了终点的一样还是会走。问两个企鹅都到达终点时，求最短路径步数，并输出路径。

模拟，把两个企鹅看成一个状态点，用一个结构体表示

struct node{
    int ax,ay,bx,by;//a企鹅，b企鹅
    string s;//记录答案
};

代码：

参考江大佬的代码，自己写了一遍。
debug了好久，落泪

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30;
#define debug(x) cout << #x << ": " << x << endl;
char a[N][N],b[N][N];

struct node{
    int ax,ay,bx,by;
    string s;
};
//DLRU,保证字典序最大 
int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};
bool vis[N][N][N][N];//因为是把两个企鹅看成一个状态，走过了这个状态就标记，跟一般BFS模板题一样，比赛时候觉得代码太长了，没敢下手，落泪。太菜了。

bool chk(int x,int y,char a[][N]){
    if(x>20||x<=0||y<=0||y>20||a[x][y]=='#') return true;
    return false;
}

//上下左右，四个方向都判断一遍，能走就加入队列。
node getD(node t){
    t.ax+=dx[0],t.ay+=dy[0];    
    if(chk(t.ax,t.ay,a)) t.ax-=dx[0],t.ay-=dy[0];
    t.bx+=dx[0],t.by+=dy[0];    
    if(chk(t.bx,t.by,b)) t.bx-=dx[0],t.by-=dy[0];
    t.s+='D';
    return t;
}

node getL(node t){
    t.ax+=dx[1],t.ay+=dy[1];    
    if(chk(t.ax,t.ay,a)) t.ax-=dx[1],t.ay-=dy[1];
    t.bx+=dx[2],t.by+=dy[2];    
    if(chk(t.bx,t.by,b)) t.bx-=dx[2],t.by-=dy[2];
    t.s+='L';
    return t;
}

node getR(node t){
    t.ax+=dx[2],t.ay+=dy[2];    
    if(chk(t.ax,t.ay,a)) t.ax-=dx[2],t.ay-=dy[2];
    t.bx+=dx[1],t.by+=dy[1];    
    if(chk(t.bx,t.by,b)) t.bx-=dx[1],t.by-=dy[1];
    t.s+='R';
    return t;
}

node getU(node t){
    t.ax+=dx[3],t.ay+=dy[3];    
    if(chk(t.ax,t.ay,a)) t.ax-=dx[3],t.ay-=dy[3];
    t.bx+=dx[3],t.by+=dy[3];    
    if(chk(t.bx,t.by,b)) t.bx-=dx[3],t.by-=dy[3];
    t.s+='U';
    return t;
}

string  bfs(){
    queue<node>q;
    node start,next;
    start={20,20,20,1,""};
    q.push(start);
    vis[20][20][20][1]=1;
    while(!q.empty()){
        start=q.front();
        q.pop();
        if(start.ax==1&&start.ay==20&&start.bx==1&&start.by==1) return start.s;
//        debug(start.ax);
//        debug(start.ay);
//        debug(start.bx);
//        debug(start.by);
//        debug(start.s);
        next=getD(start);
        if(!vis[next.ax][next.ay][next.bx][next.by]){
            vis[next.ax][next.ay][next.bx][next.by]=1;
            q.push(next);
        } 
        next=getL(start);
        if(!vis[next.ax][next.ay][next.bx][next.by]){
            vis[next.ax][next.ay][next.bx][next.by]=1;
            q.push(next);
        } 
        next=getR(start);
        if(!vis[next.ax][next.ay][next.bx][next.by]){
            vis[next.ax][next.ay][next.bx][next.by]=1;
            q.push(next);
        } 
        next=getU(start);
        if(!vis[next.ax][next.ay][next.bx][next.by]){
            vis[next.ax][next.ay][next.bx][next.by]=1;
            q.push(next);
        } 
    }
    return "";
}





int main(){;
    for(int i=1;i<=20;i++) scanf("%s", a[i] + 1), scanf("%s", b[i] + 1);
    //for(int i=1;i<=20;i++) printf("%s ", a[i] + 1), printf("%s\n", b[i] + 1);
    string ans=bfs();
    cout<<ans.size()<<endl;
    cout<<ans<<endl;
    node t={20,20,20,1,""};
    for(auto c:ans){//重新进入再走一遍，把路径覆盖成“A”
        a[t.ax][t.ay]='A';
        b[t.bx][t.by]='A';
        if(c=='D') 
        t=getD(t);
        else if(c=='L'){
            t=getL(t);
        }
        else if(c=='R'){
            t=getR(t);
        }
        else t=getU(t);
    }
    a[1][20]='A',b[1][1]='A';
    for(int i=1;i<=20;i++) printf("%s ", a[i] + 1), printf("%s\n", b[i] + 1);//输出
}