• 【cf715X】Codeforces Round #372 (Div. 1)

    【cf715X】Codeforces Round #372 (Div. 1)

    A.PlusandSquareRoot推公式可得,可构造每次按完的数为i*(i+1)[crayon-59e5ceeca10ae144547321/]B.CompleteTheGraph给一张无向图,要求赋值一些边的边权,使得最终S到T的最短路为L用f(i,j)表示从S到点i,经过j条无边权的边的最短路选择一个最小的j,使得f(T,j)+j<=L更改这条路径上的边权,使得最短路为L,将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法,写起来会短一些...

    02016年9月19日1,484dijkstra,构造
  • 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-59e5ceeca17c1195924368/]1007FriendsandEnemiesn个人,每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...

  • 【cf698X】Codeforces Round #363 (Div. 1)

    【cf698X】Codeforces Round #363 (Div. 1)

    A.Vacations题意:给出每天contest和gym的开关状态,不能连续俩天参加相同活动,问n天最少休息多少天用F(i,0-2)表示前i天,第i天的状态为(rest,contest,sport),最多能有多少天不休息简单dp一下[crayon-59e5ceeca1f97249862415/]B.FixaTree给出n个结点的父亲,问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树,剩下的每个环要选出一个当根,然后再把所有的环连成树答案是环数-(是否存在自环)[crayon-59e5...

  • 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,258深度搜索,链表,点分治
  • FJ2016集训 day5

    FJ2016集训 day5

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

    42016年7月7日1,805并查集
  • Codeforces Round #360 (Div. 1)

    Codeforces Round #360 (Div. 1)

    A.NP-HardProblem二分图染色[crayon-59e5ceeca3cd6393824021/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-59e5ceeca3ce6651451335/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-59e5ceeca3cf5767159317/] ...

  • 2014pku计算概论入学测试

    2014pku计算概论入学测试

    poj1961Periodkmp求出fail数组后,前i个的重复子串就是i-fail(i)[crayon-59e5ceeca43bd468046033/]poj1276 CashMachine用f(i,j)表示前i种面值,达到j的面值和,所需要的第i种钞票的最少数量[crayon-59e5ceeca43ca268634664/]poj1702 Eva'sBalance先把n转为3进制,若p位为2,就在左盘放3^p,进位若p位为1,就在右盘放3^p[crayon-59e5ceeca43d4760873573/]poj1273 DrainageDitches大名鼎鼎的草地排水,网络流模板[crayon-5...

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

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

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

    72016年6月26日3,470点分治,树状数组
  • 树上问题入门

    树上问题入门

    结点、叶结点、分支结点、儿子结点有根树,无根树子孙、祖先、兄弟结点结点的度,结点的层次,树的度,树的深度森林,仙人掌,沙漠树的存储树的遍历结点的父亲,树的深度,树上距离,树的子树大小,树的最大子树,子树的最长链(以子树的根为一个端点,叶为另一个端点),子树最大权,次长链公共祖先,最近公共祖先链的长度树的直径树的重心[crayon-59e5ceecc4531935636411/] ...

    02016年6月14日984
  • 二叉搜索树/set入门

    二叉搜索树/set入门

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

    02016年6月12日1,626STL,
  • 【小奇模拟赛2】小奇的危机

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

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

    02016年5月22日1,759STL,dijkstra,分块
  • 【小奇模拟赛2】[bzoj3784]小奇的树

    【小奇模拟赛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日3,421ST表,STL,点分治
  • 【cf623X】AIM Tech Round (Div. 1)

    【cf623X】AIM Tech Round (Div. 1)

    A.GraphandString题意n个点,每个点有a,b,c其中一种颜色,若两个点颜色的字母相邻则它们之间连边。给出图的连边情况,求一种可行的染色方案。题解如果有一个点和其它点都有连边,将其标号b。然后选择一个未被标号的点,标号为a,二分图染色。最后验证一下即可。[crayon-59e5ceecc5f9f906994674/]B.ArrayGCD题意给定长为n的数列和两个操作,每个操作用一次1.移除数列的一个子串,代价是长度*a2.对于一些数字+1或者-1,每个数...