0f 的小站

在whk上咕咕的我终于回来了，这用的是数学方法。 Solution首先 $(p_i-1)(q_i-1)+1$ 什么也看不出来，先拆个括号，就会变成 $p_i·q_i-p_i-q_i+2$ 这个样子，已知 $p_i·q_i=n_i$ 且 $p_i·q_i-p_i-q_i+2=e_i·d_i$ ，就可以得出来两个东西 $p_i·q_i$ 和 $p_i+q_i$ 。 $p_i+q_i$ 过程： \begin{equation*} \begin{aligned} p_i·q_i-p_i-q_i+2 &= e_i·d_i \\ p_i+q_i &= -(e_i·d_i-p_i·q_i+2) \\ &= p_i·q_i-e_i·d_i-2 \\ &= n_i-e_i·d_i-2 \end{aligned} \end{equation*} 现在我们得知了 $p_i+q_i$ 和 $p_i·q_i$ ，怎么求出 $p_i,q_i$ 呢？ 对，就是课本上的完全平方公式，因为 $(p_i+q_i)^2-(p_i-q_i)^2=4p_i ...

本文原文链接为线段树入门，转载请注明原文连接并附此声明。 蒟蒻刚学完线段树不久，写一篇线段树入门笔记。 线段树是一种二叉搜索树，是 $OI$ 中很重要的数据结构。其支持单点修改，区间修改，单点查询，区间查询（最大最小值、求和）等操作。虽然比树状数组慢，但是它支持的操作更多。 线段树可以高效地解决具有区间性质的问题，例如区间求和，一次操作(修改，查询)就要遍历整个数组，单次操作时间复杂度 $O(n)$ ，$q$ 次修改复杂度 $O(nq)$ ，远远超时。而线段树单次修改时间复杂度 $O(\log n)$ ， $q$ 次修改复杂度 $O(q \log n)$ ，节约的不少时间。 线段树基本结构比如一个长度为 $5$ 的集合 ${8,3,11,4,13}$ ，要维护他它的区间总和，建造出的线段树如下图所示： 如图所示，线段树的性质如下： $1.$ 线段树的每一个节点都管理着一段区间，其值为这一区间内需要维护的值，根节点（编号为 $1$ ）管理着整段区间 $[1,n]$ ，叶子节点管理的区间长度为 $1$ 。 $2.$ 除叶子节点外，其他节点分别有两个子节点，如当前节点的编号为 $p$ ...

这篇文章之后会与后面的内容重新整合排版，本文将会改成索引页。 什么是Markdown?先放一段介绍： Markdown是一种轻量级标记语言，创始人为约翰·格鲁伯（英语：John Gruber）。 它允许人们使用易读易写的纯文本格式编写文档，然后转换成有效的XHTML（或者HTML）文档。这种语言吸收了很多在电子邮件中已有的纯文本标记的特性。由于Markdown的轻量化、易读易写特性，并且对于图片，图表、数学式都有支持，许多网站都广泛使用Markdown来撰写帮助文档或是用于论坛上发表消息。 如GitHub、Reddit、Diaspora、Stack Exchange、OpenStreetMap 、SourceForge、简书等，甚至还能被使用来撰写电子书。——百度百科 Let’s go! 换行Markdown不同于其他文本编辑器，Markdown一个换行实际为一个空格，Markdown只有两个及两个以上的换行符实际为一个换行。 示例：12this is line 1this is line 2显示： this is line 1 this is line 2 示例：123this ...

本文同步发于洛谷博客，您也可以在题解页面访问。 这是一道很简单的模拟。 解题思路：我们定义两个变量 $cnt1$ $cnt2$，分别用于记录上一个连续 $0/1$ 区间的长度和这一个连续 $0/1$ 区间的长度。只要这个连续区间的长度不等于上个区间的长度，那么直接输出NO，然后return 0就可以了(因为这里不一样后面就无需判断，这是一个小优化)。如果相等，那么 $cnt2$ 清零，重新计算新的连续区间的长度，以此类推计算就可以了。 那么这个过程怎么实现呢？ 对于代码实现来说，对于当前的 $a_i$ 来说，分两种情况： 如果 $ai$ 等于 $a{i-1}$ ，那么说明还在当前的区间中，那么 $cnt2+1$ ，长度加 $1$ 。 如果 $ai$ 不等于 $a{i-1}$ ，那么按照上面的思路判断就可以了。 这里需要注意一些细节：加一个特判，判断 $cnt1$ 是不是 $0$ ，并在cnt2=1前面把 $cnt1$ 修改为 $cnt2$ ，就可以了。然后把 $a_{n+1}$ 赋值为 $2$ ，循环到 $n+1$ 就可以处理最后一次的问题。 ps：一定要从 $2$ 开始循环 ...

本文同步发于洛谷博客，您也可以在题解页面访问。 update：有一个图挂了，我重新补上，管理求过 这道题不难，主要考察的是数学知识。 前铺：欧几里得距离首先我们都知道，两点之间线段最短，如下图所示： 这个距离很好求，我们把 $A$ 点和 $B$ 所在的轴画出来，如下图所示： 很容易看出来这三条线构成了一个直角三角形。根据勾股定理，我们就求出了距离公式，如下： \large{dis(i,j) = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}}这个距离公式也是现在最常用的距离公式。 切比雪夫距离切比雪夫距离用于解决格点上的距离问题。这类问题只能向自己点的上、下、左、右、左上、左下、右上、右下方向走。 在这个问题中，每走一个斜线和走一个直线的距离相同。那我们想要距离最短，那就按照欧几里得距离的思想，尽量先走斜线到对方的横坐标上，在走直线到达对方的点，如下图所示： 这就是当前问题下的最短距离。 那么怎么算出距离呢？ 因为棋盘的性质，走一个斜线等于走一个直线的距离，所以只需要求出两边距离的最大值就可以了。公式如下： \large{dis(i,j)=\max(|x_i-x_ ...

本文同步发于洛谷博客，您也可以在题解页面访问。 回文数判断前面几位大佬已经讲的很清楚了，我讲一种新的 STL 做法。 这里介绍两个函数，reverse()和to_string()。 to_string()函数to_string()是在 C++11 中新加入的函数，定义于<string>头文件中。用法为to_string(val)，其中val可以是int,long,long long,unsigned int,unsigned long long,fload,double,long double类型。其作用是将数字转换成字符串。 reverse()函数reverse()函数是一个可以翻转数组，string，vector等数据结构的函数，定义于<algorithm>头文件中。用法为reverse(p1,p2)，p1为前指针，p2为后指针。 123reverse(array,array+a_length) //数组reverse(str.begin(),str.end()) //stringreverse(v.begin(),v.end()) //vector 明白 ...

本文同步发于洛谷博客，您也可以在题解页面访问。 因为题目输入格式，输出格式和数据范围没给全。所以我补充一下。 题目翻译输入格式第一行输入 $T$ 表示有 $T$ 组数据。每组数据中第一行两个整数 $R,C$ ，接下来输入一个 $R$ 行 $C$ 列的网格 $S$ ，如果 $S_{i,j} < 0$ 表示恐龙，否则表示药水。 输出格式输出包含 $T$ 组数据，每组数据输出一个正整数，表示由单元格 $1,1$ 到单元格 $R,C$ 的最小力量值。 数据范围与约定$1 \leq T \leq 5$ $2 \leq R,C \leq 500$ $-10^3 \leq S_{i,j} \leq 10^3$ $S{1,1} = S{R,C} = 0$ 下面回归正轨 解题思路这道题是一道明显的 dp 题。 定义状态： $dp_{i,j}$ 表示从第 $i$ 行第 $j$ 列走到第 $R$ 行第 $C$ 列所需最小体力值。 初始状态： $dp{R,C} = 1$ ，因为 $S{R,C} = 0$ 且体力值必须为正数，所以最小值是 $1$ 。 最终解： $dp_{1,1}$ ，从第 $1$ ...

本文同步发于洛谷博客，您也可以在题解页面访问。 这题真还挺简单的(红题不都是吗？) 废话不多说！开始！(这也不废话吗) 理解题意题目描述 题中说得很清楚了 输入格式 本题有多组数据。首先，输入整数 $t$ ，表示数据组数 $t(1\le t\le100)$ ，对于每组数据，输入整数 $n$ ,表示一共浇花或没浇花的天数 $(1\leq n\leq100)$ ，然后输入 $n$ 个整数 $a_1,a_2,\dots a_n\ (a_i=0$ 或 $a_i=1)$ ， $a_i=1$ 表示第 $i$ 天浇花了，否则表示第 $i$ 天没浇花。 输出格式 对于每组数据，如果花活着，输出花 $n$ 天后的高度，如果花死了，输出 $-1$ 。 解法这道题我们用模拟的解法。用一变量 $h$ 表示花的高度, $a_1,a_2,\dots a_n$ 浇表示第几天浇花了没。一开始让 $h$ 为 $1$ ，从第 $1$ 天起每天都会有四种情况： 如果今天浇花而且昨天也浇花了， $h+5$ 。 如果今天浇花而且昨天没浇花， $h+1$ 。 如果今天没浇花而且昨天浇花了， $h$ 不变。 如果今天没浇花而且 ...

本文同步发于洛谷博客，您也可以在题解页面访问。 看一眼算法标签就知道了是贪心 ps:文章翻译有些错误 最后一行是包裹的容量 应该是 第二行是包裹的容量 解题思路 对物品数组按体积由大往小排序 用两个变量当前指针和后指针 如果第一个和最后一个能装到箱子里，计数器 $+1$ ，前指针向后挪一位，后指针向前挪一位。否则只能装大的，计数器 $+1$ ，并且前指针要向后挪一位。 重复循环直到前指针大于或等于后指针，输出结果。 流程图(自己做的，有点丑) 献上代码核心代码 12345678910111213141516171819202122232425cin>>n;memset(V,0,sizeof(V));p1=1,p2=n,cnt=0;初始化cin>>v;for(int i=1;i<=n;i++){ cin>>V[i];}数据输入sort(V+1,V+n+1,greater<int>()); 排序while(true){ 循环处理 if(p1==p2||p1>p2)
...

本文同步发于洛谷博客，您也可以在题解页面访问。 题目传送门 水题 看不懂stringstream，所以用了这种方法，【分析】可以直接用cin>>…读入。（cin遇到空格，回车，TAB停止读入 实现方法：看个例子： I love you.会读入I 和 love 和 you. 怎么实现？直接用1234string s;while(cin>>s){ /*语句段*/}它会一直读入数据，直到EOF（输入中止结束符） 百科 https://baike.baidu.com/item/EOF/1017800?fr=aladdin 模拟:（以I love you.为例： 首先读入I，遇到空格，执行语句段，然后读入love……最后读入you.遇到EOF，结束。 reverse(s.begin(),s.end());：reverse：定义在<algorithm>中，指将字符串、数组等反转，s.begin和s.end是两个广义指针，分别指向s的开头和末尾。 介绍一下getchar: getchar原本的意思指读入一个字符，在这里可以把两个字符串之间的空 ...