2021牛客暑期多校训练营2
A：Arithmetic Progression
B：Cannon
C：Draw Grids
题意：给你一个nm的区域，共有nm个点，两个人依次选两个点（a,b）,（c,d）连线，需满足|a-c|+|b-d|=1且不能构成封闭图形，判断谁赢。
思路：根据绝对值等式可以得到每人每次只能选相邻的两个点，所以我们只要判断一下总共点数的奇偶性即可
代码：
#include <iostream>
using namespace std;
int main(){
int n,m; cin>>n>>m;
if((n*m)&1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}D：Er Ba Game
思路：按题目意思模拟一下即可。
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 5e3 + 10;
int main() {
int t; cin >> t;
while(t--) {
int a1,b1,a2,b2; cin >> a1 >> b1 >> a2 >> b2;
int a=(a1+b1)%10,b=(a2+b2)%10;
if(a1>b1) swap(a1,b1);
if(a2>b2) swap(a2,b2);
if(a1==a2&&b1==b2) 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) cout << "first" << endl;
else if(a1!=b1&&a2==b2) cout << "second" << endl;
else if(a1==b1&&a2==b2) {
if(a1>a2) cout << "first" << endl;
else if(a2>a1) cout << "second" << endl;
}
else if(a1!=b1&&a2!=b2) {
if(a>b) cout <<"first" << endl;
else if(b==a)
{
if(b1>b2) cout << "first" << endl;
else if(b2>b1) cout << "second" << endl;
}
else if(b>a) cout << "second" << endl;
}
}
return 0;
}E：Gas Station
F：Girlfriend
题意：已知四个点A,B,C,D坐标和k1,k2。再告诉你还有点p1和p2且满足∣AP1∣≥k1 *∣BP1∣,∣CP2∣≥k2 *∣DP2∣,求它们在空间上的相交部分的体积。
思路：以第一个式子为例，设A（x0,y0,z0）,B(x1,y1,z1),p(x,y,z)，代入不等式展开化简可得：（）
(
)
(
)
(
)
(
)
又因为球的一般公式为:，球心坐标为
，半径为：
。
因为展开式中x、y、z的系数都相同，所以它的形状是个球。 所以这道题就转换成求两个球是否相交并输出相交的体积，一般方程里他们的系数都是1，所以我们要将化简的式子除以
，总的来说无非就内含、内切、相交三种情况。内含和内切就直接输出里面球的体积即可，如果相交的话又涉及到一个新的知识点——球冠。所谓球冠：球面被平面所截得的一部分叫做球冠。截得的圆叫做球冠的底，垂直于截面的直径被截得的一段叫做球冠的高。
球冠的体积公式为：。
如图是两球相交的一个平面图。圆心之间的距离我们用d表示，由余弦定理可得的值，
。代入上面求体积公式即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1;
const double pi = acos(-1);
double x[5],y[5],z[5];
double k1,k2;
void solve(double x1,double y1,double z1,double r1,double x2,double y2,double z2,double r2)
{
double ans=0;
//球心距离
double dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
//相离或相切
if(dis>=r1+r2){
ans=0;
}
//内含或内切
else if (dis+r1<=r2){
ans=(4.00/3.00)*pi*r1*r1*r1;
}
else if(dis+r2<=r1){
ans=(4.00/3.00)*pi*r2*r2*r2;
}
//相交
else{
double cal=(r1*r1+dis*dis-r2*r2)/(2.00*dis*r1);
//计算cos值
double h=r1*(1-cal);
ans+=(1.00/3.00)*pi*(3.00*r1-h)*h*h;
cal=(r2*r2+dis*dis-r1*r1)/(2.00*dis*r2);
h=r2*(1.00-cal);
ans+=(1.00/3.00)*pi*(3.00*r2-h)*h*h;
}
printf("%.3lf\n",ans);
}
int main(){
int t; cin >> t;
while(t--){
for(int i=0;i<4;i++)
cin>>x[i]>>y[i]>>z[i];
cin>>k1>>k2;
double tmp1=k1*k1-1;
double c1x,c1y,c1z,c1r,tmp;
c1x=(k1*k1*x[1]-x[0])/tmp1;
c1y=(k1*k1*y[1]-y[0])/tmp1;
c1z=(k1*k1*z[1]-z[0])/tmp1;
tmp=k1*k1*((x[1]*x[1])+(y[1]*y[1])+(z[1]*z[1]))-x[0]*x[0]-y[0]*y[0]-z[0]*z[0];
tmp/=tmp1;
c1r=sqrt(c1x*c1x+c1y*c1y+c1z*c1z-tmp);
double tmp2=k2*k2-1;
double c2x,c2y,c2z,c2r;
c2x=(k2*k2*x[3]-x[2])/tmp2;
c2y=(k2*k2*y[3]-y[2])/tmp2;
c2z=(k2*k2*z[3]-z[2])/tmp2;
tmp=k2*k2*((x[3]*x[3])+(y[3]*y[3])+(z[3]*z[3]))-x[2]*x[2]-y[2]*y[2]-z[2]*z[2];
tmp/=tmp2;
c2r=sqrt(c2x*c2x+c2y*c2y+c2z*c2z-tmp);
solve(c1x,c1y,c1z,c1r,c2x,c2y,c2z,c2r);
}
return 0;
}
G：League of Legens
题意：给你n个区间，将它们分为k组，保证每组的线段都相交，问k组相交部分和最大是多少。
思路：如果一个大区间包含一个小区间，那么把大区间拿出来才会是最优解，因为你添加区间相当于是添加了一个限制，所以我们先进行把所有包含小区间的大区间筛选出来，然后对剩下的小区间进行讨论。
dp[i][j]代表分了i组用了前j个区间的最优答案。对于dp[i][j],我们枚举最后一组的人数k，然后从转移，加上这一组的游戏时间取最大值。状态转移方程如下：
所以将剩下的区间按照左右端点排序，不难得出左右端点均是单调不降的。但是这些区间可能没有交集，所以我们可以用单调队列去模拟，没有交集就弹出head，直到有交集为止，然后在该点进行转移，即经典的单调队列优化，每次转移记得更新tail。 最后统计答案的时候判断一下是否需要加上大区间的贡献即可。
单调队列压入的是j-k的可能值，所以最后一组的成员应该是从j-k+1到j，所以在计算最后一组的时间时需要+1来得到最后一组的游戏结束时间。例如：tot=5，此时i=3，那么j应该从3开始枚举，因为人数要大于等于组数，所以dp[3][3]只能从dp[2][2]转移，继续往后，i=3,j=4，此时dp[3][4]可以从dp[2][2]和dp[2][3]转移，但是dp[2][2]在i=3,j=3时已经考虑过压入单调队列，也就是说j-1前可转移的dp在之间的j循环里就已经全部考虑过了，所以dp[i-1][j-1]是唯一一个需要更新到单调队列中的dp元素。
代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e4+5;
struct node{
int l,r;
}a[N],b[N];
int c[5005],q[5005],dp[5005][5005];
bool cmp(node x,node y) {
if(x.l!=y.l) return x.l<y.l;
return x.r>y.r;
}
int main()
{
memset(dp,-1,sizeof(dp));
int n,k; cin >> n >> k;
for(int i=1;i<=n;i++) {
cin >> a[i].l >> a[i].r;
}
sort(a+1,a+1+n,cmp);
int maxn=INF;
int cnt=0,tot=0;
for(int i=n;i>=1;i--) {
if(a[i].r>=maxn) {
c[++cnt]=a[i].r-a[i].l;
}
else {
maxn=a[i].r,b[++tot]=a[i];
}
}
reverse(b+1,b+tot+1);
sort(c+1,c+1+cnt,greater<int>());
dp[0][0]=0;
for(int i=1;i<=k;i++) {
int head=1,tail=0;
for(int j=i;j<=tot;j++) {
//j=i是因为人数应该要大于等于组数
if(dp[i-1][j-1]>-1) {//防止从非法解处转移
while(head<=tail&&dp[i-1][q[tail]]+b[q[tail]+1].r<=dp[i-1][j-1]+b[j].r) tail--;//维护单调队列最大值
q[++tail]=j-1;
}
while(head<=tail&&b[q[head]+1].r<=b[j].l) head++;//弹出队首直至两个区间有交集
if(head<=tail) dp[i][j]=dp[i-1][q[head]]+b[q[head]+1].r-b[j].l;
}
}
int tmp=0,ans=0;
for(int i=0;i<=min(k,n);i++) {
tmp+=c[i];
if(dp[k-i][tot]>-1) ans=max(ans,dp[k-i][tot]+tmp);
}
cout << ans << endl;
return 0;
}H：Olefin
I：Penguins
交给队里最不会写搜的我来写这道题也就我队友能干出来这种事，又是被支配的一天。
题意：给你两个20*20的图，'#'代表墙，'.'代表空格，每个图有一个企鹅一开始分别位于（20，20），（20，1），它们分别想走到（1，20），（1，1），他们同时出发且走法为镜像，即左边企鹅往左走，那么右边的企鹅就会往右走。当两只企鹅都到达各自目的地时结束。如果有多种走法输出最小步数最小且移动的字典序要最小（D<L<R<U）的那种，并将走过的路径改为A。
思路：bfs,每次移动后记录下移动后的点是从哪个点走过来的。假如左边的企鹅此时它的左边已经是墙或者是边界，但右边的企鹅需要往右走（镜像原则，左边的企鹅要往左），那么左边的企鹅将会因为路不通而待在原地。
代码：
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 5e3 + 10;
const int eps = 1e-3;
bool flag;
char s1[25][25],s2[25][25];
string p="DLRU";
int vis[25][25][25][25];//统计走到该位置用了多少步
string dir;//记录走的方向
int cnt;
int dir1[4][2]={1,0,0,-1,0,1,-1,0};//左边企鹅,方向对应string p,保证字典序最小
int dir2[4][2]={1,0,0,1,0,-1,-1,0};//哟便企鹅
struct node{
int x1,y1,x2,y2;
};
int now[25][25][25][25][5];//记录当前位置从哪个位置走来
void print()
{
cout << vis[1][20][1][1]-1<< endl;
for(int i=dir.length()-1;i>=0;i--) cout << dir[i];
cout << endl;
s1[20][20]='A'; s2[20][1]='A'; //记得最好要将出发点更新
for(int i=1;i<=20;i++) {
printf("%s ",s1[i]+1);
printf("%s\n",s2[i]+1);
}
}
int main()
{
for(int i=1;i<=20;i++) {
scanf("%s",s1[i]+1);
scanf("%s",s2[i]+1);
}
queue<node> q;
q.push({20,20,20,1});
vis[20][20][20][1]=1;
while(!q.empty()){
node tmp=q.front();
q.pop();
for(int i=0;i<4;i++){
int dx1=tmp.x1+dir1[i][0];
int dy1=tmp.y1+dir1[i][1];
int dx2=tmp.x2+dir2[i][0];
int dy2=tmp.y2+dir2[i][1];
if(dx1<1||dx1>20){
dx1-=dir1[i][0];
}
if(dy1<1||dy1>20){
dy1-=dir1[i][1];
}
if(dx2<1||dx2>20){
dx2-=dir2[i][0];
}
if(dy2<1||dy2>20){
dy2-=dir2[i][1];
}
if(s1[dx1][dy1]=='#'){
dx1-=dir1[i][0];
dy1-=dir1[i][1];
}
if(s2[dx2][dy2]=='#'){
dx2-=dir2[i][0];
dy2-=dir2[i][1];
}
if(vis[dx1][dy1][dx2][dy2])
{
continue;
}
q.push({dx1,dy1,dx2,dy2});
vis[dx1][dy1][dx2][dy2]=vis[tmp.x1][tmp.y1][tmp.x2][tmp.y2]+1;
now[dx1][dy1][dx2][dy2][0]=i;//i对应string p的下标，每个pi代表着一个方向
now[dx1][dy1][dx2][dy2][1]=tmp.x1;//记录从哪个点走来
now[dx1][dy1][dx2][dy2][2]=tmp.y1;
now[dx1][dy1][dx2][dy2][3]=tmp.x2;
now[dx1][dy1][dx2][dy2][4]=tmp.y2;
if(dx1==1&&dy1==20&&dx2==1&&dy2==1){//两只企鹅都到目的地时更新地图 ,
int a=1,b=20,c=1,d=1; // 将走过的路径改为'A'
while(a!=20||b!=20||c!=20||d!=1) {//相当于倒着将最短路径走一边，直到返回出发点
s1[a][b]='A';//更新地图
s2[c][d]='A';
dir+=p[now[a][b][c][d][0]];
int a1=now[a][b][c][d][1];
int b1=now[a][b][c][d][2];
int c1=now[a][b][c][d][3];
int d1=now[a][b][c][d][4];
a=a1,b=b1,c=c1,d=d1;
}
print();
flag=1;
break;
}
}
}
if(!flag) cout << -1 << endl;
return 0;
}J：Product of GCDs
K：Stack
题意：含有n个数的序列a，现在将a中元素入栈，每次入栈将栈顶大于ai的弹出，bi代表栈的大小。现在告诉你部分bi，求出满足题意的序列a。
思路：
先记录下每个位置的栈中元素个数，然后从1-n遍历一遍，如果该位置元素个数为0，则该位置元素个数为上一个位置元素个数+1，如果该位置个数大于上一个上一个位置元素个数，不符合题意直接输出-1。否则，我们从后往前遍历，把1，2，3，4，5······按递增顺序放入栈里，因为单调栈元素中的数量代表的是递增数字的数量，当加入数字后的个数等于栈中元素数量的时候，就直接把数字当做该点的值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int a[N],st[N],b[N];
int flag;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n,k; cin >> n >> k;
for(int i=1;i<=k;i++) {
int x; cin >> x >>b[x];
}
for(int i=1;i<=n;i++) {
if(b[i]==0) {
b[i]=b[i-1]+1;
}
else
{
if(b[i]>b[i-1]+1) {
cout << -1 << endl;
return 0;
}
}
//cout << "ceshi: " << a[i] <<" ";
}
//cout << endl;
//for(int i=1;i<=n;i++) cout << a[i] << " "; cout << endl;
int cnt=0,top=0;
for(int i=n;i>=1;i--) {
while(b[i]>top)
{
top++;
cnt++;
st[top]=cnt;
}
a[i]=st[top];
top--;
}
for(int i=1;i<=n;i++) cout << a[i] << " ";
cout << endl;
return 0;
} L：WeChat Walk
哔哩哔哩三面6人在聊