6 夜雨声訉

尚未进行身份认证

暂无相关描述

等级
TA的排名 4w+

第四周总结

第四周已经过去了,这周看的动态规划感觉自己看的速度有点慢看到了状压dp,但是开了会之后更让我感觉到还是质量优先速度慢点就慢点。然后在做去年的网络赛的时候那道树形dp的题也是去看了一下别人的思路再结合板子套出来的(这个思路之前队友也想到过不过我们没有往更深的里面去思考)还是太弱了也,昨天晚上和队友又打了一把cf感觉还阔以(f没想到loyd除了能把所有有关系的点连起来之外还能判环)。...

2019-08-19 10:11:27

天才acm

给定一个整数MM,对于任意一个整数集合SS,定义“校验值”如下:从集合SS中取出MM对数(即2∗M2∗M个数,不能重复使用集合中的数,如果SS中的整数不够MM对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合SS的“校验值”。现在给定一个长度为NN的数列AA以及一个整数TT。我们要把AA分成若干段,使得每一段的“校验...

2019-08-18 15:25:04

8/17训练日记

今天做了几道题,有些小不顺那个树形dp的典题数组开小了就导致一直超时,然后做了一道比较明显的线性dp题。今天晚上的题可给我整坏了,先做D超时以为是算法有问题,就把sort去了循环跳二找数也去了,直接在输入的时候给他操作最后判断直接能否输出就行结果还超时,最后是卡的scanf,然后是B题看数据量不大直接暴力了这道题的坑还很多,先给你的是终止日期(注意是终止日期),然后给你需要的时间这时候就得往前推这...

2019-08-18 10:38:07

Codeforces 254C. Anagram

C.Anagramtimelimitpertest1secondmemorylimitpertest256megabytesinputinput.txtoutputoutput.txtStringxisananagramofstringy,ifwecanrearrangethelettersinstringxa...

2019-08-18 10:20:52

积累程度 poj3585

有一个树形的水系,由N-1条河道和N个交叉点组成。我们可以把交叉点看作树中的节点,编号为1~N,河道则看作树中的无向边。每条河道都有一个容量,连接x与y的河道的容量记为c(x,y)。河道中单位时间流过的水量不能超过河道的容量。有一个节点是整个水系的发源地,可以源源不断地流出水,我们称之为源点。除了源点之外,树中所有度数为1的节点都是入海口,可以吸收无限多...

2019-08-17 15:27:25

数论模板(转载)

https://blog.csdn.net/weixin_43238423/article/details/99685883这位同学总结得挺好的#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllmod=1000007;constllN=100010;llv[N],...

2019-08-17 09:25:22

8/16训练日记

今天看完了树形dp,其中二次扫描与换根法这两个是结合再一起用的首先任意定住一个节点扫描第一次求出以这个节点为根节点的最优值,然后通过这个根节点找到他的子节点和他的关系,然后通过第二遍扫描通过深度优先遍历和根子节点之间的关系就可以写出以任意一点为根节点的最优解然后遍历求解。(其实才发现自己进度慢的主要原因便是分神思绪总是乱跑,其实只要静下心来看什么都会比原来快很多)....

2019-08-17 08:52:49

有依赖的背包

题有NN个物品和一个容量是VV的背包。物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。如下图所示:如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。每件物品的编号是ii,体积是vivi,价值是wiwi,依赖的父节点编号是pipi。物品的下标范围是1…N1…N。求解将哪些物品装入背包,可使...

2019-08-16 19:31:04

选课

有依赖背包树形dp学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。例如《Windows程序设计》必须在选修了《Wi...

2019-08-16 16:48:52

codeforces 253D. Table with Letters - 2

题目D.TablewithLetters-2timelimitpertest2secondsmemorylimitpertest256megabytesinputinput.txtoutputoutput.txtVasyahasrecentlystartedtolearnEnglish.Nowheneedsto...

2019-08-16 10:55:35

8/15训练日记

今天看的区间dp和部分树形dp,树形dp给我的感觉就像是一个递归求子树的最优然后不断的返回给上一层,而在这之前重要的一步就是树的构建树的存储和这个题的做法有很大关系,树的存储确定了再去确定由子树推上一层的方程。在听讲课的时候看到了一道最长上升子序列的二分做法一开始看到的时候怎么也想不到这能和二分挂上钩,思路很巧妙但是只能求序列的长度。...

2019-08-16 09:27:20

没有上司的舞会 树形dp

Ural大学有N名职员,编号为1~N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数HiHi给出,其中1≤i≤N1≤i≤N。现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。输入格式第一行一个整数N。接...

2019-08-15 17:06:15

最长上升子序列 二分做法

给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数N。第二行包含N个整数,表示完整序列。输出格式输出一个整数,表示最大长度。数据范围1≤N≤10001≤N≤1000,−109≤数列中的数≤109−109≤数列中的数≤109输入样例:73121856输出样例:4二分做出的答案只有数量是最长上...

2019-08-15 16:22:52

8/14训练日记

今天看完的背包问题和多重背包的两种优化,看那个单调队列优化花了不少时间,思路已经看明白了,也可能还有些小细节被忽略了,现在也就只能先把知识看明白了解原理做些例题了。之后再找例题去把方法给应用起来。...

2019-08-15 09:03:28

单调队列优化多重背包

#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;intdp[1000];intmain(){intn,m,s,v,w;cin>>n>>m;...

2019-08-14 21:04:05

Codeforces 253c广搜

题目C.TextEditortimelimitpertest1secondmemorylimitpertest256megabytesinputinput.txtoutputoutput.txtVasyaispressingthekeysonthekeyboardreluctantly,squeezingouthis...

2019-08-14 09:47:04

8/13训练总结

今天看到的背包中多重背包的优化方法二进制优化和单调队列优化,单调队列优化还没太看明白还是一步步的推过去吧。今天晚上的题又跟特判干上了,一个训练赛的B本来只需要初始化为正无穷然后二分查找一下就行了不应该加特判的。然后是晚上div3的B特判完之后如果不符合的应该直接结束(因特判完没有跳出导致后续的代码进入死循环超时了)。明天看一下背包九讲。...

2019-08-14 09:01:47

codeforces 1200c

C.RoundCorridortimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAmugaeisinaverylargeroundcorridor.Thecorridorconsists...

2019-08-13 10:59:15

8/12训练总结

今天开始看的经典dp线性dp背包区间dp都是之前接触过的可以加速看过先多看看书巩固下知识然后再找题看,后面的各种优化还没有看到,在做最长公共上升子序列的时候也是了解到了,把三重循环变成了两重循环这很像背包把数组从二维换成一维数组,但是背包是该状态只由上个状态转移而来(即只与上一个状态有关),而这个是情况在不断地增多拿一个中间变量来记录这个符合情况的情况。...

2019-08-13 09:02:11

第三周总结

三个星期已经过去,基础也打了不少的时间了接下来就该开始多做题了后面的知识都不是只看看书做做板子题就能会的了。留下的时间不多了,23就要开始网络赛压力还是蛮大的,多打打cf上的比赛遇见难题不能再跳了,多看看书蓝书紫书对照着看这样虽然能更好地理解但也要加快阅读速度。平时里多做有用的题水题就算了要做那种一道顶好几道的那样做出来了才会有提升,给自己加压这样在比赛的时候才能拿下负担健步如飞。...

2019-08-12 08:32:12

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。