hzwer.com - Page 4

「CF718X」Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-5ba8175bd8c14011008814/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
02016年11月7日3,901模拟,贪心,树形动规,线段树,广度搜索,状压动规,哈希表,记忆化搜索,矩阵乘法

2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-5ba8175bd9248772843824/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-5ba8175bd9251101855927/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
02016年11月6日2,784模拟,递推与动规,KMP,贪心,深度搜索,构造,主席树,二分法
「codeforces」图论杂题
一些图论简单题：500A.NewYearTransportation437C.TheChildandToy510C.FoxAndNames475B.StronglyConnectedCity639B.BearandForgottenTree3623A.GraphandString449B.JzzhuandCities543B.DestroyingRoads500A.NewYearTransportation有n个城市排成1排，从第i个城市可以走到\(i+a_i\)号城市，并给定一个城市t，问是否能从1到t？\(1\leqn,a_i\leq10^5\)题解将1打个标记，从左往右扫一遍，若i打上标记，...
32016年11月6日3,142图论
「codeforces」数据结构杂题
一些数据结构简单题：570C.Replacement427B.PrisonTransfer519B.AandBandCompilationErrors650A.Watchmen466C.NumberofWaysCHSEQ22.ChefandFavouriteSequence460C.Present459D.PashmakandParmida’sproblem528A.GlassCarving704A.Thor339D.XeniaandBitOperations527527D.CliqueProblem718D.AndrewandChemistry570C.Replacement给定一个长为n的字符串（包含小写字母和'.'），有m次操作...
02016年10月23日4,058数据结构
2016 ACM / ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
12016年10月8日4,291哈夫曼树,最小割,STL,深度搜索,dijkstra,二分法,AC自动机,欧拉图,记忆化搜索
《数据结构与算法》作业 —— KMP
英文好难，我好菜QAQ你们这里洋文好的人多得很哪求神犇指点
12016年10月8日3,075KMP
「CF715X」Codeforces Round #372 (Div. 1)
A.PlusandSquareRoot推公式可得，可构造每次按完的数为i*(i+1)[crayon-5ba8175be9d97522327745/]B.CompleteTheGraph给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L用f(i,j)表示从S到点i，经过j条无边权的边的最短路选择一个最小的j，使得f(T,j)+j<=L更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法，写起来会短一些...
02016年9月19日2,115dijkstra,构造
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-5ba8175bea263268987866/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
02016年9月14日2,274ST表,构造,二分法,树状数组,最短路
「JoyOI」P1001 – 1099题解(44 / 99)by hzwer
只写简要题解，详见JoyOI官方题解我会尽量给出简单直白的代码「JoyOI1001」第K极值排序，计算出m并判断其是不是质数只需要循环到√m即可[crayon-5ba8175beac28858277271/]「JoyOI1002」NOIP2005谁拿了最多奖学金模拟[crayon-5ba8175beac31114990463/]「JoyOI1003」越野跑如果是平地，来回要花2F时间，否则花U+D的时间[crayon-5ba8175beac36136984212/]「JoyOI1004」滑雪记忆化搜索，从每个点向更低点记忆化...
62016年8月25日18,369入门
2016 Multi – University Training Contest 5
本场抱住卓神大腿最后过了7题。。。感觉把PKU的牌子砸了。。。我做了100110051011随便口胡几句。。。1010看起来像后缀数组。。。但是交wa了几发不知道什么情况1001ATMMechine这题似乎0元钱也要取1次1元的来确认一下，不然没法解释样例\(f(i,j)\)表示有i元以内的钱，j次warning的机会然后枚举询问点k，有t种可能warning，那么转移给\(f(t-1,j-1)\)有i-k+1种可能取钱，转移给\(f(i-t,t)\)边界j为1的情况，有k元钱需要询问k+1次...
12016年8月3日3,503回文自动机,递推与动规,概率与期望
BestCoder Round #84
1001Aaronson对n做二进制拆分，注意m对30取min[crayon-5ba8175bec93c101027023/]1002Bellovin直接输出F，显然是字典序最小的方案[crayon-5ba8175bec945284863955/]1003Colmerauer用单调栈预处理下每个点向左/右第一个小等于它的元素，向上/下第一个大等于它的元素（一开始我用set预处理结果TLE）。然后计算每个元素对答案的贡献，若设四个方向第一个使得其不能成为鞍点的数与其的距离分别为L,R,U,D则其对答案的贡献为L...
22016年7月24日2,416算法
「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-5ba8175bed110988786913/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-5ba8...
02016年7月20日2,985递推与动规,状压动规,拓扑排序,概率与期望