• avatar 咖啡蛇 2019-02-19 22:15:00

    HDU-2802-F(N)

    看到这题讨论版里有说用公式的有说用循环节的,但是个人觉得这两种方法都不靠谱,比赛场上做这种题能直接推出公式需要很强数学功底,而循环节的方法如果循环节比较大就不太好发现了。这种已知通项公式的题还是用矩阵快速幂比较通用,但同是矩阵快速幂,对于这题,也有很大的差异; 注:memmove这个函数可能不太常

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-16 20:54:00

    HDU-2642-Stars

    题意: 输入一个M,然后M次操作。'B'表示增加一个点,坐标为(x, y),如果存在不操作。'D'表示删除一个点,坐标为(x, y),如果不存在不操作。'Q'表示一次询问,输出给定范围内点的个数。 思路1: 如果本题将二维转换成一维。可以用前缀和的思想,假如求线段[y1, y2]上面点的数量可

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-13 21:21:00

    HDU-2824-The Euler function(欧拉函数)

    欧拉筛 Accepted 2824 343MS 24856K 546 B G++ #include "bits/stdc++.h"

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:02:00

    ACM小白入门之必须要了解的东西

    ACM 国际大学生程序设计竞赛历史与介绍 程序设计竞赛是指考察程序设计能力的竞赛,分为解题竞赛、创意竞赛、性能竞赛等。程序设计竞赛的主要代表是 ACM-ICPC(ACM 国际大学生程序设计竞赛),ACM 程序设计大赛是大学级别最高的脑力竞赛,素来被冠以"程序设计的奥林匹克"的尊

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 12:02:21

    P2240 【深基12.例1】部分背包问题(贪心)难度⭐

    题目链接 很经典的一道贪心题,今天在洛谷上刷到了,就再做一遍 竟然是道黄题,赶紧水一下 没想到竟然WA了一次,确实提醒了我一下,写题的时候别手***r> 思路就是一个简单的贪心,按照性价比来排序,因为金币是可以分开的所以拿不完就拿一部分 还有就是其实有除的话尽量推公式换成乘法,除容易有误差但

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 12:02:42

    P1892 [BOI2003]团伙(并查集,反集)难度⭐⭐★

    题目链接 反集 如果a和b是敌人,合并n+b和a,n+a和b 如果c和a是敌人,合并n+c和a,n+a和c 那么b和c自然就合并在一起了 这样就符合了题目敌人的敌人是朋友的规则 注意 并查集不要忘了初始化 注意 输入的时候scanf要用%s 因为scanf遇见空格是不会跳的,所以尽量这

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-02-13 12:56:00

    HDU-2594-Simpsons’ Hidden Talents

    kmp Accepted 2594 0MS 1484K 671 B G++ #include "cstdio" using name

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-13 12:17:00

    HDU-2609-How many(最小表示法)

    思路: 将输入的字符串转换成字典序最小的表示形式,存入set去重。用字典序最大的形式表示也是一样的; 最小表示法 Accepted 2609 62MS 3296K 804 B G++

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:03:03

    P1525 关押罪犯(需要巧妙思维的并查集/二分图)难度⭐⭐⭐★

    洛谷题目链接 输入 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 输出 3512 1.并查集 有意思的一道并查集的题,需要一些思维。 用并查集来维护,当a和b并到一起的时候说明他们两个在同一个监狱之中。

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-02-12 12:05:00

    CF-1114C-Trailing Loves (or L'oeufs?)

    题意: 输入n和m,求n!转换成m进制之后末尾有多少个0; 思路: 转换一下题意就可以看成,将n表示成x * (m ^ y),求y的最大值。^表示次方而不是异或; 这就比较好想了,将m分解质因数,对于每个质因数,设n!含有a个,m含有b个,则ans = min(ans, a / b);

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-10 15:30:00

    HDU-2588-GCD

    欧拉函数 Accepted 2588 15MS 1372K 916 B G++ #include "bits/stdc++.h" u

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-09 22:29:00

    HDU-2222-Keywords Search(AC自动机)

    这题是AC自动机的模板题,AC自动机是结合了字典树,和KMP两种算法产生的,去年为了学习AC自动机去看了前面说的两种算法,但是可能因为KMP当时理解的不够透彻所以这题当时也只是半背代码的做出来了,没多久就忘了。经过那么久的学习感觉KMP掌握的差不多了,今天回顾了一下AC自动机,并记录一下模板

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-08 11:24:00

    CF-1110C-Meaningless Operations

    题意: 输入q,然后输入q个a,对于每个a,找到一个b,使gcd(a ^ b, a & b)最大,输出这个最大的gcd; 思路: 用k表示a二进制最高位的二进制编号,1,2,4,8对应1,2,3,4;  假如a不是 (1 << k) - 1这种形式的,那么总能找到一个b使

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:03:25

    P1047 校门外的树(线段树优化)(校门三部曲)难度⭐⭐

    校门三部曲,总算完结了!完结散花! 难度呈阶梯状,都可以用线段树解决。 第一部 P1047 校门外的树(线段树优化)难度⭐⭐ 第二部 P1276 校门外的树(增强版)(线段树)校门三部曲难度⭐⭐⭐ 第三部 P5568 [SDOI2008]校门外的区间(离散数学应用+线段树+开闭区间处理)难度⭐⭐⭐⭐

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-02-06 20:16:00

    CF-1111C-Creative Snap

    前两天过年,所以两天前的比赛题目现在才来回顾。 这题是一个最平常的递归,加一个剪枝。题目说如果一段距离没有复仇者看守,消耗的能量为A,A一定是正整数。由此可知对于没有复仇者看守的段,不拆一定比拆成两半划得来。只有当这段距离有复仇者看守时,才比较拆开来划算还是不拆划算; 复仇者最多只有1e5个,所

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-06 19:51:00

    CF-1111B-Average Superhero Gang Power

    首先,对于这题我们要知道要删除一个数使平均值最大一定是删除最小的数,然后我们假设删除操作执行了i次,也就是删除最小的i个数。在已知删除操作次数之后求增加操作的次数就容易了,当然是m - i和k * (n - i)中比较小的数啦。用一个ans变量记录结果,遍历i,更新ans,得到最终的ans。

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-03 11:26:00

    HDU-2511-汉诺塔 X

    首先我们来求第m次移动的盘子号数,先列出当m比较小可以直接观察的前几项 m : 1、2、3、4、5、6、7、8、9、10 id : 1、2、1、3、1、2、1、4、1、2 很容易联想到树状数组的lowbit,这题的id就是lowbit(m)在二进制中的编号。   for (id = 1;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-01 21:08:00

    ZOJ-1183-Scheduling Lectures

    可以用贪心求最小讲课次数,贪心策略也很好想,就是对于任意主题,能早讲就早讲。这种方案的讲课次数一定是最少的,但是不满意指标不一定是最小,然后再利用动态规划求在最少讲课次数前提下的最小不满意指标。 方法一(自己想到的) Accepted 1

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:03:46

    P3366 【模板】最小生成树(链式前向星,prim,有坑)难度⭐⭐

    题目链接 输入: 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 输出: 7 链式前向星相比于矩阵,遍历的代码更加复杂一点,但是省空间,这道题用矩阵存就MLE,只能用链式前向星存。 又是 i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-31 20:30:00

    Painter

    时间限制:5000ms 单点时限:1000ms 内存限制:256MB 描述 杂货店出售一种由N(3<=N<=12)种不同颜色的颜料,每种一瓶(50ML),组成的颜料套装。 你现在需要使用这N种颜料;不但如此,你还需要一定数量的灰色颜料。

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-31 12:18:00

    POJ-1700-Crossing River

    贪心策略: 要么让最快的人依次把最慢的两个人渡过河再回来。要么让最快的两个人先过河,最快的人回来,然后最慢的两个过河,第二快的回来。直到剩余人数少于4人为止; 1700 Accepted 320K 16MS G++ 668B

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-31 11:34:00

    ZOJ-1163-The Staircases

    dp[i][j]表示i个砖头构成的最高台阶不高于j的楼梯数目 Accepted 1163 C++11 0 2280 #include "bits/stdc++.h" using namespac

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-30 20:58:00

    ZOJ-1177-K-Magic Number

    就是分别以1到9作为开头构造结果,取最小答案。看了参考书之后才做出来,对参考书上的代码进行了一些改进 Accepted 1177 C++11 0 408 #include "bits/stdc++.h&qu

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:04:07

    P3743 kotori的设备(二分答案,思维,线性)难度⭐⭐⭐

    题目链接 题目背景 kotori 有 n 个可同时使用的设备。 题目描述 第 i 个设备每秒消耗ai个单位能量。能量的使用是连续的,也就是说能量不是某时刻突然消耗的,而是匀速消耗。也就是说,对于任意实数 ,在 k 秒内消耗的能量均为k*ai 单位。在开始的时候第 i 个设备里存储着bi个单位

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-29 12:46:00

    HDU-3579-Hello Kiki (利用拓展欧几里得求同余方程组)

    设 ans 为满足前 n - 1个同余方程的解,lcm是前n - 1个同余方程模的最小公倍数,求前n个同余方程组的解的过程如下: ①设lcm * x + ans为前n个同余方程组的解,lcm * x + ans一定能满足前n - 1个同余方程; ②第 n 个同余方程可以转化为a[n] * y +

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-27 13:35:00

    HDU-1403-Longest Common Substring(后缀数组的高度数组运用)

    这题要求两个串中的最长相同子串的长度。高度数组可以求一个串中的最长相同子串的长度。所以想到把两个串连起来,但是这样又会产生一些新的串(第一个串的结尾和第二个串的开头组成的)于是在两个串中间放一个'\0'分隔,正好'\0'是字符里最小的,不会对第一个串的排序产生影响。 Acc

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-25 21:47:00

    洛谷-P3809-后缀排序(后缀数组)

    看了求后缀数组的倍增法之后很快就理解了,但是自己写的倍增法用map排序还是超时了。然后看了两天别人写的模板,题目是通过了,但感觉代码还是半懂半背的。以后多熟悉熟悉吧; 后缀数组 #include "bits/stdc++.h" using namespac

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-23 15:58:00

    HDU-1711-Number Sequence(KMP)(Rabin-Karp)

    Rabin-Karp Accepted 1711 904MS 5272K 1310 B G++ #include "bits/stdc++.h

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:04:28

    P1102 A-B 数对(二分,映射)难度⭐

    题目描述 给出一串数以及一个数字 C,要求计算出所有 A − B =

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-22 14:37:00

    HihoCode-1675-稀疏矩阵乘积

    上来先一顿暴力,结果70分就超时了。 然后意识到稀疏矩阵,有很多0,如果c[i][j] != 0,那么一定存在至少一个k满足a[i][k] != 0 && b[k][j] != 0; 然后就一发水A啦 1675 稀疏矩阵乘积 AC

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-21 18:33:00

    特殊排序

    <dl class="des"> <dd> 时间限制:5000ms

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-21 11:08:00

    HDU-1425-sort(计数排序以及快速排序和堆排序的变种)

    计数排序 Accepted 1425 483MS 5276K 997 B G++ #include "bits/stdc++.h"

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:04:48

    【树形DP】树的重心详解+多组例题详解

    目录 定义: 性质: 算法分析: POJ 1655 Balancing Act(求重心) POJ 3107 Godfather P1364 医院设置(树形DP) 定义: 树的重心也叫树的质心。对于一棵树n个节点的无根树,找到一个点,使得

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-20 18:25:00

    ZOJ-4089-Little Sub and Isomorphism Sequences

    给定你个数组,以及一些单点修改,以及询问,每次询问需要求得,最长的字串长度,它在其他位置存在同构。 当存在两个不相交的区间同构时,如: 1、2、……、n -1、n、n + 1、……、m、m + 1、m + 2、 ……、m + n - 1、m + n;(假设m > n&&[1

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-17 20:30:00

    位运算的妙用

    做题中常用的位运算有以下几种: 判断奇偶性 if (n & 1) { printf("偶数"); } else { printf("奇数"); } 常用于快速幂和其他判断奇偶性的地方 乘除2的整次

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-15 18:17:00

    HDU-1040-As Easy As A+B(各种排序)

    希尔排序 Accepted 1040 0MS 1224K 564 B G++ #include "cstdio" using nam

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-15 13:05:00

    最小生成树 HihoCoder-1097、1098、1109(最小生成树算法)

    太久没写最小生成树了,快忘光了。这几天回顾了一下 最小生成树一·Prim算法 AC G++ 369ms 17MB #include "cstdio"

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:05:09

    牛客 Tree(最小深度总和)(两种方法求重心)难度⭐⭐⭐

    题目链接 牛妹有一张连通图,由n个点和n-1条边构成,也就是说这是一棵树,牛妹可以任意选择一个点为根,根的深度 d e

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-13 14:21:00

    HDU-1878-欧拉回路(欧拉回路)

    欧拉回路的条件是所有节点的度数为偶数并且是联通图,但是照这题的描述所说并不需要所有点都联通,如果某个点的度为0,被孤立,依旧可能存在欧拉回路; 所以用set来存度不为0的节点,用并查集判联通就好了 #include "bits/stdc++.h" using names

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-12 16:17:00

    HDU-1285-确定比赛名次(拓扑排序)

    拓扑排序 #include "bits/stdc++.h" using namespace std; // 用来存某个点的入度数量 int num[505]; // 用来存某个节点的出度 set<int> outde[505]; int ans[505

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-10 15:35:00

    CF-1102E-Monotonic Renumeration

    比较可惜昨天比赛的时候时间不够了,在比赛结束之后五分钟找出了bug提交通过了。然并软; 首先这题说b数组的后一项要么等于前一项,要么等于前一项加一,而且如果a[i] == a[j] ,那么b[i] == b[j],所以如果a[i] == a[j],b[i]到b[j]这个区间的值都是一样的,可以看做

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-09 15:01:00

    判断一颗二叉树是否为二叉搜索树

    首先定义一个二叉树的结构体 struct BinaryTree { int value; BinaryTree* lson; BinaryTree* rson; }; 第一种方法 int maxOf(BinaryTree* root) {

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:05:30

    poj 2352 Stars 线段树(先建后查/边建边查)/树状数组三种方法思路详解,带你深入了解线段树难度⭐⭐⭐★

    poj 2352 Stars 目录 poj 2352 Stars 1.树状数组 2.线段树,先建树后查找 3.线段树,边建树边查找 Description Astronomers often examine star maps where

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-09 13:01:00

    Trie树的插入,查前缀,查单词,删前缀和删单词。

    这个Trie原先用C++就敲得很熟了,看了蓝桥杯的视频后学会把一个功能这样封装起来,以后用的时候就很爽可以直接调用了,所以就用Java写了; public class Trie { private final int SIZE = 26; private final int

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-08 21:40:00

    平衡二叉搜索树的插入和先序遍历

    构建一个值的类型为int的平衡二叉搜索树,输入N,然后进行N次插入操作,每次插入之后进行一次遍历验证代码正确性。(删除目前还写不出来,以后有机会再补吧) #include "bits/stdc++.h" using namespace std; typedef long

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-06 13:31:00

    CF-1097D-Makoto and a Blackboard

    这题在比赛的时候耗了我近两个小时,还是没做出来。用到逆元和期望。赛前掌握的不够好,现在看了几位大佬的代码之后把这题补上。 代码参考来源:https://blog.csdn.net/qq_36797743/article/details/85834812 1097D 

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:05:51

    CF448C Painting Fence(分治递归/DFS)难度⭐⭐⭐

    题目链接 有n块连着的木板,每个木板的高度为 h i h_i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-01-04 21:46:00

    二叉搜索树找前驱和后继

    输入N个数,找每个数的前驱和后继。如果没有前驱或后继,输出-1; 思路: 如果有右子树,则右子树的最小值为当前节点的后继;否则后继为当前节点往祖先搜索,第一次是左孩子的节点的父亲的值; 如果有左子树,则左子树的最大值为当前节点的前驱;否则前驱为当前节点往祖先搜索,第一次是右孩子的节点的父亲的值

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-04 16:09:00

    二叉搜索树的插入,删除,和中序遍历

    构建一个值的类型为int的二叉搜索树,输入N和M,然后进行N次插入操作,每次插入之后进行一次遍历验证代码正确性。然后进行M次删除操作,每次删除之后进行一次遍历验证代码正确性。 #include "bits/stdc++.h" using namespace std; ty

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-01-01 14:12:00

    实现一个简易的HashMap

    实现一个键的类型为int,值的类型为int的HashMap 输入一个T,表示操作次数; 之后每行接一个操作,可以包括插入、删除、修改、查询、清空、判断是否有这个键; 因为是刚学完随手敲的,所以功能粗糙。插入不考虑键已经存在的情况。删除、修改、查询不考虑键不存在的情况; #include &q

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-12-30 15:02:00

    有环链表的环起点

    用两个指针,一个快指针一次走两步,一个慢指针一次走一步。快慢指针可以重合表示链表有环,此时距离环起点的距离和起点距离环起点的距离相等。 #include "bits/stdc++.h" using namespace std; struct List { List

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:06:11

    【python】sorted和sort排序

    python3 C = [('e', 4, 2), ('a', 2, 1), ('c', 5, 4), ('b', 3, 3), ('d', 1, 5)] print(sorted(C, key=lambda y: y[0])) #[('a', 2, 1), ('b', 3, 3), ('c'

    来自 fanfansann
    00
  • avatar 咖啡蛇 2018-11-27 21:03:00

    肥宅快乐数

    肥宅快乐数 Time limit:1s Memory limit:128M Description 作为一个肥宅,栗酱每天都从不同的事物上获得快乐。今天他发现每一个形如 (i,j) 的二元组当满足 “i + j == i | j” 时都会给他带来1点快乐。现在问题来了,[1, 2^k] 以内

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-11-25 20:42:00

    HDU-1113-Word Amalgamation

    这题比较方便的解法是使用STL里的map和set代码如下: #include"bits/stdc++.h" using namespace std; map<string,set<string> >mp; string s,t; int main(

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-11-20 19:36:00

    C++ 部分STL

    map map可以理解为一个数组(但实质上并不是,只是方便理解),我们一般的数组不管定义成什么类型他的下标都是整型(int),map和这些数组的区别是他的下标可以是其他类型,由自己定义。map的创建、插值和访问示例如下: #include"cstdio"#inclu

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-11-19 22:31:00

    HDU-1166-敌兵布阵(线段树)(树状数组)

    线段树(kuangbin本题链接) #include "bits/stdc++.h" using namespace std; const int MAXN = 50010; struct Node { int l, r; int sum; } s

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:06:32

    【python】向上取整 向下取整

    python向上取整 向下取整 向上取整 ceil() 函数返回数字的向上取整整数,就是返回大于等于变量的最近的整数。 ceil()是不能直接访问的,需要导入 math 模块。 import math math.ceil( x ) 向下取整 floor(x) 返回数字的下舍整数,小于或等于

    来自 fanfansann
    00
  • avatar 咖啡蛇 2018-11-03 17:08:00

    HDU-1575-Tr A(矩阵快速幂)

    矩阵快速幂 #include"bits/stdc++.h" using namespace std; const int mod = 9973; int n, k; struct Mat { int mat[11][11]; Mat() {

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-10-14 19:28:00

    CF-1066B-Heaters

    这题就是从1到n点进行遍历,对未加热的点找到最远的能加热到这个点的点,还是看代码讲吧 #include"bits/stdc++.h" using namespace std; const int inf=0x3f3f3f3f; typedef long long LL;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-10-02 22:08:00

    HDU-5687-Problem C

    #include"bits/stdc++.h" using namespace std; struct tree{ tree* Next[26]; int cnt; }*root; tree* init(){ tree* t=(tree*)malloc(s

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:06:52

    【题解】P1080 国王游戏(贪心+高精python天下第一)

    P1080 国王游戏 题目描述 恰逢 H国国庆,国王邀请n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:

    来自 fanfansann
    10
  • avatar 咖啡蛇 2018-09-24 22:13:00

    HDU-1164-Eddy's research I(分解质因数)

    由于这道题目数据范围小,所以属于水题。可以采取暴力的做法来解决。 代码如下: #include"bits/stdc++.h" using namespace std; const int maxn=65535; bool tag[maxn+5]; vector<i

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-09-20 21:20:00

    HDU-2544-最短路(各种最短路径算法)

    迪杰斯特拉算法--O(n^2) #include"iostream" #include"cstring" #include"cstdio" using namespace std; const i

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-09-20 16:33:00

    HDU-1061-Rightmost Digit(快速幂)

    快速幂(本代码中的^表示次幂不是异或) Accepted 1061 0MS 1368K 679 B G++ #include "bits/st

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2018-09-19 20:28:00

    HDU-1251-统计难题(Trie树)(BST)(AVL)

    字典树解法(Trie树) Accepted 1251 156MS 45400K 949 B C++ #include"iostream&quo

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 12:07:13

    数独(DFS)

    题目链接 P1784 数独 题目描述 数独是根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。每一道合格的数独谜题都有且仅有唯一答案,推理方法也以此为基础,任何无解或多解的题目都是不合格的。 芬兰一位数学家号称设计出全球最难的“数独游

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 12:07:33

    【题解】CF1070E Getting Deals Done(二分+思维)难度⭐⭐⭐

    CF1070E Getting Deals Done 题意翻译 题目描述 Polycarp有很多工作要做。最近他学会了一条新的时间管理技巧:“如果任务需要五分钟或更短时间,请立即执行”。Polycarp喜欢新技巧,但他不确定五分钟是最佳值。他认为这个值 d(分钟)应根据现有任务列表选择。 Poly

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:07:40

    Rinne Loves Xor (异或和&二进制)

    Rinne Loves Xor (异或和&二进制) 题目传送门 思路: AC代码: #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:07:54

    【数论基础】有关素数的基础算法(内含三种筛法,低至O(N^(2/3))!)

    目录 1.P3383 【模板】线性筛素数 2.P3912 素数个数 3. O (

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:08:00

    小石的签到题 (博弈论&思维)

    小石的签到题 (博弈论&思维) 题目传送门 思路:显然n==1先手输,当n>1时,先手总会选择最优的情况,只要不取1,可以通过取其他数,来控制剩下数的个数,当剩下数为两个时,先手取一个,后手就必输。 AC代码: #include<bits/stdc++.h> usi

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:08:15

    【数论基础】模运算详解及其应用

    一.基本理论 1.基本概念: 给定一个正整数p,任意一个整数n,一定存在等式 n = k

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:08:21

    I - Palindrome(LCS&字符串)

    I - Palindrome(LCS&字符串) AC代码: #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<iost

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:08:36

    【题解】P1419 寻找段落(二分+单调队列)难度⭐⭐⭐★

    P1419 寻找段落 首先二分答案,即:二分最大平均值。 我们将a全部减去mid,问题转化为判断是否存在一个长度在s~t范围内的区间它的和为正,如果有说明还有更大的平均值。 用前缀和和单调队列维护。 不会单调队列的点这里 然后用单调队列求出sum[i]-min(sum[i-t]~sum[i-s])

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:08:42

    E - Chinese Girls' Amusement (高精度&数论)

    E - Chinese Girls’ Amusement (高精度&数论) 思路: AC代码: #include<cstdio> #include<cstring> using namespace std; const int N=5e3+5; int a[

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:08:57

    【题解】P1029 最大公约数和最小公倍数问题

    目录 P1029 最大公约数和最小公倍数问题 方法一 方法二 P1029 最大公约数和最小公倍数问题 方法一 要知道最大公约数和最小公倍数的乘积就是原两个数的积。 换成公式就是:

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:09:03

    J - Staircases (递推&数的划分)

    J - Staircases (递推&数的划分) 题意:求有多少种不同数之和为n的方案。(划分个数大于1) 思路: AC代码: #include<cstdio> #include<cstring> using namespace std; const int

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:09:19

    【数论基础】欧几里德算法及其各种应用

    目录: 欧几里德算法(辗转相除法) 1.问题引入:线段上格点的个数 2.输入两个正整数,求最大公约数和最小公倍数 3.P1029 最大公约数和最小公倍数问题 欧几里德算法(辗转相除法) 辗转相除法, 又名欧几里德算法(Euclidean alg

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:09:25

    P1006 传纸条 (双状态DP)

    P1006 传纸条 (双状态DP) 题目传送门 思路:与P1004类似,也可以用四维,不过可以用三维记录步数即可完成状态转移。具体看代码。 四维AC代码: #include<cstdio> #include<algorithm> using namespace std

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:09:41

    【图论】用一道题从本质上讲清楚Floyd算法

    P1119 【灾后重建】 4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4 -1 -1 5 4 一道非常好的Floyd最短路练习题,从算法本质上出的题目,对于初学Floyd算法的人来说是绝佳的练习题

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:09:45

    P1004 方格取数 (双状态DP&四维DP)

    P1004 方格取数 (双状态DP&四维DP) 题目传送门 思路:由于两个路径的最优值会互相影响,所以同时走选择最优方案才是正确解法,这样保证不会将一个数加两遍。若走两遍可能不是最优方案(因为第一次会影响第二次的方案)复杂度O(9^4)还是很小的。因为是滚动数组,所以可以降到三维,但没必

    来自 Harris-H
    00
  • avatar sunrise__sunrise 2020-05-01 12:09:53

    【每日一题】3月25日tokitsukaze and Soldier

    题目意思 给定n个人,每个人有武力值和忍耐人数上线,需要最终组成一个团去计算最终的最大武力值之和。 解题思路 很容易想到,枚举每个人的s值,求解在这个s值下选取适当的人的最大武力值是多少,最终的最大答案就是题目要求得答案。上面是一种思路,但是极其难实现,想想为啥,每个人的s值不同,选定一个人的s值,

    来自 sunrise__sunrise
    00
  • avatar fanfansann 2020-05-01 12:10:03
    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:10:06

    G - 免费馅饼 (DP&数塔)

    G - 免费馅饼 (DP&数塔) 思路:从最大时间开始倒序DP,状态转移即由前一时刻周围的三个位置得到。具体看代码。PS:一开始看成1e6,已知MLE。 AC代码: #include<cstdio> #include<algorithm> #include<

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:10:25
    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:10:26

    C. Yet Another Counting Problem(数论&取模)

    C. Yet Another Counting Problem(数论&取模) 题目传送门 思路: AC代码: #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,q,c; ll

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:10:47

    使用MarkDown编辑器做出有意思的柱状图(完整代码)

    这是生成的效果 <menclose notation="box"> <mstyle displaystyle="false" scriptlevel="0"

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:10:47

    B. Binary Period(思维&字符串)

    B. Binary Period(思维&字符串) 题目传送门 思路:显然最小周期不会超过2.pos1:全为1或全为0,只用输出本身即可,pos2:其他情况,显然由于s可以为两倍t长度,只用构造01即可,因为对于当前位的字符只能选择0或1,所以长度为2|t|的010101……串刚好满足条件

    来自 Harris-H
    00
  • avatar Harris-H 2020-05-01 12:11:07

    A. Road To Zero (贪心)

    A. Road To Zero (贪心) 题目传送门 题意:给定非负整数x,y,两个操作1(花费a):其中一个数加1或减1,操作2(花费b):全部加1或减1,问让x=y=0的最少花费是多少。PS:坑爹题意:此处不需要让x=y=0为同时到达 思路:由于最后X=Y=0,显然X与Y的差值带来的花费是

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:11:07

    CF231C To Add or Not to Add(思维,模拟)

    CF231C To Add or Not to Add 先排序,每次更新一个i就以a[i]为最终的答案来看当前区间里的这些数能否通过不大于k次的+1(排过序了就不会有-1了)操作实现区间内所有的值都为a[i],一旦大于k次就把最前面的pop掉(类似滑动窗口) #include<bits/s

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:11:28

    牛牛染颜色 (树形DP)

    牛牛染颜色 (树形DP) 题目传送门 思路: AC代码: #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std;

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:11:28

    ACM竞赛技巧总结

    目录 1.更快(最快)的读入优化 2.memset用来赋最大值(非0,-1) 3.错排公式 4. 圆周率 5.自然对数 6.浮点数比较时最好控制精度 7.判断是不是2的幂 8.lowbit函数 : 9.Runtime Error 10.除vector和st

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:11:49

    HDU2196.Computer(树形DP)

    HDU2196.Computer(树形DP) 题目传送门 思路:每个结点的最大距离转化为到子树结点的最大距离与到上部最大的距离的较大值。到上部最大距离要分两种情况(在最长距离子树上和不在最长距离子树上)通过两次DFS就可完成状态转移。具体看代码。 AC代码: #include<bits

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:11:49

    P2888 [USACO07NOV]牛栏Cow Hurdles(Floyd算法)

    P2888 [USACO07NOV]牛栏Cow Hurdles 行 1…T: 行 i 为一个整数,表示任务i路径上最高的栏的高度的最小值。如果无法到达,输出 -1。 5 6 3 1 2 12 3 2 8 1 3 5 2 5 3 3 4 4 2 4 8 3 4 1 2 5 1 4 8 -1

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:12:09

    HDU1520.Anniversary party(树形DP&DFS)

    HDU1520.Anniversary party(树形DP&DFS) 题目传送门 思路:状态转移方程有两个:1.不选父结点,则加上子结点选或者不选的最大值,2.选父结点,则加上不选子结点的最大值。具体看代码。 AC代码: #include<bits/stdc++.h>

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:12:11

    最短路合集(Dijkstra、SPFA、Floyd以及路径还原模板)

    目录 一.Dijkstra算法(不能处理存在负权的清况) 1.堆(优先队列)优化版本:(慢,占用内存还大) 2.普通线段树优化版本(一般块) 2.大佬的特殊线段树优化版本:(超快的) 二.SPFA 算法(可以处理存在负权的清况) 三.Floyd算法(可以

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:12:30

    R - Transformation (线段树&lazy标记)

    R - Transformation (线段树&lazy标记) 思路:由于都是对区间进行修改和询问,所以可以用lazy标记该区间是否相等。若不相等总能分成若干个相等小的区间进行求和。具体看代码。 AC代码: #include<cstdio> #include<cstr

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:12:33

    P4779 【模板】单源最短路径(标准版)(dijkstra模板)

    dijkstra模板 输入: 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出: 0 2 4 3 堆优化版本 #include<bits/stdc++.h> using namespace std; #define debug(x)

    来自 fanfansann
    00
  • avatar Harris-H 2020-05-01 12:12:50

    Q - Can you answer these queries? (线段树&区间开平方修改)

    Q - Can you answer these queries? (线段树&区间开平方修改) 思路:线段树模板改编,需要对update进行剪枝,因为一个数最多开平方到1就为止了,判断一下这个区间和是否等于该区间长度即可。还有需要注意一点得是x,y未知,若x>y,需要swap一下。。

    来自 Harris-H
    00
  • avatar fanfansann 2020-05-01 12:12:54

    【题解】P1508 Likecloud-吃、吃、吃(简单DP)

    题目链接 题目描述 正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个nm(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了nm个小方格,每一个方格中都有一个

    来自 fanfansann
    00