• avatar fanfansann 2020-05-01 11:49:47

    C/C++ 取整函数 ceil()、floor()、trunc()

    向上取整函数 ceil() 向下取整函数 floor() 舍尾取整函数 trunc() 这三个函数都在头文件 math.h 中 floor(x)返回的是小于或等于x的最大整数。 ceil(x)返回的是大于x的最小整数。 trunc(x)返回的是x舍取小数位后的整数。 floor()是向负无穷

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:50:08

    【每日DP】day13、P3147 [USACO16OPEN]262144 (区间DP,2048游戏)难度⭐⭐⭐★

    P3147 [USACO16OPEN]262144 P 想到合并,自然就想到区间dp,一个被合成的数之前是一个区间,并且由两个数比它小 1 1

    来自 fanfansann
    00
  • avatar 咖啡蛇 2020-04-26 11:57:00

    牛客-牛牛染颜色

    题目传送门 sol:树形dp,用$dp[u]$表示节点$u$代表的子树合法染色方案的数量,若$u$节点是黑色,则所有儿子随意,产生的方案数为$\prod dp[v], v \in son[u]$;若$u$节点是白色,则含有黑节点的儿子最多只能有一个,也可以没有。因为$dp[v]$里必有一种方案是整

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:50:29

    P2119 魔法阵(优化枚举,数***算优化)难度⭐⭐⭐★

    P2119 魔法阵 %%% #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<

    来自 fanfansann
    00
  • avatar 咖啡蛇 2020-04-24 16:06:00

    CF-637

    题目传送门 --------------------真还就是翻译场,英语四级阅读理解看到吐,我太菜了-------------------- A .Nastya and Rice pro:问能否找出$n$个区间$[a - b, a + b]$内的数,满足和在区间$[c - d, c + d]$

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-03-10 12:59:00

    CF-Educational Codeforces Round 83-D-Count the Arrays

    题目传送门 sol:首先我们考虑在一个长度为$n$的序列里只有一个数出现了两次其他数都只出现了一次,那么在序列中出现过的数就有$n - 1$个。而这些数的范围是$[1, m]$,从$[1, m]$里选$n - 1$个不同的数的方案数为$C_{m}^{n - 1}$。这$n - 1$个数里最大的数不

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-03-05 16:04:00

    牛客-XOR TREE

    题目传送门 sol:假如把这题树上这个条件改成序列,那么对于操作2,求某区间$[l, r]$所有连续子序列的异或和。观察得出若$r - l + 1$是偶数,则答案是$[l, r]$区间的异或和。否则,答案是$[l, r]$区间内下标奇偶性与$l$不同的元素的异或和。那么可以用三颗线段树来分别维护奇

    来自 咖啡蛇
    00
  • avatar 求求大佬带带我emm 2020-05-01 11:50:49

    NC50439 tokitsukaze and Soldier

    思路: 算是比较有意思的贪心^-^其实乍看就是简单01背包问题,由于我太弱没想到怎么优化复杂度。于是,换了贪心思路。 考虑一个简单问题,如果现在给定最多取K人,那么怎样最优取呢?显然找出n个人中s[]大于等于K的人,记为S。那我们只需要在S集合中找前K大的v值,并对其求和 敲黑板:最暴力的方法就

  • avatar 咖啡蛇 2020-02-23 22:22:00

    牛客小白月赛22

    题目传送门 官方题解传送门 A .操作序列 sol:如果STL熟悉,那么就是一道模拟题。就是输入有点奇葩。但是看了官方题解中提到了平衡树。嗯,没错,map和set的底层都是平衡树。红黑树不会,平衡树觉得还是fhq-treap好敲。所以,提供一份map的解法和一份fhq-treap的解法。

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:50:54

    P3382 【模板】三分法,难度⭐⭐⭐

    P3382 【模板】三分法 法1 : 三分法 对于一个二次函数[L,R]内取最值,选取两个点x=(2∗l+r)/3,y=(l+2∗r)/3 若f(x)>f(y),那么[y,R]这一段可以舍弃(一定不会成为最优解),否则[l,x]这一段舍弃 #include<iostream&g

    来自 fanfansann
    00
  • avatar 咖啡蛇 2020-02-09 20:55:00

    牛客-牛牛的Link Power II

    题目传送门 sol:可以用线段树来维护,线段树的节点除了标配的$l$和$r$同时记录该区间$link$的个数记为$cnt$,该区间$link$点的和记为$sum$,该区间题目中所谓的能量记为$dis$。然后$cnt$和$sum$就直接两个儿子相加就好,$dis$还要另外加上$segTree[rs]

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-25 19:48:00

    洛谷-P5357-【模板】AC自动机(二次加强版)

    题目传送门 -------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题 sol:AC自动机,还是要解决跳fail边产生的重复访问,但是这次用last边已经不行了,只能拿76分。我们把跳fail边的过程放到串扫描完之后一次性进行。

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-25 19:35:00

    洛谷-P3796-【模板】AC自动机(加强版)

    题目传送门 -------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题 sol:AC自动机,在fail边的基础上再加一个last边,指向真正有效的节点,跳fail边改成跳last边来跳过无效点。 AC自动机

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-25 19:23:00

    洛谷-P3808-【模板】AC自动机(简单版)

    题目传送门 -------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题 sol:标准AC自动机,注意不能重复跳fail边,像"aaaaaaa...aaaaaaaa"这样的数据每跳一次fail边只往上走了一层。

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

    【分治】P1228 地毯填补问题(多联骨牌覆盖棋盘问题)(递归,分治)难度⭐⭐⭐

    P1228 地毯填补问题 离散上讲了这个问题,如下图 初看这个问题,似乎无从下手,于是我们可以先考虑最简单的情况,既n = 2时 0 0 0 1 这时,无论公主在哪个格子,我们都可以用一块毯子填满 继续考虑n = 4的情况 我们已经知道了解决2 * 2的格子中有一个障碍的情况如何解决,因此我们可

    来自 fanfansann
    00
  • avatar 咖啡蛇 2020-01-21 12:19:00

    2020 CCPC Wannafly Winter Camp Day1-F-乘法

    题目传送门 sol:二分答案$K$,算大于$K$的乘积有多少个。关键在于怎么算这个个数,官方题解上给出的复杂度是$O(nlogn)$,那么计算个数的复杂度是$O(n)$的。感觉写着有点困难,自己写了一个复杂度是$O(nlog^{2}n)$,也够AC了。有正有负,控制边界有点难度。 二分答案

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-16 17:18:00

    牛客-德育分博弈政治课

    题目传送门 sol:根据题意建立流量网络然后跑网络流,这两天刚学的网络流,练练手。 网络最大流 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-13 16:43:00

    牛客-装货物

    题目传送门 sol:题目的数据范围就是对解决方案的一种提示,原先以为当数据范围只有$20$的时候都是dfs或者二进制枚举这种,从这题了解到还有状压dp。不解释了,反正就是状压dp,做的不多,记录一下。 状压dp #include <bits/stdc++.h>

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2020-01-13 16:06:00

    2019-ECfinal-M题-value

    题目传送门 sol:每个下标都有选和不选两种情况,所以总方案数是$2^{n}$,在$n$最大是$100000$的情况下不符合要求。可以这样想,假设$i^{p}=k$有符合题目要求的解,还有一个整数$j$,$j$不是$i$的整次幂,$i$也不是$j$的整次幂,那么$j^{p}=k$不可能成立,所以我

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

    牛客-回文串

    题目传送门 sol:根据题意,可以把字符串截成两段,要求两段中最大的两个回文串相加最大的方案,于是跑马拉车维护一个前缀,再倒着跑马拉车维护后缀。因为最优方案肯定是在两个字母之间截,所以最后只考虑在'#'位置截断的情况 马拉车 #include <bits/stdc++

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-12-30 10:08:00

    TZOJ-STL系列题

    C++实验:STL之vector #include <bits/stdc++.h> using namespace std; void Input(vector<int>& v) { int n, m; sc

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-12-17 09:23:00

    洛谷-P3919-可持久化数组

    题目传送门 sol:在洛谷上看到一种dfs + 离线的方法,可以解决大部分可持久化问题。把依赖关系看成边,然后建树。这样本来要解决的多个版本只要在一个版本上进行修改就好了。 离线 + dfs #include <bits/stdc++.h> using name

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

    【每日DP】day12、P1063 能量项链(区间DP又一模板,震惊,只需要4行代码?)难度⭐⭐⭐

    P1063 能量项链 本题(NOIP2006)和石子合并(NOI1999)几乎一模一样 垃圾NOIP抄袭NOI,手动狗头 但是还是有细微的区别的,首先你得先能看懂题,石子合并是N堆石子,是 i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-11-27 12:19:00

    绍兴市第十三届大学生计算机技能竞赛程序设计

    A .Cake Cutting Problem -------------------零AC,打扰了 B .Function des:f(x) = f(x-1) + 1. f(0) = k. 给出x、k,求f(x)。 sol:签到题,好翻译好做。直接两数相加没什么好说的。 数学

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-11-06 11:09:00

    牛客-Forsaken的数列(Treap)

    题目传送门 sol:第一次看题还真信了是用线段树来做,但是没什么想法,看了题解发现是我不会的Treap,然后花了几天时间学习了一下并补掉题目 无旋Treap #include <bits/stdc++.h> using namespace std; typede

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-11-04 16:21:00

    洛谷-P3369-普通平衡树(Treap)

    题目传送门 标题说平衡树,那么应该AVL,红黑树都能过,但是这次做这题主要是学习Treap,所以花了几天搞出了这题。其他方法以后再说吧 Treap(带旋转) #include <bits/stdc++.h> using namespace std; const

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-10-24 15:06:00

    CF-595

    题目传送门 A .Yet Another Dividing into Teams sol:原先是用比较复杂的方法来解的,后来学弟看了一眼,发现不是1就是2,当出现两个人水平相差为1就分成两组,1组全是奇数,1组全是偶数,必然符合题意。 思维 #

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:52:23

    区间DP入门

    区间 DP 什么是区间 DP? 区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态 f (

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:52:45

    【每日DP】day 10、P1005 矩阵取数游戏【区间DP+高精(python)】难度⭐⭐⭐★

    P1005 矩阵取数游戏 输入 2 3 1 2 3 3 4 2 输出 82 说明/提示 NOIP 2007 提高第三题。 数据范围: 60 %

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:53:07

    P2949 [USACO09OPEN]Work Scheduling (后悔法,贪心)难度⭐⭐⭐

    P2949 [USACO09OPEN]Work Scheduling G 3 2 10 1 5 1 7 17 后悔法的贪心。 首先思路就是先按截止日期排序,然后如果一个工作有时间去做,就先做了它,然后把它的价值压入一个小根堆。当我们找到一个没法做却价值比当前堆顶高的工作时,我们

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-10-13 14:12:00

    牛客-富豪凯匹配串(bitset)

    题目传送门 sol1:用bitset来维护,其实感觉挺暴力的,不怎么会用bitset,借着这道题学习一下。 bitset暴力维护 #include "bits/stdc++.h" #define debug puts("what the ***

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:53:28

    P2280 [HNOI2003]激光炸弹(二维前缀和的简单应用)难度⭐⭐⭐

    P2280 [HNOI2003]激光炸弹 输出 2 1 0 0 1 1 1 1 输入 1 这道题就是最基础的二位前缀和的应用,如果不会的话可以点击下方链接学习哟 前缀和差分详解 #include<iostream> #include<stdio.h> //#i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-10-04 21:56:00

    牛客-Highway

    题目传送门 sol:看了题意显然是最大生成树,但是任意两个点之间都有边,大概有n*n条边。用朴素的最小生成树算法显然不行。联想了一下树的直径还是不会。看了大佬的题解,懂了。。。 所以还是直接贴大佬博客链接好了:https://blog.csdn.net/yasola/article/detail

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-09-26 19:44:00

    POJ-1811-Prime Test(pollard_rho模板,快速找最小素因子)

    题目传送门 sol:Pollard_Rho的模板题,刚看了Pollard_Rho和Miller_Rabin很多原理性的东西看不懂,只是记住了结论勉强能敲代码。 Pollard_Rho #include "cstdio" #include "cs

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-09-26 10:13:00

    HDU-2138-How many prime numbers(Miller-Rabin新解法)

    题目传送门 sol1:普通判到sqrt(n)的素数判定,不多说了。 素数判定 #include "bits/stdc++.h" using namespace std; bool is_prime(int n) { for (int i = 2;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-09-24 18:14:00

    牛客-斐波那契数列卷积

    题目传送门 sol: 官方题解的随便简单推导我推不出来,推了很久倒是推出了另一种解法。 用 c[i][j] 表示 a[i] 的第 j 项,举个例子 c[3][0] = f[0] * f[3] = 0;  c[4][1] = f[1] * f[3] = 2; 那么我们求 a[n] 也就是 c[

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

    【蓝桥杯】2019年第十届蓝桥杯省赛B组试题J — 灵能传输(前缀和,猜想结论)难度⭐⭐⭐⭐

    蓝桥杯的题还是有难题的。这道题的可行性证明比较麻烦,但是代码比较简单。 学到了新的序列操作。前缀和的应用,前缀和还是学的不够扎实,晚上再复习一遍。 #include<iostream> #include<stdio.h> #include<string.h> #

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-09-05 20:56:00

    牛客-小y的盒子

    题目传送门 -------------------稍加观察就会发现,4n - 1就是题目要的答案。至于为什么,看官方的题解。不过这个n非常的大,用正常快速幂解决不了。这道题我学到的就是解决幂非常大的情况。 官方题解传送门 sol1:之前好像做过一道类似的题目,想不出来,在群里看到网友发了一个名

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-09-02 20:36:00

    牛客-DongDong数颜色 及其相似题

    大佬博客 ps:在牛客上做到这题不会,学会之后补了两道相关题。顺便记录一下。 牛客-DongDong数颜色 sol:dfs序+莫队,先把树上的点标上dfs序,因为子树的dfs序是连续的,所以子树可以表示为id[x]到id[x] + size[x] + 1,然后就是序列上莫队了(引用自官方题解)

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

    CF20C Dijkstra?( Dijkstra!练手)难度⭐⭐⭐

    题意翻译 题目大意 给出一张图,请输出其中任意一条可行的从点 11 1 到点 nn n 的最短路径。 输入输出格式 输入格式 第一行:两个整数n,m,分别表示点数和边数 接下来m行:每行三个整数u,v,w,表示u和v之间连一条边权为w的双向边。 输出格式 一行:一个可行的路径,如果不存在这种路径输出

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:54:33

    【构造】CF12E Start of the season(神奇的构造)难度⭐⭐⭐

    CF12E Start of the season 题目描述 在伯兰的足球节开幕式中有一个奇怪的魔术秀。最有经验的魔术师会找一个 n ×

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:54:53

    CF5A Chat Server's Outgoing Traffic(字符串模拟,find函数的应用)难度⭐

    题意翻译 Polycarp正在开发一个名为“Polychat”的新项目。按照IT的现代倾向,他决定,这个项目也应该包含聊天。为了实现这一目标,Polycarp在笔记本电脑前花费了几个小时,实现了一个可以处理三种命令的聊天服务器: 将一个人加入聊天(“添加”命令)。 从聊天中删除一个人(“删除”命令)

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-08-29 19:21:00

    牛客-小w的a=b问题

      题目传送门 sol1:老实做,预处理出所有2到1e5的素数,对所有数进行分解质因数,然后对比因子个数。感觉有点卡常,用了快读然后多次优化之后才过的,map也用上了。 素数筛,快速分解质因数 #include "bits/stdc++.h" usin

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:55:14

    【每日DP】day 9、P1156 垃圾陷阱(神奇的背包,时间节点处理)难度⭐⭐⭐

    P1156 垃圾陷阱 每个垃圾只能用一次,典型的01背包。 关键是时间的处理 ll f[N];题目要中求的是生存的最长时间,所以这里的f[i]是指高度i时生存的最长时间 对于每一块垃圾,我们都有两种选择,吃,或者不吃。这里时间的处理类似迷宫DP,对于i,求所有能到达这一高度的时间中取最大值,不用记

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-08-27 15:09:00

    HDU-6707-Shuffle Card(很数据结构的一道题)

    题目传送门 sol1:拿到这题的时候刚上完课,讲的是指针。所以一下子就联想到了双向链表。链表可以解决卡片移动的问题,但是无法快速定位要移动的卡片,所以再开一个指针数组,结合数组下标访问的特性快速定位到要移动的卡片。把链表和数组的优势结合起来; 双向链表 #include &

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-08-18 11:34:00

    HDU-6672-Seq

    题目传送门 ps:一般这种给一个数列求第n项,n还特别大的。要么矩阵快速幂,要么转化递推式。不过这题数据也特别多有100000组,所以就算矩阵快速幂可能也要超时,而且我还没推出来。转化递推式需要比较强的数学基础,我也转化不了。ε=(´ο`*)))唉,只能打表找规律。 打表代码

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-07-14 21:38:00

    牛客-随机数

    题目传送门 -------------------上个星期的假日团队赛,这题别人的代码看了四五天才明白,来补上代码 sol1:排列组合,当考虑某一位本来是1的,现在改成了0,那么在这一位后面位的就可以随意排列组合了。 排列组合 #include "bits/st

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

    牛客-小阳的贝壳

    题目传送门 sol:题目读完就知道是线段树,gcd满足结合律。操作2也好想到差分,但是不会修改后维护gcd。看了题解发现还是差分,这个差分用的妙啊; 线段树+差分 #include "bits/stdc++.h" using namespace std;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-07-03 21:03:00

    HDU-4417-Super Mario

    题目传送门 sol1:离线处理询问,对所有询问按高度排序,然后按高度顺序把每个点的坐标存入树状数组或线段树。 树状数组 #include "bits/stdc++.h" using namespace std; typedef pair<int,

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:55:35

    【每日DP】day 8、P2014 [CTSC1997]选课(树形DP(树形背包)模板)难度⭐⭐⭐

    P2014 [CTSC1997]选课 题意为选一门课前要看它是否有前提条件:即选了一门主课才能选 “副科”,所以可以树形背包来做。 注意是不能用分组背包来做,因为这道题附件有很多个,光是两个附件的分组背包就需要四个转移方程,在这里根本没法做。 链式前向星建树。 本身这道题的数据是一组森林,但是森林

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-06-30 14:28:00

    牛客-Corn Fields

    题目传送门 sol:状压和动规,把每一行的m个01压缩成一个int 状压dp #include "bits/stdc++.h" using namespace std; const int MAXN = 15; const int MOD = 1e8;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-06-23 22:20:00

    HDU-2665-Kth number

    题目传送门 sol:主席树,模板题 PS:这题从第一次错误提交到成功AC隔了半年,然后从半懂到现在会用了又隔了将近一年。前几天回顾了主席树,补上代码。 主席树 #include "cstdio" #include "algorithm&quo

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-06-18 19:35:00

    线段树模板

    sol:模板题就不解释了 洛谷-P3372-线段树1 线段树 #include "bits/stdc++.h" using namespace std; typedef long long LL; const int MAXN = 100010; str

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-06-17 22:20:00

    牛客小白月赛15

    题目传送门 官方题解传送门 -------------------这次的题目出的不错,有9题是我赛后能做出来的。但是数据太智障了,重配好几次还是有问题。 A .斑羚飞渡 sol:贪心:如果x[i] + y[i] < m,则第i只斑羚一定到不了对岸,所以要尽量多的使用这种斑羚当跳板;如果

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:55:56

    【每日DP】day7P1064 金明的预算方案 (分组背包,我又悟了)难度⭐⭐★

    P1064 金明的预算方案 背包其实就是把一个大问题拆分成若干个子问题,把一个要拿东西的动作按照题目要求分成若干个动作,分别枚举(DP其实就是非常的暴力),比较取最大值。 比如这道题,背包的物品之间是有依赖的,所以分情况讨论,考虑 只放主件 放主件和附件一(如果有的话) 放主件和

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:56:18

    POJ 3111 K Best (最大化平均值,贪心 二分)难度⭐⭐⭐

    题目来源: 【题意】 有n个物品的重量和价值分别是wi,vi,从中选取k个物品使得单位重量的价值最大。 输出格式: 输出一行物品的编号。 #include<iostream> #include<stdio.h> #include<algorithm> #def

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:56:39

    CF3B Lorry (手动模拟01背包,贪心)难度⭐⭐⭐

    这道题洛谷上的翻译是错的,最后输出格式那里应该是输出一行所选物品的编号,中间用空格隔开 手动模拟01背包 这道题看上去很像是01背包的模板题,但是很明显,v=1e9,正常的01背包是肯定会爆掉62MB的内存的,所以不可能用普通的01背包来做, 但是转念一想,这道题是由10背包魔改过来的,增加的难度

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:57:01

    【每日DP】day6 P1541 乌龟棋(四维DP)难度⭐⭐⭐

    P1541 乌龟棋 四维DP——四种状态,所以四维DP f [ i ]

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-06-15 21:37:00

    牛客-接机

    题目传送门 sol:很基础的二分答案板子题。一开始方向搞错了往动规贪心那边想了,想了一个多小时都没思路。 二分答案 #include "cstdio" #include "algorithm" using namespace std;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-06-15 21:26:00

    牛客-分组

    题目传送门 sol:dp[i]为前i头牛按题目要求分组后的最大技能水平和。然后dp方程式就显而易见了; 动态规划 #include "bits/stdc++.h" using namespace std; const int MAXN = 1e4 + 5

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-06-03 18:15:00

    2019计蒜之道初赛第三场题解

    题目传送门 A .淘宝商品价格大PK sol:枚举删除每一个数,然后求最大上升子序列。 枚举 #include "bits/stdc++.h" using namespace std; const int MAXN = 10

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-05-14 19:40:00

    牛客小白月赛14 :部分题目总结

     题目链接:https://ac.nowcoder.com/acm/contest/879#question  官方题解:https://ac.nowcoder.com/discuss/189446?type=101&order=0&pos=1&page=1 A .简单计

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:57:22

    P1083 借教室(标记永久化线段树/二分+前缀和)难度⭐⭐⭐★

    P1083 借教室 标记永久化线段树 很典型的区间修改问题,先输入赋值建树(这就是最典型的线段树呀,别忘了),然后修改 这里问的是是否有足够的空教室,所以线段树中 min 代表的是当前区间内最小的剩余教室量。 一般的线段树使用lazytag标记,每次都需要往下修改到根节点,本题中1e6有可能被

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-05-10 21:17:00

    CF-558:部分题目总结

    题目链接:http://codeforces.com/contest/1163 A .Eating Soup sol:在n / 2、n - m、m三个数中取最小值,结果受这三个值限制。但是m == 0的情况需要特判 思维 #include &q

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-05-02 19:26:00

    浙江省第十六届大学生ACM程序设计竞赛部分题解

      E .Sequence in the Pocket sol:将数组copy一份,然后sort一下,找寻后面最多多少个元素在原数组中保持有序,用总个数减去已经有序的就是我们需要移动的次数。 思维题 #include "bits/st

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-04-25 20:19:00

    浙江省高职院校联合训练(一)

    题目链接:http://acm.hdu.edu.cn/webcontest/contest_show.php?cid=13137 A .Problem A(ZOJ1048普通签到题) sol:不解释 水题 #include "cstd

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-04-24 10:00:00

    CF-544:部分题目总结

    -------------------昨天打的重现赛,感觉是我打的发挥的最好的一场比赛了,六题都一次AC。那么就来总结一下吧 题目链接:http://codeforces.com/contest/1133 A .Middle of the Contest sol:简单模拟,注意一下跨天的情况就

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:57:43

    【每日DP】day 5、P1095 守望者的逃离(好像悟到了DP的真谛)难度⭐⭐★

    P1095 守望者的逃离 输入 39 200 4 输出 No 197 输入 36 255 10 输出 Yes 6 好像悟到了DP的真谛(doge) 动态规划,就是动态地维护当前的状态。 本题种状态是距离,用

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-04-17 21:36:00

    CF-552E-Two Teams

    pro:给出n, k和长度为n的数组a, 两个人轮流取数1先取,设a[i]是当前数组中最大值,则取走a[i - k]到a[i + k]这段数,然后把a[i + k + 1]和后面的补到 a[i - k]的位置。(当然要考虑前后边界,i - k不能小于1,i + k不能大于n)输出一个字符串s[i]表

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-04-16 11:20:00

    CF-551:部分题目总结

    题目链接:http://codeforces.com/contest/1153 A .Serval and Bus pro:给出n种公交车的首班车时间和两班车之间的时间间隔,找t时间以后的第一辆车是第几种车 sol:对于每种车,找到t时间以后的第一班车的时间,计算这个时间和t的差距,然后找离t

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

    P1276 校门外的树(增强版)(线段树)(校门三部曲)难度⭐⭐⭐

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

    来自 fanfansann
    00
  • avatar 微分几何 2020-05-01 11:58:23

    三种最短路

    回顾一下三种经典最短路算法1、floydfloyd算法,又称MIF算法,是最容易理解的最短路算法,写起来也很简单,就一个三重循环就好了,可是复杂度过高,所以只会在数据水的最短路题目上。这是代码,边可负权,n最大1000 for(i=1;i<=n;i++) { for(j=1

    来自 微分几何
    00
  • avatar fanfansann 2020-05-01 11:58:26

    实现选择开区间或闭区间的操作,输出开区间或闭区间 详解(线段树运用)

    该操作源于此题目 P5568 [SDOI2008]校门外的区间(离散数学应用+线段树+开闭区间处理)难度⭐⭐⭐⭐★ 题目中输入的区间有开区间也有闭区间,输出的答案也是有开区间或闭区间,所以这里就需要特殊的开闭区间操作来处理。 详细规则及解释: 代码实现 输出 U [1,5] D [3

    来自 fanfansann
    00
  • avatar fanfansann 2020-05-01 11:58:49

    P5568 [SDOI2008]校门外的区间(离散数学应用+线段树+开闭区间处理)(校门三部曲)难度⭐⭐⭐⭐

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

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-04-14 15:08:00

    牛客小白月赛13 :部分题目总结

    -------------------感觉这场小白赛给我难度正好,可能我就是个小白吧。今天总结一下。  题目链接:https://ac.nowcoder.com/acm/contest/549#question  官方题解:https://ac.nowcoder.com/discuss/1774

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-04-12 16:32:00

    HDU-2157-How many ways??

      广度优先搜索+动态规划 Accepted 2157 0MS 1376K 1415B G++ #include "bits/stdc

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:59:10

    【每日DP】day4 P1417 烹调方案(奇怪的01背包增加了)难度⭐⭐⭐

    P1417 烹调方案 每件物品只有一个,很明显是01背包,但是价值的转换方式不同,是要求 a i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-04-09 18:37:00

    nowcoder-548C-Tachibana Kanade Loves Review

    链接:https://ac.nowcoder.com/acm/contest/548/C来源:牛客网 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 524288K,其他语言1048576K 64bit IO Format: %lld 题目

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-04-02 18:16:00

    CF-1144F-Graph Without Long Directed Paths

    题意: 给出一个无向联通图,要求你给出每条边的方向,使得无论从哪个点出发最多只能走一条边; 思路: 对于每个点,要么出度为0,要么入度为0即可。所以这就是一个判断二分图。 二分图 #include "cstdio" #include "cs

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-22 11:31:00

    ZOJ-1167-Trees on the Level

    题解: 我的解法是用一个类似字典树结构的结构体来表示节点。看到另一种解法是用数组来映射二叉树的,开到14000就过了,但是我觉得是数据水了,因为题中说最多 256个节点,如果256个节点连成链型,除根节点外每个节点都是父节点的右儿子。那么数组要开pow(2, 256)个。可见这种方法是不可行的;

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-21 22:48:00

    蓝桥杯-PREV45-图形排版

    这是2017年蓝桥杯C组C++的压轴题,拿到之后没什么想法。但是蓝桥杯有部分分。所以直接敲了个大暴力提交上去过了一半的数据。后来想到了DP,但是没能实现出来,感觉还是有问题的。后来看了解题视频发现是预处理。 大暴力 图形排版 739B

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:59:31

    【每日DP】day3 P1387 最大正方形(奇怪的DP增加了 / 二维前缀和)难度⭐⭐★

    奇怪的DP增加了 这道题,刚看见真是一脸懵逼,看了题解才明白。 本题中神奇的转移方程是: f [ i

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-03-17 20:00:00

    HDU-5818-Joint Stacks

    题解: 用优先队列和pair来模拟栈,这个很好想。关键点是开第三个栈,因为可能有多次A栈和B栈的合并,如果转移次数多了会超时。这时候就用到第三个栈了,把所以合并都合并到C栈里去。取的时候,先从A/B栈里取。如果是空栈,就从C栈里取; 思维题+优先队列+栈

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-14 15:59:00

    蓝桥杯-2016CC-卡片换位

    卡片换位 你玩过华容道的游戏吗?这是个类似的,但更简单的游戏。看下面 3 x 2 的格子 在其中放5张牌,其中A代表关羽,B代表张飞,* 代表士兵。还有一个格子是空着的。 你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。 输

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-08 16:16:00

    HDU-2255-奔小康赚大钱(KM算法)

    KM算法的模板题,记录一下 KM算法 Accepted 2255 468MS 1756K 1600 B G++ #include "b

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-05 19:29:00

    蓝桥杯-PREV31-小朋友排队

    解法: 这题有点像冒泡排序,但是做这题并不需要冒泡排序。 假设第i个小朋友比第j个小朋友高,而且i < j 为了把队伍排成从小到大,第i个小朋友一定要去第j个小朋友的右边。又因为只能交换位置相邻的两个小朋友,所以第i个小朋友一定要和第j个小朋友换位置。同理如果第i个小朋友比第j个小朋友矮

    来自 咖啡蛇
    00
  • avatar fanfansann 2020-05-01 11:59:52

    【每日DP】day2、P1879 [USACO06NOV]Corn Fields G玉米地(状压DP模板题)难度⭐⭐⭐★

    昨天的每日DP我还在写01背包,今天就到状压DP了,真刺激。 P1879 [USACO06NOV]Corn Fields G 题目链接 输入 2 3 1 1 1 0 1 0 输出 9 一道简单的状压DP入门题。 先看大佬讲解样例这是链接我截下来放到下面了 本题我的代码的思路

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

    【状压DP】状态压缩动态规划入门超详解

    状压DP 一、概述 1.状态压缩 2.使用条件 3.状压DP 二、位运算 三、例题引入 1、入门例题【例1】填满棋盘 2、入门例题【例二】玉米地 感觉好多讲状压DP的博客都有点乱,我就结合各路大佬的博客,加上我自己的理解

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

    SP11469 SUBSET - Balanced Cow Subsets(折半搜索+状态压缩)难度⭐⭐⭐⭐★

    题目链接 SP11469 SUBSET - Balanced Cow Subsets 题目翻译 给出 N ( 1

    来自 fanfansann
    00
  • avatar 咖啡蛇 2019-03-05 09:50:00

    蓝桥杯-PREV28-地宫取宝

    先自己用dp解了一遍,然后看了官方讲解视频是用记忆化搜索做的。感觉那位老师的方法比较容易实现(效率上和我的差不多的);记录一下三种方法。 动态规划 地宫取宝 1.195KB C++ 正确 100

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

    HihoCode-1053-居民迁移

    解法: 一开始不会做,看到标签说是贪心加二分忽然就会了,二分是分的是人口最多居住点的人口,检查人口最多的居住点人口为mid是否可行。贪心是如果从左往右循环就尽量把人口往左迁移,如果从右往左循环就尽量把人口往右迁移。 二分 + 贪心 1053

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-03-01 13:17:00

    HihoCode-1323-回文字符串

    参考博客: https://blog.csdn.net/mitsuha_/article/details/76690634 https://blog.csdn.net/u014142379/article/details/51761551 解题过程: 先看了第一位大佬的博客,了解了这题的解法

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

    蓝桥杯-PREV3-带分数

    有人管蓝桥杯叫暴力杯,现在感觉还是挺贴切的。看到这题首先想到让i从1到n循环,首先判断i中无重复数字,再怎样判断能否用剩下的数构成n - i的假分数。之后看了题解。发现思路错了。 总结两点: 1、蓝桥杯的编程题大多暴力枚举,首先从这个方向想; 2、next_permutation这个函数解决排

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

    【每日DP】day1 P1802 5倍经验日(别样的01背包)难度⭐★

    题目链接 输入 6 8 21 52 1 21 70 5 21 48 2 14 38 3 14 36 1 14 36 2 输出 1060 一道有点意思的01背包,可以帮助理解。好久没写DP了,每天一道DP,从基础学起,正好复习一下。 这道题不同之处在于失败了(不拿走这件东西)也会有收益,

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

    HDU-6312-Game

    题意: 一个集合里有1到n,两个人轮流从中取数,取出一个数的同时这个数的因子也被取走。取走最后一个数者为胜。判断是否先手必胜。 思路: 一道挺有意思的博弈题。一开始在纸上列出了n为1到6的情况,发现都是先手胜。大胆猜测不管n是多少都是先手胜,发现果真如此。求证方法是后来想到的 现在考虑集合中

    来自 咖啡蛇
    00
  • avatar 咖啡蛇 2019-02-22 16:56:00

    HDU-6438-Buy and Resell

    思路参考自https://www.cnblogs.com/zbh2047/p/9736378.html 贪心 Accepted 6438 234MS 2300K 1054 B G++

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

    CF-1117C-Magic Ship

    二分 C - Magic Ship GNU C++11 Accepted 31 ms 1700 KB #include "bits/stdc++.h&qu

    来自 咖啡蛇
    00