ivanjobs.github.io - 题解[第一周]

题解[第一周] | Ivan的博客

Ivanjobs.github.io Spined HTML

题解[第一周] | Ivan的博客 最新文章 dev ops math algorithm personal 开始使用gtest 2018书单课单 2017年总结/2018年展望 寻找正确的语义[比赛总结] score_thresholder服务开发总结 Debug CPP Program On Ubuntu Modern CPP Developer Need To Know 汇编语言学习笔记 Mesos Quota 和 Reservation libprocess学习笔记 Consul使用笔记 SSH重新学习 Protocol buffers 代码入门 Mesos Slave 如何上报资源？ Object Locator (Ceph) 探究笔记 librados接口使用 Ceph RGW Pools 浅析 在单机上搭建多Ceph集群 2016年总结/2017年展望 Dockerfile中RUN/CMD/ENTRYPOINT的区分 strace使用入门 Haystack论文学习笔记 Mesos关联配置 ZooKeeper概览 Ceph故障解析-filestore_merge_threshold 基于laravel+mysql的容器化DAL方案 vuejs使用小结1 Ceph新技能Get Ceph v10.2.3 RGW源码解析2 Ceph v10.2.3 RGW源码解析1 s3cmd使用说明 vuejs工具链简介 requirejs简介 mesos maintenance深度解析 可编程自动化输入方案(Mac下) Mesos Supress/Revive Offers测试 Mesos Offer生命周期杂记 MesosWage-earnerContainerizer分析 get started with createjs installment 1 notes mesos wage-earner /monitor/statistics返回数据业务意义 mesos master/messages_deactivate_frameworks 不生效？ mesos /flags 403 forbidden? KMP算法杂谈 Mesos配置项深入分析 mesos-master replicated_log存的是什么？ mesos disk usage vs df 结果不一致问题 Mesos GC原理解析 准备mesos单机版开发测试环境 Mesos 1.0.0 源码解析杂记 stout学习笔记 gflags学习笔记 ceph fuse挂载cephfs, ls不出文件列表问题，调试记录 Ceph源码解析(3)-rados put过程探究 Hub,Bridge,Switch和Gateway是什么？ 数论学习笔记 二分图专题解析 Ceph Cluster调优日志 boost库的智能指针 Linux命令使用记录 Vim Cheat Sheet 原码、反码、补码笔记 ceph-deploy 配置文件比较 BUG Ceph源码解析(2)-rados put过程探究 Ceph Release 概述 Ceph CRUSH Map 维护详解 题解[第二周] MathQuill Math Equation Cheatsheet 题解[第一周] Ceph集群运维问题记录 linux man高级技巧 Git 我错了！ Ceph源码解析(1)-Create Pool过程探究 准备Ceph开发环境 Ceph:Too Many PGs Per OSD UVA 11292 题解 Docker Private Registry(Ceph Swift) 搭建笔记 Ceph RBD 文件映射实验笔记 硬盘分区 硬盘模型 Ceph配置项 OSTEP 文件系统实现 在Ceph底层xfs上找到你上传的文件 使用s3cmd操作ceph rgw Ceph核心概念备忘录 COSBench使用笔记 GCJ2015 Qualification Round-B题解 使用saltstack部署运维ceph集群笔记 如何使用salt states? ceph-deploy命令详解 dd笔记 DTrace是什么？ Ceph Cache Tier笔记 Linux下理解filesystem/device/mount等概念 Base64编码详解与应用 URLEncoder学习笔记 Ceph论文阅读笔记 使用Python inotify监控文件变化 Git命令Snippets 使用Nginx做LB MathQuill学习笔记 Docker化Laravel开发环境 Ceph Pool PG配置说明 Ceph 笔记 Ceph源码分析 Latex数学符号 为Ceph OSS服务搭建LB Ceph RGW S3接口测试：诡异的403 AccessDenied问题 访问Ceph RGW失败 403 Forbidden问题 解决历程 Ceph RADOS论文研读笔记 Ceph源码分析：从一个REST请求，到OSD存储。 各种开源代码协议简述 OpenStack Projects简述 OpenStack Ceilometer 笔记 RabbitMQ 和 oslo.messaging Ceph Rest API 身份验证方式(S3) tcpdump笔记 Ceph集群部署笔记 Python PEP8规范笔记 Python Decorator(装饰器)模式 笔记 libvirt笔记 OpenStack oslo 概览 OpenStack KeyStone API http://localhost:5000/ 源码追踪 Python pdb笔记 zero length variety in a struct Jenkins' Hash Functions NTP部署笔记 Linux iptables笔记 Python Paste笔记 Python PasteDeploy笔记 Python eventlet笔记 使用curl测试RESTful接口 ubuntu14.04下安装devstack devstack 安装指南【最简单】 Docker操作记录 git merge 详解 Python 包管理详解 阿里云服务器设置swapfile的方法 shell脚本编写向导 搭建Laravel全栈开发环境 2016 May 22 题解[第一周] LA 3708 在一个圆环上，有n个点均匀分布，现在加入m个点（一共n + m个点）要求均匀分布，需要移动原先的点， 求移动距离和的最小值。 首先直觉告诉我们，n个点的均衡分布 和 (n + m)个点的均衡分布，至少公用一个点。也就是说，假设有一个 最优解没有公用一个点，那么这种情况也可以转化为公用一个点。这样我们就可以基于公用一个点来考虑，把 这个点当作是起点，考虑第2到n-1个点的摆放位置。在考虑第2到n-1点时，参考它临近的点，取一个最近的摆放即可。 #include <bits/stdc++.h> #define REP(i, n) for(int _n = n, i = 0; i < _n; i++) #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++) #define RFOR(i, b, a) for (int i = (b), _b = (a); i >= _b; i--) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) #define Abs(x) ((x) > 0 ? (x) :(-(x))) #define L(fmt, ...) do {if(true) printf(fmt"\n", ##__VA_ARGS__);} while(false) #define EP 0.0000000001 int main() { int n, m; const double L = 10000.00; while(scanf("%d%d", &n, &m) != EOF) { double dn = L/(double)n; double dm = L/(double)(m + n); double res = 0.0; FOR(i, 1, n - 1) { double remain = (dn * i) - floor(dn * i / dm) * dm; res += Min(remain, dm - remain); } printf("%.4lf\n", res); } return 0; } 看了其他的题解之后，其实周长是个绝对长度，可以不参与运算，最后结果乘以放缩比例即可。 Sumsets(hust) 这一题，给你一个整数，用2的n次幂来表示这个整数的和，问有多少种表示方法？ 例如7可以表示成6种： 1) 1 + 1 + 1 + 1 + 1 + 1 + 1 2) 1 + 1 + 1 + 1 + 1 + 2 3) 1 + 1 + 1 + 2 + 2 4) 1 + 1 + 1 + 4 5) 1 + 2 + 2 + 2 6) 1 + 2 + 4 这道题目，递推是个明显可以考虑的方向，关键是能想到奇偶性，因为二进制和奇偶性有天生的映射关系。 有些同学要说了，我就是没有想到奇偶性啊，这种直觉需要不断做题思考来培养。假设我们输入的是n, 我们要求的 结果为： f(n) 那么，如果n为奇数，则必定有一个1。那么： f(n) = f(n - 1) 如果n为偶数，如果有1，则至少有两个1，那么： f(n) = f(n - 2) 如果没有1，则都是2的倍数，则： f(n) = f(n/2) 这几种情况分开考虑，则可以写出递推关系。 #include <stdio.h> #define REP(i, n) for(int _n = n, i = 0; i < _n; i++) #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++) #define RFOR(i, b, a) for (int i = (b), _b = (a); i >= _b; i--) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) #define Abs(x) ((x) > 0 ? (x) :(-(x))) #define L(fmt, ...) do {if(true) printf(fmt"\n", ##__VA_ARGS__);} while(false) long long A[1000000 + 100]; int main() { int N; scanf("%d", &N); A[1] = 1; A[2] = 2; A[3] = 2; A[4] = 4; if (N <= 4) printf("%lld\n", A[N]); else { for (int i = 5; i <= N; i++) { if (i & 1) { A[i] = A[i - 1]; } else { A[i] = (A[i - 2] + A[i/2]) % 1000000000; } } printf("%lld\n", A[N]); } return 0; } CF353DIV2 C 给你n个值，和为0，这些值是循环邻接的，只允许一个操作，在邻近的数值之间进行转移数值， 目标是把所有的值都归零，求操作次数的最小值。 直觉上，如果能够就近清零，是最好的。假设，我们考虑环上（因为是循环邻接）一小段区间，该区间 的和为0，并且这一小段里，没有一个子小段，是和为0的。那么这一段具有0和原子性。ok，原谅我，我也知道 我说的有点让人听不懂。那么整个大环，就可以转化成多个0和子区间，这种转化是不唯一的。并且这些0和区间， 它的操作次数代价为区间长度-1，最优解就是，整个长度 - 最多划分0和区间个数。 好吧，上面这段只有我能看懂。下面用数学的形式化语言，进行定义说明： 假设n个值为 A[1…n], 并且这个n个值是循环邻接的，也就是说 A[1] 和 A[n]是邻接的。并且： \sum_{i=1}^nA[i]=0 我们以其中的一个子区间为研究对象，即A[b..e],注意，这里是环形的，也就是说b<=e不一定成立。假设 \sum_{i=b}^eA[i]=0 我们可以在A[1…n]中，找到很多像A[b…e]这样的区间。考虑A[b…e], 如果A[b…e]不能再次分隔（按照0和的性质）。 那么，对于A[b…e]全部元素清零，需要的操作次数是？LEN(A[b…e]) - 1, 即区间长度-1。 由于整个A[1…n]由多个类似A[b..e]这样的0和区间组成，则总共的操作次数为LEN(A[1..n]) - num(like A[b…e])。 也就是n-可以划分成0和区间的个数。问题转化成， 求可被划分的0和区间个数的最大值。可以使用前缀和来解决这个问题： 假设: prefixsum[j] = \sum_{i=1}^j A[i] 那么，我们只要找到prefix_sum里众数的个数，即为可以划分的0和组的最大个数。这里大家可以思考下，为什么？ 这样，代码如下： n = int(raw_input()) a = map(int, raw_input().split()) d = {} prefix_sum = [0] * n prefix_sum[0] = a[0] for i in range(1, n): prefix_sum[i] = a[i] + prefix_sum[i - 1] # dict prefix_sum for i in prefix_sum: if i in d: d[i] += 1 else: d[i] = 1 print n - max(d.values()) Please enable JavaScript to view the comments powered by Disqus. All content is licensed under CC BY-NC-SA Buit with Jekyll and 3-Jekyll theme • Hosted on Github Table of Contents