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; } }