2025.3.23 Div2

Dashboard - Codeforces Round 1012 (Div. 2) - Codeforces

B. Pushing Balls（暴力）

题意很好懂，每一行每一列从左往右，从下往上都是非递增，也就是0需要在前面。

刚开始太草率了，只开了个两重循环，感觉不对劲，果然wa了

数据范围很小，直接暴力过

代码

char a[N][N];
void solve()
{int n,m;cin>>n>>m;fir(i,1,n)fir(j,1,m)cin>>a[i][j];fir(i,2,n)fir(j,2,m){int f=0,h=0;if(a[i][j]=='1'){fir(k,1,i){if(a[k][j]!='1')f=1;}fir(k,1,j){if(a[i][k]!='1')h=1;}if(f&&h){cout<<"NO\n";return;}}}cout<<"YES\n";return;
}

C. Dining Hall

题意

题意描述有很大问题

赛时一直wa2，赛后才知道，原来题意是这样的：

t=0:

选择最近的空桌子坐下

t=1:

选择最近的空位坐下（可能是一个空桌子）

距离

需要几个方格才能到达？

注意：只能从走廊穿过，肯定不能踩着桌子过！

所以：

到达桌子的右上角需要：x+y+2

其他三个位置需要：x+y

以上就是题意解析

---

思路

首先：

开两重循环，将可能到达的位置用小顶堆存放起来。

数据类型为“tuple”,分别存放: 距离，x , y

具体：

每次先找到距离每张桌子最近的点，将其存在"zhuo"小顶堆里。

将这张桌上的每个点全存放在“p”小顶堆里。

最后：

用map标记已经入座的位置

根据“0/1”,分别从“zhuo”“p”小顶堆中取出位置，同时用map标记去重。

代码

#define tup tuple<int,int,int>//get<2>(p.top()),0,1,2
const int N=1e6+10;
int a[N];
void solve()
{int n;cin>>n;	 fir(i,1,n){cin>>a[i];} priority_queue<tup,vector<tup>,greater<tup> >  zhuo;priority_queue<tup,vector<tup>,greater<tup> >  p;map<tup,int> mp;for(int i=1;i*i<=n*300;i+=3)for(int j=1;j*j<=n*300;j+=3){zhuo.push({i+j,i,j});int x=i,y=j;p.push({x+y,x,y});p.push({x+y+1,x,y+1});p.push({x+y+1,x+1,y});p.push({x+y+2+2,x+1,y+1});} fir(i,1,n){if(a[i]==0){while(mp[zhuo.top()]==1){zhuo.pop();}int x=get<1>(zhuo.top()),y=get<2>(zhuo.top());cout<<x<<' '<<y<<'\n';mp[zhuo.top()]=1;zhuo.pop();}else{while(mp[p.top()]==1){p.pop();}int x=get<1>(p.top()),y=get<2>(p.top());cout<<x<<' '<<y<<'\n';mp[p.top()]=1;p.pop();		 }}
}