• 2016 ACM/ICPC Asia Regional Dalian Online

    2016 ACM/ICPC Asia Regional Dalian Online

    1002DifferentGCDSubarrayQuery问长为n的序列,m个询问,问区间[L,R]所有子段的不同gcd值个数考虑固定左端点,随着右端点的移动,gcd至多衰减log次(每次至少折半)从n开始添加询问的左端点,用树状数组维护每个gcd右端点的最小值[crayon-5a31dc3529c89439897383/]1007FriendsandEnemiesn个人,每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...

  • FJ2016集训 day7

    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,430深度搜索,链表,点分治
  • 【NOI考前欢乐赛】[bzoj3648]小奇泛舟

    【NOI考前欢乐赛】[bzoj3648]小奇泛舟

    【题目背景】微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》【问题描述】小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美,名花异石甚多,小奇在地图上标记了n处景观(标号从1到n),有些景观通过溪流连接,这样的溪流有m段。小奇想知道,有多少种泛舟的路径,经过的景观数大于等于K呢?(小奇不喜欢一次泛舟重复经过一个景观)【输入格式】第一行包括3个整数,n,m,K。接下来m行,每行2个整...

    72016年6月26日3,671点分治,树状数组
  • 【NOI考前欢乐赛】小奇遐想

    【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,013树状数组
  • 【分块】数列分块入门1-9 by hzwer

    【分块】数列分块入门1-9 by hzwer

    整理一些思路,然后我会在CH小组内出一系列的分块训练题https://www.contesthunter.org/group/%E7%A6%8F%E5%BB%BA%E5%B8%88%E5%A4%A7%E9%99%84%E4%B8%AD已完结由于每道题题面太长,限于篇幅,只给出大意,具体题目见小组内赛题,代码附在文末 可能涉及的几个词语解释:区间:数列中连续一段的元素区间操作:将某个区间[a,b]的所有元素进行某种改动的操作块:我们将数列划分成若干个不相交的区间,每个区间...

    132016年6月18日9,205分块
  • 【STL练习】丑数

    【STL练习】丑数

    题目描述丑数是指不能被2,3,5以外的其他素数整除的数。把丑数从小到大排列起来,结果如下:1,2,3,4,5,6,8,9,10,12,15,......请编写一个程序,求第k个丑数。输入一个整数k(k<=1500)。输出仅有一个整数为第k大丑数。样例输入[crayon-5a31dc3531548402404905/]样例输出[crayon-5a31dc3531557366041172/]题解STL练习,每次从数据结构中取出最小值x,加入2x,3x,5xpriority_queue[crayon-5a31dc353155c103058501/]priority_que...

    12016年6月15日1,744STL
  • 【bzoj1208】[HNOI2004]宠物收养所

    【bzoj1208】[HNOI2004]宠物收养所

    Description最近,阿Q开了一间宠物收养所。收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物,阿Q根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养所总是会有两种情况发生:被遗弃的宠物过多或者...

    82016年6月14日6,784STL,splay
  • 【二叉搜索树/set/朝鲜树/替罪羊树】快速排序

    【二叉搜索树/set/朝鲜树/替罪羊树】快速排序

    本文上接http://hzwer.com/8009.htmlhttps://www.contesthunter.org/contest/%E5%B9%B3%E8%A1%A1%E6%A0%91%E8%AE%B2%E8%A7%A3/%E6%8E%92%E5%BA%8F这题当然可以直接调用sort[crayon-5a31dc3575033175415872/]用set实现排序[crayon-5a31dc3575044989322178/]用二叉搜索树来排序,不能通过已经排序好的大数据点[crayon-5a31dc357504b599983984/]可以打乱输入的数据实现深度期望[crayon-5a31dc3575052499583992/]...

    32016年6月13日2,862替罪羊树
  • 二叉搜索树/set入门

    二叉搜索树/set入门

    仅列出纲要二叉树— 结点,叶结点,分支结点,结点的度左右孩子— 树的深度,大小二叉树类型—  满二叉树—  完全二叉树—  平衡二叉树二叉搜索树—性质1.前驱后继2.如何查找?—构建1.对已经排序的数快速构建二叉搜索树2.如何顺序插入?效率讨论STL-set顾名思义的操作—什么是Iterator?如何遍历set?用法示例—[crayon-5a31dc3576715795086794/] 替罪羊树阅读http://pan.baidu.com/share/link?shareid=318543&a...

    02016年6月12日1,815STL,
  • 【codevs2875】RY哥查字典

    【codevs2875】RY哥查字典

     题目描述DescriptionRY哥最近新买了一本字典,他十分高兴,因为这上面的单词都十分的和谐,他天天查字典。输入描述InputDescription1个整数N,表示字典里面的单词数量。接下来N行,每行一个字符串,表示一个单词。然后第N+2行,一个整数M,表示要查的单词数。接下来M行,每行一个字符串,表示一个要查的单词。输出描述OutputDescription对于每一个要查的单词,如果在字典里面,就输出'Yes',否则输出'No',一行一个。样例输入Sa...

    02016年6月12日1,135哈希表
  • 【codevs1004】四子连棋

    【codevs1004】四子连棋

    题目描述 Description在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜线),这样的状态为目标棋局。●○●○●○●●○●○○●○ 输入描述 InputDescription[crayon-5a31dc3577ac5837497910/]输出描述 Ou...

    02016年6月12日5,817哈希表,广度搜索
  • 【codevs1230】元素查找

    【codevs1230】元素查找

    题目描述Description给出n个正整数,然后有m个询问,每个询问一个整数,询问该整数是否在n个正整数中出现过。输入描述InputDescription第一行两个整数n和m。第二行n个正整数(1<=n<=100000)第三行m个整数(1<=m<=100000)输出描述OutputDescription一共m行,若出现则输出YES,否则输出NO样例输入SampleInput42213419样例输出SampleOutputYESNO数据范围及提示DataSize&Hint所有数据都不超过10...

    12016年6月11日2,112STL,哈希表
  • 【小奇模拟赛2】小奇的危机

    【小奇模拟赛2】小奇的危机

    【题目背景】小奇驾驶飞船来到了一个奇怪的星球,这个星球的所以城市都在地下,而且由于环境不断恶化,星球上发生了可怕的生化危机。【问题描述】星球上有n个城市,标号为1-n,用n-1条双向通道连接,保证任意两个城市能互相到达。生化危机爆发了!但由于政府安全能力有限,安全区只包括在标号l到r的城市,小奇现在在城市x,它想知道最近的安全城市的距离。【输入格式】第一行有1个整数n。接下来n-1行,每行3个整数u,v,l,表示u,...

    02016年5月22日1,903STL,dijkstra,分块