- 博客(85)
- 收藏
- 关注
RSS订阅
原创 退役感想（2019.11）
3银退役了，有点遗憾ccpcfinal梦回nmb西安邀请赛，找规律疯狂白给然后改暴力搜重新找规律。。大二到大三主要努力的方向就是dp，可惜赛场上两题dp都没往dp上想，哈尔滨太可惜了~~来自neuq竞赛队退役老队长sy，有新的学弟在算法学习上有疑问的欢迎找俺~~~希望neuq早日拿金！！！以后就搞搞机器学习方面了，另外有日本读研或者想去日本读研的小伙伴欢迎联系我主页！！！想找个战友...
2020-02-23 22:28:08
253
原创 (复健)Codeforces Round #686 (Div. 3)个人题解
退役老狗复健ing，virtue了一下做了4题，前期做的太慢了，然后剩了40分钟吧，看的F，ST表那边写错了一个地方到死没debug出来= = 复健路漫漫啊A - Special Permutation就分奇偶，相邻两个交换一下就行，奇数最后三个交换int t;int n,m,a,b;int main(){ cin>>t; while(t--) { cin>>n; if(n%2==1) {
2020-12-03 20:13:44
162
原创 LeetCode2020春季编程赛团队赛 题解（暂完成ABCD题）
D题 切割数组题目链接 ： https://leetcode-cn.com/problems/qie-fen-shu-zu/题目大意：拆分原来的一个数组，拆分后的每个数组满足最左和最优元素gcd>1gcd>1gcd>1 求最小拆分次数。题解思路：先手写了几个数据，否决了贪心的做法，强行把每个数组扩成最大 这样的做法不是最优的。考虑dp的思路，大概的复杂度是O(nm)O...
2020-04-28 01:10:00
271
原创 2017-2018 ACM-ICPC Latin American Regional E Enigma dp 记忆化搜索
题目链接https://vjudge.net/problem/Gym-101889E题目大意给定数字串和kkk，数字串为???的位置可以任意填0−90-90−9，求最小的%k为0的数，没有则输出∗*∗1≤len≤10001 \leq len \leq 10001≤len≤1000 , 1≤k≤10001\leq k \leq 10001≤k≤1000题解思路状态很多，不能直接暴搜。这...
2019-10-09 13:55:46
270
原创 NCPC 2018 E. Explosion Exploit 状压 记忆化搜索
题目链接：https://codeforces.com/gym/101933/problem/E题目大意我方有nnn个士兵，对方有mmm个士兵，每个士兵有对应的血量，血量xxx为000时士兵消失。现在轮到我方进行攻击，共攻击ddd次，每次攻击会等概率选择场上还活着的士兵减少其一滴血，问ddd次攻击后地方士兵全部死亡的概率。1≤n,m≤51\leq n,m \leq51≤n,m≤5 , 1≤...
2019-10-08 21:36:24
230
原创 HDU - 4784 Dinner Coming Soon （dp）
题目链接https://vjudge.net/problem/HDU-4784题目大意从111号点走到nnn号点，有mmm条有向路径，每条路径需要花费时间和路费，初始有r元，在每个点可以选择买入 ororor 卖出 商品 ororor不做 商品最多携带bbb个， 共有[0,k−1][0,k-1][0,k−1]个空间，可以花费111的时间穿越到(i+1)(i+1)%k(i+1)号空间，不同空间...
2019-09-29 14:05:51
107
原创 hdu 6006 Engineer Assignment 2016 ccpc final (状压dp)
题目链接https://vjudge.net/problem/HDU-6006题目大意有nnn个工程和mmm个人，每个工程需要几个方面的人才，一个人在某几个方面精通，问同时最多可以进行多少个工程 (一个人只能参与一个工程)题解思路这道题的数据范围很小，考虑状压dp用dp[i][sta]dp[i][sta]dp[i][sta]表示进行到第iii个工程，用了stastasta状态的人的最大...
2019-09-29 13:19:42
130
原创 2018 ccpc秦皇岛 Riddle 状压dp
拖了一年了才补。。。去年现场赛3个小时没做出来，今年看了半个小时就有思路了= =题目大意有数组an{a_n}an其中ai{a_i}ai可以作为物品，也可以作为袋子如果作为物品，ai{a_i}ai作为物品的重量，不一定要装在袋子里如果作为袋子，ai{a_i}ai作为袋子的容量，必须要装满物品。对每一组输入，输出总的方案数n<15,ai<2000n<15,{a_i...
2019-09-20 11:43:19
196
原创 Coprime HDU - 5072 2014 Asia AnShan Regional Contest B （数学 容斥）
题目链接 https://vjudge.net/problem/HDU-5072题目大意给定数组aia_iai求满足以下两个条件其中一个的三元组(a,b,c)(a,b,c)(a,b,c)的数量 ps:(a,b,c)=(b,c,a)ps:(a,b,c)=(b,c,a)ps:(a,b,c)=(b,c,a)1.(a,b)=1,(a,c)=1,(b,c)=1(a,b)=1,(a,c)=1,(b,c...
2019-09-20 11:23:49
127
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 J Random Access Iterator（树型dp）
题目链接： https://nanti.jisuanke.com/t/41392题目大意：以111号节点作为根节点，假如当前节点有mmm个子节点，就进行mmm次等概率的选择下一个节点，直到叶子节点为止，问最后走到最深的叶子节点的概率。解题思路：树上的一个dpdpdp转移，直接考虑转移到合法的情况比较复杂，每次转移我们考虑转移不到合法节点的情况。设dp[i]dp[i]dp[i]表示iii号...
2019-09-10 16:49:11
155
原创 The 2019 Asia Nanchang First Round Online Programming Contest E Magic Master （思维 模拟 暴力）
题目链接https://nanti.jisuanke.com/t/41352大概的模型就是一个约瑟夫环例如题目样例，可以改写成：555个人围成一圈，第一个人第一个退出，报数222，报到111的人退出，问第xxx个人是第几轮退出的这个题6s 而且只有10组。。感觉O(nm)O(nm)O(nm)的复杂度是可以过的，结果真就过了。。具体的实现用最暴力的方法ttt了，改进了一下用一个nex[i]n...
2019-09-09 21:14:04
102
原创 两道图上概率dp
1.2019icpc南京网络赛D Robot题目链接：https://nanti.jisuanke.com/t/41301题目大意：有一个nnn个点mmm条边的DAGDAGDAG, 第iii步的花费是iii, 问DAGDAGDAG上从1th1_{th}1th节点到nthn_{th}nth节点的期望花费。题解思路：概率dp的题目一般都是用dp[1]dp[1]dp[1]表示答案，这题同样...
2019-09-05 23:01:15
208
原创 牛客暑期多校训练第五场 B generator 1
题目链接：https://ac.nowcoder.com/acm/contest/885/B矩阵快速幂指数为大数需要改成十进制快速幂，常数比较大，需要用二进制优化。用作十进制矩阵快速幂的板子PS:这题我队做了3个小时的欧拉降幂，矩阵乘法不适用欧拉降幂，是用错场合了。#include <bits/stdc++.h>using namespace std;#define l...
2019-08-02 09:33:23
108
原创 数论学习之 fft (模板+例题)
例题1：给定两个很大的整数（会卡掉高精度）输出其乘积用作fft的模板#include<bitset>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define N 400005#define pi acos(-1.0)us...
2019-07-23 19:18:51
196
原创 ecnu个人赛 B Black Peter dp
题目链接https://codeforces.com/gym/102190题解思路设dp[i][0]dp[i][0]dp[i][0]表示乌龟在对面，两边各有一张的牌共iii个先手赢的概率设dp[i][1]dp[i][1]dp[i][1]表示乌龟在自己，两边各有一张的牌共iii个先手赢的概率乌龟在对面有两种转移方式，分别是抽对面乌龟和抽对面正常牌乌龟在自己有一种转移方式，抽对面正常牌我...
2019-05-07 00:18:58
279
3
原创 2019浙江省省赛 ZOJ 4101 Element Swapping 数学
题目链接https://vjudge.net/problem/ZOJ-4101题解思路赛场想的是O(nlogn)O(nlogn)O(nlogn)的算法，T了有20发从头讲一下，就是化简一下 Δ\DeltaΔxxx和 Δ\DeltaΔyyy 这里我设的是变化前减去变化后，我们可以把数组看做是初始的，给定的x和y是变化后的。化简完：Δ\DeltaΔx=(j−i)∗(ai−aj)x=(j-...
2019-05-06 21:23:03
263
原创 Codeforces Round #549 (Div. 2) E. Lynyrd Skynyrd 倍增
题目链接：https://codeforces.com/contest/1143/problem/E题目大意给定一个排列ppp，给定一个数组bbb每个询问给出l,rl,rl,r问在[l,r][l,r][l,r]中是否存在ppp的循环排列题解思路需要预处理每个点作为右端点对应的左端点，然后和给定的区间长度作比较直接处理的话是O(n∗m)O(n*m)O(n∗m)的复杂度这个地方用到了一...
2019-04-25 21:11:32
128
原创 Codeforces Round #552 (Div. 3) E stl模拟 F dp G gcd
contest链接https://codeforces.com/contest/1154E题解思路直接哈希模拟删除T了，可以用setsetset和lowerlowerlower_boundboundbound函数减少寻找下一个没有删除元素的复杂度#include <bits/stdc++.h>using namespace std;#define IOS ios::syn...
2019-04-25 20:10:36
106
原创 Codeforces Round #553 (Div. 2) E. Number of Components (计数)
题目链接：https://codeforces.com/contest/1151/problem题目大意：a[i]a_[i]a[i]表示iii号节点的权值，iii号节点和i−1i-1i−1号，i+1i+1i+1号节点相邻f(l,r)f(l,r)f(l,r)表示只留下权值在[l,r][l,r][l,r]范围内的节点后，连通块的个数求∑l=1n∑r=inf(l,r)\sum_{l=1}^{...
2019-04-25 19:41:40
119
原创 Codeforces Round #553 (Div. 2) F. Sonya and Informatics （dp 矩阵快速幂）
题目大意：给定一个数组包含010101两种字符，每次操作可以选其中两个调换位置，问经过kkk次操作之后变为00000011111这样非严格升序的概率，用逆元的形式输出。题解思路分别记000的数量为zerozerozero，111的数量为oneoneone在[1−zero][1-zero][1−zero]中的000的数量为nownownow先不考虑时空复杂度的问题：设dp[i][j]dp[...
2019-04-25 19:00:47
155
原创 The Preliminary Contest for ICPC China Nanchang National K MORE XOR 找规律
题目链接https://nanti.jisuanke.com/t/38230题目大意f(l,r)f(l,r)f(l,r)表示aaa数组的区间异或和g(l,r)g(l,r)g(l,r)表示f(l,r)f(l,r)f(l,r)的区间异或和w(l,r)w(l,r)w(l,r)表示g(l,r)g(l,r)g(l,r)的区间异或和对每组询问给出对应的答案对g(l,r)g(l,r)g(l,r)枚举...
2019-04-21 20:03:59
110
原创 Educational Codeforces Round 62 (Rated for Div. 2) E. Palindrome-less Arrays dp 计数 组合数学
题目链接：https://codeforces.com/contest/1140/problem/E题目大意给定一个串，不能出现长度为奇数(len≥3)(len\geq3)(len≥3)的回文串，−1-1−1的位置可以填1−k1-k1−k的所有数，问有多少种合法的方案，输出方案数。题解思路思路来源于官方题解，看完就是恍然大悟的感觉。不能出现长度为奇数(len≥3)(len\geq3)(l...
2019-04-10 21:16:19
147
原创 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest B - Ultraman vs. Aodzilla and Bodzilla 贪心
题目链接：https://codeforces.com/gym/102028/problem/B题目描述：奥特曼打怪兽，有怪兽aaa和bbb 分别对应的生命值为HPa，HPbHP_a，HP_bHPa，HPb和攻击力ATKa,ATKbATK_a,ATK_bATKa,ATKb，按回合制进行攻击，如果怪物活着，将对奥特曼先造成对应的伤害，在第iii回合奥特曼打怪的伤害为iii，问奥特曼杀死这...
2019-04-09 19:28:16
390
原创 2018-2019 ACM-ICPC, Asia East Continent Finals I Misunderstood … Missing（dp）
题目链接:https://codeforces.com/gym/102056/problem/I题目大意：打怪，人一开始有的初始攻击力,的攻击力增量(每回合增加D的攻击力 ())，问对怪造成的最大伤害是多少每回合可以选择以下操作的一种1. 打怪，造成点伤害2. 增加增量3. 直接增加攻击力给出总的回合数，和每回合对应的题解思路：这道题的关键在于如何用d...
2019-04-04 15:16:12
294
原创 codeforces#550 div3 G. Two Merged Sequences (贪心 / dp)
题意：从一个数组中提取出一个严格升序和一个严格降序的序列，可行输出方案题解思路：维护一个升序序列，一个降序序列，如果只满足其中一个，就插入，如果都不满足就输出no如果两个都满足，需要比较和下一个的大小关系：贪心思路就是尽量保持降序的最小值最大，保持升序的最大值最小很巧妙的贪心思路#include<bits/stdc++.h>using nam...
2019-04-03 21:28:56
96
原创 CodeForces 1139D Steps to One（概率dp 容斥/莫比乌斯反演）
题目链接https://codeforces.com/contest/1139/problem/D题意：给定一个m，每次在1-m中随机取一个数放到容器中，当容器的gcd为1时停止，求期望步数，用分数形式的逆元输出题解思路：表示只会容斥的思路啊，反演的题解那步概率的转移没看懂= =(p/(1-p))哪个不知道怎么来的下面主要提一下容斥，以后有能力了补莫比乌斯反演的方法。...
2019-03-26 22:15:53
986
原创 天梯赛 并查集相关题目
L2-007家庭房产（25分)给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。输入格式：输入第一行给出一个正整数N（≤1000），随后N行，每行按下列格式给出一个人的房产：其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0≤k≤5）是该人的子女...
2019-03-20 11:58:37
146
原创 天梯赛 二叉树相关题目
L2 006 树的遍历给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。利用二叉树左右儿子和根节点的下...
2019-03-19 20:12:22
160
原创 天梯赛L2-004 这是二叉搜索树吗？
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，其左子树中所有结点的键值小于该结点的键值； 其右子树中所有结点的键值大于等于该结点的键值； 其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。输入格式：输入的第一行给出正整...
2019-03-19 12:25:39
130
原创 天梯赛L2-1 紧急救援
#include <iostream>#include <queue>#include <cstring>#include <algorithm>using namespace std;const int maxn=505;const int inf=99999999;int n,m,s,d;int num[maxn];int s...
2019-03-18 21:24:30
120
原创 Codeforces Round #538 (Div. 2) D Flood Fill (区间dp)
题目链接：https://codeforces.com/contest/1114/problem/D题目大意：一个数组，ai表示i点的颜色，开始选一个点开始，每次可以将相同颜色的块全部变成另一种颜色，问最少花费的步数 最后要合成一个颜色相同的条。对区间 [ L , R ] 有两种转移方法：1.全部变成a[r+1]的颜色，如果当前颜色不同则需要+12.全部变成a[l-1]的颜色...
2019-03-12 20:41:12
150
原创 Codeforces Round #542 E Wrong Answer
题目链接：https://codeforces.com/contest/1130/problem/E题目大意：求一个数组中最大的 (R-L+1)*sum(a[i]~a[j]) 题目给出了一种错误的求法，输入一个数x，使正确的的答案是错误的答案+x，构造出这样的a数组错误的解法就是一旦前缀和小于0了，就抛掉不要，由于是构造题，我们可以简化这个问题。假设这个数组只有第一项是负的...
2019-03-12 17:14:38
160
原创 Codeforces Round #543 div2 C System Testing (乱搞)
题目链接https://codeforces.com/contest/1121/problem/C窒息乱搞题。。赛场一个多小时没出，赛后看别人代码用了两个set写还是很方便的这种不考算法的题。。先想好自己的思路，再找合适的数据结构去搞我认为最靠谱的方法是一个set存当前在跑的id一个set存符合题目要求的id（去重）一个queue存尚未跑的一个vector存...
2019-03-11 22:21:29
258
原创 CodeForce 1132F - Clear the String (区间dp)
题意：一个string，每次消可以消掉一串字母相同的子串，问删除整个串的最小删除次数很典型的区间dp，赛场没出可惜了设表示消除 [ L , R ]区间所需的最小花费转移方向：1.单独删除L 可以转移到2.循环遍历区间，设下标为i时存在 此时可以转移到注意如果边界的话，需要特判由于是区间dp，要求的是在求解时，其所有的子区间都是已知的，在循环时...
2019-03-11 21:56:32
258
原创 CodeForce 1133E - K Balanced Teams （dp）
题目链接：https://codeforces.com/contest/1133/problem/E题目大意：有n个人每个人对应一个值ai，要求组成至少一个，至多k个队伍，且队伍内的人权值差最大不超过5，问此时在队伍中的最多队员数先对数组从小到大排个序假设表示当前将第i个人作为新的队伍的第一个人，且此时有j个非空队伍的状态对应的最大在队伍里的队员数量转移方向：1.跳过第i个，直...
2019-03-11 20:30:44
553
原创 wannafly day 8 看演唱会div2 拓欧应用
题目链接：https://www.zhixincode.com/contest/29/problem/J题目大意：和纱每b天休息前a天，后面开演唱会，雪菜每d天工作前c天，后面休息，问她在n天中有多少天有空看演唱会div2中的数据范围比较小，可以n方循环可行天数用类欧解答(i,j)表示和纱的可行区间中第i天 雪菜的可行区间的第j天重合用x表示和纱在第一个区间后又进行了几个区间，y表...
2019-02-28 23:54:50
118
原创 ccpc wanna fly day 7 斐波那契数列
题目链接：https://www.zhixincode.com/contest/25/problem/C?problem_id=361将题目所求转换成然后分别求一下Fib的前n项和 就是 Fib(n+2)-1和lowbit( F(n))的前n项和打表观察lowbit的数据可以看出：1.%3不为0的时候全部为12.%3为0的时候 若n是奇数，全部为23.%3为0的时...
2019-02-28 17:27:06
122
转载 杜教BM板子解决线性递推问题
https://codeforces.com/contest/1117/problem/D转自https://blog.csdn.net/qq_37632935/article/details/87889975这题中看到了一个30ms的神仙代码，嫖了个杜教BM的板子O(n)搞一下前面几百项，放进去。。。 nb#include<bits/stdc++.h>usin...
2019-02-24 14:51:27
404
原创 wannafly day5 Kropki
题目链接https://www.zhixincode.com/contest/21/problem/F给定一个01串，为1表示i和第i+1位 有一个数是另一个的2倍 问总的符合要求的排列的 总数量 题解思路：n很小，考虑状压dp需要记录的有：当前到第几位了，当前的数是多少，当前已经选了的集合（状压表示）成2倍关系那边比较烦，写个函数清晰很多#include <c...
2019-02-24 14:30:10
163
原创 wannafly day4 欧拉回路
题目链接https://www.zhixincode.com/contest/17/problem/D?problem_id=251怼了三个小时吧。。完全没考虑有一条边等于2的情况。。主要思路就是欧拉回路每个点出度=入度，对每条边加方向，加边（走几次）尝试了很多次之后，直觉告诉我每条边最多走两次，并且要让走两次的边尽量少。#include <cstdio>#in...
2019-02-18 01:43:14
136
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人