- 博客(18)
- 收藏
- 关注
RSS订阅
原创 洛谷P4513 【小白逛公园】解题报告
这道题难点在于如何在logn的范围内找到该区间最大值，我们不妨先分析最大值有哪几种情况。如图所示：可分为3种情况1.全部在中线左边。2.全部在中线右边。3.经过跨过中线。如果在二叉树上分析，全部在中线左边即为左儿子的最大值，全部在中线右边即为右儿子的最大值，跨国中线的情况需要分析左儿子包含右端点的最大值和右儿子包含左端点的最大值。如图所示：代码实现如下void update(...
2019-07-24 10:28:32
139
原创 扩展中国剩余定理
先简单介绍下线性同余方程 ax%n=b 其有解需满足(a,n)|b，令d=gcd(a,n) 设t为(a/d)x % (n/d) = (b/d)的唯一解，则ax%n=b的d个解为t,t+n/d,t+2n/d....t+(d-1)n/d。问题模型：给定模线性同余方程组 r[i]%a[i]=m (1<i<=n,r[i],a[i]均为正整数)，判断是否存在最小非负整数解，为一般方程不考虑中国...
2019-08-23 20:47:44
215
1
原创 强大的位运算
位运算让计算机的操作变得简单并且迅速，掌握位运算的常见用法可以迅速解决一些看似复杂的题目，理解位运算也能让我们更透彻的理解计算机。位运算符1.&，按位与，若相应二进制位均为1，则结果的此二进制位为1否则为0,简单来说就是如果有一个0就为0，两个1才为1与按位或相反。2.|，按位或，若相应二进制位只要有一位为1则为1，否则为0。3.^，按位异或，若相应二进制位相同为0，否则为1。4...
2019-08-23 19:08:55
517
原创 动态规划1P4170解题报告
先看题嘛：好像就是一道区间动规，而且数据范围也很小，那我们就直接进入动态规划的基本步骤吧。分析：既然是动规，好嘛我就记得状态和状态转移方程了，那怎么搞呢，想起学过递推的嘛，从小的推到大的，这道题也可以用的嘛，我们可以知道如果只有一个的话那肯定是涂一次的嘛，这样就可以把F[i][j]赋值成1；我们再来考虑，如果两头颜色一样即s[i]==s[j]我们只需要取F[i+1][j]和F[i][j-1...
2019-08-20 11:29:54
95
原创 关于图的遍历
图的遍历主要分为两种：一、深度优先搜索这个就跟字面意思一样，深搜嘛，从一个顶点开始，如果有和他相连的顶点就走，直到没有路可以走了就回溯，深搜的过程中应该注意走过的路就不要再走了。但是有些时候从一个顶点开始无法将整个图遍历...
2019-08-17 08:24:46
104
原创 扩展欧几里得求乘法逆元模板
若ax+by=1,gcd(a,b)=1；则a的逆元为x%b；#include<iostream>#include<cstdio>using namespace std;int l,m,n,s,p;void exgcd(int a,int b,int &x,int &y){ if (!b) { x=1; ...
2019-07-28 18:49:59
188
原创 P2054洗牌解题报告
题目描述为了表彰小联为Samuel星球的探险所做出的贡献，小联被邀请参加Samuel星球近距离载人探险活动。由于Samuel星球相当遥远，科学家们要在飞船中度过相当长的一段时间，小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后，大家觉得单纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。对于扑克牌的一次洗牌是这样定义的，将一叠N（N为偶数）张扑克牌平均分...
2019-07-28 18:02:13
144
原创 POJ1061青蛙的约会解题报告
分析：由题意易得出同余方程：x + km ≡ y + kn (mod L)；化解方程得：(n-m) * k ≡ x-y (mod L)；转化为一般方程得：(n-m)k + Ls = x-y；看成ax+by=c；要求ax + by = c的整数 x 解，首先，设d = gcd(a, b)，方程两边同时除以d得到a/d * x + b/d * y = c/d，由于a是整除d的，b也是...
2019-07-28 15:08:06
135
原创 洛谷P3372解题报告
题目描述如下：，可用单调栈或扫描线方法。首先我们尝试扫描线；核心代码如下for(int j=1;j<=m;j++) { scanf("%s",str); if(str[0]=='F')d[i][j]=d[i-1][j...
2019-07-18 08:45:52
101
原创 关于逆波兰表达式
后缀式，又称逆波兰表达式，其优点在于不用添加括号，而且计算机在识别时通常情况下都是识别后缀式，因此后缀式亦可加快编译速度。由中缀式（一般算式）转换为后缀式一般有三步。1.按照运算符优先级和左右对齐补充括号（一般只有"^"右对齐）。2.将运算符移到最近的又括号处并删除右括号。3.删除左括号。eg. a+b*c-d ——>（（a+(b*c) )-d ) ; ——>（（a...
2019-07-15 01:18:21
128
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人