Menu Sidebar
Menu

Codeforces

CAS (Compare-and-Swap) 以及相关问题

CAS (Compare-and-Swap) 是一种硬件上, 实现非锁同步的一种方法. 这种方法比传统的blocked方法在硬件上实现, 效率高而且内存命中率高. CAS实现的是一种先验的赋值方法, 即: 给出一个当前值v, 当想改变这个当前值的时候, 一个线程需要进行先验操作, 以当前线程为观察者, 查看改变对象是否是当前线程中期待的对象的值. 如果是才去改变它.  整个行为并非通过锁住线程实现的, 而在硬件上, 访问一个内存片段上的速度远远快于在更高层锁住当前线程的速度. 所以CAS被认为是比所要快速的实现原子化操作的方法之一.CAS 和 CAS2 被用在了Java自带的AtomicInteger, AtomicBoolean, AtomicReference上. 这些变量都是可以常常用作判断线程进行状态的flag. 传统的关键字volatile只保证了变量的visibility, 却缺乏了accessibility. 而使用Java自带的原子变量, 可以更有效的, 快速的解决并发的实际问题. 一个CAS的赋值操作, 由一个pair组成: (expectedCurrentValue, newValue). 当赋值实现了CAS的变量一个新值的时候, 先验当前值是否等于expectedCurrentValue, 如果等于, 则赋newValue, 否则返回CAS变量的值, 这样, 通过比较返回的值, 就可以知道是否赋值成功. 通过以上的CAS, 延伸出了ConcurrentStack (Treiber, 1986), Non-blocking Queue (Michael and Scoot, 1996) 等non-blocking的数据结构. 这些数据结构因为更贴近硬件操作并且是线程安全的, 所以在新的JVM中, 很多Concurrent的数据结构都使用了这种CAS的思想. 但是设计一个CAS的数据结构, 需要充分理解数据结构在并发下的state机制, […]

Educational Codeforces Round 1 A. Tricky Sum

原题: http://codeforces.com/contest/598/problem/A 题目大意: 给一个数字n, 求1…n的合, 其中如果遇到2的倍数的数,要当负数处理. 分析: 直接求O(n) 会超时, 所以会想到求和公式. 通过观察可以发现, 给一个n, 我们可以: 求1到n的合, 用等差数列求和公式. 找到1到n中,有多少个2的倍数, 用对数公式, 这里注意, 1也是, 所以求完log后要用flooring求包含几个2的倍数后, 要加上1. 用公式 减去两杯的上面公式的结果就是答案了.

Codeforces Round #322 (Div. 2) B. Luxurious Houses

原题: http://codeforces.com/contest/581/problem/B 题目大意: 给n个数, 表示n层楼, 问从左向右, 加盖几层楼可以使得当前的楼比右边最高的楼还高. 分析:开始的时候直接写了一个O(n^2)的算法, i遍历每个楼, j遍历当前楼右边的楼找出最大. 后来超时了, 想想发现可以从右向左扫,记录一下max 如果当前楼比max矮, 则盖max-ary[i]+1层, 然后每次扫一个数都更新max.

Codeforces Round #322 (Div. 2) A. Vasya the Hipster

原题: http://codeforces.com/contest/581/problem/A 题目大意:  给两个数,n和m, 两个表示不同颜色的袜子, 每天都穿不同的袜子, 问几天能穿不同的袜子, 剩下的袜子能穿几天. 分析: 不同袜子就是两个数取最小, 剩下的袜子的数除以2就是剩下的袜子能穿几天

Codeforces Round #321 (Div. 2) C. Kefa and Park

原题: http://codeforces.com/contest/580/problem/C 题目大意: 给一个tree, tree上有几个mark的节点, 连续走m个mark的节点就不能继续往下走了. 问你能走到多少个leaf. leaf的定义是没有child的节点. 分析: 首先找出mark的节点的index, 存一下, 然后找到leaf的index, 存一下, 找leaf时, 看一下相邻的节点个数就可以判断出那个是leaf, 如果节点个数是1(只有父节点), 那么就是leaf. 然后从root dfs一下, 每次搜到一个mark的节点就计数, 达到m个就return, 然后遍历每个leaf节点, 如果这些节点都visited了, 那么就res++.

Codeforces Round #321 (Div. 2) B. Kefa and Company

原题:http://codeforces.com/contest/580/problem/B 题目大意: 给n,d两个整数,给n个pair<first,second>, 让你找second的合最大的pair组, 满足first之间的差值不大于d. 返回sum. 分析: 因为要满足的条件是pair中, first的差值不大于d, 所以首先我们要以first为基准, 排序n个pair. 其次,我们要找期中second的合最大的数组, 满足first的差不大于d, 这时, 我们已经知道, 答案在已排序的数组中, 并且是连续的子数组. 这时, 我们用双指针扫描. 第一个指针i扫整个pair组的每一个pair, 第二个指针j在i后边, 用来判断当前元素是否能满足abs(A[cur] .first – A[i].first) < d. 如果不满足, 要往前移动j,并且把A[j]从cur中踢除.. 然后每次取最大值.

Codeforces Round #321 (Div. 2) A. Kefa and First Steps

原题: http://codeforces.com/contest/580/problem/A 题目大意: 给一个数组, 找最大的连续非递减子数组. 分析: 这个…就扫一下, count一下每次有多少个连续的数是非递减的, 注意的是counter要从1开始. 因为如果一个数, 自己就是非递减的.

Codeforces Round #320 (Div. 2) [Bayan Thanks-Round] A. Raising Bacteria

原题: http://codeforces.com/contest/579/problem/A 题目大意: 繁殖细菌, 细菌每天翻倍, 每天都可以添加任意个数的细菌. 问最后得到n个细菌, 需要加多少个细菌. 分析: 倍数增加, 就是二进制的1的个数, 每过一天, 前一天的细菌个数都增加 <<1 个, 所以找一下n中有几个1就可以了.

Codeforces Round #319 (Div. 2) C. Vasya and Petya’s Game

原题: http://codeforces.com/contest/577/problem/C 题目大意: 给一个数字n, 一个人猜这个n是多少, 他可以提问: n是不是整除x, 问你最少提问多少次,问的是什么可以猜出n. 分析: 算术基本定理(https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). 可以证明,我们需要猜出每个n前边的的质数p, 对于每个p,我们还要猜出其不大于n的倍数, 才能确保n的唯一. 所以答案先晒质数, 再求倍数.

Codeforces Round #319 (Div. 2) B. Modulo Sum

原题: http://codeforces.com/contest/577/problem/B 题目大意: 给n个数, 问能不能找到其中的subsequence的合可以整除k. 分析: 额..这题开始做的时候考虑不周, 老是过不了, 后来加了个mod k 就过了. 看了答案后, 感觉思路差不多, 首先,当n>k时, 因为鸽巢原理, n个数,每个贡献1,肯定能找到合整除k的. 而当n<=k时, 我们可以通过记录数组当前数字与前一个数组合的模来判断是不是是否可以整除, 即: 如果合的模是0, 那么找到了答案返回YES.

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.