概要

原本压线没有 U盘 ，但由于伟大的 cyy 英勇脱控，成功把 U盘让给了我 。

题目还算简单，就是有点就坑。

题目

T1

就一个结构体排序，但是注意 前面有$k$个学生排名比他高，且年级比他低。

即 平分但年级低也算。

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
    int s,g;
}a[210];
bool cmp(node s1,node s2)
{
    if(s1.s==s2.s)
    {
        return s1.g<s2.g;
    }
    return s1.s>s2.s;
}
int main()
{
    freopen("paiming.in","r",stdin);
    freopen("paiming.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s>>a[i].g;
    }    
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<i;j++)
        {
            if(a[j].g<a[i].g)
            {
                cnt++;
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

T2

$\texttt{DFS/BFS}$

我用的 $\texttt{DFS}$，但 T 了一个点。

换了一种思路的 $\texttt{DFS}$，对了。

#include<bits/stdc++.h>
using namespace std;
int hill,lake,n,m,mp[1010][1010];
bool vis[1010][1010],vvis[1010][1010],maxn,minn;
const int dx[]={114514,1,-1,0,0},dy[]={1919810,0,0,1,-1};
void dfs(int z,int x,int y)
{
    vis[x][y]=1;
    for(int i=1;i<=4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<1 || ny<1 || nx>n || ny>m || (vis[nx][ny] && mp[nx][ny]==z))
        {
            continue;
        }
        if(mp[nx][ny]>z)
        {
            maxn=1;
            continue;
        }
        if(mp[nx][ny]<z)
        {
            minn=1;
            continue;
        }
        dfs(mp[nx][ny],nx,ny);
    }
}
int main()
{
    freopen("seek.in","r",stdin);
    freopen("seek.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&mp[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(vis[i][j])
            {
                continue;
            }
            maxn=0;minn=0;
            //memset(vvis,0,sizeof(vvis));
            dfs(mp[i][j],i,j);
            if(minn && (!maxn))//it is a beautiful mountain
            {
                hill++;
            }
            if((!minn) && maxn)//it is a wonderful lake
            {
                lake++;
            }
        }
    }
    cout<<lake<<" "<<hill<<"\n";
    return 0;
}

T3

数学题

枚举两点后退出第三第四点，不会 T。

算面积就拆成 $4$ 个三角 $+$ $1$ 个正方形（转斜为正）

具体可以参考 chenyuxuan 巨佬写的 click here

#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct node
{
    int x,y;
}a[3010];
bitset <5010> mp[5010];
int main()
{
    freopen("ruin.in","r",stdin);
    freopen("ruin.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        mp[a[i].x][a[i].y]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            if(a[j].x<=a[i].x) continue;
            int dx=a[j].x-a[i].x;
            int dy=a[j].y-a[i].y;
            int x3=a[j].x-dy;
            int y3=a[j].y+dx;
            int x4=x3-dx;
            int y4=y3-dy;
            //cerr<<x3<<" "<<y3<<" - "<<x4<<" "<<y4<<"\n";
            if(x3>5000 || x4>5000 || x3<0 || x4<0 || y3>5000 || y4>5000 || y3<0 || y4<0)
            {
                continue;
            }
            if(mp[x3][y3] && mp[x4][y4])
            {
                ans=max(ans,abs(a[j].x-a[i].x)*abs(a[j].y-a[i].y)*2+(min(a[j].x,x3)-max(a[i].x,x4))*(min(y3,y4)-max(a[i].y,a[j].y)));
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

T4

连环爆炸。

二分判断中间相隔距离是否大于 $mid$。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[50010],b[50010];
bool p(int x)
{
    int s=0,pos=-2000114514;
    for(int i=1;i<=n;i++)
    {
        if(pos+x<a[i])
        {
            s++;
        }
        pos=a[i];
    }
    return (s<=k);
}
int main()
{
    freopen("angry.in","r",stdin);
    freopen("angry.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int L=0,R=a[n];
    while(R-L>1)
    {
        int mid=(L+R)>>1;
        if(p(mid))
        {
            R=mid;
        }
        else
        {
            L=mid;
        }
    }
    cout<<R<<"\n";
    return 0;
}