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 28 题解[第二周] CF354DIV2B 用酒杯架起金字塔，从上往下倒酒，问t秒的时候，已经满了的酒杯有多少个？ 因为题目的数据规模不大，所以第一个应该想到的是模拟，我没有第一个想到，所以 失败。过了一段时间之后才想到，但实现模拟时速度慢，而且有一个地方没有优化， 也就是我是一秒一秒的模拟的，而题目并不关心，每一秒的状态，只关心最后一秒。 所以只需要一股脑的把所有酒一起倒下去即可。代码如下： n, t = map(int, raw_input().split()) glass = [] for i in range(n): glass.append([0] * (i + 1)) cham = 2 ** (n - 1) j, cur = 0, [cham * t, ] flag = cham * t while flag != 0 and j < n: size = len(glass[j]) res = [] for k in range(size): # judge cur[k] ~ glass[j][k] pending = [] if cur[k] + glass[j][k] <= cham: pending = [0.0, 0.0] glass[j][k] += cur[k] flag -= cur[k] else: delta = cur[k] + glass[j][k] - cham flag -= (cham - glass[j][k]) pending = [delta/2.0, delta/2.0] glass[j][k] = cham if len(res) == 0: res.extend(pending) else: res[len(res) - 1] += pending[0] res.append(pending[1]) cur = res j += 1 # count full res = 0 for i in range(n): tmp = glass[i] res += tmp.count(cham) print res HDU1005 数论水题： f(1) = 1, f(2) = 1 f(n) = (A * f(n - 1) + B * f(n - 2)) % 7 给你n，要你求f(n)。因为数据规模很大，所以如果递推的话，会超时。这个时候，我们需要找规律。 首先，f(n)的取值范围是[0, 6]，这是一个很有用的信息，由f(n)的表达式观察，必然会在有限的迭代过程中出现循环。 考虑两个连续的pair=>(f(n - 1), f(n)), 最多有 7 ＊ 7 ＝ 49种情况。 #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) using namespace std; int F[100]; map<string, int> M; string make_key(int a, int b) { return to_string(a) + ':' + to_string(b); } int main() { int A, B, n; F[1] = F[2] = 1; while(scanf("%d%d%d", &A, &B, &n) && !(A == 0 && B == 0 && n == 0)) { M.clear(); M[make_key(F[1], F[2])] = 2; int i = 3; int j = -1; do { F[i] = (A * F[i - 1] + B * F[i - 2]) % 7; string key = make_key(F[i], F[i - 1]); if (M.find(key) == M.end()) { M[key] = i; } else { j = M[key]; break; } i++; } while(true); // from j => i - 1 if (n < j) printf("%d\n", F[n]); else { int idx = (n - j) % (i - j); idx += j; printf("%d\n", F[idx]); } } return 0; } 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