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

Boundary
思路：枚举每两个点，算出圆心的坐标，比较得到圆心出现最多的次数即可，当两点斜率相同说明这两点一定不在同一圆上。

#include<iostream>
using namespace std;
#include<map>
#include<algorithm>
double x[2010],y[2010];
map<pair<double,double>,int>mp;
int ans=0;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
       scanf("%lf%lf",&x[i],&y[i]);
    for(int i=0;i<n;i++)
    {
        mp.clear();
        for(int j=i+1;j<n;j++)
        {
            if(x[i]*y[j]==x[j]*y[i]) continue;
            double xx = ((y[j]-y[i])*y[i]*y[j]-x[i]*x[i]*y[j]+x[j]*x[j]*y[i])/(x[j]*y[i]-x[i]*y[j]);
            double yy = ((x[j]-x[i])*x[i]*x[j]-y[i]*y[i]*x[j]+y[j]*y[j]*x[i])/(y[j]*x[i]-y[i]*x[j]);
            mp[{xx,yy}]++;
            ans=max(ans,mp[{xx,yy}]);
        }
    }
    printf("%d",ans+1);
    return 0;
}

Fake Maxpooling
思路：易证从i=1，j=1开始，每个kxk子矩阵的最大数一定大于等于前一个子矩阵，距此每次将矩阵的的数与上一行，上一列的数进行比较，取出最大数相加即可。

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 5010;
int dp[5010][5010] = { 0 };
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int m, n, k;
    long long ans=0;
    scanf("%d%d%d",&n,&m,&k);
 for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!dp[i][j])
            {dp[i][j]=i*j/gcd(i,j);
             dp[j][i]=dp[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]});
            if(i>=k&&j>=k) {ans+=dp[i][j];
                           }
                           }
    printf("%lld",ans);
    return 0;
}