- 博客(88)
- 收藏
- 关注
RSS订阅原创 dsu on tree简介及例题
dsu on treedsu ~on ~treedsu on tree树上启发式合并，多用于对子树的暴力询问，通过使用轻重链定义来进行优化，将算法复杂度降到O(nlogn)O(nlogn)O(nlogn)算是一种优雅的暴力先用一道dsu on tree比较模版的题来引一下codeforces 600E题意：一棵树n个点，每个点有一个颜色 要求每个结点子树的出现哪个颜色次数最多 如果有多个颜色次数同时最多，结果为这些颜色编号相加首先可以考虑暴力的写.
2020-11-11 13:58:30
524
原创 NC23051 华华和月月种树(DFS序+树状数组)
题目链接题意：华华和月月一起维护了一棵动态有根树华华和月月一起维护了一棵动态有根树华华和月月一起维护了一棵动态有根树每个点有一个权值。刚开存档的时候，树上只有0号节点，权值为0每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0每个点有一个权值。刚开存档的时候，树上只有0号节点，权值为0操作1：表示月月氪金使节点i长出了一个新的儿子节点操作 1：表示月月氪金使节点 i 长出了一个新的儿子节点操作1：表示月月氪金使节点i长出了一个新的儿子节点权值为0，编号为当前最大编号+1权值为0，编
2020-08-19 15:18:44
244
原创 NC200532 装货物(DFS)
题目链接题意：有n件货物，第i件重wi吨有 n 件货物， 第 i 件重 w_i 吨有n件货物，第i件重wi吨另有x个集装箱，每个集装箱可以装重量不超过W吨的货物。另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。另有x个集装箱，每个集装箱可以装重量不超过W吨的货物。货物不能拆分，问能否装下货物不能拆分，问能否装下货物不能拆分，问能否装下题解：n<=20,x,w<=1e9n<=20,x,w<=1e9n<=20,x,w<=1e9所以直接考虑暴力搜
2020-08-18 13:53:29
259
2
原创 NC14250 MMSet2
题目链接题意：给一棵n个点的树，点的编号为1，2，3，……，n给一棵n个点的树，点的编号为1，2，3，……，n给一棵n个点的树，点的编号为1，2，3，……，nq次询问，每次询问给定一个点集Sq次询问，每次询问给定一个点集Sq次询问，每次询问给定一个点集S令f(u)为u到点集内点的最大距离令f(u)为u到点集内点的最大距离令f(u)为u到点集内点的最大距离求minu=1..nf(u)求min_{u=1..n}f(u)求minu=1..nf(u)题解：n<=3e5,∑S<=1e6n&
2020-08-17 22:01:53
120
原创 [SCOI2009]生日礼物 (尺取)
题目链接题意：有k种彩珠总共n个，分别在彩带的某个位置x有k种彩珠总共n个，分别在彩带的某个位置x有k种彩珠总共n个，分别在彩带的某个位置x找一个最短距离包括所有彩珠找一个最短距离包括所有彩珠找一个最短距离包括所有彩珠题解：n<=1e6,k<=60n<=1e6,k<=60n<=1e6,k<=60区间统计问题区间统计问题区间统计问题就可以考虑尺取，并且k比较小，可以进行判断就可以考虑尺取，并且k比较小，可以进行判断就可以考虑尺取，并且k比较小，可以进行判断将
2020-08-14 18:45:42
156
原创 [SCOI2010]游戏 (并查集)
题目链接题意：每个装备有两个属性每个装备有两个属性每个装备有两个属性每个装备只能选择一个属性每个装备只能选择一个属性每个装备只能选择一个属性现在需要打败一个怪物，每次对怪物的攻击属性只能是从1开始连续的现在需要打败一个怪物，每次对怪物的攻击属性只能是从1开始连续的现在需要打败一个怪物，每次对怪物的攻击属性只能是从1开始连续的问最多能连续攻击怪物几次问最多能连续攻击怪物几次问最多能连续攻击怪物几次题解：这道题可以考虑用二分图匹配这道题可以考虑用二分图匹配这道题可以考虑用二分图匹配对每个将要攻击
2020-08-13 23:53:08
217
原创 NC19833 地斗主(矩阵快速幂)
题目链接题意：有一个4∗n的网格有一个4*n的网格有一个4∗n的网格有无数个1∗2的骨牌，可以旋转有无数个1*2的骨牌，可以旋转有无数个1∗2的骨牌，可以旋转问把他铺满网格有多少方案数问把他铺满网格有多少方案数问把他铺满网格有多少方案数题解：首先我们假设f(n)表示4∗n网格的方案数首先我们假设f(n)表示4*n网格的方案数首先我们假设f(n)表示4∗n网格的方案数那么可以发现，他是通过前几个补充转移来的那么可以发现，他是通过前几个补充转移来的那么可以发现，他是通过前几个补充转移来的那么就有
2020-08-12 14:02:11
142
原创 CF505C Mr. Kitayuta, the Treasure Hunter(DP)
题目链接题意：长为30000的一条路长为30000的一条路长为30000的一条路有n个位置具有宝藏有n个位置具有宝藏有n个位置具有宝藏一开始在0位置，第一步走d一开始在0位置，第一步走d一开始在0位置，第一步走d如果上一步走了k，这一步可以走k−1,k,k+1如果上一步走了k，这一步可以走k-1,k,k+1如果上一步走了k，这一步可以走k−1,k,k+1问最多能得到多少宝藏问最多能得到多少宝藏问最多能得到多少宝藏题解：最优解问题，可以考虑用dp最优解问题，可以考虑用dp最优解问题，可以考虑用
2020-08-11 19:29:28
183
原创 NC200190 矩阵消除游戏(二进制枚举)
题目链接题意：n∗m的矩阵，可以消除一行或者一列k次n*m的矩阵，可以消除一行或者一列k次n∗m的矩阵，可以消除一行或者一列k次每次消除可以得到该行(列)的分数和，并且这一行(列)全部变0每次消除可以得到该行(列)的分数和，并且这一行(列)全部变0每次消除可以得到该行(列)的分数和，并且这一行(列)全部变0求最大可得到的分数求最大可得到的分数求最大可得到的分数题解：n,m<=15,k<=n∗mn,m<=15,k<=n*mn,m<=15,k<=n∗m发现这个n
2020-08-10 13:33:49
204
原创 NC16618 排座椅(贪心)
题目链接题意：n∗m的座位，有d对同学互相交头接耳n*m的座位，有d对同学互相交头接耳n∗m的座位，有d对同学互相交头接耳可以隔开k行和l列，隔开之后就不会再交头接耳可以隔开k行和l列，隔开之后就不会再交头接耳可以隔开k行和l列，隔开之后就不会再交头接耳问隔开哪些行列可以使得交头接耳同学最少问隔开哪些行列可以使得交头接耳同学最少问隔开哪些行列可以使得交头接耳同学最少题解：由于行和列，每行，每列交头接耳的同学是独立的由于行和列，每行，每列交头接耳的同学是独立的由于行和列，每行，每列交头接耳的同学是
2020-08-07 15:10:59
156
原创 NC16616 双栈排序(二分图)
题目链接题意：给两个栈和一个排列给两个栈和一个排列给两个栈和一个排列每次可以选择序列的第一个数入任何一个栈每次可以选择序列的第一个数入任何一个栈每次可以选择序列的第一个数入任何一个栈或者让任一一个栈顶元素出栈或者让任一一个栈顶元素出栈或者让任一一个栈顶元素出栈要求出栈顺序为1−n要求出栈顺序为1-n要求出栈顺序为1−n题解：n<=1000n<=1000n<=1000首先，思考一个栈的情况首先，思考一个栈的情况首先，思考一个栈的情况想要一个栈的情况下成为顺序想要一个栈的情况
2020-08-06 19:31:08
121
原创 NC14700 追债之旅(单源最短路问题)
题目链接题意：小明要追讨债务小明要追讨债务小明要追讨债务共有n个城市，m条路共有n个城市，m条路共有n个城市，m条路小明在1城，欠债人在n城小明在1城，欠债人在n城小明在1城，欠债人在n城小明经过一条路需要花掉路飞，欠债人第i天会挥霍ai的钱小明经过一条路需要花掉路飞，欠债人第i天会挥霍a_i的钱小明经过一条路需要花掉路飞，欠债人第i天会挥霍ai的钱小明想要这些花费总和最少小明想要这些花费总和最少小明想要这些花费总和最少求这个最小值求这个最小值求这个最小值题解：n<=1000n&l
2020-08-05 12:17:36
173
原创 NC20811 蓝魔法师(树形DP)
题目链接题意：给出一棵树，求有多少种删边方案给出一棵树，求有多少种删边方案给出一棵树，求有多少种删边方案使得删后的图每个连通块大小小于等于k使得删后的图每个连通块大小小于等于k使得删后的图每个连通块大小小于等于k答案对998244353取模答案对998244353取模答案对998244353取模题解：n,k<=2000n,k<=2000n,k<=2000数据范围很明显能开一个二维dp数据范围很明显能开一个二维dp数据范围很明显能开一个二维dp需要的维护是连通块大小和点数需要
2020-08-04 19:27:19
221
1
原创 NC14526 购物(DP)
题目链接题意：共n天，每天有m种糖果可以买，也可以不买共n天，每天有m种糖果可以买， 也可以不买共n天，每天有m种糖果可以买，也可以不买价钱是cij价钱是c_{ij}价钱是cij每天买k个糖果需要额外支付k2的钱每天买k个糖果需要额外支付k^2的钱每天买k个糖果需要额外支付k2的钱要每天都能有一个糖果吃要每天都能有一个糖果吃要每天都能有一个糖果吃问最少花多少钱每天都能有糖果吃问最少花多少钱每天都能有糖果吃问最少花多少钱每天都能有糖果吃题解：n,m<=300n,m<=300n,m
2020-08-03 20:49:00
133
原创 NC23482 小A的最短路(LCA)
题目链接题意：有一棵n个点的树有一棵n个点的树有一棵n个点的树n−1条边经过每条边都需要1点体力n-1条边经过每条边都需要1点体力n−1条边经过每条边都需要1点体力给定一组u,v可以从u到v或者v到u不需要花费体力给定一组u,v可以从u到v或者v到u不需要花费体力给定一组u,v可以从u到v或者v到u不需要花费体力q次询问，x到y最少花费体力q次询问，x到y最少花费体力q次询问，x到y最少花费体力题解：n<=3e5,q<=1e6n<=3e5,q<=1e6n<=3e5
2020-07-31 12:51:58
148
原创 NC20860 兔子的区间密码(二进制)
题目链接题意：给你一个区间[l,r]给你一个区间[l,r]给你一个区间[l,r]找出区间两个数异或最大找出区间两个数异或最大找出区间两个数异或最大题解：l,r<=1e18l,r<=1e18l,r<=1e18肯定不能暴力枚举去找肯定不能暴力枚举去找肯定不能暴力枚举去找然后可以想到，想让这个数最大，就是尽量让二进制全1然后可以想到，想让这个数最大，就是尽量让二进制全1然后可以想到，想让这个数最大，就是尽量让二进制全1那么就找比如100和11这种异或那么就找比如100和11这种异
2020-07-31 01:18:14
194
原创 NC20857 Xor Path(树形DP)
题目链接题意：n个点每个点点权为ain个点每个点点权为a_in个点每个点点权为aipath(i,j)表示i到j最短路点权的异或和path(i,j)表示i到j最短路点权的异或和path(i,j)表示i到j最短路点权的异或和求所有path(i,j)的异或和(i<j)求所有path(i,j)的异或和(i<j)求所有path(i,j)的异或和(i<j)题解：n<=5e5n<=5e5n<=5e5如果只考虑两两点最短路枚举如果只考虑两两点最短路枚举如果只考虑两两点最短
2020-07-29 12:40:04
144
原创 NC20663 Max Power(DP)
题目链接题意：小卤蛋玩dnf学技能，共n行，每行n−i+1个技能小卤蛋玩dnf学技能，共n行，每行n-i+1个技能小卤蛋玩dnf学技能，共n行，每行n−i+1个技能要学习第i行第j个技能的前提是要学习第i行第j个技能的前提是要学习第i行第j个技能的前提是学会i−1行的第j和j+1个技能，每个技能包含战力学会i-1行的第j和j+1个技能，每个技能包含战力学会i−1行的第j和j+1个技能，每个技能包含战力小卤蛋有m个技能点，学一个技能耗费一点，最多能得多少战力小卤蛋有m个技能点，学一个技能耗费一点，最
2020-07-28 20:15:11
84
原创 [CQOI2007]涂色PAINT(区间DP)
题目链接题意：有一个目标字符串，每个字符表示颜色有一个目标字符串，每个字符表示颜色有一个目标字符串，每个字符表示颜色你每次可以为一个区间染色，染成一种颜色你每次可以为一个区间染色，染成一种颜色你每次可以为一个区间染色，染成一种颜色问最少多少次能染成目标颜色问最少多少次能染成目标颜色问最少多少次能染成目标颜色题解：∣s∣<=50|s|<=50∣s∣<=50字符串的长度很小，所以可以考虑较暴力的方法字符串的长度很小，所以可以考虑较暴力的方法字符串的长度很小，所以可以考虑较暴力的方
2020-07-27 20:19:13
170
原创 NC16590 乌龟棋(记忆化搜索)
题目链接题意：有n个格子，1为起点，n为终点有n个格子，1为起点，n为终点有n个格子，1为起点，n为终点每个格子有一个分数每个格子有一个分数每个格子有一个分数有m种卡片，每种卡片有数字1，2，3，4有m种卡片，每种卡片有数字1，2，3，4有m种卡片，每种卡片有数字1，2，3，4代表能走的步数代表能走的步数代表能走的步数走到一点取的该点分数，所有卡片相加恰好到n走到一点取的该点分数，所有卡片相加恰好到n走到一点取的该点分数，所有卡片相加恰好到n求最大能得到的分数求最大能得到的分数求最大能得到的分
2020-07-24 15:14:31
138
原创 浅谈笛卡尔树
题目链接题意：有n个宽a，高h的矩阵块有n个宽a，高h的矩阵块有n个宽a，高h的矩阵块求最大的子矩阵面积求最大的子矩阵面积求最大的子矩阵面积题解：这道题可以用单调栈轻松解决这道题可以用单调栈轻松解决这道题可以用单调栈轻松解决然而前两天多校新学习了笛卡尔树，碰巧这道题可以解决然而前两天多校新学习了笛卡尔树，碰巧这道题可以解决然而前两天多校新学习了笛卡尔树，碰巧这道题可以解决所以用一波笛卡尔树所以用一波笛卡尔树所以用一波笛卡尔树笛卡尔树是一个如图所示的数据结构笛卡尔树是一个如图所示的数据结构笛
2020-07-23 18:49:07
215
原创 NC20684 wpy的请求(SPFA)
题目链接题意：给一个n个点，m条边的有向图给一个n个点，m条边的有向图给一个n个点，m条边的有向图每条边边权可能为负值每条边边权可能为负值每条边边权可能为负值现在要修改边权，使所有边权为非负现在要修改边权，使所有边权为非负现在要修改边权，使所有边权为非负并且使得原图中的任意两点u,v最短路经过路径不变并且使得原图中的任意两点u,v最短路经过路径不变并且使得原图中的任意两点u,v最短路经过路径不变题解：所有边权边为非负，其实就是把负值变大所有边权边为非负，其实就是把负值变大所有边权边为非负，其实
2020-07-22 14:02:09
169
原创 NC22596 Rinne Loves Data Structure(STL)
题目链接题意：存在一棵空树存在一棵空树存在一棵空树每次向根插入一个值，如果该值小于当前点，往左插入，否则往右每次向根插入一个值，如果该值小于当前点，往左插入，否则往右每次向根插入一个值，如果该值小于当前点，往左插入，否则往右如果左右存在值，再次进行判断，直到空插入如果左右存在值，再次进行判断，直到空插入如果左右存在值，再次进行判断，直到空插入问每次插入时所有结点的深度和问每次插入时所有结点的深度和问每次插入时所有结点的深度和题解：n<=3e5,−1e9<=val<=1e9n&
2020-07-21 21:43:08
161
原创 NC19798 区间权值
题目链接题意：有长度为n的数组a和w有长度为n的数组a和w有长度为n的数组a和wf(l,r)=(∑lrai)∗wr−l+1f(l,r)=(\sum_{l}^{r}a_i)*w_{r-l+1}f(l,r)=(∑lrai)∗wr−l+1求∑l=1n∑r=lnf(l,r)mod1e9+7求\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r) mod 1e9+7求∑l=1n∑r=lnf(l,r)mod1e9+7题解：n<=3e5n<=3e5n<=3e5所以只
2020-07-20 17:35:42
201
原创 NC20265 [SCOI2008]着色方案(记忆化搜索)
题目链接题意：有n个木块有n个木块有n个木块k种油漆，每种ci个k种油漆，每种c_i个k种油漆，每种ci个c1+c2+……+ck=nc_1+c_2+……+c_k=nc1+c2+……+ck=n相邻两个木块不能涂相同颜色相邻两个木块不能涂相同颜色相邻两个木块不能涂相同颜色求方案数求方案数求方案数题解：k<=15,ci<=5k<=15,c_i<=5k<=15,ci<=5数据很小，所以可以直接考虑暴力算法数据很小，所以可以直接考虑暴力算法数据很小，所以
2020-07-17 12:33:07
87
原创 NC20464 [ZJOI2006]BOWL 碗的叠放(全排列枚举)
题目链接题意：有n个倒梯形，上宽下窄的碗有n个倒梯形，上宽下窄的碗有n个倒梯形，上宽下窄的碗他们的下底边是r1,上底边是r2,高是h他们的下底边是r1,上底边是r2,高是h他们的下底边是r1,上底边是r2,高是h求出碗叠放的最低高度求出碗叠放的最低高度求出碗叠放的最低高度题解：n<=10n<=10n<=10所以直接枚举放碗顺序，找一下怎么能最低所以直接枚举放碗顺序，找一下怎么能最低所以直接枚举放碗顺序，找一下怎么能最低然后考虑放碗的高度然后考虑放碗的高度然后考虑放碗的高度
2020-07-16 14:44:06
169
原创 NC14393 点权和(计数)
题目链接题意：一棵n个点的树，最开始点权为0一棵n个点的树，最开始点权为0一棵n个点的树，最开始点权为0每次选一个点并且把和他距离为1的点的权值加一每次选一个点并且把和他距离为1的点的权值加一每次选一个点并且把和他距离为1的点的权值加一统计该次加的这些点的最终权值和，乘上次数的总和统计该次加的这些点的最终权值和，乘上次数的总和统计该次加的这些点的最终权值和，乘上次数的总和mod19260817mod19260817mod19260817题解：n<=1e5,m<=1e6n <=
2020-07-15 16:06:06
174
原创 NC20272 [SCOI2009]生日快乐(DFS)
题目链接题意：长宽分别为x,y的蛋糕长宽分别为x,y的蛋糕长宽分别为x,y的蛋糕切n−1次切成n块面积相等的蛋糕切n-1次切成n块面积相等的蛋糕切n−1次切成n块面积相等的蛋糕怎么切能让蛋糕的长比宽的最大值最小怎么切能让蛋糕的长比宽的最大值最小怎么切能让蛋糕的长比宽的最大值最小题解：n<=10n<=10n<=10所以直接暴力切即可所以直接暴力切即可所以直接暴力切即可对于每一刀，切的必须是x/n或者y/n的倍数对于每一刀，切的必须是x/n或者y/n的倍数对于每一刀，切的必须是
2020-07-14 12:38:29
142
原创 NC20252 [SCOI2007]压缩(区间DP)
题目链接题意：给一个字符串，对其进行压缩给一个字符串，对其进行压缩给一个字符串，对其进行压缩对于每个重复串，例如abab可以压缩为MabR对于每个重复串，例如abab可以压缩为MabR对于每个重复串，例如abab可以压缩为MabRR表示重复到上一个M中间所有的解压后内容R表示重复到上一个M中间所有的解压后内容R表示重复到上一个M中间所有的解压后内容求压缩后的最短长度求压缩后的最短长度求压缩后的最短长度题解：∣s∣<=50|s| <=50∣s∣<=50所以考虑用区间dp所以考
2020-07-14 11:11:00
140
原创 NC19810 kingdom(DP)
题目链接题意：一棵树有n个结点一棵树有n个结点一棵树有n个结点每个结点的重儿子到该结点花费为0，其他花费为1每个结点的重儿子到该结点花费为0，其他花费为1每个结点的重儿子到该结点花费为0，其他花费为1问这棵树怎么样连所有结点到根结点1花费最大问这棵树怎么样连所有结点到根结点1花费最大问这棵树怎么样连所有结点到根结点1花费最大题解：n<=8000n<=8000n<=8000n比较小，所以考虑dpn比较小，所以考虑dpn比较小，所以考虑dpdpn表示n个结点的树的最大结果dp_
2020-07-10 17:27:26
134
原创 NC16645 矩阵取数游戏(记忆化搜索)
题目链接题意：有n行m列的矩阵有n行m列的矩阵有n行m列的矩阵对于第i行，可以取出行首或行尾的一个元素对于第i行，可以取出行首或行尾的一个元素对于第i行，可以取出行首或行尾的一个元素对于每一行第k次取出可以得到2k∗aij的分数对于每一行第k次取出可以得到 2^k *a_{ij}的分数对于每一行第k次取出可以得到2k∗aij的分数问最多能得到多少分问最多能得到多少分问最多能得到多少分题解：n,m<=80,aij<=8000n,m<=80,a_{ij}<=8000n,m
2020-07-09 14:24:04
184
原创 NC14254 Color(二分图最大匹配)
题目链接题意：给一个没有重边的二分图,要求给边染色给一个没有重边的二分图, 要求给边染色给一个没有重边的二分图,要求给边染色有公共点的边不能同色.问最少用多少种颜色有公共点的边不能同色. 问最少用多少种颜色有公共点的边不能同色.问最少用多少种颜色并任意构造一组方案.并任意构造一组方案.并任意构造一组方案.题解：n<=1e3,m<=2e3n <=1e3,m<=2e3n<=1e3,m<=2e3题目要求转化一下，就是从一个点出入的所有边，颜色必须不同题目要求转化一
2020-07-08 13:48:24
178
原创 NC13950 Alliances(DFS序 + LCA)
题目链接题意：一个国家有n个城市，形成一棵树，有n−1条边一个国家有n个城市，形成一棵树，有n-1条边一个国家有n个城市，形成一棵树，有n−1条边国家中有k个帮派，分别占领一些城市国家中有k个帮派，分别占领一些城市国家中有k个帮派，分别占领一些城市每个帮派占领ci个城市，以及这ci个城市路径上的所有点每个帮派占领c_i个城市，以及这c_i个城市路径上的所有点每个帮派占领ci个城市，以及这ci个城市路径上的所有点帮派可以联盟，联盟会将几个帮派的所有占领城市和路径上的城市占领帮派可以联盟，联盟会将
2020-07-07 19:05:37
543
原创 NC19814 最短路(LCA)
题目链接题意：给一个连通图，q次询问两点间最短路。每条边的长度都是1。给一个连通图，q次询问两点间最短路。每条边的长度都是1。给一个连通图，q次询问两点间最短路。每条边的长度都是1。题解：n<=1e5,m<=n+100n<=1e5,m<=n+100n<=1e5,m<=n+100q<=1e5q<=1e5q<=1e5多次询问两点间最短路，并且每条边长度都为1多次询问两点间最短路，并且每条边长度都为1多次询问两点间最短路，并且每条边长度都为1最先
2020-07-06 13:23:10
318
原创 NC19775 平衡二叉树(记忆化搜索 || dp)
题目链接题意：建一棵高度为n，并且每个结点的左右子树高度差不超过d的平衡二叉树建一棵高度为n，并且每个结点的左右子树高度差不超过d的平衡二叉树建一棵高度为n，并且每个结点的左右子树高度差不超过d的平衡二叉树在这基础上，问这个平衡树的左右子树的结点个数差最多为多少在这基础上，问这个平衡树的左右子树的结点个数差最多为多少在这基础上，问这个平衡树的左右子树的结点个数差最多为多少题解：n,d<=60n,d<=60n,d<=60想要结点个数差最大，肯定是一棵子树结点个数最少，另外一个最大
2020-07-03 12:55:25
102
原创 NC14699 队伍配置（DP）
题目链接题意：可供玩家选择的作战人物被称作“从者”可供玩家选择的作战人物被称作“从者”可供玩家选择的作战人物被称作“从者”玩家可以对每个“从者”可以装备至多1件的“概念礼装”玩家可以对每个“从者”可以装备至多1件的“概念礼装”玩家可以对每个“从者”可以装备至多1件的“概念礼装”共有n个从者，m个概念礼装共有n个从者，m个概念礼装共有n个从者，m个概念礼装玩家具有一个cost上限值d玩家具有一个cost上限值d玩家具有一个cost上限值d每个从者和概念礼装都有一个ATK和cost，并且不能重复使用
2020-06-24 12:06:50
264
1
原创 NC23413 小A买彩票（背包DP）
题目链接题意：小A买彩票，每张彩票3元小A买彩票，每张彩票3元小A买彩票，每张彩票3元可以中奖1，2，3，4元，概率相同可以中奖1，2，3，4元，概率相同可以中奖1，2，3，4元，概率相同问买n张彩票不亏的概率问买n张彩票不亏的概率问买n张彩票不亏的概率题解：n<=30n<=30n<=30题目要求输出分子分母的最简形式题目要求输出分子分母的最简形式题目要求输出分子分母的最简形式所以就是求，买n张彩票的所有情况，和不亏的情况所以就是求，买n张彩票的所有情况，和不亏的情况所以就
2020-06-23 12:37:52
169
原创 NC53079 Forsaken喜欢数论(数论)
题目链接题意：求出1到n每个数的最小质因子的和求出1到n每个数的最小质因子的和求出1到n每个数的最小质因子的和题解：n>=3e7n>=3e7n>=3e7如果对每个数暴力取，复杂度肯定是O(nn)如果对每个数暴力取，复杂度肯定是O(n\sqrt{n})如果对每个数暴力取，复杂度肯定是O(nn)这是一定超时的，所以考虑对每个数进行预处理这是一定超时的，所以考虑对每个数进行预处理这是一定超时的，所以考虑对每个数进行预处理然后直接用O(1)求除1到n的每个数的最小质因子然后直接用O
2020-06-22 15:22:06
255
原创 CodeforcesRound#327(Div.2)E.ThreeStates(BFS)
题目链接题意：有三个国家，想要相互交通有三个国家，想要相互交通有三个国家，想要相互交通有一个n∗m的矩阵，#代表墙，表示不能走动有一个n*m的矩阵，\#代表墙，表示不能走动有一个n∗m的矩阵，#代表墙，表示不能走动1，2，3代表国家，之间可以走动1，2，3代表国家，之间可以走动1，2，3代表国家，之间可以走动.代表可开设的路，开设路需要花费1.代表可开设的路，开设路需要花费1.代表可开设的路，开设路需要花费1最少花费多少可以让三个国家相互连通最少花费多少可以让三个国家相互连通最少花费多少可以让三
2020-06-19 13:07:11
167
原创 [SCOI2005]扫雷MINE(思维+枚举+递推)
题目链接题意：扫雷游戏扫雷游戏扫雷游戏一个n∗2的图，第一列的位置可能有雷，第二列没有一个n*2的图，第一列的位置可能有雷，第二列没有一个n∗2的图，第一列的位置可能有雷，第二列没有给出第二列第i行的数字ai，表示周围8个位置的雷数给出第二列第i行的数字a_i，表示周围8个位置的雷数给出第二列第i行的数字ai，表示周围8个位置的雷数问总共有多少种摆雷的方案问总共有多少种摆雷的方案问总共有多少种摆雷的方案题解：这种题一眼看下去，第一个想到的就是dp这种题一眼看下去，第一个想到的就是dp这种题一
2020-06-18 14:52:59
200
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人