点分治 - hzwer.com

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,829链表,深度搜索,点分治

「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟
「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）「输入格式」第一行包括3个整数，n，m，K。接下来m行，每行2个整...
72016年6月26日6,647点分治,树状数组
「小奇模拟赛2」[BZOJ3784] 小奇的树
「题目背景」小奇在研究树时，遇到了一个难题。「问题描述」给定一棵n个节点的树，求前m条最长路径的长度。「输入格式」第1行2个整数n，m。接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的边。「输出格式」m行如题，从大到小输出。「样例输入」42121132143「样例输出」54「数据范围」序号nm数据类型1103暴力223323333暴力32000300000暴力42000300000暴力5500001随机生成6779817798随机生成7779827798随机生成877983...
22016年5月22日7,850STL,ST表,点分治
「CF293X」Croc Champ 2013 – Round 2
A.WeirdGame两个人都应该采取贪心策略根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些取0的时候同理，尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-673fb6aab3aba338647430/]B.DistinctPaths容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所...
22015年6月11日5,231贪心,深度搜索,点分治,数学,状压动规,概率与期望
PKUSC 2014 #1
A:unix纪元模拟[crayon-673fb6aab437d048969775/]B:连环锁真心不会格雷码QAQ[crayon-673fb6aab438a961005108/]C:Zhu'smultiset二分答案，得出每个数的增长开始时间[crayon-673fb6aab4398959947317/]D:TeamThemUp!二分图染色+dp[crayon-673fb6aab439f273879025/]F.Boatherds傻逼点分治[crayon-673fb6aab43b1603573930/] ...
42015年5月11日4,731递推与动规,模拟,STL,点分治,二分法,高精度,二分图染色
「BZOJ1095」[ZJOI2007] Hide 捉迷藏
Description捉迷藏Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激...
72015年4月20日24,841STL,线段树,点分治,最近公共祖先
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-673fb6aab5729842482282/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,298spfa,贪心,floyd,点分治
「点分治练习」[hdu4812] multik
「问题描述」给定一棵n个点的树,每个点有权值Vi问是否存在一条路径使得路径上所有点的权值乘积mod(10^6+3)为K输出路径的首尾标号,若有多解,输出字典序最小的解「输入格式」第一行两个数n,K第二行n个数,表示vi接下来n-1行每行两个数x,y表示一条边「输出格式」输出两个数a,b(a<b),无解输出”Nosolution”(不含引号)。「样例输入」5602523312132425「样例输出」34「数据规模与约定」对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2...
62015年1月12日6,277点分治,乘法逆元
「点分治练习」不虚就是要AK
「问题描述」czy很火，因为又有人说他虚了为了证明他不虚,他决定要在这次比赛AK现在他正在和别人玩一个游戏:在一棵树上随机取两个点(两个点可以相同)如果这两个点的距离是4的倍数,那么算czy赢,否则对方赢现在czy想知道他能获胜的概率以即约分数形式输出这个概率(即”a/b”的形式,其中a和b必须互质。如果概率为1,输出”1/1”)「输入格式」多组数据,对于每组数据第一行一个数n,表示树上的节点个数接下来n-1条边a,b,c描述a到b有一条...
52015年1月10日6,063点分治
「点分治练习」boatherds
「问题描述」询问一颗树上距离为K的点对是否存在「输入格式」第一行两个整数n,m接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K「输出格式」对于每个K每行输出一个答案存在输出”AYE”,否则输出”NYE”(不包含引号)「样例输入」2212112「样例输出」AYENYE「数据规模与约定」对于30%的数据,有1≤n≤100对于60%的数据,有1≤n≤10^31≤m≤50对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1...
12015年1月10日4,044STL,点分治
「SPOJ1825」Free tour II
Afterthesuccessof2ndanniversary(takealookatproblemFTOURformoredetails),this3rdyear,TravelAgentSPOJgoesonwithanotherdiscounttour.ThetourwillbeheldonICPCisland,amiraculousoneonthePacificOcean.WelistNplaces(indexedfrom1toN)wherethevisitorscanhaveatrip.Eachroadconnectingthemhasaninterestvalue,andthisvaluecanbenegative(ifthereisnothinginterestingtoviewthere).Simply,theseNplaces...
32015年1月1日5,135点分治
「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-673fb6aac5dd0315501249/] ...
52014年12月15日7,794STL,dijkstra,点分治