- 博客(580)
- 收藏
- 关注
RSS订阅
原创 HDU 6000 Wash （双二分+贪心）
WashTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 64000/64000 K (Java/Others)Total Submission(s): 2613 Accepted Submission(s): 700 Problem DescriptionMr.Panda is about to engage...
2018-10-29 21:45:17
562
原创 2019-2020 ICPC香港 A. Axis of Symmetry （思维+结论）
传送门题意TTT组数据，每组数据给你一个正整数nnn，然后给你笛卡尔坐标系下nnn个矩形的左下角和右上角的点的坐标(xi1,yi1),(xi2,yi2)(x_{i_1},y_{i_1}),(x_{i_2},y_{i_2})(xi1,yi1),(xi2,yi2)，保证矩形之间不会有重叠，求出所有的对称轴。输出格式：第一行一个整数szszsz，表示对称轴数量。接下来一行输出若干条对称轴的三个参数，一条对称轴的三个参数形式为 aaa bbb ccc，表示对称轴ax+by=cax+by=c
2020-12-16 14:22:33
1409
原创 2019-2020 ICPC香港 C. Constructing Ranches （点分治）
传送门题意TTT组数据，每组数据给你一个正整数nnn，然后每个点的权值aia_iai，再给你n−1n-1n−1条无向边(ui,vi)(u_i,v_i)(ui,vi)，保证构成一棵树。求有多少条合法的路径（相当于多少个点对），使得路径上经过的所有点的权值可以构成一个简单多边形。数据范围：1⩽n⩽2×105,1⩽ai⩽1091\leqslant n\leqslant 2\times10^5,1\leqslant a_i\leqslant 10^91⩽n⩽2×105,1⩽ai⩽1091⩽ui,
2020-12-15 20:11:37
573
原创 2020 China Collegiate Programming Contest - Mianyang Site 2020 CCPC 绵阳站 B. Building Blocks（dp）
传送门题意TTT组数据，每组数据给你三个正整数n,m,kn,m,kn,m,k，其中n，mn，mn，m分别为积木的长和宽（积木由若干个1×1×11\times1\times11×1×1的小方块组成），再给你左前视图（如图所示）每一部分的最终高度aia_iai（共n+mn+mn+m部分），接下来kkk行，每行三个正整数x,y,hx,y,hx,y,h，表示第xxx行yyy列的高度指定为正整数hhh，问你合法的积木总数，对109+710^9+7109+7取模。数据范围：1⩽T,n,m,k⩽105,
2020-11-30 18:48:19
656
原创 2020 China Collegiate Programming Contest, Weihai Site L. Clock Master（分组背包+预处理）
传送门题意给你一个正整数nnn，你需要将nnn拆成若干个正整数的和。设拆成了t1,t2,...,ts{t_1,t_2,...,t_s}t1,t2,...,ts这sss个正整数，对于任意自然数kkk，存在向量(k(k(k modmodmod t1,{t_1},t1,kkk modmodmod t2,...,{t_2},...,t2,..., kkk modmodmod ts){t_s})ts)，这些向量中的不同向量个数记为xxx。因此每种拆分对应一个不同的向量个数，现在让你求一个使xxx最
2020-11-23 16:07:22
368
2
原创 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019) E. Life Transfer（大模拟）
传送门题意给你nnn，kkk表示nnn个人要出去玩，每辆车可以带kkk个人，再给你lc{l_c}lc，pc{p_c}pc，lm{l_m}lm，pm{p_m}pm分别表示开车需要达到的年龄，买一辆车的花费，骑摩托需要达到的年龄，买一辆摩托的花费（摩托不能载人，也就是一辆摩托只能一个人骑着去）。接下来给你ttt，ddd，表示nnn个人之间可以互相转移年龄，每转移111岁花费为ttt，每个人最多转移ddd岁（一个人的年龄不能低于111岁），最后给你nnn个人的年龄ai{a_i}ai。也就是说，
2020-11-14 12:55:31
350
原创 2019-2020 ACM-ICPC Brazil Subregional Programming Contest I. Interplanetary（思维+floyed）
传送门题意给你nnn，mmm表示nnn个点，mmm条无向带权边，接下来给出nnn个点的权值vi{v_i}vi ，再给出每条无向边的两个端点和权值www。再给你qqq，接下来qqq次查询，每次查询的格式为aaa bbb kkk ttt查询的是aaa到bbb经过的中间节点的值只能是前kkk小的或者是前kkk大的点的最短路长度，如果不可达输出−1-1−1。如果t=0t=0t=0表示前kkk小，t=1t=1t=1表示前kkk大。数据范围：2⩽n⩽400,0⩽m⩽n(n−1),−109⩽vi⩽109
2020-11-11 20:09:11
430
原创 Educational Codeforces Round 97 (Rated for Div. 2) G. Death DBMS （AC自动机）
传送门G. Death DBMStime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputFor the simplicity, let’s say that the “Death Note” is a notebook that kills a person when their name is written in it.It’s easy to
2020-11-10 15:05:25
249
原创 2020 China Collegiate Programming Contest Qinhuangdao Site B. Bounding Wall（思维+并查集）
传送门B. Bounding Walltime limit per test4.0 smemory limit per test512 megabytesinputstandard inputoutputstandard outputAlex is a professional computer game player.These days, Alex is playing a war strategy game. His land is a rectangular grid with n r
2020-10-28 22:17:17
408
原创 Central Europe Regional Contest 2019 J. Saba1000kg （并查集+根号讨论）
链接：https://ac.nowcoder.com/acm/contest/7817/I来源：牛客网时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述There are many different streams in Viking rock movement. Old Icelandic granite rock, Mid- dle Danish dusty Viking rock,
2020-10-06 20:16:38
291
原创 2020杭电多校第三场 1006 - X Number （HDU 6796 数位dp）
X NumberTime Limit: 3000/3000 MS (Java/Others)Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 805Accepted Submission(s): 327Problem DescriptionTeitoku loves many different kinds of numbers, and today Little W wants him to c...
2020-09-21 20:51:40
296
原创 HDU 5519 Kykneion asma （2015 ICPC 沈阳 K）状压dp+容斥
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5519题意给你n(<=15000)，再给你0~4这五个数字的可用数量a[i](<=30000)，你需要用这些数字构造长度为n的序列，不能有前导零，求合法的方案数。分析网上有多种解法，主要如下：①生成函数FFT（窝不会）：https://blog.csdn.net/Quack_quack/article/details/50748753?utm_source=blogxgwz4②
2020-07-05 20:29:51
239
原创 Educational Codeforces Round 90 (Rated for Div. 2) G. Pawns （线段树）
G. Pawnstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a chessboard consisting ofnnrows andnncolumns. Rows are numbered from bottom to top from11tonn. Columns are...
2020-07-03 14:30:08
252
原创 Educational Codeforces Round 90 (Rated for Div. 2) F. Network Coverage（二分 or 思维）
F. Network Coveragetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe government of Berland decided to improve network coverage in his country. Berland has a unique structure: the cap
2020-07-01 20:52:15
313
原创 Codeforces Global Round 8 E. Ski Accidents （思维）
E. Ski Accidentstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputArthur owns a ski resort on a mountain. There arennlanding spots on the mountain numbered from11tonnfrom the top t...
2020-06-28 20:58:33
304
原创 The 2017 ACM-ICPC Asia Jakarta Regional Contest L - Sacred Scarecrows/UVALive - 8144 （状压dp+容斥）
传送门题目：题意：多组输入，给你n*m(n<=14,m<=1e3)的字符矩阵，只包含 v 和 . 其中v是障碍物。你需要在.上涂色，使得每一行都有格子被涂色，相邻两列必须有一列有格子被涂色。求最终的合法方案总数%1e9+7。思路：一看到这个题意和n的范围，肯定是状压dp。首先，如果直接暴力状压的话，我们需要枚举每一列，这一列的状态，上一列的状态，复杂度将会爆炸。发现对于障碍物，我们直接开一个数组记录这一列合法的位置即可，至于相邻两列必有一列涂色，我们就设dp.
2020-06-27 12:57:30
493
原创 ZOJ 3984 Graph Generator（2017CCPC秦皇岛 D）可撤销并查集+思维
题目传送门题意：T组数据，每组数据给你n(<=1e5)个点，m(<=min(1e5,n*(n-1)/2))条无向边，你需要构造一个合法的序列，其中每一项输出三个数：点x，你选择的点集的大小，然后给出这些点。（初始为空图，之后系统会增加一个新点x，并将x与你给出的这些点所在的连通块的每一个结点连边！）最后形成题中给你的图。问你是否存在合法方案，如果存在输出Yes和任意一种方案，否则输出No。思路：直接正着做找合法序列太难了，我们考虑从原图往下一个一个拆点，拆成一个合
2020-06-24 22:07:04
368
原创 Codeforces Round #651 (Div. 2) F2. The Hidden Pair (Hard Version) （二分+剪枝）
F2. The Hidden Pair (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputNote that the only difference between the easy and hard version is the constraint on the number of que
2020-06-24 20:03:43
263
原创 2020年6月24日训练总结（codeforces辛路历程）
5月底研究生复试完以后，终于可以专心备战ACM了。这一个月，也确实让我有了不小的收获。1、绝大部分题目的知识点还是常用的那些，只是因为思维能力没跟上，才没做出来。所以多做一些高难度（特别是考思维能力）的题目，是可以收获很多东西的，这些题目要细品，仔细思考每一步是如何想到的，是否可以用在其他的地方。2、不要把问题想太复杂了，题目往往并没有我们想象的那么难（当然一些毒瘤题除外）。题目中给的每个条件都暗藏玄机，其中某个数据的范围可能就是你解题的突破口。3、对于一些你不会但是很多人过（并且通过率比较高）
2020-06-24 13:16:29
1078
4
原创 HDU 6268 Master of Subgraph （2017CCPC杭州 E）分治+bitset优化
题目传送门题意：给你一颗n(<=3e3)个点的无向树，再给你一个数m(<=1e5)，再给你n个点的权值a[i](<=1e5)求对于每个x属于[1,m]，是否存在一个连通子图的权值和正好为x。输出一个长度为m的01串，第i个位置上的数字表示是否存在连通子图的权值和正好为i。思路：点分治+bitset优化知识盲区。。。打重现的时候满脑子暴力优化，然后T到结束。。。考虑枚举每个点，找出包含这个点的所有连通子图的权值（这里需要注意，枚举节点u为根时，往下搜索的每一步都是
2020-06-22 21:00:44
265
原创 HDU 6240 Server（2017CCPC哈尔滨 K）01分数规划+树状数组优化dp
题目传送门ServerTime Limit: 20000/10000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1540Accepted Submission(s): 256Problem DescriptionAlice and Bob are working on a new assignment. In this project, they nee...
2020-06-20 12:46:53
247
原创 HDU 6231 K-th Number （2017CCPC哈尔滨 B）离散化+二分
K-th NumberTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 3111Accepted Submission(s): 1126Problem DescriptionAlice are given an arrayA[1..N]withNnumbers.Now Alice want to build an...
2020-06-16 22:30:22
196
原创 Pangu and Stones HihoCoder - 1636 （ICPC 2017 北京 J） 区间dp
传送门：https://hihocoder.com/problemset/problem/1636题意：给你n(<=100)堆石子，再给你两个数L，R(2<=L<=R<=n)，表示你只能将连续的x(L<=x<=R)堆石子合并成为一堆，费用为这x堆石子的总数。求将这n堆石子合并成1堆的最小花费，如果不能合并成一堆输出0。思路：这题跟区间dp的入门很像，但是暴力枚举[i,k][k+1,j]区间的同时还要考虑两个子区间的石子数量，直接枚举的复杂度就成了O(n^5)，
2020-06-12 14:45:59
176
原创 Puzzle Game HihoCoder - 1634（ICPC 北京 2017 H ）最大子矩阵+思维
传送门：https://hihocoder.com/problemset/problem/1634题意：给你一个n*m(n,m<=150)的数字矩阵，每个元素val(-1000<=val<=1000)，以及一个数字p(-1000<=p<=1000)。你现在最多可以修改矩阵中的一个数字，改成p，求最大子矩阵的最小值思路：其实关键还是想到，对于某个点(i,j)，要么最大子矩阵（设值为ma）经过了这个点，要么没有经过这个点。如果没有经过这个点，我们只需要统计其上下左右四个部分
2020-06-12 14:28:50
219
原创 Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! F. Johnny and Megan’s Necklace（思维+欧拉回路）
F. Johnny and Megan's Necklacetime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputJohnny's younger sister Megan had a birthday recently. Her brother has bought her a box signed as "Your be
2020-06-10 17:40:15
427
原创 HDU 6224 （ICPC 沈阳 2017 H） Legends of the Three Kingdoms（记忆化搜索）
Legends of the Three KingdomsTime Limit: 8000/4000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 928Accepted Submission(s): 148Problem DescriptionIn the game of Three Kingdoms’ Legends, there are 4 players...
2020-06-08 22:06:29
468
原创 2014-2015 ACM-ICPC, Asia Xian Regional Contest Problem C. The Problem Needs 3D Arrays（网络流之最大密度子图）
题意：给你一个长度为n(<=100)的序列T，S为T的任意子序列，r(S)表示子序列S(不连续)中的逆序对数，l(S) 表示S的长度，求出 r(S) / l(S) 的最大值。思路：将r(S)看成边，l(S)看成点，问题转化为求 E / V 的最大值。经典的最大密度子图问题。利用类似0/1分数规划的思想，二分答案，设为mid，则有E /V=mid 即E=V*mid。即使E-V*mid趋近于0。问题再转化为求最大权闭合图。最大权闭合图参考：https://blog.csdn.ne.
2020-06-06 22:06:58
250
原创 2014-2015 ACM-ICPC, Asia Xian Regional Contest Problem H. The Problem to Make You Happy（博弈，记忆化搜索）
题意：给你n(<=100)个点m(<=n*(n-1))条边的有向简单图，Alice和Bob（两个人都足够聪明）在这个图上玩游戏，两个人轮流沿着有向图走，一次只能走一条边，Bob先走，如果Alice和Bob走到同一个点，或者Bob无法走了，则Bob输，否则Bob赢（Alice永远追不上Bob或者Alice无路可走）。如果Bob能赢输出Yes，否则输出No。思路：考虑记忆化搜索。但是由于图并不是DAG，我们只能倒着从已知的状态往前推，从而找出所有的Bob的必败态。dp[i][j][k
2020-06-06 18:33:16
225
原创 Educational Codeforces Round 88 (Rated for Div. 2) E. Modular Stability（组合数模板）
E. Modular Stabilitytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWe definexmodyxmodyas the remainder of division ofxxbyyy(%%operator in C++ or Java,modoperator in Pascal)....
2020-05-29 13:56:41
349
原创 牛客练习赛63 F 牛牛的树行棋 （SG函数+树差分）
链接：https://ac.nowcoder.com/acm/contest/5531/F来源：牛客网牛牛的树行棋时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld题目描述牛牛和牛妹是一对好朋友，这天他们俩决定在树上玩一个游戏。游戏的名字是“树行棋”，规则如下：给定一个含有n个节点分别从1到n编号且以节点1为根的树，一开始每个节点各有1个棋子。牛牛和牛妹轮流进行操作，且牛..
2020-05-09 17:02:22
423
原创 Codeforces Round #638 (Div. 2) F. Phoenix and Memory（贪心+线段树）
F. Phoenix and Memorytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPhoenix is trying to take a photo of hisnnfriends with labels1,2,…,n1,2,…,nwho are lined up in a row in a speci...
2020-05-08 18:41:09
309
转载 C++ bitset用法小结
C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。常用函数： bitset<8> foo ("10011011"); cout << foo.count() << endl; //5 （count函数用来求bitset中1的位数，foo中共有５个１ cout &l...
2020-05-05 22:29:48
495
原创 Wannafly挑战赛19-C-多彩的树（状压+容斥）
链接：https://www.nowcoder.com/acm/contest/131/C来源：牛客网多彩的树时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述有一棵树包含 N 个节点，节点编号从 1 到 N。节点总共有 K 种颜色，颜色编号从 1 到 K。第 i 个节点的颜...
2020-05-05 22:22:48
409
原创 2020年4月26日训练日记
01bfs可以O(V+E)求解边权全为1的图上最短路。而当边权只有0或1时，使用其它最短路算法是有些浪费的，此时可以使用bfs的变种：0-1 bfs来快速求解，复杂度仍为O(V+E).01bfs维护一个双端队列，当边权为0时，使用push_front，当边权为1时，使用push_back.资料摘自:https://blog.csdn.net/m0_37809890/article/de...
2020-04-26 17:54:54
216
原创 Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! D. Nastya and Scoreboard（贪心+dp）
D. Nastya and Scoreboardtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDenis, who managed to buy flowers and sweets (you will le...
2020-04-24 16:29:51
382
原创 Codeforces Round #635 (Div. 2) C - Linova and Kingdom（树形dp+思维）
Linova and Kingdomtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputWriting light novels is the most important thing in Linova's l...
2020-04-18 12:54:34
238
原创 Educational Codeforces Round 85 (Rated for Div. 2)E. Divisor Paths（数论，思维）
E. Divisor Pathstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a positive integerDD. Let's build the following g...
2020-04-16 22:13:27
230
原创 Codeforces Round #633 (Div. 2) E. Perfect Triples （打表找规律）
E. Perfect Triplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputConsider the infinite sequencessof positive integers, create...
2020-04-15 14:58:28
459
原创 Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov! D. Dreamoon Likes Sequences（打表找规律）
D. Dreamoon Likes Sequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDreamoon likes sequences very much. So he created a pr...
2020-04-05 21:14:18
451
原创 Codeforces Round #629 (Div. 3) E. Tree Queries（LCA+思维）
E. Tree Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a rooted tree consisting ofnnvertices numbered fr...
2020-04-04 21:25:21
563
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人