Menu Sidebar
Menu

Codeforces

Educational Codeforces Round 1 D. Igor In the Museum

原题:http://codeforces.com/contest/598/problem/D 题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个. 分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是!@#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多.

 

Educational Codeforces Round 1 B. Queries on a String

原题: http://codeforces.com/contest/598/problem/B 题目大意: 给一个string, 给l,r,k三个数, l和r是其中的char的index(以1为底), 求k次右shift后的string 分析: 没有什么算法, 就是注意是以1为底, 然后特殊情况有两种, 一个是k比r-l+1大, 所以取余, 另一个是r==l, 别的都是照常实现就好.

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的唯一. 所以答案先晒质数, 再求倍数.

Older Posts

书脊

倾城与倾国, 佳人难再得