• avatar Walker_ 2020-12-17 16:51:41

    PR算法 大数质因数分解优化

    const int MAXN = 1000005 ; int64_t mulEx(int64_t a , int64_t b , int64_t Mod) { ///logn快速乘 if(!a) return 0 ; int64_t ans(0) ; while(b

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:52:02

    (最大流,二分图的多重匹配) Magic Potion

    题意:n个人,m个怪物,k瓶药水,每个人可以打死对应的集合里面的一个怪物,一碰药水可以让一个人多打死一个怪物,每个人最多只能用一瓶药水,问最多能打死多少个怪物 思路:想到了匹配,然后用最大流做,一开始想的建图是从超级原点连一条容量是n+k的边到虚拟节点,然后虚拟节点与所有勇士连一条容量是2的边,然后

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:52:23

    The Hard Work of Paparazzi(dp巧妙优化)

    链接 题意:r,n代表一个r * r的矩阵,n代表有n个金币,初始时间是0,现在你站在(1,1)位置,然后给出n个金币出现的位置(x,y)和出现的时间t,这个金币只在t这一分钟出现,过了t就消失,然后保证给出的t是严格递增的,求你能获得的最大收益。每分钟你能向四周移动一个单位。 思路:dp[i]以第

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:52:45

    最大流模板dinic

    复杂度o n^2m 思路:bfs出分层图,不断dfs,用当前弧优化。 #include<bits/stdc++.h> using namespace std; const int N=10010; const int M=200010; int h[N],e[M],ne[M],f[M]

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:53:05

    Birthday Paradox

    vj 题意:给你一个数一年有k天,选择最少的人使得他们满足他们生日概率大于等于0.5。 思路:这就是很简单的概率论的生日概率模型,然而我没想出来,看了思路以后还写复杂了,二分模拟来求然后tle了,结果直接递推算就能过了。 tle代码: #include<bits/stdc++.h> u

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:53:26

    线段树找从1开始大于等于该值的模板

    一开始我和大佬想的是二分再套线段树,然后tle了,想不到优化然后就查网了,如果左子树满足条件就不要递归右子树了可以优化一下,然后如果整段区间的最大值也不满足那就没必要往下递归了。 int query(int m,int l,int r,int val){ if(tree[m].l=

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:54:07

    饼干 (贪心+dp+奇妙转换)

    思路: dp[][]代表前i个小朋友发j个饼干的最小怒气值,由于排序不等式的证明,所有怒气值最高的小孩应该发的饼干是最大值,依次递减,我们先排序,然后记录在数组中原来的值,但是状态转移很难想啊,是类似整数划分,最后有几个饼干是等于1的,如果有k,K>0那么就可以由f[i][j]=min(f[i

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:54:28

    Polygon

    题意:有n个点构成的环,环上的边t代表+,x代表*,选择先断一条边,然后问能获取最大值的方案和最大值。 思路:一开始想的是dp[l][r]代表l~r之间运算出来的最大值,结果发现不太行,因为l到r之间的数可能是负数,负数乘以负数可能会更新最大值那么我们多开一维记录最大值和最小值。最后就是细节问题了,

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:54:49

    选课

    题意:某个课只有它父节点选的时候他才能选,问n个点构成的树,选m个课的最大学分数。 思路:构建一个虚拟节点0,那么0就是必选了,把选的课数量+1,对问题造成的影响是等价的,然后就是熟悉的分组背包问题了,早上卡了很久,因为要空出一格来放父亲的节点,然后对于背包dp的顺序是不能改变的,1物品组2体积最后

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:55:11

    扑克牌 概率dp

    题意: 从54张牌中抽牌,问抽到a张红,b张黑,c张方,d张梅的概率,当抽取到大王和小王的时候,会固定抽期望步数最少的牌。求最小的期望步数。 思路:期望dp ,dp(a,b,c,d,e,f),a,b,c,d,代表前4种牌的数量,e,f代表大王和小王的状态,要注意判断不合法的情况,即所有牌都抽完了,还

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:55:32

    金字塔

    题意:给你一个字符串,问你有多少个树形结构。 思路:有dfs序那味道了,哈哈哈哈,然而是个区间dp,f[l][r]代表字符串从l到r中有多少种树形结构,状态转移不太好想,为了达到不重不漏的目的,我们通过枚举k来枚举第一个子树出现的大小,然后,只有在两端点相等的时候才能执行,因为最后要回到该点。其实k

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:55:53

    积蓄程度

    题意:找一个点作为源点,问能往周围流的最多的水流。树形dp,dp数组代表以i为根的能流的所有水流,转移很简单,看代码,然后我们要处理一下从父节点流下来的值。如图。 之前wa了三十分钟,是因为转移的时候忘记考虑了父节点子树给他的贡献,从上面留下来的水流包括父节点父节点流下来的水流+子树的水流,然后别

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:56:15

    tokitsukaze and Soldier

    题意: 选择k个士兵,在满足总共的mins>=k的情况下,让他们的值和最大 思路: 是真的菜,这么简单的贪心都想不到,假设我们已经知道了最后选取k个士兵,那么我们可以优先选择s>=k最大的k个士兵,然后我们将士兵们排序嘛,然后按照值放进堆中,如果堆的大小大于限制,把最垃圾的t出来! ac

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:56:40

    D - Timofey and a tree

    题意: 给定一棵树,每个点带有各自的颜色,问是否能找出一个点当做根节点,并且它的子树颜色都是相同的。 思路:每颗子树之间的边的两端都是相同的颜色,对不同颜色的答案和是没有贡献的,那么如果找到两端颜色不同的就让不同边数++,两端点都++,如果有个点他的val值等于不同边的总数,那么它一定可以当做根节点

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:57:01

    K - Appleman and Tree

    题意: 给定一棵树,将树分成k个连通块,并且每个连通块内只有一个节点的方案数。 思路: 这个实在是想不出来啊,标解是开个dp[u][2]数组,表示只考虑u这颗子树并且u这个节点是否在有黑棋子的连通块中的方案数。 初始化就是如果黑色dp[u][1]=1,否则dp[u][0]=1; 转移也很骚: 枚举每

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:57:23

    A - Distance in Tree

    题意:给你一棵树,让你记录树上两点距离为k的点对数。 思路: dp[i][j]代表考虑i这颗子树,与它距离为j的点数量,dp[i][0]就是1了,然后dfs处理一下就可以,那么它就是答案的一部分,还有一部分就是把i当做中转节点,从u开始递归,枚举它的每个子树,ans+=(dp[u][tt]-dp[j

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:57:44

    B - Zero Tree

    题意:每次可以将包含1的节点的子树加1或者减1,问最小的操作数让整棵树变成0; 解题思路: 由于每次操作都要带上1,那么我们把1当做根节点,然后我们发现他的操作数与子树有关,先不考虑u这个节点,仅考虑他的子树,那么操作数有上升的也有下降的,那就是启发我们开两个数组,up,down记录上升的次数和下降

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:58:06

    I - Tree with Maximum Cost

    题意:选择一个点作为根节点,然后每个顶点到它的花费为距离那个顶点的值。求最大值。 思路:也是树形dp,dp[i]代表考虑以i为根节点,他的子树对他的花费,sum[i]代表i整颗子树的节点个数和,那么dfs两次就行了,第一次dfs预处理出来sum和dp数组,第二次处理出每个点的答案。u节点的答案就是a

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:58:31

    F - Computer

    题意:给定一棵树,求出每个点到树上所有点的最大距离。 思路: 先dfs预处理出来 考虑u这颗子树,往下走的最大值和次大值,然后每个点的最大值,来源一下面的最大值和它根节点往上走的最大值再取max,那么往上走的情况有两种例如下图: p代表u的父节点,根节点往上走的途径有两条,一条是继续往他的父节点走

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:58:53

    E - Two Round Dances

    题意:给定n个人 ,n为偶数 ,让它平均分为两组,然后如果两个序列他们的圆排列相同那他们就等价,例如 4,1,2,3 和 3,4,1,2是等价的,问有多少种分法。 思路:好多人都是查oeis,太赖皮了,我还是偷偷摸摸的看题解慢慢懂吧QAQ,那么正确的解法是啥呢,给定了一个长度为n的序列与它等价的序列

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:59:13

    E. Carrots for Rabbits(贪心)

    题意: 有n个萝卜 ,每根萝卜长度不一样,现在将这些萝卜分为k段 这k根萝卜每根萝卜的花费是长度的平方,求最小的花费。 思路: 原本想的是放进将萝卜放进大根堆,然后取最大的对半分,其实这样是不正确的,hack数据:3 5 10 3 1 如果按照对半分的思路来 就是分为 2 3 5 3 1 ,然而最优

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 16:59:34

    D. Hexagons

    题目链接:http://codeforces.com/contest/1421/problem/D D. Hexagons time limit per test2 seconds memory limit per test256 megabytes inputstandard input outp

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:01:02

    min25筛前n项素数个数的板子

    ll s[320010]; ll a[320010]; ll b[320010]; double inv[320010]; inline ll Prime(ll N) { ll S = sqrt(N); for (int i = 1; i <= S; ++i) a[i]

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:01:22

    B. Chess Cheater

    题意:给定含有WL的序列,最多能将k的L变成W,问最大的分值,当有连续的W的时候后面的W加二,第一个W加1。 解题思路: 一开始想的是dp,dp复杂度过不去啊。。后来想着把所有夹在两个W之间得区间都排序,就没继续往下面想了,看了题解,发现贪心策略跟我差不多,策略:尽量往贴近W的位置修改L,因为这样对

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:01:44

    Maze 概率dp

    题意:有一棵树,主人公要从1开始走,逃生,问逃生的期望步数,在1这个点 不可能死也不可能逃生,在别的点有ei的概率逃生,ki的概率死亡并且回到1这个点。 思路: 真的是难推啊,我们定义f数组为在i这个点逃生的期望步数,由于是无向图,我们先从叶子结点考虑, f[i]=0e[i]+ k[i]f[1] +

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:03:12

    C2. Pokémon Army (hard version)

    题意:给你一个序列,从左往右一次选择数字,奇数次选的符号为正,反之符号为负,问最后的最大值是多少,qwq这是简单版本的,然后难的版本多了一个修改,该修改是交换两个数的位置。 解题思路:如果是简单版本那么可以用dp来做,数组定义为考虑前i个 且轮到第i个的时候是奇数还是偶数次,难的版本有大佬说可以用线

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:03:34

    概率dp 神仙题

    题目大致意思: 总共有n种邮票,每选一张邮票,邮票的价格会加一,邮票的初始值是1,最后问拿完n种邮票的期望价格。 思路: 发表一下看这个题题解的感想:这个题太仙了,概率dp的套路司空见惯就是把数组定义成已经考虑前i个—到n的期望。那么我们先开一个数组来记录,f[]记录从已经选了i个从第i种开始选到第

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:05:01

    ABC178 E - Dist Max

    题意很简单:求平面所有点最大的曼哈顿距离。 |xi - xj | + | yi - yj | 的最大值。 思路 : 假设 xi > xj ,那么yi 和 yj 有两种情况, yi大于yj的时候 即 ( xi - yi ) - ( xj - yj) 的最大值,反之 (xi + yi) - (xj

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:05:22

    AtCoder Beginner Contest 179

    题意很简单:求前n项的和 并且第i项是i-1的平方倍%m。 思路:由于n很大,那么我们可以找循环节,但貌似循环节不一定从第一个位置开始,那么可以找出现两次和出现三次的pos,出现次数用map记录,然后一个一个算就行了。 代码: #include<iostream> #include&l

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:05:46

    5444 ( Elven Postman )

    Elven Postman Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 3784 Accepted Submission(s): 226

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:06:06

    [HDU-6831]

    分手了不太开心QAQ,写篇博客吧。这题是区间dp的问题,题意就是给你无限个1145141919,有t次询问,询问的n小于等于5000,问是否存在这样的前缀使得你操作无限次加、乘和括号,没啥思路,看了大佬的代码,发现是有规律的?我这种菜鸡来打表都不会,那当且仅当前缀长度小于等于13,那就区间dp好了,

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:06:27

    2019icpc 南昌站 --And and pair

    iven an extremely large non-negative integer nn, you are asked to count the number of pairs (i,j)(i,j) of integers satisfying the following conditions

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:06:48

    (我上绿了)Hills

    纪念一下自己上绿了。 下面是题目: 题意:当一个数满足大于他相邻的数的时候,可以在他这建房子,我们每次操作可以将某个数减1,问最少操作多少次可以满足(1~(n+1)/2)。 思路: 一开始想的是定义状态是f[i][j]表示考虑前i个建立j个房子的最小操作数,后来发现好像不够,因为我们很难判断出第

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:07:09

    数位dp变相 [HDU-5456]

    题意:给你n个火柴 让你凑成a-b=c的形式,不包括前导0,问总共有多少个方案数(mod上m)。 思路:真的想不出来,太妙了,先把a-b=c变形成a=b+c,然后从低位往高位枚举每位填的数,dp状态定义成f[i][f1][f2][flow] (只剩下i根火柴,b是否填完,c是否填完,是否有进位的方案

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:07:33

    CF1407D Discrete Centrifugal Jumps dp

    题意:如图 思路:单调栈维护某个点的前驱节点有多少个,设置f[i],定义为跳到i这个位置最少跳的次数。然后我们考虑一下什么时候可以跳 1:两边比中间都大,并且左边比右边大 2:两边比中间大,并且右边比左边大 3:两边比中间小,并且右边比左边大 4:两边比中间小,并且左边比右边大。维护四个单调栈。

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:07:54

    组合数 Counting Arrays

    题意:求一长度为y乘积为x的方案数,允许出现负数。 解题思路:我们先处理正数的,把x分解质因数,然后枚举每个质因数的次数,考虑把他们放进y个位置的方案数,就好比是将d个相同球放进y个位置,位置可以为空,为空就不好做,我们往每个位置都放一个球,问题就转变为将d+y个球放进y个位置,且位置不空,用隔板法

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:08:15

    CF362C Insertion Sort树状数组,思维,枚举

    题意:先交换任意两个,然后只能交换相邻两个,问最少操作次数和方案。 思路:由于冒泡排序有个定理就是逆序数的个数等于最少的交换相邻元素的次数,问题就转换为了交换两个数并且使得整个数组逆序数个数最少,我们枚举交换哪两个数,用树状数组处理b[i][j],f[i][j],i之前大于a[j]的个数,i之后小于

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:08:36

    CF229D Towers

    题意是:每次操作能将某个数加到隔壁的数上面,最后求最少操作数,使得序列是非递减序列。 思路:我们发现每次可以将l~r之间的区间合并成一个数,然后需要r-l次操作,我们设定从f[i]为从1处理到i并且序列是递增的最少操作数,然后枚举i是在哪一段区间里,维护l[i](在不影响f[i]最优值的情况下l[i

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:08:58

    CF296B Yaroslav and Two Strings

    题意:有两个串,每个串的内容要么是数字要么是问号,一共多少种方案使得两个串中存在两个位置一个位置比另一个大,一个位置比另一个小。问号可以填0~9. 思路: 容斥原理,看一共有多少状态减去非法状态,一共的状态数等于10的问号次方,非法状态,要么就是全大于等于,要么就是全小于等于,要么就是全等于,假设r

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:09:19

    P1629 邮递员送信

    有一个邮递员要送东西,邮局在节点 11。他总共要送 n-1n−1 样东西,其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 mm 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n-1n−1 样东西并且最终回到邮局最

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:09:40

    P5200 [USACO19JAN]Sleepy Cow Sorting G

    题意:给定一个排列 ,每次能让队头移动到后面任意的位置,问最后需要多少步可以变成升序排列。 思路:看到了一个很妙的思路,我们从末尾开始往前面扫如果遇到不是降序的那么它以及它前面的元素都需要往后移动,所以第一个答案就确定了。第二问要输出方案,我们仔细观察,每一头牛需要往后的距离=他后面还没有排队好的牛

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:10:00

    最大子矩阵(小于等于某值)

    思路:原来的思路就是枚举右下角点和左上角点,复杂度o(n^4)不太行,那我们我们把每一行的前缀和存下来,枚举两行然后枚举列结尾,二分出他前面最小的前缀和使得它大于等于sum-k,最后别忘记特判一下,如果最左边的l也能满足sum-k,l–。 #include<iostream> #inc

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:10:25

    9d

    题意翻译 用 n个点组成二叉树,问高度大于等于 h 的有多少个。 输入n和h 解题思路 : 这道是一道dp题,看了题解,思路是问的什么dp转移的方程就是什么,那么我们设成考虑i个节点的子树,高度不大于j的方案数,最后可以通过容斥原理求出答案,答案就是f[n][n]-f[n][h-1] 初始化:当节点

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:11:06

    2020CCPC秦皇岛 k Kingdom’s Power

    题意:有无数个军队可以从树根1出发,每花费一个点可以让军队走一步,问遍历完整个树的最小花费。 思路:先记录每个节点的高度,用节点根据它子树的高度的高度来排序,然后节点的高度为子树的最高高度+1,然后类似树形dp,从上往下递归h和与从下往上走的值取min。最后把所以的根节点的值加起来。 #inclu

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:11:27

    D. Rescue Nibel!

    题意:总共有n个线段,问选择k条线段,使得他们相交于一点的方案数。 思路:用类似差分的思想,将每条线段的l和r+1放进数组里并且分别带有1和-1的权值,将数组按照坐标大小排序,如果坐标大小不同按照权制大小排序,权值小的放在前面,然后依次遍历下来,把方案定义为以第i个灯泡为末尾(即该灯泡的坐标在选的坐

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:11:48

    张老师的旅行 区间dp

    区间dp,由于n很小,开两维,然后外加一维,最后遍历完所有区间内的点停在最左边还是最右边。 #include<stdio.h> #include<string.h> #include<algorithm> #include<map> #include

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:12:12

    P4053 [JSOI2007]建筑抢修

    题意:问能选取最大多少个数的建筑, 满足在规定时间内,每个建筑的建立都不能超过截止时间。 解题思路:先按照截止日期排序,如果能在截止日期内完成,那么我们就尽量往里扔,如果不能完成,那么我们选择大根堆中最大的看看它是不是比当前任务耗时大,如果耗时大,那么我们一定能把它抛下,并且完成任务,并且总耗时最少

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:12:34

    对顶堆P1801 黑匣子

    题目链接:看看 对顶堆?如图 对顶堆就是由小根堆和大根堆所组成,小根堆的值都比大根堆的大,这种数据结构可以用来动态查询数组中的前k小值,我们要维护大根堆的数量是k,当大根堆的size大于小根堆,就把最大值push进小根堆,如果大根堆数量不够,就往小根堆里拿最小值。 代码: #include<

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:13:01

    Balanced Bitstring

    题意:判断长度为n的串中的每个长度为k的子串是否0和1相等,字符串中的问号既可以是1也可以是0。 解题思路: 例如n=10 ,k=4 对于 s[0~3] 和 s[1~4] 我们可以发现1~3的部分是相同的,那么不难发现0和4相同,同理可得s[2]和s[5]也是相同的因此若该串合理就一定是k循环节子串

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:13:24

    清理班次

    农民约翰正在指挥他的N头牛进行清理工作。 他将一天划分为了T个班次(1~T)。 每头牛都只能在一天中的某一个时间段内进行不间断的工作。 你需要帮助约翰排列出一个合理的奶牛的清理班次,使得每个班次都有奶牛在进行清理,而且动用的奶牛数量可以尽可能的少。 输入格式 第1行:两个空格隔开的整数N和T

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:13:45

    Magic Grid

    题意:把0~n^2-1 之间的所有数填进n*n的矩阵,让整个矩阵的横向和纵向异或和相同。 思路: 小技巧就是偶数与它下一个数 异或和为1,偶数开始的4个异或和为0,然后我们突发奇想 构造一个 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 然后发现这个矩阵刚好符合。由于n

    来自 Walker_
    00
  • avatar 心里的字节在跳动 2020-12-17 17:13:53

    直接插入排序

    //从第一个元素开始,该元素可以认为已经被排序; // 取出下一个元素,在已经排序的元素序列中从后向前扫描; // 如果该元素(已排序)大于新元素,将该元素移到下一位置; // 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置; // 将新元素插入到该位置后; // 重复步骤2~5。 //

  • avatar Walker_ 2020-12-17 17:14:06

    New Year Parties

    题意给定你n个点,每个点可以停在原地或者向左向右,问最多能有多少个不重合的点 还有 最少能有多少个点。 解题报告:看题目就感觉是dp题 但听大佬说不能dp做? 但我抱着侥幸的心里写了写dp,一开始确实wa了,后来看了看状态转移 ,我们dp数组定义的是考虑前i个人并且第i个人的状态是向左、向右、不动

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:14:29

    Points and Powers of Two

    很难证明出这个合法数列最大值就是3。。 然后就好做了 假设存在四个数 x , x+2^i ,x + 2^j , x + 2^l x+2^j - x-2^i = 2^j - 2^i 要是2的整数倍 j=i+1; 同理 l=j+1 那么第二个数和第四个数就不满足差值是2的幂了QUQ。 #include

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:14:50

    Ugly Pairs

    解题报告: 这题真不会。。看了别人的思路就是把奇偶不同的字母分为两类,然后排序,假设两个字符串是a和b ,这样我们检查a+b 是否合法,或者b+a是否合法,如果都不合法就没机会了,不难发现 a和b内部的差值都是偶数,一定是合法的,只需要check 两个字符串连接的地方是否是合法的就行了。 #inc

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:15:12

    Interesting Array

    解题报告: 这题看着别人板子写的,竟然是线段树,真没看出来Orz,思路就是我们通过m次操作,建立线段树,并且每次给区间l,r 或上一个d值,最后检查每次询问的范围内想与的值还是不是原来的值,如果不是就输出no #include<iostream> #include<cstring

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:15:33

    Neko does Maths

    解题报告: lcm(a+k,b+k)= (a+k)(b+k)/gcd(a+k,b+k) ,gcd(a+k,b+k) = gcd(b+k,a-b). 无论k怎么变 a-b就是定值,我们暴力枚举a-b的因子,假设该因子是两个数的最大公约数,因为b+k能被枚举的d所整除,可以求出来k的值,记录最小值就行了

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:15:54

    Variable, or There and Back Again

    题意 有一个序列 ,有1,0,2三种点,每个点之间是有向边,如果存在一条路径从1出发中间不要有1并且以2结尾,这些点都是有趣点,否则不是有趣的。 解题报告:我们将1的点bfs ,将2的点反向bfs,那么一个点是有趣点等价于他同时被1,2点所遍历过。 代码: #include<iostream

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:16:14

    Count The Blocks

    题意:长度最大为i的块,块指的是里面数字相同并且不能向左右延伸。 求长度为n的每个长度块的个数。 解题报告: 看了大佬的思路,发现是一个组合数的问题,我们通过仔细观察,总长度为n 长度为n的块 是固定的 是10个,如000000,111111,当i<n的时候就是一个组合数的问题了,当块不在中

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:16:38

    power products

    解题思路: tle思路:计算出每个值出现的次数,然后枚举x ,因为我看乘机最大也才1e10嘛 ,但是不行,当k=2的时候会卡,别的情况应该不会。哎,, #include<iostream> #include<cstring> #include<vector> #

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:16:59

    Labyrinth

    一看就是bfs题,但是单纯的想,就错了 错误代码: #include<iostream> #include<cstring> #include<queue> using namespace std; const int N=2010; char g[N][N];

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:17:21

    Christmas Trees

    思路: 如下 ,从三个小点开始 ,像不像bfs ,没错就是bfs ,拿个map来记录每个点是否有树或者人, 把可以放的位置放进答案容器里就行了。 #include<iostream> #include<cstring> #include<vector> #inc

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:17:45

    CF776C Molly‘s Chemicals

    解题报告:题目问的是存在区间使得区间和为k的n次幂的方案数,即s[r]-s[l]==pow(k,i) , 由于i很小,那么我们枚举右端点 通过map来记录前面前缀和出现的次数。 #include<iostream> #include<cstring> #include<

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:18:06

    Maximum White Subtree

    解题报告: 这题感觉是树形dp,但想不出来怎么做,看了题解,题解的意思是先从根开始dfs用子树的信息更新根,f数组先定义出包括i的子树中最大的白点减去黑点,由于黑点是0我们可以把它变成-1,那么就是等价于求子树的最大和,然后递归完,除了根以外,每个点都成为过儿子节点,那么我们要考虑根节点对他的影响啦

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:18:28

    Vasya And Array

    题目含义:给定一个长度为n的数列,给你m次操作 ,输入t,l,r ,如果t等于1的话说明l到r之间是不降序区间,t=0则相反,然后问你这所有询问是否有矛盾,如果无矛盾输入一组解。 思路:定义一个差分序列,原数组flag[i]代表i与i+1是否呈不降序,那么可以发现t等于1的时候每次操作就等价于将a[

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:18:48

    线性dp

    题目背景 建筑大师最近在跟着数学大师 ljt12138 学数学,今天他学了等差数列,ljt12138 决定给他留一道练习题。 题目描述 ljt12138 首先建了 nn 个特斯拉电磁塔,这些电塔排成一排,从左到右依次标号为 11 到 nn ,第 ii 个电塔的高度为 h[i]h[i] 。 建筑大

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:19:09

    大致题意:让你求以每个点为中心,所有点到这个中心的距离和。 思路:看了大佬代码,先处理包含每个点的子树的个数,我们当且仅把1当作根结点,然后往下传。然后处理出所有点到1的距离和, res[u] += num[j]; res[u] += res[j];我们可以很好的证明出,u以后的子节点到u的距离无非

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:19:30

    P1279 字串距离

    题目描述 设有字符串X,我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串,如字符串X为”abcbcd”,则字符串“abcb□cd”,“□a□bcbcd□”和“abcb□cd□”都是X的扩展串,这里“□”代表空格字符。 如果A1是字符串A的扩展串,B1是字符串B的扩展串,A1与B1

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:19:51

    CF176B Word Cut

    题意:定义一***作:对于一个串,从任意地方截断,然后把两部分位置交换得到新的串。 对于aa 串一共进行kk 轮这种操作。 问从aa 串变到bb 串有多少种方法。 f数组定义为操作n次是否变成原串的方案数 需要算出s1经过多少种方式能变成s2 这里有个技巧,如果某个串与目标串不同,他有x次可以

    来自 Walker_
    00
  • avatar 驊驊龔頾 2020-12-17 17:19:58

    JS实现:有序数组数字缺失问题

    此题比较容易理解,由于是从零开始的有序数列,所以可以用循环的形式匹配当前元素与索引是否一致,将找到的不一致的值减 1 就是缺失的值。所以可以使用数组循环的方法进行处理,es6中新增的find,filter是比较好的选择 find方法: function solve( a

    来自 驊驊龔頾
    10
  • avatar Walker_ 2020-12-17 17:20:11

    CF1392D Omkar and Bed Wars

    题意: 现在有 nn 个人正在进行Bed War,这 nn 个人排列成环状,第 ii 个人在第 i+1i+1 个人左边,第 nn 个人在第 11 个人左边。 每个人会攻击相邻的一个人,用字母L或R表示,L表示这个人正在攻击左边的人,R则是右边。 一个合法的攻击状态满足以下条件: 如果 aa 在

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:20:32

    C. Good Subarrays

    You are given an array 𝑎1,𝑎2,…,𝑎𝑛 consisting of integers from 0 to 9. A subarray 𝑎𝑙,𝑎𝑙+1,𝑎𝑙+2,…,𝑎𝑟−1,𝑎𝑟 is good if the sum of elements o

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:20:53

    贪心cf d

    解析:这个题的贪心听大佬说还是很明显的,最后的答案就是所有边经过的次数边权,当m比n-1大的时候意味着多出来了m-n+1个乘积,因为贪心我们当然选取大点乘在一起比较好,直接乘到n-1这个数上面,那么每条边走过的次数该怎么算呢,size[u](n-size[u]),假设是u,v这条边,那么v的子树中的

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:21:15

    读入优化

    读入优化 inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:21:35

    D. Unmerge

    题目意思给定一个长度为2n数组,从来2n中分别选n个分为两组,每次选择开头的最小的数,比如3.5.1 2.4.6 第一次选2,第二次选3,第三次选4,第四次选5,第五次1,第六次选6。 思路:每次确定个最大值,然后后面比他小的必定和他一组,如果01背包,看看能不能组成n项。 #include<

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:21:56

    C2. Prefix Flip (Hard Version)

    题目大致意思:给你一个字符串ab,每次你都可以选择前缀n,然后将前n个位翻转(从’0’变为‘1’),然后再整体反转,比如0111 =》1110,让你在2*n步里面从a变到b然后让你输出方案。 解题思路:可以让a先变为全0或者全1,然后我们发现最后是1还是0取决于最后一位是0还是1,然后让b也变为全0

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:22:17

    牛客多校签到

    可以发现,要让答案答案大,那么c的次数多,也就是分解的次数多,那么将某个n按照因数分解,c的因数的个数次就是答案了。 #include<iostream> using namespace std; typedef long long ll; const int mod=1e9+7; l

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:22:38

    牛客多校签到题

    wa了好多次呢我,嘻嘻,按照四边形的性质,对角线的之和肯定大于两对边之和,所以就能判断了。 代码: #include<iostream> using namespace std; int main() { int t; cin>>t; while(t--) {

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:23:04

    构造,循环节

    大致题意:在长度为n的数组里插入一些数,让他每k个数只和都相等。 思路:最后的数列一定是a,b,c,d ,a,b,c,d。。它是拥有循环节的,可以把存在的数放到set里,如果set比k还大,就无法构造循环节了,我们可以构造n个循环节,每个循环节里面如果set个数比k小可以用1来代替。 代码: #i

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:23:26

    叉鸡判断顺时针还是逆时针

    a[20] = a[0]; double res = 0.0; for(int i = 0;i < 20;i++){ res += (a[i].x * a[i+1].y - a[i].y * a[i+1].x); }

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:23:46

    构造AR

    好久没写题解了,于是我不要脸的又回来了,这题算是水题,但是我并没有看出来,😂,如果给定的n 存在a和b 使得a+b==n && a*b == n 那么答案可以由a个A和b个R组成,那么一般的情况呢,可能会存在余数为k的情况,什么是余数为k的情况呢,就是在第一个放A后面几位放k个R接

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:24:08

    二维vector定义方式

    //二维vector初始化 vector< vector > vt;//初始化一个 二维vector vector<vector > vect(vt);//使用另一个 二维 vector 初始化当前二维vector vector< vector > vec(row

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:24:30

    D. Yet Another Yet Another Task

    解题感想:很久没更了,这是昨晚的cf题,题意就是选一段区间,区间的总和减去区间最大值的值最大,用二维dp数组,表示前i个已经扔了最大值的区间最大值,然后枚举扔掉的数,因为扔掉的数很小。当前该点的值如果大于枚举的值,直接跳过,因为他如果在区间里就不合法,如果等于就要分情况,是否扔掉它,如果小于取max

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:24:51

    Codeforces Round #642 (D,E)补

    题目意思就是每次选择当前0最多的一段在这一段的中间将中间的数赋值,是个模拟题,然而我没有思路,看了题解可以用优先队列做,不过优先队列的函数定义特别的奇怪,因为默认是大根堆,所以要排序也要反着排hh,而且定义一个函数要用个结构体存,比如a<b就返回的是a>b,大的在堆顶。然后我们只需要每次

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:25:14

    蓝桥训练(dfs,推公式)

    解题报告:double能储存300位的数,真香。不会大数gg。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath&g

    来自 Walker_
    00
  • avatar ITIronMan 2020-12-17 17:25:26

    IEDA常用快捷键

    以下是我整理的常用的idea快捷键 Ctrl+Z:撤销Ctrl+Shift+Z:撤销的反动作,回退被撤销的内容Ctrl+X:剪贴Ctrl+C:复制Ctrl+V:粘贴Ctrl+Y:光标停留位置直接删除当前行Ctrl+D: 光标停留位置直接复制当前行Ctrl+Shift+J:将选中的行合并成一行Ctrl

    来自 ITIronMan
    00
  • avatar Walker_ 2020-12-17 17:25:35

    Codeforces 1352 G. Special Permutation(构造)

    #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include&l

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:25:57

    并查集(专题)

    解题报告:看似像博弈论的问题,其实就是在询问当两个点在一个集合了就结束游戏了,并查集处理就行了。 #include<iostream> using namespace std; const int N=210,M=N*N; int p[M]; int n,m; int get(in

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:26:20

    练习赛牛客

    这题讲讲思路吧,告诉你两个数,算出他们俩能组成哪些数,其实就是裴蜀定理的应用,他们gcd的倍数都可以组成,只要判断奇偶性就行了。 dfs题,我卡了太久了,按照不同辆小车dfs就行啦。 #include<iostream> #include<cstring> #incl

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:27:02

    树形dp

    实在太菜了,之前做过的模板还是给忘记了,wa10000次才刻骨铭心。 #include<iostream> #include<cstring> using namespace std; const int N=200010; typedef long long ll;

    来自 Walker_
    00
  • avatar 得无 2020-12-17 17:27:02

    从零搭建符合自己需求的开发环境

    从零搭建符合自己需求的开发环境 本文长期持续更新中,保持和自己实际开发环境一致,欢迎关注交流讨论! 前言 这篇文章,一是总结自己,二是给新上道的小白一些思路,三是 何时能重组大学时的EXplosion工作组呢? 现状分析 个人自述 成长于一个有着IT背景的家庭,从小学到大学疯狂参加各种机器人比赛

    来自 得无
    00
  • avatar Walker_ 2020-12-17 17:27:23

    拓扑排序(专题)

    解题报告:拓扑排序的板子题,不想说了。 #include<iostream> #include<cstring> using namespace std; const int N=110,M=10010; int q[N]; bool st[N]; int n; int

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:27:45

    欧拉回路,欧拉路径(专题)

    1123 铲雪车 解题报告:这题其实不知道欧拉路径也能做出来,由于铲雪车在路径上,那么只要算出来所有路径长*2,因为两边都要铲,除以速度就是答案了。 #include<iostream> #include<cmath> using namespace std; doub

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:28:08

    二分图(专题)

    解题报告:二分出来答案,让小于等于答案的罪犯放在同一个监狱,让大于答案的放在另一个监狱,看是否染色成功。 #include<iostream> #include<cstring> using namespace std; const int N=20010,M=2000

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:28:31

    AcWing 368. 银河

    解题报告:这题其实可以差分约束做。但是spfa跑太慢了,我们今天来讲一个线性的做法,tarjan,因为图中没有负点,如果图中存在正环就说明存在和为正数的强联通分量,然后最后问的所有亮度和,可以求出每个连通分量的个数再乘以亮度,亮度可以跑在长路,按照拓扑序的做法。 #include<iostr

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:28:52

    最大半连通子图

    解题思路:只要找一个最长的链,因为不需要两个点互相到达,只需要一个点能到另一个点就行了,但是这条链不能分叉,先tarjan,缩点,建新图,然后用递推思想,从ssc_cnt开始递减,按照拓扑序做,g[]数组代表以i点为终点的方案数,f[]数组代表以i为终点集合中点的数量。如果f[k]<f[i]+

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:29:14

    学校网络

    题目大致意思:给定一个图,问最少激活多少个点可以遍历整个图,至少加几条边可以让每个点都能到达任何点(成为一个大连通分量)。 第一个问题很简单,只要让入度为0的起点都激活,肯定能遍历所有点,第二个答案是max(起点个数,终点个数),类似于这样,记录规律就行了。。 #include<iostr

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:29:36

    174. 受欢迎的牛

    当一头牛的出度为0他一定是受欢迎的牛。 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=10010,M=50010; int h[

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:29:58

    树上差分

    #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include&l

    来自 Walker_
    00
  • avatar Walker_ 2020-12-17 17:30:23

    差分约束(专题)

    其实我个人的看法,觉得差分约束最难的还是要把问题的限制想全,如果遗漏了一个点肯定错,然后求最大值就是<=k1,k2,k3,因为都要满足所以肯定要求k里面的最小值,最短路,求最小值>=k1,k2,k3,就是求最大值,最长路。最短路对应负环,最长路对应正环,如果传统队列的spfa太慢那就考虑

    来自 Walker_
    00