2 Andres_Lionel

尚未进行身份认证

谁无暴风劲雨时,守得云开见日明!

等级
TA的排名 2k+

Decay of Signals【2020 年 “游族杯” D题】【树形dp】

题目链接 这题有一个规律的东西,就是我们实际上只需要看1、2的链,譬如说有一个大于2权值为k的点,如果它的周围有权值为1的点的话,那么我们实际上没有必要去选上k,只需要选1即可,因为若是选上权值为k的话,,那么需要使得要取的值为1的点的个数为x的情况下:,又有,所以必须存在一条存在点度大于2的链,显然,这是不现实的,所以我们只需要考虑1、2两个点就是了,0的时候答案自然为“0/1”,若是没有1、2和0那肯定就是每个点“minn/1”就是了。 所以,关于2,还是要特殊的,需要保证的是,2的两边的x..

2020-05-29 16:17:00

[BOI2003]Gem 气垫车【贪心+DP】

题目链接 P4395 [BOI2003]Gem 气垫车 很容易让人往树上最大独立集的dp[maxN][2]这样的做法去想,但是实际上是有错的,很容易举反例。如果按照0、1分配最大独立集的做法去解决这个问题,很显然的就会变成偏大的结果17了,所以这里需要进行改善。按照这样的分配可以让他变成16:我们假设中间递增的点为1~x,再假设有如果存在则显然是有可能成立的。我们可以出于重心,根据点个数的贪心的方式来进行选择,...

2020-05-29 09:04:24

[USACO18FEB]Snow Boots G【set】

题目链接 P4269 [USACO18FEB]Snow Boots G 我们可以按照离线的方式,先进行离散化,然后再看当每个高度的最少需要的距离由此判断答案的可行性,于是可以用两个set(其中一个得是multi)来进行维护。 一个维护点坐标,这样当一个点插入的时候,就可以缩短两端的距离了。 另一个存储最远距离,存储答案。#include <iostream>#include <cstdio>#include <cmath>#include &...

2020-05-28 20:49:12

EOJ3745. 迷宫【二分答案+最大流】

题目链接 这里的点和边的个数都是比较小的,当然,不是说可以暴力了。可以用分层图的方式来解决这题,就是,我们给每个点每个时间对应的流,假设ans时间可以完成最大流,于是就可以利用最大流再加上每个点到下一个点的时间来进行计算了,如果最大流等于人数了,说明这个时间是可行时间,不然就是时间偏小了。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include.

2020-05-28 09:23:14

寒假作业【主席树】

题目链接 P2717 寒假作业 题目要求的是平均值不小于K的,那么可以将问题变成,对所有的都减去K,然后求“权值和大于等于0”的子串的个数有多少个? 于是,我们可以求,以每个点作为子串结尾的点时候的可能的子串的数量,这里就可以用前缀和来维护了,然后加上前缀和小于等于当前前缀和的点的个数,就是答案了。 用一个主席树维护一下即可。#include <iostream>#include <cstdio>#include <cmath>#includ...

2020-05-26 16:45:33

[AHOI2009]最小割【最小割+Tarjan】

题目链接 P4126 [AHOI2009]最小割 将题目拆解成两个问题,我们分别进行求解。 可以作为最小割的边 如果它可以是最小割中的边的话,首先它需要满足的是流过它的流是满流的,这是因为如果它被割去了,那么一定是满流的,否则一定不会是最小割中的一条边。 再者,虽然它是满流的,但是它可以被替换掉,怎么理解?就是它现在表面上是别割去了,但是实际上图中还有残余网络,可以代替这条被割去的边。给组合适的样例:6 6 1 61 2 12 3 22 4 23 5 14 5 ...

2020-05-26 15:52:16

骰子【概率dp】

题目链接 P1409 骰子 因为会有人被弹出队列,所以我设置的期望dp为,表示当现在队列中有i个人的时候,第j个人获胜的概率。 于是有当只剩一个人的时候,那个人必胜,。 再往下,先看它在队首的情况,也就是直接获胜的概率加上它被弹到队尾时候的概率。 其他的情况呢,也就是不在队首的时候呢,,表示的是如果第一个被弹出队列,或者第一个被弹到队尾时候,第j-1个获胜,也就是现在的j获胜,因为j的位置就变成了j-1。 于是,连立这两个方程组,可以得到的求解方式,因为这里i比较的不清晰,接下...

2020-05-26 10:22:20

[NOI Online #3 入门组 T3]买表【二进制优化dp背包】

题目链接 很可惜的一点就是,我正赛的时候好像把a和k看反了,于是一直想不到如何做,打了个暴力分,现在想想,暴力分也错了,因为a和k真的很关键,使得最后300变成200分,人生第一场OI就这样草草结束——或许这就是OI选手的刺激所在吧(得亏我不打正式赛 题目中的k指的是面额,而a指的是数量! 于是,我们可以用二进制优化的思想,将原来1000个的数量,优化到10个,于是复杂度就变成了这样的复杂度,能恰到好处的把题卡过去,是真的卡过去的。数据较强。#include <iostream...

2020-05-26 08:55:21

Boring Class 【HDU - 5324】【cdq套cdq+SPFA输出最长上升子序列】

题目链接 经典三维偏序,求这样的一个最长上升子序列:,,,其中,id这个很容易被忽略掉。 然后我们可以直接用外层cdq套内层cdq的方式去解决这个问题了。 第一维的x直接用sort排序,这里就不管了,接下去,第二维的y呢,我们用外层cdq去解决,因为要求一个上升子序列,所以可以先对左区间处理完,然后将左区间的贡献先给右区间,然后再处理右区间内的左区间,然后逐步这样往下即可。 关于输出答案,也就是要输出字典序最小的最长上升子序列,我们可以先得到每个点的当前值可以是由前面的哪个id转移过...

2020-05-25 11:19:13

Coronavirus Battle【CDQ套CDQ】【2020 年 “游族杯” 全国高校程序设计网络挑战赛 C】

题目链接 题意:给出N个三维坐标,输入按照题意的这个给出:ull CoronavirusBeats(){ ull k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 << 23; k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26); return k2 + k4;} 只有一个N,和K1和K2,然后N个三维坐标由该式子确定。 然后求一个最长上升子序列,使得且不能...

2020-05-24 21:18:02

Power Strings 【POJ - 2406】【KMP】

题目链接假设s可以由t重复k次拼成,即s=tttt……tt,我们称为s=t^k。先给定一个字符串s,求最大的n使得存在t满足s=t^n。 于是,我们可以先知道一个后缀,看看这个字符串是否可以由多个该字符串组成?于是后缀2=后缀1*2,后缀3 = 后缀2 + 后缀1 = 后缀1 * 3。 于是,我们可以利用KMP的next指针,如果现在从第N个向前跳,跳到ff点,那么说明ff + 1到N这段,肯定是和ff前面一段等长的相等,又因为KMP的next的连续传递性,说明ff-(N - ff)到f...

2020-05-23 11:15:43

Distinct Substrings 【SPOJ - DISUBSTR】【后缀数组求不同子串个数】

题目链接 求不同子串的个数。 于是,我们可以考虑成,一个后缀,和它前一个sa的后缀有多少个不重叠的前缀子串。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <limits>#include <vector&..

2020-05-23 09:47:52

Milk Patterns 【POJ - 3261】【后缀数组+RMQ求出现K次可重叠子串最长相同长度】

题目链接 求出现K次可重叠子串的最长相同长度。 于是,因为是可以重叠的,所以就可以利用后缀数组,查sa临近的每K个的最小height,然后不断更新答案即可。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <limits&..

2020-05-23 09:38:34

Musical Theme 【POJ - 1743】【后缀数组+二分答案】

题目链接有N(1<=N<=20000)个音符的序列来表示一首乐曲,每个音符都是1..88范围内的整数,现在要找一个重复的子串,它需要满足如下条件:1.长度至少为5个音符。 2.在乐曲中重复出现(就是出现过至少两次)。(可能经过转调,“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值) 3.重复出现的同一主题不能有公共部分。 既然可以同时减去或者加上一个数,那么其实就是换作算差值,使得差值是一个相同的子串就是可以的了。 于是,问题变成了求最长的两个相同且不重叠的子串...

2020-05-23 09:14:11

图的遍历【奇数环存在性】

题目链接 其实就是让我们找奇数环和联通块,如果存在一个奇数环的话,那么只需要把联通块连起来就可以了,如果不存在奇数环,除了把联通块连起来,还需要再多一条边来增添一个奇数环。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <.

2020-05-22 14:04:32

#529. 【美团杯2020】114514【贪心】

题目链接 题目给出的条件是给出一个长度不超过6e5的串,它一定是由n个“114514”组成的长度为6n的串。114514的顺序一定是按照这个顺序,但是排列可以是错综复杂的,但是保证一定有解。 一个“114514”中有两个‘4’,这是很关键的,我们可以把原式拆成11(4a)51(4b)这样的形式,4a指的是出现于前面的4,4b指的是出现于后面的4。于是我们想根据(4a)、(4b)确定这个串的组合。 如果我们确定了4a、4b,那么首先就可以确定5了,从后往前,第i个4a对应第i个4b对应第i个...

2020-05-21 23:27:55

Xcode中加入音频文件所需头文件

#import<AudioToolbox/AudioToolbox.h>但是如果直接输入这段却会发现找不到这个头文件,于是我们需要开发者选项了。首先创建工程,这都不用说的;然后选中中间图示的“build Phases”第五个按钮找到该选项选中AudioToolbox.framework,并add。最后别忘记添加头文件,然后就可以开始音频文件的操作了。...

2020-05-21 19:54:32

Xcode创建头文件

首先点击到工程文件上去:然后创建头文件:记住要把你需要用到的Target给点上。然后譬如对头文件定义一个这样的函数:现在返回到Target文件:就可以编译运行了。

2020-05-21 12:34:04

Xcode在同一个工程下创建多个可分别运行程序

这里主要用到的功能就是Target这个功能。首先,点到工程文件然后在该工程文件下:然后选择C/C++等等就可以做到同一个工程下分别运行了。只需要调整这个,然后点运行就可以了。

2020-05-21 12:25:56

#525. 【美团杯2020】平行四边形【原根】

题目链接 既然x和y都是排列的话,我们不妨让x先升序从1~n如此输出,这样只用管y了。如果在不要求退化平行四边形的时候,我们可以用1, n, 2, n-1, 3,……这样的不断的两边互取的方式来完成,但是本题却要求求一个同时还要不满足退化的平行四边形的。 于是这里引入了原根的思想,什么是原根,就是一个可以保证、、、……、他们(%p)之后,是1~p-1的排列,这p-1个元素互不相同,这题由于n+1是个质数,所以我们只需要对n+1取求一个原根就可以了。 快速求原根的方式:从2到p-1进行枚举,...

2020-05-19 23:06:43

查看更多

勋章 我的勋章
  • 领英
    领英
    绑定领英第三方账户获取
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)