B.Boundary

题解：n^2求出x、y以及原点三点的外接圆心，找到圆心数量最多的maxn，求maxn=(x-1)*x,解出方程即可，主要是要特判三点共线的情况以及精度问题

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1)
const int maxn=2e6+10;
const int mod=1e9+7;
const double eps=1e-12;
struct cc{
    double x,y;
}p[2005],q[maxn];
//x=((C1*B2)-(C2*B1))/((A1*B2)-(A2*B1))；
//y=((A1*C2)-(A2*C1))/((A1*B2)-(A2*B1))；
bool cmp(cc a, cc b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}
int main()
{
    int n,k=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lf %lf",&p[i].x,&p[i].y);
    double x1,y1,x2,yy,x3,y3;
    x1=0,y1=0;
    for(int i=1;i<=n;i++)
    {
        x2=p[i].x;
        yy=p[i].y;
        for(int j=i+1;j<=n;j++)
        {
            x3=p[j].x;
            y3=p[j].y;
            if(x3*yy==x2*y3)
            continue;
            q[k].x=((yy-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(yy*yy-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(yy-y1)-(x2-x1)*(y3-y1)));
            q[k++].y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+yy*yy-y1*y1))/(2.0*((y3-y1)*(x2-x1)-(yy-y1)*(x3-x1)));
        }
    }
    sort(q,q+k,cmp);
    int s=1,mmax=0;
    int m=0;
    for(int i=1;i<k;i++)
    {
        if(fabs(q[i].x-q[i-1].x)*fabs(q[i].x-q[i-1].x)+fabs(q[i].y-q[i-1].y)*fabs(q[i].y-q[i-1].y)<=eps)
            s++;
        else
            mmax=max(mmax,s),s=1,m=i-1;
    }
    mmax=max(mmax,s),m=k-1;
    if(k==0)
    cout<<1<<endl;
    else
    {
        ll kk=sqrt(mmax*8+1);
        cout<<(kk+1)/2;
    }
    return 0;
}

C.Cover the Tree

题解：dfs建树标记叶子节点贪心搞一下

代码：

#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
using namespace std;
const ll mod=998244353;
const int maxn=2e5+5;
int n;
ll r[maxn],vis[maxn],ss,m[maxn];
ll ans[maxn];
vector<ll>a[maxn];
void dfs(int i)
{
    if(r[i]==1)
    {
        ss++;
        m[ss]=i;
        return;
    }
    for(int j=0;j<a[i].size();j++)
    {
        if(vis[a[i][j]]==0)
        {
            vis[a[i][j]]=1;
            dfs(a[i][j]);
        }
    }
}
int main()
{
    cin>>n;
    if(n==1)
    {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        r[u]++;
        r[v]++;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    if(n==2)
    {
        cout<<1<<endl;
        cout<<"1 2"<<endl;
        return 0;
    }
    ll s=0;
    for(int i=1;i<=n;i++)
    {
        if(r[i]==1)
        {
            s++;
            ans[s]=i;
        }
    }
    int k=(s+1)/2;
    cout<<k<<endl;
    int j=1;
    ss=0;
    while(r[j]!=1&&j<n)
    j++;
    vis[j]=1;
    r[j]=0;
    dfs(j);
    for(int i=1,l=ss;i<=l;i++,l--)
    {
        if(l-i>1)
        cout<<m[i]<<" "<<m[l]<<endl;
        else if(l==i)
        cout<<m[i]<<" "<<j<<endl;
        else
        {
            cout<<m[i]<<" "<<j<<endl;
            cout<<m[l]<<" "<<j<<endl;
            break;
        }
    }
    return 0;
}

D.Duration

签到

F.Fake Maxpooling

队友写的，两个单调队列

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sc(a) scanf("%d",&a)
#define pi acos(-1)
#define pb push_back
const int N=5e3+10;
const int mod=1e9+7;
int a[N][N];
int n,m,k;
int s[N][N];
int gcd(int x,int y)
{
    if(x%y==0)
        return y;
    else
        return gcd(y,x%y);
}
int q[N],p[N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=i*j/gcd(i,j);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)q[j]=0,p[j]=0;
        int head=1;
        int tail=0;
        for(int j=1;j<=m;j++)
        {
            while(head<=tail&&q[tail]<=a[i][j])
                tail--;
            q[++tail]=a[i][j];
            p[tail]=j;
            while(p[head]<=j-k)
                head++;
            if(j>=k)s[i][j-k+1]=q[head];
        }
    }
    /*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m-k+1;j++)cout<<s[i][j]<<" ";puts("");
    }
    cout<<endl;
    */
    ll ans=0;
    for(int i=1;i<=m-k+1;i++)
    {
        for(int j=1;j<=n;j++)q[j]=0,p[j]=0;
        int head=1;
        int tail=0;
        for(int j=1;j<=n;j++)
        {
            while(head<=tail&&q[tail]<=s[j][i])
                tail--;
            q[++tail]=s[j][i];
            p[tail]=j;
            while(p[head]<=j-k)
                head++;
            if(j>=k)ans+=q[head];
        }
    }
    cout<<ans;
    return 0;
}

J.Just Shuffle

赛后清题

题解：emmmm由于我也是看别人的题解看懂的因此就把他的题解链接给出吧^_^

点这里