3 LSD20164388

尚未进行身份认证

我要认证

如果你过几天就忘了,那么你并没有真正的掌握。

等级
TA的排名 9k+

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

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

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

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

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

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

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

2020年6月24日训练总结(codeforces辛路历程)

5月底研究生复试完以后,终于可以专心备战ACM了。这一个月,也确实让我有了不小的收获。1、绝大部分题目的知识点还是常用的那些,只是因为思维能力没跟上,才没做出来。所以多做一些高难度(特别是考思维能力)的题目,是可以收获很多东西的,这些题目要细品,仔细思考每一步是如何想到的,是否可以用在其他的地方。2、不要把问题想太复杂了,题目往往并没有我们想象的那么难(当然一些毒瘤题除外)。题目中给的每个条件都暗藏玄机,其中某个数据的范围可能就是你解题的突破口。3、对于一些你不会但是很多人过(并且通过率比较高)

2020-06-24 13:16:29

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

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

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

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

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

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

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

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

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

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

牛客练习赛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

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

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。