hzwer.com - Page 4

「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日2,904图论

「codeforces」数据结构杂题
一些数据结构简单题：570C.Replacement427B.PrisonTransfer519B.AandBandCompilationErrors650A.Watchmen466C.NumberofWaysCHSEQ22.ChefandFavouriteSequence460C.Present459D.PashmakandParmida’sproblem528A.GlassCarving704A.Thor339D.XeniaandBitOperations527527D.CliqueProblem718D.AndrewandChemistry570C.Replacement给定一个长为n的字符串（包含小写字母和'.'），有m次操作...
02016年10月23日3,758数据结构
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,038哈夫曼树,最小割,STL,dijkstra,深度搜索,二分法,欧拉图,AC自动机,记忆化搜索
《数据结构与算法》作业 —— KMP
英文好难，我好菜QAQ你们这里洋文好的人多得很哪求神犇指点
12016年10月8日2,946KMP
「CF715X」Codeforces Round #372 (Div. 1)
A.PlusandSquareRoot推公式可得，可构造每次按完的数为i*(i+1)[crayon-5b519d1507959330581527/]B.CompleteTheGraph给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L用f(i,j)表示从S到点i，经过j条无边权的边的最短路选择一个最小的j，使得f(T,j)+j<=L更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法，写起来会短一些...
02016年9月19日1,996dijkstra,构造
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-5b519d15080a0515814105/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
02016年9月14日2,148ST表,构造,二分法,树状数组,最短路
「JoyOI」P1001 – 1099题解(44 / 99)by hzwer
只写简要题解，详见JoyOI官方题解我会尽量给出简单直白的代码「JoyOI1001」第K极值排序，计算出m并判断其是不是质数只需要循环到√m即可[crayon-5b519d1508b6b829750518/]「JoyOI1002」NOIP2005谁拿了最多奖学金模拟[crayon-5b519d1508b76256986884/]「JoyOI1003」越野跑如果是平地，来回要花2F时间，否则花U+D的时间[crayon-5b519d1508b7b326332951/]「JoyOI1004」滑雪记忆化搜索，从每个点向更低点记忆化...
62016年8月25日17,345入门
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,297递推与动规,回文自动机,概率与期望
BestCoder Round #84
1001Aaronson对n做二进制拆分，注意m对30取min[crayon-5b519d150ae0b233290668/]1002Bellovin直接输出F，显然是字典序最小的方案[crayon-5b519d150ae17337085374/]1003Colmerauer用单调栈预处理下每个点向左/右第一个小等于它的元素，向上/下第一个大等于它的元素（一开始我用set预处理结果TLE）。然后计算每个元素对答案的贡献，若设四个方向第一个使得其不能成为鞍点的数与其的距离分别为L,R,U,D则其对答案的贡献为L...
22016年7月24日2,294算法
「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-5b519d150b69a069584145/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-5b51...
02016年7月20日2,855递推与动规,状压动规,拓扑排序,概率与期望
AHSOFNU NOIP模拟赛整理(update)by hzwer
把几个包整合了一下，并做了一些修改------------------------以下是原文-------------------------------既然我退役了就发点福利给大家2014-2015年我校各类模拟赛。。。包括我和lwh学长从各处搬运的。。。以及部分原创题。。。大部分为noip难度希望能对大家起到一点帮助0.0链接:https://pan.baidu.com/s/1c3tbLOs密码:2wq7文件夹里没有题解的话。。。我的博客里也许有。。。还有在vjudge上组的题大家有好的套题分享的可以通过...
412016年7月16日10,749算法
FJ2016集训 day7
题目来自coolinging（orz）Problem1挑选子序列(sequence.cpp/c/pas)题目来源：原创考察要点：搜索与剪枝、dancinglinks、二分、排序涉及要点：动态规划、随机化算法、贪心解题报告：题目可以理解为在串t中选取m个字母，每个字母覆盖串s1和串s2的部分位置，使串s1和串s2被完全覆盖，求满足如上条件时距离的最小值。对于数据点1，n<=10，T<=10，可以直接枚举选取哪m个字母，简单计算即可。由此可知，对于本题来说，判定比求解...
42016年7月9日2,978深度搜索,链表,点分治