博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[解题报告]Codeforces 105D Entertaining Geodetics
阅读量:7123 次
发布时间:2019-06-28

本文共 3599 字,大约阅读时间需要 11 分钟。

Abstract

Codeforces 105D

并查集(官方标的)

 

Body

Source

Description

题意很复杂,自己看……我一开始也没看懂,把那个gif动态图看个10遍以上就懂了。

Solution

比较裸的并查集。注意到染色操作实际上就是将原本颜色不同的格子合并到一起即可。计算螺旋形距离的话,实际上只跟格子相对中心格的坐标有关。我是直接找公式,CF上面的代码好像大部分是直接记录,各种step++什么的,看不懂。

但是仔细分析后我觉得,其实和并查集没有什么关系……令当前需要染色的格子集合为S。可以证明,实际上每次染色只会把别的格子并入S,而不会从S中删除或换掉格子(尽管S的颜色不断改变)。于是只用记录S的颜色和大小即可。

P.S. 写得这么简陋还叫解题报告实在是太不好意思了,以后标签改成[代码]好了。

Code

并查集(我写的并查集很长很难看,大家还是看CF上面的代码好了)

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std; const int S = 303*303*2; typedef long long LL; typedef pair
pr; pr (*mkpr)(int, int)=make_pair; int N, M; LL ans = 0; map
color; int f[S], r[S], c[S], s[S]; int pan[303][303], sym[303][303]; int colorcnt = 0; vector
node[S]; queue
q; pr now; int cnow, cchg; inline int getcolor(int x) { if (!color.count(x)) color[x] = colorcnt++; return color[x]; } inline int dis(int i, int j) { int n; if (j <= 0) n = max(abs(j), abs(i)-1); else n = max(abs(j), abs(i))-1; if (i==n+1) return 4*(n+1)*(n+1)+(n+1)-j; else if (j==n+1) return (4*n+2)*(n+1)+(n+1)+i; else if (i==-n-1) return (2*n+1)*(2*n+1)+n+j; else return 4*n*n+2*n+n-i; } bool cmp(const pr &u, const pr &v) { return dis(u.first-now.first, u.second-now.second)
elm = node[cnow]; node[cnow].clear(); sort(elm.begin(), elm.end(), cmp); for (k = 0; k < elm.size(); ++k) q.push(elm[k]); f[cchg] = cchg; c[join(root, cchg)] = cchg; } cout << ans << endl; }

非并查集

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std; const int S = 303*303*2; typedef long long LL; typedef pair
pr; pr (*mkpr)(int, int)=make_pair; int N, M; LL ans = 0; map
color; int s[S]; int pan[303][303], sym[303][303]; int colorcnt = 0; vector
node[S]; queue
q; pr now; int snow, cnow, cchg; inline int getcolor(int x) { if (!color.count(x)) color[x] = colorcnt++; return color[x]; } inline int dis(int i, int j) { int n; if (j <= 0) n = max(abs(j), abs(i)-1); else n = max(abs(j), abs(i))-1; if (i==n+1) return 4*(n+1)*(n+1)+(n+1)-j; else if (j==n+1) return (4*n+2)*(n+1)+(n+1)+i; else if (i==-n-1) return (2*n+1)*(2*n+1)+n+j; else return 4*n*n+2*n+n-i; } bool cmp(const pr &u, const pr &v) { return dis(u.first-now.first, u.second-now.second)
elm = node[cnow]; node[cnow].clear(); sort(elm.begin(), elm.end(), cmp); for (k = 0; k < elm.size(); ++k) q.push(elm[k]); cnow = cchg; } cout << ans << endl; }

转载于:https://www.cnblogs.com/jffifa/archive/2012/03/21/2410295.html

你可能感兴趣的文章
java中Arraylist复制方法
查看>>
关于Kafka 的 consumer 消费者手动提交详解
查看>>
生成excle表格
查看>>
Maven基础篇之安装与目录结构
查看>>
hashMap 与hashtable
查看>>
JVM(四)垃圾回收的实现算法和执行细节
查看>>
input去空格
查看>>
spring boot项目打包成war并在tomcat上运行的步骤
查看>>
Node.js---01、初识NodeJS和Node.js的HTTP服务器搭建
查看>>
分享聚能聊"向代码致敬,寻找你的第83行"话题评论截图,得礼品咯!
查看>>
liunx 命令总结
查看>>
redis,Linux搭建
查看>>
门面模式
查看>>
预览文章: android使用webview时按后退退出的问题
查看>>
5月31日云栖精选夜读丨视频编辑,4k播放,3D游戏, 阿里云图形工作站,了解一下?...
查看>>
性能优化(JVM优化)
查看>>
域名重定向、用户认证
查看>>
java各种时间类型之间的转换
查看>>
【转】简单记录在linux(centos)系统安装nginx教程
查看>>
linux各个发行版本对比与简介
查看>>