2020牛客暑期多校训练营（第二场）（补题）

Boundary
链接：https://ac.nowcoder.com/acm/contest/5667/B
枚举点，然后再枚举另一点，通过圆心公式代出圆心坐标，然后求最多对于同一点A，有多少点B使得圆心同一点，答案+1即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n,ans;
double a[MAXN],b[MAXN],x,y;
typedef pair<double,double> p;
map<p,int> mx;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%lf%lf",a+i,b+i);
    for(int i=1;i<=n;i++){
        mx.clear();
        for(int j=i+1;j<=n;j++)
            if(a[i]*b[j]!=a[j]*b[i]){
                x=((b[j]-b[i])*b[i]*b[j]-a[i]*a[i]*b[j]+a[j]*a[j]*b[i])/(a[j]*b[i]-a[i]*b[j]);
                y=((a[j]-a[i])*a[i]*a[j]-b[i]*b[i]*a[j]+b[j]*b[j]*a[i])/(b[j]*a[i]-b[i]*a[j]);
                mx[p(x,y)]++;
                ans=max(mx[p(x,y)],ans);
            }
    }
    printf("%d\n",ans+1);
    return 0;
}

Duration
链接：https://ac.nowcoder.com/acm/contest/5667/D
这题非常简单，只要把时间转换为以秒为单位即可

#include<iostream> 
using namespace std;
int main(){
    int a,b,c,d,e,f;
    scanf("%d:%d:%d\n%d:%d:%d",&a,&b,&c,&d,&e,&f);
    cout<<abs(a*3600+b*60+c-d*3600-e*60-f);
    return 0; 
} 

Fake Maxpooling
链接：https://ac.nowcoder.com/acm/contest/5667/F
看了很多大佬的题解，这题的正解应该是单调队列，不过我暂时还没学到那一块，所以只好用DP来做这道题。通过打表可以发现，最大值一般出现在点的周围，故其递推关系容易得出，具体见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
typedef long long ll;
int dp[N][N];
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int n,m,k;
    ll ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)    dp[i][j]=i*j/gcd(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(k!=1)    dp[i][j]=max({dp[i][j],dp[i-1][j],dp[i][j-1]});
            else        dp[i][j]=dp[i][j];
            if(i>=k&&j>=k) ans+=dp[i][j];
        }
    printf("%lld",ans);
    return 0;
}