数据结构 - Page 2

2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-67430554b413f757766233/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-67430554b414a550114272/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
12017年8月8日6,063递推与动规,贪心,单调队列,图的连通,二分图匹配,扩展欧几里得算法

程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-67430554b4d32453709959/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-67430554b4d40324927276/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-67430554b4d48274332295/]POJ2373DividingthePath用dp(i)...
12017年6月24日8,635递推与动规,STL,快速幂,单调队列,莫队算法,高斯消元
程序设计实习实验班2017作业(算法作业19, 20, 21)
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-67430554b5729681966681/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-67430554b5733980690554/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-67430554b5737056220758/]「poj1523」SPF求割点，并且求删去割点后的连通分量个数[cr...
02017年6月24日7,374状压动规,树状数组,博弈论,树上倍增,矩阵乘法
程序设计实习实验班2017作业(算法作业1, 5)
「Bailian4115」鸣人和佐助bfs的时候多一维记录查克拉[crayon-67430554b5fe1776360861/]「poj1190」生日蛋糕/泰国佛塔从下往上一层一层搜索，每一层枚举半径和高度（注意范围）根据每一层半径和高度严格递减，进行一些剪枝：1、剩下的若干层都放最小的圆柱，体积也不够2、剩下的若干层都放最小的圆柱，得出的表面积比当前最优解劣3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣[crayon-67430554b5ff2792281757/]「B...
52017年3月27日8,829递推与动规,STL,深度搜索,广度搜索,记忆化搜索
2015程序设计实习实验班免修考试(校内)
「poj1037」decorativefence用f(i,j)表示长度为i，开头为j，开头为上升的序列用g(i,j)表示长度为i，开头为j，开头为下降的序列考虑在序列的第二位放一个数字，改变上升/下降预处理完之后，一位位枚举贪心[crayon-67430554b6f25587073546/]「poj1011」Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时，如果不能加入某根木棍，同种长度的木...
02017年2月19日7,781递推与动规,深度搜索,线段树,最大流,广度搜索,博弈论
2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-67430554b77d4719532242/]05:MPIMaelstrom[crayon-67430554b77de040298665/]06:Ultra-QuickSort[crayon-67430554b77e3343430331/]08:DrainageDitches[crayon-67430554b77e8218060648/] ...
02017年2月10日6,337STL,floyd,最大流,树状数组
「CF718X」Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-67430554b7cd7874200618/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
02016年11月7日8,125模拟,贪心,树形动规,线段树,广度搜索,哈希表,状压动规,记忆化搜索,矩阵乘法
2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-67430554b8320894836433/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-67430554b8329208888713/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
02016年11月6日5,682模拟,递推与动规,KMP,贪心,深度搜索,构造,主席树,二分法
「codeforces」数据结构杂题
一些数据结构简单题：570C.Replacement427B.PrisonTransfer519B.AandBandCompilationErrors650A.Watchmen466C.NumberofWaysCHSEQ22.ChefandFavouriteSequence460C.Present459D.PashmakandParmida’sproblem528A.GlassCarving704A.Thor339D.XeniaandBitOperations527527D.CliqueProblem718D.AndrewandChemistry570C.Replacement给定一个长为n的字符串（包含小写字母和'.'），有m次操作...
02016年10月23日11,660数据结构
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日7,724哈夫曼树,最小割,STL,深度搜索,dijkstra,二分法,AC自动机,欧拉图,记忆化搜索
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-67430554d3a1f882598041/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
02016年9月14日3,962ST表,构造,二分法,最短路,树状数组
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日5,836链表,深度搜索,点分治