公告栏
CSP-J2022 T2 解密
在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?先放一段介绍:
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 ...
CF926C题解
本文同步发于洛谷博客,您也可以在题解页面访问。
这是一道很简单的模拟。
解题思路:我们定义两个变量 $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$ 开始循环 ...
CF620A题解
本文同步发于洛谷博客,您也可以在题解页面访问。
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_ ...
AT3935题解
本文同步发于洛谷博客,您也可以在题解页面访问。
回文数判断前面几位大佬已经讲的很清楚了,我讲一种新的 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
明白 ...
SP10228题解
本文同步发于洛谷博客,您也可以在题解页面访问。
因为题目输入格式,输出格式和数据范围没给全。所以我补充一下。
题目翻译输入格式第一行输入 $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$ ...
CF1591A题解
本文同步发于洛谷博客,您也可以在题解页面访问。
这题真还挺简单的(红题不都是吗?)
废话不多说!开始!(这也不废话吗)
理解题意题目描述
题中说得很清楚了
输入格式
本题有多组数据。首先,输入整数 $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$ 不变。
如果今天没浇花而且 ...
UVA1149题解
本文同步发于洛谷博客,您也可以在题解页面访问。
看一眼算法标签就知道了是贪心
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) ...
UVA483题解
本文同步发于洛谷博客,您也可以在题解页面访问。
题目传送门
水题
看不懂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原本的意思指读入一个字符,在这里可以把两个字符串之间的空 ...