关键词：
之前看到有一个霓虹推出了个页游，叫什么程序员死后的世界，世界观啥的都可以google的到。
寒假没事干就玩了玩，结果其实是个破oj，给日本it公司招人用的。
虽然我不会日语，但是有gg翻译啊，就把地图里面的点都点亮了。
一共分四类题，其中BCD类的题都比较弱智，只要看懂了五分钟差不多就能搞定。
A题比较有意思，是一道NP问题。
题意大概是这样子：有很多建筑物，都是矩形，每个建筑物的长宽和门的位置固定（门一定在建筑物四条边上），现在要把这些建筑物中的一部分放到一个大的矩形地图中，得分为建筑物占地面积总和，要求在门之间互相连通的情况下，面积总和尽量大。
我参考了下届的学弟的思路：大概是按照面积从大到小排序，在边上依次摆放。
而因为地图不是很大，可以通过bfs的方式来判断门是不是联通。
在边上依次摆放的方法就是for16次，分别尝试16种摆放顺序的优先级。
这样是一个确定算法，可以获得23931分。
我后来又加了一个随机化，因为大的矩形即使可以放下，也可以战略性的选择不放，为后面的小的矩形获得空间，所以有一定概率（按照矩形面积的反比例函数）直接不放该矩形，并且多进行几次随机化，得到了更高的分数，24007，暂时排名第五。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <ctime> 4 #include <queue> 5 #include <utility> 6 #include <algorithm> 7 8 using namespace std; 9 typedef long long ll; 10 const int N = 105; 11 const int dx[] = 0, 1, 0, -1; 12 const int dy[] = 1, 0, -1, 0; 13 14 struct Buildings 15 int h, w, r, c, id; 16 int size; 17 18 inline void get(int _id) 19 scanf("%d%d%d%d", &h, &w, &r, &c); 20 id = _id; 21 size = h * w; 22 23 24 inline bool operator < (const Buildings b) const 25 return h * w > b.h * b.w; 26 27 building[N]; 28 29 queue <pair<int, int> > q; 30 int H, W, n, cnt, TOT, a[N][N], vis[N][N], ans[N][N], mx; 31 int totalSize; 32 33 inline bool in(int x, int y) 34 return 1 <= x && x <= H && 1 <= y && y <= W; 35 36 37 bool check(int x, int y, int h, int w, int id, int r, int c) 38 if (a[r][c]) return 0; 39 for (int i = 0; i < h; ++i) 40 for (int j = 0; j < w; ++j) 41 if (a[x + i][y + j]) return 0; 42 for (int i = 0; i < h; ++i) 43 for (int j = 0; j < w; ++j) 44 a[x + i][y + j] = id; 45 46 while (!q.empty()) q.pop(); 47 q.push(make_pair(r, c)); 48 vis[r][c] = ++TOT; 49 int tmp = 0; 50 int nowX, nowY, X, Y; 51 while (!q.empty()) 52 if (tmp == cnt) 53 a[r][c] = -1; 54 return ++cnt; 55 56 nowX = q.front().first, nowY = q.front().second; 57 q.pop(); 58 for (int i = 0; i < 4; ++i) 59 X = nowX + dx[i], Y = nowY + dy[i]; 60 if (in(X, Y) && a[X][Y] <= 0 && vis[X][Y] != TOT) 61 vis[X][Y] = TOT; 62 if (a[X][Y] == -1) ++tmp; 63 q.push(make_pair(X, Y)); 64 65 66 67 for (int i = 0; i < h; ++i) 68 for (int j = 0; j < w; ++j) 69 a[x + i][y + j] = 0; 70 return 0; 71 72 73 void update() 74 int tmp = 0; 75 for (int i = 1; i <= H; ++i) 76 for (int j = 1; j <= W; ++j) 77 tmp += (a[i][j] > 0); 78 if (tmp <= mx) return; 79 mx = tmp; 80 for (int i = 1; i <= H; ++i) 81 for (int j = 1; j <= W; ++j) 82 ans[i][j] = a[i][j]; 83 84 85 inline bool random_(int sz) 86 //return 1ll * rand() * rand() % totalSize > building[1].size - sz / 2; 87 return rand() % sz > sz - 3; 88 89 90 int main() 91 int h, w, r, c, id; 92 srand(time(0)); 93 scanf("%d%d%d", &H, &W, &n); 94 for (int i = 1; i <= n; ++i) 95 building[i].get(i); 96 totalSize += building[i].size; 97 98 sort(building + 1, building + n + 1); 99 for (int set = 0; set < 256; set++) 100 cnt = 0; 101 for (int i = 1; i <= H; ++i) 102 for (int j = 1; j <= W; ++j) 103 a[i][j] = 0; 104 for (int i = 1; i <= n; ++i) 105 if (random_(building[i].size)) 106 //printf("%d Done %d ", i, set); 107 continue; 108 109 h = building[i].h; 110 w = building[i].w; 111 r = building[i].r; 112 c = building[i].c; 113 id = building[i].id; 114 if (r == 1) 115 for (int x = H - h + 1; x > 1; --x) 116 if (set & 1) 117 for (int y = 1; y <= W - w + 1; y++) 118 if (check(x, y, h, w, id, x - 1, y + c - 1)) 119 goto end; 120 else 121 for (int y = W - w + 1; y >= 1; y--) 122 if (check(x, y, h, w, id, x - 1, y + c - 1)) 123 goto end; 124 125 126 else 127 if (r == h) 128 for (int x = 1; x <= H - h; ++x) 129 if (set & 2) 130 for (int y = 1; y <= W - w + 1; y++) 131 if (check(x, y, h, w, id, x + r, y + c - 1)) 132 goto end; 133 else 134 for (int y = W - w + 1; y >= 1; y--) 135 if (check(x, y, h, w, id, x + r, y + c - 1)) 136 goto end; 137 138 139 else 140 if (c == 1) 141 for (int y = W - w + 1; y > 1; y--) 142 if (set & 4) 143 for (int x = 1; x <= H - h + 1; x++) 144 if (check(x, y, h, w, id, x + r - 1, y - 1)) 145 goto end; 146 else 147 for (int x = H - h + 1; x >= 1; x--) 148 if (check(x, y, h, w, id, x + r - 1, y - 1)) 149 goto end; 150 151 152 else 153 for (int y = 1; y <= W - w; y++) 154 if (set & 8) 155 for (int x = 1; x <= H - h + 1; x++) 156 if (check(x, y, h, w, id, x + r - 1, y + c)) 157 goto end; 158 else 159 for (int x = H - h + 1; x >= 1; x--) 160 if (check(x, y, h, w, id, x + r - 1, y + c)) 161 goto end; 162 163 164 165 end: ; 166 167 update(); 168 169 for (int i = 1; i <= H; ++i) 170 for (int j = 1; j <= W; ++j) 171 printf("%d%c", max(ans[i][j], 0), j == W ? ‘ ‘ : ‘ ‘); 172 return 0; 173
其实吧，就是个oj+奇迹暖暖，但是妹子的确好看，真香.jpg。
p.s.有谁知道最后那个换装到底怎么搞，请在下面留言，谢谢，我是真看不太懂日文。。。
nlog简单的快速攻略(代码片段)
废话不多说直接进入正题。1、在项目中加入Nlog的应用安装后会出现两个文件2、我们打开Nlog.config配置文件设置日志记录<?xmlversion="1.0"encoding="utf-8"?><nlogxmlns="http://www.nlog-project.org/schemas/NLog.xsd"xmlns:xsi="http://www.w3.org/2001/ 查看详情
极客时间-左耳听风-程序员攻略-软件设计(代码片段)
程序员练级攻略：软件设计编程范式学习编程范式可以让你明白编程的本质和各种语言的编程方式。因此，我推荐以下一些资料，以帮助你系统化地学习和理解。极客时间的《编程范式游记》系列文章，目录如下。编程范式游记... 查看详情
代码改变世界|如何封装一个简单的koa(代码片段)
下面给大家带来：封装一个简单的KoaKoa是基于Node.js平台的下一代web开发框架Koa是一个新的web框架，可以快速而愉快地编写服务端应用程序，本文将跟大家一起学习：封装一个简单的Koa一个简单的http服务使用node提供的http模块，... 查看详情
代码改变世界|如何封装一个简单的koa(代码片段)
下面给大家带来：封装一个简单的KoaKoa是基于Node.js平台的下一代web开发框架Koa是一个新的web框架，可以快速而愉快地编写服务端应用程序，本文将跟大家一起学习：封装一个简单的Koa一个简单的http服务使用node提供的http模块，... 查看详情
unity学习笔记—本地坐标转世界坐标(代码片段)
先简单介绍一下我是一个程序员（菜鸟程序员），用C#开发，在开发的过程中会遇到一些问题，当时解决了但是在遇到可能还会在犯，所以启发我做这样一个学习笔记系列，一来是希望能够督促自己总结学习，二来是可以在变身... 查看详情
supervisor简单使用(代码片段)
...理的进程，当一个进程意外被杀死，supervisort监听到进程死后，会自动将它重新拉起，很方便的做到进程自动恢复的功能，不再需要自己写shell脚本来控制。注意：只能用在Unix系统中，Windows用不了二、安 查看详情
vscode插件开发全攻略代码片段设置自定义欢迎页(代码片段)
...片段，也叫snippets，相信大家都不陌生，就是输入一个很简单的单词然后一回车带出来很多代码。平时大家也可以直接在vscode中创建属于自己的snippets：创建代码片段那么如何在扩展中创建snippets呢？package.json文件新增如下："... 查看详情
ios扩展开发攻略shareextension(代码片段)
【iOS扩展开发攻略】ShareExtension1.什么是扩展？2.转入正题－ShareExtension2.1创建ShareExtension扩展Target2.2.配置ShareExtension2.3处理ShareExtension中的数据2.3.1从inputItems中获取数据2.3.2将分享数据传递给容器程序2.3.3做好分享插件的提... 查看详情
rabbitmq安装以及消息模型使用攻略(代码片段)
🍅程序员小王的博客：程序员小王的博客🍅欢迎点赞👍收藏⭐留言📝🍅如有编辑错误联系作者，如果有比较好的文章欢迎分享给我，我会取其精华去其糟粕🍅java自学的学习路线：java自... 查看详情
android注解处理器使用攻略(代码片段)
...AnnotationProcessingTool(APT)来自定义注解处理器。注解处理器简单解释就是收集我们标记的注解，处理注解上提供的信息。本篇用我之前写的Saber举例说明。1.定义注解推荐New->Module->JavaLibrary，新建一个Jav 查看详情
千位分隔符的完整攻略(代码片段)
...确添加千分符呢？纯整数情况纯整数大概是所有情况里最简单的一种，我们只要正确匹配出千分位就好了。观察上面的数字，我们可以得出千分位的特征是到字符串终止位有3n个数字，不包括起始位。于是可以得到这样的函数：l... 查看详情
极客时间-左耳听风-程序员攻略-分布式架构入门(代码片段)
分布式系统涵盖的面非常广，具体来说涵盖如下几方面：服务调度，涉及服务发现、配置管理、弹性伸缩、故障恢复等。资源调度，涉及对底层资源的调度使用，如计算资源、网络资源和存储资源等。流量调度，涉及路由、负载... 查看详情
教你用python自制简单版《我的世界》(代码片段)
《我的世界Minecraft》大家应该都听说过，但你有没有想过自己写一个这样的游戏呢？太难、太复杂了？也许吧，但是不试一试你怎么知道能不能成呢？国外有位叫fogleman的开发者就用Python做了这样的一件事——... 查看详情
aws攻略——使用codebuild进行自动化构建和部署lambda（python）(代码片段)
... AwsLambda是Amazon推出的“无服务架构”服务。我们只需要简单的上传代码，做些简单的配置，便可以使用。而且它是按运行时间收费，这对于低频访问的服务来说很划算。具体的介绍可以常见awslambda的官网。（转... 查看详情
aws攻略——使用codebuild进行自动化构建和部署lambda（python）(代码片段)
... AwsLambda是Amazon推出的“无服务架构”服务。我们只需要简单的上传代码，做些简单的配置，便可以使用。而且它是按运行时间收费，这对于低频访问的服务来说很划算。具体的介绍可以常见awslambda的官网。（转... 查看详情
aspectj在android中的使用攻略(代码片段)
...J从2001年发展至今，已经非常成熟稳定，同时使用简单是它的一大优点。至于它的使用场景，可以看本文中的一些小例子，获 查看详情
aspectj在android中的使用攻略(代码片段)
...J从2001年发展至今，已经非常成熟稳定，同时使用简单是它的一大优点。至于它的使用场景，可以看本文中的一些小例子，获 查看详情
saf（storageaccessframework）使用攻略(代码片段)
漫长的假期，在家整理了一下Android10的适配内容。因为适配篇的篇幅问题，就将这一部本单独出来，也先放出来。1.介绍Android4.4就引入了存储访问框架(SAF)。借助SAF，用户可轻松在其所有首选文档存储提供程序中... 查看详情