2023年（GPLT）上海理工大学校内选拔赛（同步赛) 部分题目 题解_gplt官方考点

本人大一，说来惭愧，这比赛只做出来了两道题；（特此来写几篇题解）

第一道讲解的题目是 C题 也就是N皇后的；

当时没做出来 赛后看了很多人的题解也都是大同小异：但是我从来都没有见过（特此拿来整理一下）

思路：本题的关键就是如何不通过暴力模拟的方法（也就是直接开一个map的二维数组）实现记录每个皇后棋子的攻击范围，皇后的攻击路径有两种，一种是横冲直撞的（每一行 每一列都会受到攻击）（这种我们直接可以使用两个一维数组记录下攻击的行和列） 第二种是歪来斜去的（当时就是卡在这里，不理解这个到底怎么实现）。但是实际上就是，在两个方向的某一个方向上 的X和Y相加为一个定值并且每个不相交的同向的斜线的网格点上的定值互不相同，在另一个方向上，X和Y的差值的绝对值也是唯一特征的！！！

所以代码就很简单啦：

#include <bits/stdc++.h>
 
using namespace std;
int a[1001000],b[1001000],c[2001000],d[2001000];
//别人的代码 不得不说真的是太厉害了
//关键点在于使用不同的方式唯一表示出 每两个方向上的斜线的表示！！
 
//也就是如何特征化的表示数据
 
 
int main()
{
    int n,t;
    cin >> n>> t;
    int x,y;
    for(int i=1; i<=t; i++)
    {
        scanf("%d %d",&x,&y);
        if(a[x]==0&&b[y]==0&&c[x-y+n]==0&&d[x+y]==0)
        {
            a[x]++;
            b[y]++;
            c[x-y+n]++;
            d[x+y]++;
            printf("Yes\n");
        }
        else
        {
           printf("No\n");
        }
 
    }
    return 0;
}

第二题是

这道题很明显是个签到题，说真的做不出来就真的很尬。

首先是当时没理解清楚题意，我一直不清楚案例当中是怎么做出9来的？

后来（比赛过后） 才看懂（笨）：1 1 2 2 3的首先每个i 与 j可以是相等的 也就是说 先就有5个对子，然后是 <1,2> <2,1>  <3,4> <4,3>这四个就这样emm

#include <bits/stdc++.h>
 
using namespace std;
long long a[200000];
int main ()
{
    int n,maxt=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        a[temp]++;
    }
    long long ans=0;
    for(int i=0;i<=200000;i++)
    {
        ans+=a[i]*(a[i]-1);
    }
    ans+=n;
    cout<<ans<<endl;
    return 0;
}

第三道题是D题 

DA:(

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
 
typedef long long ll;
 
ll n1,n2,n3,n4;
int main(){
    
    multiset<int> s;
    ll n;
    cin>>n;
    ll x,y,c;
    ll xx,yy,cc;
    cin>>x>>y>>c;
    cin>>xx>>yy>>cc;
    for(int i=1;i<=n;i++){
        ll  a,b;
        cin>>a>>b;
        if(a*x+c>=-1ll*b*y){
            if(a*xx+cc>=-1l*b*yy){
                n1++;
            }else{
                n2++;
            }
        }else{
            if(a*x+c<-1l*b*y){
                if(a*xx+cc>=-1l*b*yy){
                    n3++;
                }else{
                    n4++;
                }
            }
        }
    }
    s.insert(n1);
    s.insert(n2);
    s.insert(n3);
    s.insert(n4);
    for(multiset<int>::iterator i=s.begin();i!=s.end();i++){
        cout<<*i<<" ";
    }
    return 0;
}

这个我当时是卡在了 if的判断中 

现在可以思考一下if（a*x+c<-1l*b*y) 和 if(a*xx+cc+bb*y<0) 这两个有什么区别？

其实就会发现a b x y 这些乘积加起来非常大 很有可能会爆long long所以必须要避免的话，可以使用这样的方式！（就是写在两边）

其实还有像F E题之类的，也是值得细讲的。现在太晚了，还是先睡吧！

00点35分 2023年3月13日