hzwer.com - Page 5

FJ2016集训 day5
打了个酱油，身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn)，常数较小。假如写了常数较大的可以得到80分。[crayon-5b2990b7b99d04...
42016年7月7日2,236并查集

Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-5b2990b7ba1b1067771798/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-5b2990b7ba1bb883887415/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-5b2990b7ba1c0029478461/] ...
02016年6月30日2,515背包动规,二分图染色,最大公约数与最小公倍数
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-5b2990b7c5421012124357/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-5b2990b7c542c095745344/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-5b2990b7c5432669934633/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-5...
42016年6月30日3,124递推与动规,KMP,最大流,后缀数组
2013PKU计算概论入学测试
OpenJ_Bailian3254.约瑟夫问题2模拟，用vector比较方便[crayon-5b2990b7c5f14550006533/]poj2393.Yogurtfactory求出将酸奶保存到某一天的最小代价贪心[crayon-5b2990b7c5f1e381873831/]poj1321.棋盘问题回溯裸题[crayon-5b2990b7c5f22820215849/]poj2576.TugofWarf(i,j,k)表示前i个选j个能不能凑成k，第一维滚动[crayon-5b2990b7c5f27054320276/]poj1974.RebuildingRoads用f(i,j)表示子树i，剩j个结点需要至少删多少条边[c...
22016年6月28日2,214模拟,贪心,深度搜索,树形动规
「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟
「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）「输入格式」第一行包括3个整数，n，m，K。接下来m行，每行2个整...
72016年6月26日4,326点分治,树状数组
「NOI考前欢乐赛」小奇遐想
「题目背景」撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑——《清风醉梦》「问题描述」小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，c，d，使得h_a<h_b<h_d<h_c，即看起来像是彩虹的形状！它想知道有多少种方案数。「输入格式」第一行包括1个整数n。第二行包括n个整数，第i个正数表示h_i，保证这n个整数是...
02016年6月26日2,332树状数组
「NOI考前欢乐赛」小奇赏花
「题目背景」桃之夭夭还绿了芭蕉管他雨打风吹夜潇潇花绽了新红也会凋少年的心儿永不老——《桃花笑》「问题描述」小奇的花园里有n行m列棵桃花树，花色各不相同。小奇漫步在花园中，有时它觉得某一行/列的桃花很美，便会在这一整行/列的每棵树下捡一枚花瓣，到了傍晚，他发现自己选择了r行c列（同一行/列可能被选择不止一次）的花瓣。回家之后，小奇发现：有s种颜色的花瓣数为奇数，他想知道，有多少种选择方案能有这样的效果呢？（...
02016年6月26日2,029排列组合
「NOI考前欢乐赛」小奇画画
「题目背景」红莲清泪两行欲吐半点却无如初是你杳然若绯雾还在水榭畔画楼处是谁衣白衫如初谁红裳如故——《忆红莲》「问题描述」小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）「输入格式」第一行包括1个整数n。接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一...
02016年6月26日2,118广度搜索
Codeforces Round #359 (Div. 1)
A.Robbers'watch可以先算出n-1,m-1所需的位数如果位数和超过7，根据抽屉原理，则一定会存在相同的数字特判一下输出0后，位数小等于7的情况暴力即可枚举i<n,j<m，七进制拆分一下看有没有相同数字[crayon-5b2990b7c8128718034771/]B.KayandSnowflake题意是询问一棵树某些子树的重心树的重心定义为，删去这个结点后，剩下的连通块大小不超过1/2*（总结点数）用yi表示x结点的儿子预处理size[x]和mx[x]表示树的大小，yi树的最...
32016年6月24日1,744树形动规
OI算法学习材料 by hzwer
复杂度分析见时间复杂度——经典解说有语言基础的同学建议练习 JoyOI前100题代码见「JoyOI」P1001-1099题解byhzwer省一以上水平的同学建议衡阳八中OJcodeforces 是个很好的竞赛网站STL入门基础「分块」数列分块入门1-9byhzwer考点见省选算法汇总一些早期的杂题包模拟赛整理另外一些课件和题课件题目还有在vjudge上组的题 ...
122016年6月23日18,292算法
「计算几何模板」「CF498A」Crazy Town
CrazyTownisaplaneonwhichthereareninfinitelineroads.Eachroadisdefinedbytheequationaix + biy + ci = 0,whereaiandbiarenotbothequaltothezero.Theroadsdividetheplaneintoconnectedregions,possiblyofinfinitespace.Let'scalleachsuchregionablock.Wedefineanintersectionasthepointwhereatleasttwodifferentroadsintersect.Yourhomeislocatedinoneoftheblocks.TodayyouneedtogettotheUniversity,alsolocatedin...
02016年6月18日2,206几何
「NOI联考by ysy」庆典
「题目描述」战狂在昌和帝国的首都法法城召开了庆典，向一万名最杰出的士兵分发了用魔法猪做的猪肉饺子，士兵们吃了猪肉饺子后，战斗力大幅提高。为了保护战狂的安全以及维护现场秩序，大预言家抽调了n名普通士兵组成了m个小队完成一些不同的任务。由于一些特殊的原因，所有小队的人数都互不相同。你需要求出有多少种可能的组队方案。注意士兵是相同的，而小队是不同的。「输入数据」第一行两个个整数n，m。「输出数据」一行一个数...
02016年6月17日1,428递推与动规