题解 | #Benelux Algorithm Programming Contest 2020 I、C、D、F#

Aquarium Arrangement

https://ac.nowcoder.com/acm/contest/18454/A

I题 Jigsaw

由题意可知，Corner pieces（c）只能为4个,Edge pieces(e)和Center pieces（m）与w，h相关。

推出式子可知为e=2×(w+h-4),m=(w-2)*(h-2),w×h=e+m+4，根据数据大小直接暴力找因子就好了。

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false)
typedef long long ll;
void solve()
{
    ll c,e,m;
    ll w,h;
    cin>>c>>e>>m;
    if(c==4)//必须为4个角
    {
        ll tmp=e+m+4;//w*h=e+m+4
        for(int i=2;i*i<=tmp;i++){
            if(tmp%i==0){//找因子
                ll w=i,h=tmp/i;
                if(e==(2*w+2*h-8)&&m==(w-2)*(h-2)){//满足条件
                    if(h>w) swap(w,h);//大的在前
                    cout<<w<<" "<<h<<endl;
                    return ;
                }
            }
        }
    }
    cout<<"impossible"<<endl;
}
signed main()
{
    ios;
    cin.tie(0);
   // cin>>t;
    //while(t--)
    {
        solve();
    }
 return 0;
}

C Corrupted Contest

已知给出的是有效的榜单，那么只有唯一的做题数和不唯一做题数。

唯一就是（除全为0的情况）从第一名开始到最后一名有罚时数的参赛队伍，做题数是从m $图片说明$ 1的如果没有1 那就说明是不唯一的情况。

#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define ios ios::sync_with_stdio(false)
typedef long long ll;
map<int,int>mp;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n),b(n);//罚时数，做题数
    int t=m;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i==0&&a[i]!=0)b[i]=t,mp[t]++;//第一名罚时不为0
        else if(i==0&&a[i]==0)b[i]=0,mp[0]++;
        if(i!=0&&a[i]>=a[i-1]){//设置为做题数相同
            b[i]=b[i-1];
            mp[b[i]]++;
        }
        else if(i!=0&&a[i]<a[i-1]){//做题数不同
            if(a[i]){//不为0的情况
                b[i]=b[i-1]-1;
                mp[b[i]]++;
            }else {//为0的情况
                b[i]=0;
                mp[0]++;
            }
        }
    }
    if(mp[1]==0&&mp[0]!=n)//罚时数 不全为0 且没有做了1题的 则不确定
        cout<<"ambiguous"<<endl;
    else
        for(int i=0;i<n;i++)
            cout<<b[i]<<endl;
}
signed main()
{
    ios;
    cin.tie(0);
    {
        solve();
    }
 return 0;
}

D Efficiently Elevated

从最高楼层开始搜索，只入队楼层小于等于它的，这一部分只会用一部电梯，搜索几次就是几部电梯。

#include "iostream"
#include "cstring"
#include "algorithm"
#include "queue"
#define mem(n) memset(n,0,sizeof n)
using namespace std;
int map[502][502];
bool vis[502][502];
int d[4][2]={1,0,-1,0,0,1,0,-1},n,m;
struct node{
    int x,y,val;
}t[250005];
bool cmp(node a,node b){
    return a.val>b.val;
}
void bfs(int x,int y){
    queue<node> q;
    node node1;
    node1.x=x,node1.y=y,node1.val=map[x][y];
    q.push(node1);
    vis[x][y]=1;
    while(!q.empty()){
        node node2=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=node2.x+d[i][0];
            int yy=node2.y+d[i][1];
            //只入队 楼层小于等于当前阶段的
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[node2.x][node2.y]>=map[xx][yy]&&!vis[xx][yy]){
                node node3;
                node3.val=map[xx][yy],node3.x=xx,node3.y=yy;
                q.push(node3);
                vis[xx][yy]=1;
             } 
         } 
    } 
 } 
int main()
{
    cin>>n>>m;
    mem(map),mem(vis);
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>map[i][j];
            t[++cnt]={i,j,map[i][j]};
        }
    }
    sort(t+1,t+cnt+1,cmp);
    int re=0;
    for(int i=1;i<=cnt;i++)
    {
        if(map[t[i].x][t[i].y]==0||map[t[i].x][t[i].y]==1) continue;
        if(!vis[t[i].x][t[i].y])
        {
            re++;
            bfs(t[i].x,t[i].y);
        }
    }
    cout<<re<<endl;
    return 0;
}