1 Flyzz~

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 24w+

练习dsu on tree

题目注意点‘:1. 1~1e5每个数最多因子数不超过1002.dsu on tree标准步骤:1.找好重儿子2. dfs先处理轻儿子,在处理重儿子,保留重儿子的数据,在遍历轻儿子及后代得到相关信息。3. 如若当前点为轻儿子删除该点及后代的影响。#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;struct edge{ int to,next,w; edge(int to=0,int

2020-08-25 17:21:56

斜率dp入门

[HNOI]玩具装箱算是斜率dp的入门题吧,记录一下自己的学习心得。S[]处理前缀和,可得状态转移方程F[i]=F[j]+(S[i]−S[j]+i−j−1−L)2,0<=j<iF[i]=F[j]+(S[i]-S[j]+i-j-1-L)^2,0<=j<iF[i]=F[j]+(S[i]−S[j]+i−j−1−L)2,0<=j<i换元简化a=S[i]+i,b=S[j]+j+L+1a=S[i]+i,b=S[j]+j+L+1a=S[i]+i,b=S[j]+j+L+1 可得F[

2020-08-25 11:40:31

练习记录:可持久化权值线段树

链接通过可持久化建n棵权值线段树,因为最小未出现自然数一定小于数列长度所以权值线段树长度为2e5+1即可,储存每个数最后出现的位置,每次查询l,r,即查询第r棵线段树第一个出现位置小于l的数即可,为了查询还需要保存区间最小值,查询时最小值小于l就往哪边继续查。总结一下:1可持久化。2利用线段树可查询第一个权值小于k的数。#include<bits/stdc++.h>using namespace std;const int maxn=2e5+5;struct node{ i

2020-08-18 09:46:18

前缀函数学习

前缀函数在oi-wiki上学习了前缀函数,自己也总结一下。定义:pi[i]=max(j),s[0..j]=s[i−j+1,i]pi[i]=max(j),s[0..j]=s[i-j+1,i]pi[i]=max(j),s[0..j]=s[i−j+1,i]O(n)计算方法:#include<bits/stdc++.h>using namespace std;const int maxn=1e5;int p[maxn];char s[maxn];void getpi(int n){

2020-08-11 09:38:31

多项式算法学习记录

多项式单纯记录一下拉格朗日插值大佬博客链接f(k)=∑i=0nyi∏i≠jk−x[j]x[i]−x[j]f(k) = \sum_{i = 0}^{n} y_i \prod_{i \not = j} \frac{k - x[j]}{x[i] - x[j]}f(k)=i=0∑n​yi​i​=j∏​x[i]−x[j]k−x[j]​普通拉格朗日插值代码如下ll x[maxn],y[maxn];ll solve(int n,ll k){ ll ans=0; for(int

2020-07-23 20:30:10

练习纪录(网络流)

uva1658利用了分点法,如果直接跑流量为2最小费用流,有可能出现某个点出现两次,所以把2~v-1分为两个点中间连一条容量为1,费用为0的边,实操时可用2i,2i+1代替i点一个连入的边,一个连出的边。另外紫书上提示这是解决节点容量问题的通法,需要注意。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2000+7;const int inf=1e9;struct edge

2020-07-06 16:04:10

练习记录(网络流入门)

uva11082没有想法,看了紫书的解析。先把矩阵每一个元素-1,这样每个元素取值范围变为0~19,这样就允许了0流量的存在。把所有行的和x1,x2…xr,列的和y1,y2,…yc看为节点源点于所有行和节点相连,容量为x[i]-c;列和节点于汇点相连,容量为y[i]-r;每个x节点在与所有y节点相连,容量为19,跑最大流。则xi于yj边的流量变为 A[i][j]-1.可以这样理解每一行的和可以由不同列的元素构成,只要与源点和汇点相连的边都满载,即说明在满足行和列和一定的条件下有解。#include&lt

2020-07-05 21:05:48

练习记录(权值线段树or set)

牛客练习赛的一道题目 先想到一个思路,对于一个固定的左端点,右边第一个比他大的数下标为i,第二个为j,则右端点必然在[i,j-1]之间,同时对于每一个右端点满足要求的左端点也在一个区间中,还需要检查固定的左端点是否在该区间中。直接检查的话会超时,可以检索每个点为右端点,对应的区间中有多少成立的左端点转化为区间和问题,可用树状数组解决。而某个点A作为左端点成立时仅在右端点为[i,j-1]是成立,只需要在枚举到以i为右端点时将A激活(即树状数组add(A,1)),在枚举j时再消除他的影响即可。#includ

2020-07-01 20:31:19

暑期培训:数论总结

只是单纯记录一下结论1.裴蜀定理:对于给定的正整数a,b,方程ax+by=c有解的充要条件为c是gcd(a,b)的整数倍。定理的推广: 方程ax+by+cz+…+nm=f(其中a,b,c…n,f为整数)有解的充要条件是f为gcd(a,b,c,…,n)的整数倍。2.扩展欧几里得算法:可以求出两个整数x,y,使其满足ax+by=d,d为gcd(a,b).在此前提下使|x|+|y|最小,算法可以求出一组特解,通解为:x=x+k∗bdy=y−k∗ad x=x+k*\frac{b}{d}\qquad y=y-k

2020-06-21 22:35:39

练习记录uva1354

题目一道暴力搜索题目,第一个要点:枚举天平就相当枚举二叉树。另外要记录不同集合可以摆出的二叉树所有状态(偏左值,偏右值),再往上推。刚开始没做过多少暴力搜索题,以为像回溯法一样找到一棵二叉树统计宽度,在统计下一颗,貌似不太好办。考虑到数据不大,直接记录所有状态即可。#include<iostream>#include<cstdio>#include<algorithm>#include<set>#include<queue>#inc

2020-06-14 16:23:19

刷题记录(LA4850 贪心)

题目如果是问最大惩罚值的最小值的话,只需要按截止时间从小到大排一下序就可以了。但问的是最大两个惩罚值的最小值。有点没办法,一度以为有什么操作能直接优化两个数的和最小,好像不太行。在网上搜了题解看到一个思路。先按截止时间排序,在尝试把一个任务A调到任务B后这样A+1到B的惩罚值都得到优化而A的惩罚值提高,不过最大两值的和有可能减小。另外每次移动后A的惩罚值直接变得比原本A~B中最大的惩罚值还要大,因为交换后A的理想结束点最靠前,但完成点在区间终点。所以只会移动一次,要不然会造出两个比原来大的值。#incl

2020-06-09 20:43:07

练习记录la 4254

题目最大值的最小值,显然要二分答案,问题则转化为如何检验答案是否可行。可以发现每一个时刻优先处理结束时间最近的工作是最优的。利用这一点贪心,比较好的做法是从下到大检查时刻,每个时刻做结束时间离得最近的(利用优先队列),如过出现结束时间在检查的时刻之前则不可行。然而我没想到,这是做完后查博客看到的。此题我利用了线段树。由之前的贪心,可以先处理结束时间早的工件,且完成它的时间因尽量偏左(小),感觉比较麻烦,唉,还是要灵活思考问题。#include<iostream>#include<

2020-06-05 15:59:21

Numpy入门:数据存取与函数

Numpy数据存取与函数CSV文件存取利用Numpy库函数可以实现写入,导出CSV文件生成CSV文件:读入CSV文件:对于CSV文件,delimiter要指定为’,’.另外CSV文件只能有效储存一维或二维数组。示例import numpy as npa=np.arange(100).reshape(5,20)np.savetxt("a.csv",a,"%d",delimiter=',')生成如下文件:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,

2020-06-04 14:04:00

练习记录(单调队列优化dp)

uva上的题目#include<iostream>#include<cstdio>#include<algorithm>#include<set>#include<queue>#include<cstring>#include<string>#include<cmath>#include<vector>#include<stack>#include<map&gt

2020-06-03 11:04:59

Numpy库入门:数组

ndarray数组对象嵩天老师mooc文档链接: 链接提取码:zyknndarray为Numpy中的数组对象,在程序中的别名为array.ndarray数组创建 (1) 从Python中的列表,元组等类型创建ndarray数组,用dtype指定数据类型 import numpy as np x=np.array(list/tuple) x=np.array(list,dtype=np.float32)(2)利用Numpy中函数创建ndarray数组zeros,ones等函

2020-06-01 20:37:54

刷题记录(离线,树状数组)

题目看其他人的题解,不离线要用主席树(板子题),还有一个是莫队+值域分块(萌新暂时都不会,有空学一下,学期末作业太多了,哭)。离线做法:对a数组间接排序,b保存序号。 把询问储存下来,间接排序,按k从小到大处理,对于每一个k,暴力对小于等于它的值的pos(b中保存的位置)+1(有一些处理更小的k时加过,直接忽略),树状数组查询l~r的区间和即为对应询问的答案。#include<iostream>#include<cstdio>#include<algorithm&g

2020-05-22 22:40:48

练习记录(二分,尺取)

牛客每日一题上的题二分就没想到,也是题做得少,还幻想有什么妙法求第k大。二分答案后,要判断它是否为第m大,只需判断比它大的数超不超过m个,不超过还可更小,r=mid-1.超过则相反。判断方法:利用尺取法(假如统计区间中满足某种条件的数要超过k,则统计时r(右边界)随l(左边界)递增)那么第k大数大于x的区间一共有多少怎么求?第k大数大于x的其实也就是大于x的数至少有k个,当我们枚举区间左...

2020-05-03 22:44:33

线段树练习

题目大意:给出一个长度为n的序列a,支持如下两个操作1: 给[l,r]区间加上一个首项为val,公差为d的等差数列。2: 询问[l,r]区间的和。思路:利用线段树维护区间的首项(l处的值),公差。原题中还有一个取模:可能的模数m为25以内的素数,那么可以把所有数先对35。。1923取模,最后计算完再对m取模。维护线段树时需要pushdown()函数,如果不用则要像区间加固定数一样记录祖先...

2020-04-18 22:03:42

bitset的操作

bitset在bitset头文件中对于一个叫做a的bitset:a.size() 返回大小(位数)a.count() 返回1的个数a.any() 返回是否有1a.none() 返回是否没有1a.set() 全都变成1a.set§ 将第p+1位变成1a.set(p, x) 将第p+1位变成xa.reset() ...

2020-04-14 22:55:01

刷题记录(利用dfs序)

题目来源:牛客网shy有一颗树,树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的,当且仅当对于所有相同颜色的点对(x,y),x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。一看题两眼发懵,最终还是看题解了。利用dfs序来dp.先通过dfs确定dfs序(不用记录回溯),之后分析一下,再选dfs序中第i个时他要么新选一个颜色,要么和他父亲颜色相同,而因为是dfs序...

2020-04-08 22:18:18

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。