应该又是一个模拟...模拟此生之敌. 首先考虑一个方向和不同速度的情况叭? 很容易想到,假如方向从右到左,那么我们按从左到右输入,考虑相邻两个,假如我右边那个速度小于左边那个,肯定是追不上的啦(这辈子都不可能追上). 从此我们可以得出,它们前面那些炸弹共存的条件就是速度递减,那么我假如突然来了一个速度大于它的咋办!肯定是把那个最前面那个速度最小的炸弹堆掉,一个方向的话,单调栈就可以做啦~ 那么现在考虑两个方向,其实也差不多的.我们还是按从左往右考虑,方向为负我们用单调栈,方向为正我们用单调队列叭!队列嘛!肯定是单调递减的(对头到队尾),因为前面速度假如比我的大那我不是g了. 假设我现在在i的位...

根号分治. 对于队列里面没有满sqrt(n∗m∗h){sqrt(n*m*h)}sqrt(n∗m∗h)的直接对于每个查询进行暴力. 对于满了的,对队列所有的元素做一次bfs{bfs}bfs,bfs{bfs}bfs复杂度是n∗m∗h{n*m*h}n∗m∗h. 然后清空队列即可. 总复杂度为nsqrt(n)nsqrt(n)nsqrt(n). code: using namespace std; typedef long long ll; const int N=5e5+5; //根号分治. int n,m,h,q; int dis[N]; int dx[6]={1,0,0,-1,0,0}; int...

求助...不知道dp状态设计错了还是贪心设计的有问题. fu,0/1f_{u,0/1}fu,0/1​到了u这个节点删不删和它父亲相连的边 使得度数都<=k 最少删除多少边. 然后抛出子节点状态更新父亲节点状态. 对于fu,0f_{u,0}fu,0​来说它必须删除子节点个数−(k−1){-(k-1)}−(k−1),对于fu,1f_{u,1}fu,1​来说它必须删除子节点个数−(k){-(k)}−(k). 对于更新可以使用贪心策略,不选fv,0f_{v,0}fv,0​就要选fv,1f_{v,1}fv,1​,假如我fv,1f_{v,1}fv,1​<fv,0f_{v,0}fv,0​,那么我...

<发现自己写代码的能力好垃圾...也可能是饿的> 一下午在debug...跟昨天一样,自己写了份动态开点的代码,然后最后告诉自己清醒一点清楚每个变量要干什么终于解决了.QWQ code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e6+5; const int mod=1e9+7; //区间修改 维护区间最值. struct Seg{ int mx[N],lz[N],lc[N],rc[N],id=1; void me() { for(int...

问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环 首先对于最大值最小可以考虑二分,至于ckckck的话,我们对于边的权值小于二分值uuu的都可以缩成w>uw>uw>u上的一点,这是显然的,然后呢,只要从小到大连接/从大到小连接即可.检测有没有环只要判断边权>www的是否能被DAGDAGDAG图遍历到即可. code: https://codeforces.com/contest/1100/submission/151...

好菜 做了一下午签了个到 A: 可以发现n/i值是一样的数成等差数列,所以对于大数据暴力分治就好了,小数据用rmq查询. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51451018 I: 同样也可以发现i,i+k这种是位于同一组的,那么我们只要把他们划分成一组.然后进行dp,因为不一定是偶数,奇数贪心有点难,所以考虑dp,fi j表示第i个选没选. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51420990 E: 原来后...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; const int M=25; const int mod=1e9+7; int fx[N][M],fi[N][M]; int a[N],b[N]; int n,k; int p[M]; int lg[N]; void STx() { for(int i=1; i<=n; i++) fx[i][0]=a[i]; for(int j=1; p[j]<=n; j++) { ...

换根dp{dp}dp. 首先我们假如知道子树相连点的答案,我们肯定优先选择最大的. dpdpdp方程为:fu=max(fu,fv+i/wu+1).f_u=max(f_u,f_v+i/w_u+1).fu​=max(fu​,fv​+i/wu​+1). iii表示第i大的fvf_vfv​. 通过树形dpdpdp转移后.那么紧接着就是换根dpdpdp了,考虑如何通过父亲节点得到子节点的答案,可以通过前后缀的形式,我通过把父亲节点的所有子节点做个前缀和后缀,然后转移得到在这个节点当根节点时候,父亲节点相邻对它的贡献gug_ugu​. 然后就解决了. code: #include <bits/std...

假如我知道这个值的第k小,那么它选择第k+1小是不是有n种选择. 所以就类似bfs,但是在bfs过程中会产生重复,什么重复呢,就是我现在是1搜3,搜出来是1+3,我现在是3搜1,搜出来是3+1,但是两者在题目中属于同一种含义. 所以我们简单的去重一下,就像定义两个for都从1开始循环,我们只要把两个for第一个for定义从1开始循环,第二个for定义从i开始循环,就不重不漏的记录了,同时用n个单调队列就可以O(N∗K){O(N*K)}O(N∗K)解决了. #include <bits/stdc++.h> using namespace std; typedef long long ...

提供一个保证正确但是有点麻烦的写法. 因为障碍物就2500个,你假如矩阵大小n,m都大于2500,那么你只要没有把开头的2500∗2500{2500*2500}2500∗2500的矩阵围住且结尾的2500∗2500{2500*2500}2500∗2500的围住就是YES. 假如n,m都小于2500,直接暴力判断可以到达即可. 假如n,m有一个大于2500,另外一个小于,那么只要判断小的那部分是否存在一堵墙,dp也能解决. 代码: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50136840

枚举枚举枚举:简单的来说就是枚举第一个1出现在哪个位子,其他位子的1就是在一个特定的区间,特定区间取min,然后用rmq维护查询.O(n2)O(n^2)O(n2)解决. code: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49457505 还可以dp枚举: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49460454

按每个点有没有超过条边分为重点和轻点.令超过的为重点,没超过的为轻点. 设数组表示这个点最后成为冠军的时间,初始值为表示还不是冠军. 令数组表示重点附近轻点的最大权值是多少. 令数组为答案数组,用于最后输出. 令数组为下标为多少的为第几个大点,用来缩小空间. 令该点包含的大点下标. 令为小点存在大点的最大值. 对于一次点的修改它分为修改轻点和修改重点.假如修改轻点,它会对附近的点造成影响,直接访问与它相连的点即可.因为一定不超过条边嘛.但是如果修改重点的话,因为重点相连的点实在是太多了,因此我们可以直接访问和重点相邻的重点,但是对于和重点相邻的轻点,因为修改的权值不会超过.我们可以通过数值暴力...

等我见完女朋友就把多校所有的数据结构题 dp题都写了...我真的好浮躁啊差不多两个月没学习了...QAQ小伤感QWQ有一起的也行诶？反正我博客不可能有人看的叭123456！！！

= =两个月不学习的fw这两个月来写的第一个题..简单的来说就是树状数组硬搞...首先在假如温度区间不在这个范围的点,先做个标记,就不用往上跳,且下面的点也一定不行..然后就简单的倍增因为符合单调性就跳,跳到最高点然后判断子树中合法的.简单的说就是在这个温度区间的,然后因为不涉及修改操作,可以树状数组离线按权值排序,左右端点的权值先分开再整合..然后离散化一下dfs序一下就可以通过这个题目了.\ code: #include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=20; vector<int>G...