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