Blog E

路漫漫其修远兮,吾将上下而求索。

和小哥哥一起刷洛谷(13)【未完】

一维dp

文前一唠:今天(4月18日)的洛谷日报是我的文章~(没有开玩笑,真的是我写的,不信你去看) dp是什么? dp就是一种将大问题拆分成数个子问题,用已知情况的最值,推出未知情况的最值的递推思想的算法,速度与爆搜相比,快到不知道哪里去(并非指数级增加),跟记忆化搜索的复杂度相比有时会相差一些常数。 动态规划常常适用于有重叠子问题和最优子结构性质的问题。本行改自维基百科 通常许多子问题完全相同,动态规划只会解决每个子问题一次然后用数组存储下来,从而减少计算量。这点与记忆化搜索有异曲同工之妙。 P1115 最大子段和 写\(dp\)时要考虑几个东西:状态(\(f[i]\)存什么...

和小哥哥一起刷洛谷(12)

记忆化搜索

其实记忆化搜索就相当于加了记录的深搜,代码实现与爆搜非常类似,故我经常先写深搜然后硬改成睿智搜索记忆化搜索。 接苹果 分析 这题显然可以非常轻松的写出爆搜代码,但由于这样将很多的情况重复计算了很多次,会超时,故我们可以将已经计算过的情况用数组存下来,即可更快地调用。典型的记忆化搜索/dp。 以上面的思路,我们可以先写出爆搜代码,然后稍加改动即可。 代码: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int NR=1005,MX...

在使用c++的宏时发生的灵异事件

define,还我“青春”!

在一道\(luogu\)题目里,我定义了一个取绝对值的宏: #define abs(x) (x>0?x:-x) 而调用这个宏的代码大概是这样滴: if(abs(arr[i]-ans[x-1])<=k)continue; 结果出现了某些神奇的现象,比如说:AC cout<<abs(-3-1); 显示的的结果竟然是——\(2\) 什么?!!(我的鼠标于是被砸坏了) 其实,正确的宏应该写成这样: #define abs(x) ((x)>0?(x):-(x)) 因为c++的宏只是粗暴地将文字替换掉(我的理解),与函数不同,他...

和小哥哥一起刷洛谷(11)

二分答案进阶二

POJ2773 Happy 2006 今天竟然是一道poj题目。(题目链接戳标题↑) 只写了一道题是因为其他的题我wa了 思路 首先观察这题的\(k\)的大小,一锅煮不下\(O(n)\)都扛不住,更别说你还得用辗转相除法用\(O(log(n))\)测试两个数的最大公约数了。 何以解忧,唯有二分。那么怎么二分呢,掐指一算,如果对于一个任意的自然数x,我们能求出小于他的所有与m互质的数的数量,那么我们就可以直接二分答案了! 相信学过小奥的诸位都知道如何解决这个问题了——容斥原理(详情请百度)。我们只需存下m的所有质因子,然后就可以计算以上的那个东西了。终于,这题的大体思路形成了。 ...

和小哥哥一起刷洛谷(10)

二分答案进阶

SP1296 SUMFOUR - 4 values whose sum is 0(二分搜索) 思路 这题的数据量显然不能暴力枚举的(\(O(n^4)=O(4000^4)\)) 其实我们可以将四个数列中前两个数列中的数按不同排列两两加起来存进数组,后两个数列中的数按也不同排列两两加起来存进数组(其实不必要,本人脑子一时“抽搐”来着)。再遍历第一个数组中的每一个数,再从第二个数组中二分查找出一个与前一个数的和为0的数。 然鹅这题有一个坑——数列中可能有相同的数字。相信你能想出怎么处理这种情况。 代码 #include<cstdio> #include<algor...

更换域名通知

更换到blog-e.tk

也许有些朋友也访问过我以前的hexo博客ethan.gayethan.ga。自从我的hexo博客爆炸以后我就一直在寻找合适的搭建博客方式,试过博客园,wordpress,最终又发现了与hexo颇为类似的jekyll博客(我的博客历程详见“关于”页面)。(专业人士:“hexo和jekyll根本就是两种东西!”我:“我好像不明白。”) 在对jekyll博客模板进行一通魔改之后我又把这个博客绑定了原来的域名ethan.ga,然后打算开始弄SEO优化,结果发现用谷歌搜索“site:ethan.ga”全都是我以前博客的东西,点开了以后纷纷都是404。所以只好忍痛放弃了以前的那个有深刻意义的域...

和小哥哥一起刷洛谷(9)

二分答案

本人对于二分极度不擅长,于是每次代码都bug百出。怪我喽 在写二分模板时时经常分不清二分是叉叉勾勾还是勾勾叉叉形,加之有时check函数的返回值又写错。。。人生无望啊~ P1316 丢瓶盖 题目链接戳标题↑ 分析: 一道典型的二分答案题,所有可能的答案,满足勾勾叉叉形(我们老师说的,大概就是说:要求出的最小距离越短,则能拿出的瓶盖越多,越可能能满足题目要求)。 伪代码(以及我的花式错误) 就只写写本题目二分部分的啦 大概是酱紫的↓(正确): 左指针<右指针时重复进行: 平均数=(左指针+右指针+1)/2 若距离为平均数时满足题意: 左指针等于平均数 否则:...

jQuery学习笔记(2)

了解jQuery事件

何为事件 就是你的鼠标,键盘等对网页元素进行的操作。 常见事件 鼠标事件 键盘事件 表单事件 文档/窗口事件 click keypress submit load dblclick keydown change resize mouseenter keyup focus scroll ...

jQuery学习笔记(1)

基本了解jQuery

安装 两种方法: 从 jquery.com 下载jQuery。 从 CDN 中载入 jQuery: <script src="https://cdn.staticfile.org/jquery/1.10.2/jquery.min.js"> 语法 $(selector).action() ​选择器 + 事件 文档就绪事件 $(document).ready(function(){ /* code */ }); 我们通常将所有jQuery代码写在上面代码的注释处,这样是为了防止网页在加载完毕之前就运行jQuer...

优雅地使用eruda在移动端上调试网页

本人乱搞前端

注:本文有一小部分截图为桌面端,但所有内容都亲测在移动端上可用。 你曾否在洛谷上用<F12>把错的数据点改成AC?是否有过自己尝试搭建网站,在移动端上js代码运行出错?如果你的回答是肯定的,那么eruda就正好适合你! 1. eruda简介 github开源项目网址:eruda Demo演示 Eruda是一个专为手机网页前端设计的调试面板,类似 DevTools 的迷你版,其主要功能包括:捕获 console 日志、检查元素状态、捕获XHR请求、显示本地存储和 Cookie 信息等等。 其有以下功能: Console面板:捕获...