1 qq_47188574

尚未进行身份认证

我要认证

……

等级
TA的排名 42w+

树状数组

树状数组可以在O(logn)的时间复杂度内求出前缀和||插入一个数树状数组的三种基本模板区间查询+单点修改 将a[i]最为树状数组中的每个元素题目链接#include<iostream>#include<cstdio>using namespace std;int n,m;const int N=1000010;int tr[N];int lowbit(int x){ return x&-x;}void add(int x,int v

2020-08-30 17:03:09

贪心训练日记

1.陶陶摘苹果luoguP1478贪心贪心假设:在所有可以摘到的苹果中,优先选择需要力气小的苹果。贪心证明:因为要求的是共能摘多少个苹果,所以我们可以将每个苹果的价值都视为1。那么无论是摘比较费劲的苹果还是比较省力的苹果所得到的价值都是一样的。但如果摘比较省力的苹果,就可以留下更多的力气去摘其他的苹果。#include<iostream>#include<algorithm>using namespace std;const int N=5100;int n;int

2020-08-24 15:46:52

动态规划训练日记

1.洛谷P1244青蛙过河

2020-08-22 20:42:06

noip中的那些鲜为人知的“常识“

在看题解时,我们经常会看到这样一句话:大家应该都知道……,众所周知……,但对于我这种蒟蒻,大佬眼们中的常识,到我这里仿佛比高级算法还难,大多都是听都没听过。所以,本蒟蒻决定总结一下那些鲜为人知的"常识",让自己不断变强。持续更新1.两个数的积=它们的最大公约数和最小公倍数的积。2.一个序列最少可以用多少个下降子序列拼出来=这个序列最长上升子序列的长度3.八数码问题中如果逆序对的数量是奇数,那么一定无解。所有的奇数码问题中,如果逆序对的数量时奇数,那么一定无解。4.偶数码问题中,如果空格到当前目

2020-08-21 18:03:54

DFS训练日记

洛谷P1019

2020-08-20 15:46:31

lgP1146 硬币反转

一道经典的规律题:仔细想一次反转n-1个数,和一次反转一个数实际上时等价的。#include<iostream>using namespace std;int n;const int MAX=110;bool vt[MAX];int a[MAX];int main(){ cin>>n; cout<<n<<endl; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ i

2020-08-16 15:32:57

BFS之flood_fill模型

xa1249:Lake Counting#include<cstdio>#include<iostream>using namespace std;typedef pair<int ,int > PII;int n,m;const int MAX=210;char g[MAX][MAX];PII q[MAX*MAX];int mx[8]={-1,-1,-1,0,0,1,1,1};int my[8]={-1,0,1,-1,1,-1,0,1};voi

2020-08-05 17:37:06

动态规划之最长上升子序列模型

## LIS问题及其应用模板#include<iostream>#include<algorithm>using namespace std;int n;const int MAX=1010;int a[MAX];int dp[MAX]; int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++){ ...

2020-07-27 19:57:18

动态规划之数字三角形模型

模板#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int MAX=1010;int a[MAX][MAX];int n;int main(){ cin>>n; for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) cin>>a[i][j]; for (int

2020-07-24 17:00:02

进阶指南IncDec Sequence

一道典型的差分+贪心首先我们来了解一下差分的原理差分是前缀和的逆运算,差分数组往往是这样定义的:b[i]=b[i]-b[i-1]b[1]=a[1];根据这个定义我们可以看出,如果b[i]=b[i-1]那么差分序列的值就会是0.有因为b[1]=a[1].所以如果从2到末尾的差分序列的值都为0,那么序列中的所有数就都一样了。题目中的把所有数都变成一样就变为了,把从0到末尾的差分序列全部变成0.既然如此,我们如何求得最少的操作次数呢?我们可以以0为分界线,把整个差分序列分成正负两种情况(因为值为.

2020-07-23 12:12:08

激光炸弹

这个题我本来写对了,但是提交后就是有一个case点过不了,看了别人的代码,才知道要注意这样几个细节。1.同一个坐标上可能会有两个目标,所以在处理读入的时候要写+=2.如果给定坐标中的最大值<爆炸范围r,那么最后更新ans的循环就不会进行,从而输出0.所以,坐标的范围最少也应该是r。3.(这一点我注意到了),因为在递推区间和的时候需要-1操作,而本题中的坐标又是从0开始的。所以应该把所有的坐标都在读入时+1,防止数组越界。接下来是思路分析:在一个2维的坐标系中,求一个2维区间的和,很轻易便能想

2020-07-22 15:44:36

进阶指南004

看到数据范围就知道,这道题肯定是状压dp(纯暴力做法肯定会超时)设状态dp[i][j] i表示当前走过的点的集合, j表示当前停在了哪个点?这个状态该如何转移呢?显然:可以用floyed得算法思路,不断枚举中间界限来尝试松弛操作。但需要注意的是:** 集合i中必须要包含k 否则该状态就是不合法的(因为如果当前在的点是k点,那么我就肯定走过k点)**按照刚才的思路,如果i中不包含j,那么该状态也是不合法的。即:12if (i>>j&1)continue;这里着重解释.

2020-07-22 11:45:40

进阶指南003

64位整数乘法 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2020072211290487.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3MTg4NTc0,size_16,color_FFFFFF,t_70)本题位快速幂思想的一个简单应用:简单来说就是,既然我们可以用快速幂...

2020-07-22 11:33:36

进阶指南002

因为不是中文题,这里给出大致题意。输入一个数T表示有T组测试数据,每组测试数据中先输入一个数mod表示用来取模的数。再输入一个数n表示接下来会后n组数。接下来输入n个a和b,表示a的b次幂。对于每组测试数据,输出这n个a的b次幂之和%mod的值。仍然是一道快速幂的题目。注意数据要开long long 还有答案res再每次循环中都要恢复成0#include<cstdio>#include<iostream>typedef long long ll;using name..

2020-07-21 18:01:59

进阶指南001

进阶指南刷题日志,这里的进阶指南题目是从牛客网上刷的。本人也是一个菜鸡,如果有错误的欢迎指出。这是一道十分裸的题目,第一眼就应该能看出这道题考察的时快速幂。快速幂的原理就不赘述了。这里给出...

2020-07-21 17:53:32

markdown使用手册

markdown编辑器使用手册欢迎使用Markdown编辑器你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:全新的界面设计 ,将会带来全新的写作体验;在创作中心设置你喜爱的代码高亮样式,Markdown 将代码片显示选择的高

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