2020牛客暑期多校训练营2

B Boundary

对于圆而言有三点定圆定理和相关公式。

其中x0，y0坐标为圆心坐标。
我们利用三点定圆定理求出的圆心坐标来判断是否点在同一圆上。

除开原点，每次确定圆还需要两个点。若圆上除了原点还有N个数据点，那么每个数据点都能和其他(N-1)个点确定这个圆，那么我们通过两个点确定的圆心数和圆上的点数有这样的关系。
C(N,2) *(圆上的点的数量) = 圆心的重复出现的次数。

其实比赛是可以做出来的，因为思维固化习惯性用STL（map），忘记了sort，超时。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6 + 5;
const double eps = 1e-8;
typedef struct Point{
    double x,y;
    bool operator <(const Point & pp){
        if(fabs(x-pp.x)>eps)return x - pp.x > eps;
        if(fabs(y-pp.y)>eps)return y - pp.y > eps;
    }
}P;
int num[maxn];
double a,b,c,d,f,e;
int N,cnt= 0;
P p[5000];
double pro[maxn];
P rp[maxn];
void init(){
    for(int i = 1;i <= 2000;i++){
        num[i*(i-1)/2] = i;
    }
}
int main(){
    init();
    cin >> N;
    for(int i = 1;i <= N;i++){
        cin >> p[i].x >> p[i].y;
    }
    if(N<=1){
        cout << N <<endl;   
    }
    else {
    for(int i = 1;i <= N-1;i++){
        a = -p[i].x;b = -p[i].y;
        for(int j = i+1;j <= N;j++){
            if(p[i].x*p[j].y==p[j].x*p[i].y)continue;
            c = -p[j].x;d = -p[j].y;
            e = -(p[i].x*p[i].x+p[i].y*p[i].y)/2;
            f = -(p[j].x*p[j].x+p[j].y*p[j].y)/2;
            ++cnt;
            rp[cnt].x = -(d*e - b*f)/(b*c - a*d);
            rp[cnt].y = -(a*f - c*e)/(b*c - a*d);
          
        }
    }
    sort(rp + 1, rp+1+cnt);
    P sp;
    int tot = 0;
    int ans = 0;
    sp.x = rp[1].x;sp.y = rp[1].y;
    for(int i = 1;i <= cnt;i++){
       if(fabs(sp.x-rp[i].x)<=eps&&fabs(sp.y-rp[i].y)<=eps)tot++;
       else {
           ans = max(ans,tot);
           tot = 1;
           sp.x = rp[i].x;sp.y = rp[i].y;
       }
    }
      ans = max(ans,tot);
      cout << num[ans]<<endl;
    }
    return 0;
}

---

J Just Shuffle

本题就是用按照题目要求用单调对列把k * k的矩阵压缩，第一次压缩成了1 * k，第二次就成了1 * 1的矩阵，即是答案。

最开始我觉得lcm可能是突破点，是一个规律，很可惜没有找到。
其实这题很类似去年牛客多校的部分题，不过那些题是单调栈，这就是单调对列。感觉暴力可以过，就STL暴力，卡了小部分样例。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+5;
int N,M,K;
typedef long long ll;

int Max[maxn][maxn],lcm[maxn][maxn];
int que[maxn];

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

void Init(){
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= M;j++){
             if(lcm[i][j]==0){
                 lcm[i][j] = i/(gcd(i,j))*j;
                 lcm[j][i] = lcm[i][j];
             }
        }
    }
}

void test(){
    for(int i = 1;i <= N;i++){
        for(int j = K;j <= M;j++){
            cout << Max[i][j]<<" ";
        }
        cout <<endl;
    }
}
int main(){
    cin >> N >> M >>K;
    Init();
    int fro,re,i,j;
    for(i = 1;i <= N;i++){
        fro = 1;re = 0;
        for(j = 1;j <= K;j++){
            que[++re] = lcm[i][j];
            while((re>fro&&que[re]>=que[fro])||j-fro>=K)fro++;
        }
        Max[i][j-1] = que[fro];
        for(;j<=M;j++){
            que[++re] = lcm[i][j];
            while((re>fro&&que[re]>=que[fro])||j-fro>=K)fro++;
            Max[i][j] = que[fro];
        }
        
    }
    ll ans = 0;
    for(j = K;j <= M;j++){
         fro = 1;re = 0;
        for(i = 1;i <= K;i++){
            que[++re] = Max[i][j];
            while((re>fro&&que[re]>=que[fro])||i-fro>=K)fro++;
        }
        ans += 1ll*que[fro];
        for(;i<=N;i++){
            que[++re] = Max[i][j];
            while((re>fro&&que[re]>=que[fro])||i-fro>=K)fro++;
            ans += 1ll*que[fro];
        }
    }
    cout << ans <<endl;
    return 0;
}