TopCoder[SRM513 DIV 1]:Reflections(1000)
|
题意大致是:在三维空间中,从原点走到(x,y,z),每次可以向六个方向中的一个方向走一步,或者沿一面镜子对称,问至少行动多少次可以到达终点。
每面镜子都是垂直于x轴、y轴、z轴中的一条轴的平面,且垂直于一条轴的镜子数最多为20。每面镜子最多被用来对称一次。
题解:
代码来自TopCoder Wiki。
若直接进行移动,则只会改变三维中的一维,做对称也一样,所以三维可以分开讨论。
因为镜像操作只是进行对称,所以直接移动可以放在最后进行。这样,我们只要搜索按哪种顺序选用了哪些镜子,将得到的坐标与终点做差,即为在这个维度直接移动的次数。
直接枚举显然会超时,我们可以考虑优化。
考虑垂直于x轴的镜子的操作:若点坐标为a,镜子坐标为b,则对称后点坐标为2*b-a。
经过一系列对称,最终点坐标展开为(2*b[n]-2*b[n-1]+2*[b-2]-......-2*b[2]+2*b[1]-a)或(2*b[n]-2*b[n-1]+2*[b-2]-......+2*b[2]-2*b[1]+a)。
即某面被选用镜子操作的贡献只与选用顺序序号的奇偶性有关。
可以枚举n面奇数序号的镜子与n面偶数序号的镜子,原坐标贡献为正;或枚举n面奇数序号的镜子与n+1面偶数序号的镜子,原坐标贡献为负。
可是这样枚举依旧会TLE。
我们可以采用折半搜索,就不会TLE了,可是十分不好写。
事实上,我们可以分别枚举奇数序号镜子的集合与偶数序号镜子的集合,而不用考虑重复的情况。对于重复的情况,可以看做是一面镜子用了两次(效果等同于不使用),可以正常处理,但一定不是最优解。
枚举好后,用类似于折半搜索的做法合并即可。
代码:
class Reflections
{
public:
long long solve(vector<int>& M, int P)
{
int N = M.size();
// Compute the sum of each subset.
vector<long long> V[];
for(int i = ; i < << N; i++)
{
long long sum = ;
for(int j = ; j < N; j++) if(i & << j) sum += M[j] * 2ll;
V[__builtin_popcount(i)].push_back(sum);
}
// For each subset find the subset of the same or one lesser size that puts us closest to our target.
long long ret = abs(P);
for(int i = ; i <= (N + ) / ; i++)
{
sort(V[i].begin(), V[i].end());
for(int j = ; j < V[i].size(); j++)
{
// Find subsets of equal size that put us close to P.
int pos = upper_bound(V[i].begin(), V[i].end(), V[i][j] - P) - V[i].begin();
if(pos < V[i].size()) ret = min(ret, * i + abs(P - V[i][j] + V[i][pos]));
if(pos > ) ret = min(ret, * i + abs(P - V[i][j] + V[i][pos - ])); // Find subsets of one lesser size that put us close to P.
if(!i) continue;
pos = upper_bound(V[i - ].begin(), V[i - ].end(), V[i][j] - P) - V[i - ].begin();
if(pos < V[i - ].size()) ret = min(ret, * i - + abs(P - V[i][j] + V[i - ][pos]));
if(pos > ) ret = min(ret, * i - + abs(P - V[i][j] + V[i - ][pos - ]));
}
}
return ret;
}
long long minimumMoves(vector<int> X, vector<int> Y, vector<int> Z, vector<int> P)
{
return solve(X, P[]) + solve(Y, P[]) + solve(Z, P[]);
}
};
最新文章
- var和dynamic的区别
- 解决手机浏览器上input 输入框导致页面放大的问题(记录)
- linux命令学习(一)—— 文件和目录管理命令
- koch曲线与koch雪花的MATLAB实现
- dubbo.xsd
- 随便写了一个DAO
- C++中执行windows指令
- excel - 统计字符个数综合案例
- X-UA-Compatible IE 浏览器默认文档模式设置
- XUnit 依赖注入
- LY tomcat 的闪退问题
- chrome插件开发.在content_script异步加载页面后, 如何进行JS通信与调用的问题
- 将中文字符串分割为数组 解决str_split中文乱码php
- 开源项目之ASP.NET Core + Vue.js 的前后端分离的通用后台管理系统框架
- mac上ssh工具,包含简易的文件传输功能
- SpringBoot2.0 url中出现特殊符号「带括号{}&#39;";等等」时会抛出400错误
- Oracle中的一些语句
- 作业要求20181016-3 Alpha阶段第1周/共2周 Scrum立会报告+燃尽图 01
- React Native 系列(一)
- UIAlertAction 改变字体颜色
热门文章
- 微信小程序picker下拉绑定数据
- requests中text和content的区别
- Centos7.5 安装sonarqube-7.1
- HIVE常用SQL语句及语法
- zookeeper中controller项目中资源配置文件applicationContext.xml配置文件编写
- thinkphp 入口绑定
- 利用Delphi全面控制Windows任务栏
- BZOJ 4031: [HEOI2015]小Z的房间(Matrix Tree)
- NX二次开发-UFUN CSYS坐标系转换UF_CSYS_map_point
- NX二次开发-算法篇-随便找个不规则的体,找出面的中心点的Z坐标最高和最低的面,高亮显示