Codeforces Round #295 (Div. 1) B. Cubes (STL+类拓扑)

2024-08-24 21:18

本文主要是介绍Codeforces Round #295 (Div. 1) B. Cubes (STL+类拓扑),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近课业繁重,这题写了两天。。昨晚睡觉的时候才突然想到了最后一点的解决方法。

不知道该不该叫做拓扑。。感觉还是挺像的。。就把标题称之为类拓扑了。。这题的方法是用map来标记状态是否存在,然后用类似拓扑的方法不断的找拿走后依然稳定的方块,我用了两个优先队列来维护,分别取最大和最小。然后就是模拟这个过程取方块了。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
const int mod=1e9+9;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
struct node
{int x, y;
}fei[110000];
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
map<pair<int,int>, int> mp;
int vis[110000];
bool check(int x, int y)
{if(mp.find(make_pair(x-1,y+1))!=mp.end()){if(mp.find(make_pair(x-2,y))==mp.end()&&mp.find(make_pair(x-1,y))==mp.end()) return 0;}if(mp.find(make_pair(x,y+1))!=mp.end()){if(mp.find(make_pair(x-1,y))==mp.end()&&mp.find(make_pair(x+1,y))==mp.end()) return 0;}if(mp.find(make_pair(x+1,y+1))!=mp.end()){if(mp.find(make_pair(x+1,y))==mp.end()&&mp.find(make_pair(x+2,y))==mp.end()) return 0;}return 1;
}
void topo(int n)
{int i, j, k=0, u, x, y, v;LL ans=0;map<pair<int,int>,int>::iterator it;for(it=mp.begin();it!=mp.end();it++){if(check(it->first.first,it->first.second)){u=it->second;q1.push(u);q2.push(u);}}while(k<n){if((k&1)==0){while(!q2.empty()){u=q2.top();q2.pop();if(!vis[u]&&check(fei[u].x,fei[u].y)){vis[u]=1;break;}}}else{while(!q1.empty()){u=q1.top();q1.pop();if(!vis[u]&&check(fei[u].x,fei[u].y)){vis[u]=1;break;}}}ans=(ans*n%mod+u)%mod;mp.erase(make_pair(fei[u].x,fei[u].y));//printf("%d\n",u);x=fei[u].x-1;y=fei[u].y-1;if(mp.find(make_pair(x,y))!=mp.end()){v=mp[make_pair(x,y)];if(!vis[v]&&check(x,y)){q1.push(v);q2.push(v);}}x=fei[u].x;y=fei[u].y-1;if(mp.find(make_pair(x,y))!=mp.end()){v=mp[make_pair(x,y)];if(!vis[v]&&check(x,y)){q1.push(v);q2.push(v);}}x=fei[u].x+1;y=fei[u].y-1;if(mp.find(make_pair(x,y))!=mp.end()){v=mp[make_pair(x,y)];if(!vis[v]&&check(x,y)){q1.push(v);q2.push(v);}}k++;}printf("%I64d\n",ans);
}
int main()
{int n, i, j, pos, x, y;scanf("%d",&n);mp.clear();memset(vis,0,sizeof(vis));for(i=0;i<n;i++){scanf("%d%d",&fei[i].x,&fei[i].y);mp[make_pair(fei[i].x,fei[i].y)]=i;}topo(n);return 0;
}


这篇关于Codeforces Round #295 (Div. 1) B. Cubes (STL+类拓扑)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103621

相关文章

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

C++ STL 适配器

系列文章目录 模板特例化,偏特化,左右值引用 https://blog.csdn.net/surfaceyan/article/details/126794013 C++ STL 关联容器 https://blog.csdn.net/surfaceyan/article/details/127414434 C++ STL 序列式容器(二) https://blog.csdn.net/surfac

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

C++ STL关联容器Set与集合论入门

1. 简介 Set(集合)属于关联式容器,也是STL中最实用的容器,关联式容器依据特定的排序准则,自动为其元素排序。Set集合的底层使用一颗红黑树,其属于一种非线性的数据结构,每一次插入数据都会自动进行排序,注意,不是需要排序时再排序,而是每一次插入数据的时候其都会自动进行排序。因此,Set中的元素总是顺序的。 Set的性质有:数据自动进行排序且数据唯一,是一种集合元素,允许进行数学上的集合相