1 AndrewMe8211

尚未进行身份认证

no more threads

等级
TA的排名 3w+

NOIP2018 道路铺设

analysysDP设f[i]f[i]f[i]为填满1~i需要的天数则当d[i]<d[i−1]时,f[i]=f[i−1]当d[i]>d[i−1]时,f[i]=f[i−1]+d[i]−d[i−1]当d[i]<d[i-1]时,f[i]=f[i-1]\\当d[i]>d[i-1]时,f[i]=f[i-1]+d[i]-d[i-1]当d[i]<d[i−1]时,f[i]=...

2019-10-30 16:27:29

luogu P3393 逃离僵尸岛

analysis关键是解决这个问题:给你几个点,其他的点离这些给出的点的最近距离是多少这个很简单:我们可以自己给出一个点,然后向每个被标记的点连一条单向边,这样就只需要进行一次 dijkstra 就可以了。code#include<bits/stdc++.h>using namespace std;#define loop(i,start,end) for(regis...

2019-10-10 18:38:41

luogu P2827 [NOIP 2016] 蚯蚓

analysis这题的关键妙处在单调性三个字上能够O1处理出单调性,我们就不需要用nlogn的优先队列等来维护这个单调性了能够处理出单调性,我们就能够O(1)的找出最长的那个蚯蚓从而快速的模拟了但为什么有单调性呢?(我太懒了,借用wqu大佬的ppt一用)code#include<bits/stdc++.h>using namespace std;#define l...

2019-10-07 21:33:44

luogu P4363 [九省联考2018]一双木棋chess

analysis这是一道很好的状压dp这个题首先需要分析出任何一个合法的状态都可以化为从左下角到右上角的一条对角线这样一来状态就很好表示了:我们考虑设f[s]表示从状态s出发,最后先手减后手的得分。对于转移,我们考虑枚举哪些位置可以落子,假设落子后能够到达的所有状态是t,那么f[s]=max(A[i][j]+f[t])(黑棋先)或f[s]=min(f[t]−B[i][j])(白棋先)...

2019-10-07 21:25:49

luogu P2824 [HEOI2016/TJOI2016]排序

analysis这题思路很巧妙啊关键点是能够想到对一个01序列的排序可以用log级别的线段树来操作想到这点后,我们可以二分q位置上的数字,将原序列大于等于这个值的数字都写成1,其他的写成0,然后用线段树模拟排序就行能够这样做的原因:假设我们二分的值是mid,这里的数字本来是x,那么当x>mid时,最后排序后的q处的数就等于1,反之等于0实现的时候注意初始化和lazy函数的初值#...

2019-10-07 21:07:07

set,multiset用法总结

c++语言中,multiset是set库中一个非常有用的类型,它可以看成一个序列,插入一个数,删除一个数都能够在O(logn)的时间内完成,而且他能时刻保证序列中的数是有序的,而且序列中可以存在重复的数。简单应用:通过一个程序来看如何使用multiset: #include <string> #include <iostream> #includ...

2019-09-27 18:46:02

POJ 1821 Fence

analysis先把工匠按照s排序,然后DP方程:设f[i][j]为前i个工匠刷前j块木板的最大收益:f[i][j]=max{f[i−1][j]f[i][j−1]f[i−1][k]+p[i]×(j−k),k∈[s[i]−l[i],s[i]−1],j∈[s[i],n],j−k<=Lf[i][j]=max\begin{cases}f[i-1][j]\\f[i][j-1]\\f[i-...

2019-09-27 08:44:53

单调队列-从入门到入门到无边界递归入门

前置博客解决的问题静态区间最值模版class dandiaoqueue{ public: struct node{ int pos; int w; }; node que[maxn]; int l,r; void init(){clean(que,0);l=1;r=0;} void push_back(int pos,int w){ qu...

2019-09-25 21:42:33

luogu P1440 求m区间内的最小值

analysis单调队列code#include<bits/stdc++.h>using namespace std;#define loop(i,start,end) for(register int i=start;i<=end;++i)#define clean(arry,num) memset(arry,num,sizeof(arry))#define a...

2019-09-25 21:32:47

acwing135. 最大子序和

analysis单调队列code#include<bits/stdc++.h>using namespace std;#define loop(i,start,end) for(register int i=start;i<=end;++i)#define clean(arry,num) memset(arry,num,sizeof(arry))#define a...

2019-09-25 20:54:51

「雅礼集训 2018 Day10」贪玩蓝月

大渣好,我四渣渣辉,点一下,玩一年,装备不花一分钱,说话战斗,罩杯回收,找一基友,极限到手。0 元 VIP,3 天满级,一秒一刀 999,装备全爆 666,广告做得再牛,不如进服遛一遛!古天乐绿了,古天乐绿了,惊喜不断,月入上万!不花钱还赚钱的绿色游戏,等级能提现,装备换点钱!《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备,每件装备有一个特征值w和一个战斗力v 。在每种...

2019-09-25 17:01:57

luogu P4316 绿豆蛙的归宿

analysisE=∑A∈S∏j∈APj×∑k∈AWkE=\sum_{A\in S}\prod _{j\in A}P_j\times\sum_{k \in A}W_kE=A∈S∑​j∈A∏​Pj​×k∈A∑​Wk​(S为所有1到n路径方案的集合,A为一种方案包含的边的集合,Pi为走过i边的概率)(S为所有1到n路径方案的集合,A为一种方案包含的边的集合,P_i为走过i边的概率)(S为所有1到...

2019-09-24 19:31:17

luoguP1850 NOIP2016 换教室

analysis这题如果往DP方向去想的话应该还是比较好想的f[i][j][0..1]f[i][j][0..1]f[i][j][0..1]为前i间教室,用了j个机会申请,当前教室申不申请(0\1)至于第三维的必要性,可以这样理解:当前的决策为第i间教室是否申请,如果不用第3维,那么就不能够体现此决策,也无法转移于是DP方程为:f[i][j][0]=min(f[i−1][j][1]+...

2019-09-24 16:37:36

「雅礼集训 2018 Day10」足球大战

题面有一场足球比赛,还有nnn秒就要结束了,比分还是0:00:00:0。主队每秒进球概率为ppp,客队每秒进球概率为qqq,求主队获胜概率。注意,一秒钟一个队最多进一个球,主队获胜当且仅当主队进球比客队多。为了避免精度误差,把最后的答案化成最简分数xy\frac{x}{y}yx​,输出xxx和yyy关于(109+7)(10^9+7)(109+7)的逆元的乘积即可。根据费马小定理xy&n...

2019-09-23 14:36:16

noip模拟 矩阵加速递推 数学老师的报复

analysis很容易写出如下矩阵关系(f[n−1]f[n−2])×(A1B0)=(f[n]f[n−1])\begin{pmatrix}f[n-1] & f[n-2]\\\end{pmatrix}\times\begin{pmatrix}A & 1\\B & 0\\\end{pmatrix}=\begin{pmatrix}f[n] & f[...

2019-09-22 17:36:49

矩阵加速递推式递推

前提矩阵乘法板子struct martix{ ll m[10][10]; void init(){clean(m,0);}};inline martix mutiply(martix input1,martix input2,int a,int b,int c){ martix output; output.init(); loop(i,1,a){ loop(j,1,b){...

2019-09-21 21:30:28

luogu P3199 [HNOI2009]最小圈

analysis首先要理解题目中的那个"圈"的含义这个圈不是强连通分量!这就说明这个题和scc或tarjan没什么关系因为他说的是:c=(c1,c2,⋯ ,ck)(ci∈V)c=(c_1,c_2,\cdots,c_k)(c_i\in V)c=(c1​,c2​,⋯,ck​)(ci​∈V)是GGG中的一个圈当且仅当(ci,ci+1)(1≤i<k)(c_...

2019-09-14 15:47:33

算法竞赛之各种数据结构调试经验(坑点)贴

前言我不想调试!!!就是这样,本文诞生了线段树update函数没有在update函数里面pushdown和pushupupdate的时候lazy标记是累加的而非赋值:void update(int l,int r,int nl,int nr,int rt,ll w){ if(l<=nl&&nr<=r){ lazy[rt]+=w;//不能写成laz...

2019-09-14 10:21:01

luogu P4943 密室

analysis首先简化问题,即哈利和罗恩是等价的,也就是说罗恩能走的地方哈利都能够走(可怜的韦斯莱),所以我们可以只考虑哈利对于哈利(哈利+罗恩)最后完成任务的方式,可能有以下三种情况:从1到达第一个房间+从1到达第二个房间从1到达第一个房间然后到达第二个房间从1到达第二个房间后到达第一个房间我们只需要把这些方案的最短路算出来做一个比较就可以了但是注意第一种情况中...

2019-09-14 09:22:38

luogu P4377 [USACO18OPEN]Talent Show

analysis题目有两个条件:总重量至少为W总才艺值与总重量的比值最大由于出现了比值,这个题一定是01分数规划了那么这个比值可以表示为∑i=1nCi×xiWi×xi\sum_{i=1}^{n}\frac{C_i\times x_i}{W_i\times x_i}i=1∑n​Wi​×xi​Ci​×xi​​且∑i=1nWi>=W且\sum_{i=1}^{n}W...

2019-09-08 15:44:09

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。