洛谷 @ 2018-07-11 22:28:42
2022 年
2021 年
2020 年
2019 年
2018 年
#109 运行linux的第四种方式：双系统（作者：SIGSEGV）
https://www.luogu.com.cn/blog/_post/94249
#108 从零开始的矩阵乘法（作者：可爱即是正义）
https://shehuizhuyihao.blog.luogu.org/post-zhen-sheng-fa
#107 Turbo Pascal的进化史（作者：zhzh2001）
https://zhzh2001.blog.luogu.org/evolution-of-turbo-pascal
#106 初探容斥原理（作者：iki9）
https://www.luogu.org/blog/KingSann/chu-tan-rong-chi-yuan-li
#105 铃悬的数学小讲堂——杜教筛（作者：铃悬）
https://lx-2003.blog.luogu.org/dujiao-sieve
#104 不常用的黑科技——三元环（作者：iki9）
https://www.luogu.org/blog/KingSann/fou-chang-yong-di-hei-ke-ji-san-yuan-huan-post
#103 可并堆之左偏树（作者：HolseLeet）
https://www.luogu.org/blog/cytus/ke-bing-dui-zhi-zuo-pian-shu
#102 区块链，你知道多少？（作者：ShineEternal）
https://www.luogu.com.cn/blog/_post/64579
#101 信息学竞赛全攻略3：信息学竞赛考什么（作者：kkksc03）
https://www.luogu.org/blog/kkksc03/oi-descption3
#100 线段树合并：从入门到放弃（作者：Styx）
https://www.luogu.org/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-qi
#99 零基础零成本搭建属于自己的WordPressHexo博客（作者：CokeMine）
https://www.luogu.com.cn/blog/65360/ling-ji-chu-ling-cheng-ben-da-jian-shu-yu-zi-ji-di-wordpresshexo-bo-ke
#98
该文章涉嫌抄袭，已经撤下。
#97 北京大学2018年中学生暑期课堂（信息科学）3日游（作者：lhy1210302421）
https://www.luogu.org/blog/lhy1210302421/BDXLY2018
#96 Typora ---一款简洁的Markdown编辑器（作者：顾z）
https://rpdreamer.blog.luogu.org/typora-yi-kuan-jian-jie-di-markdown-bian-ji-qi
#95 信息学竞赛全攻略2：为什么要参加竞赛（作者：kkksc03）
https://www.luogu.org/blog/kkksc03/oi-descption2
#94 在你的Android手机上运行Linux（作者：wendster）
https://www.luogu.org/blog/wendster/play-linux-on-your-android-phone
#93 C++11 Unordered_map & set 你真的了解了吗？（作者：yijan）
https://www.luogu.com.cn/blog/_post/76302
#92 OI中组合数的若干求法与CRT（作者：ButterflyDew）
https://www.luogu.org/blog/ButterflyDew/post-oi-CRTblabla
#91 浅谈玄学数据结构：跳表（作者：I_love_him52）
https://www.luogu.com.cn/blog/_post/78392
#90 浅谈Dijkstra（作者：灯火丿葳蕤）
https://www.luogu.com.cn/blog/_post/53048
#89 厌倦了Windows自带的远程桌面连接？试试TeamViewer（作者：小猪之最）
https://www.luogu.org/blog/thepigblog/Teamviewer
#88 Arbiter评测系统指北（作者：dingyuxiao99）
https://dingyx99.blog.luogu.org/use-arbiter-to-generate-arbitrary-results
#87 浅谈并查集优化（作者：喵小皮）
https://www.luogu.com.cn/blog/_post/74686
#86 NOIP选手必知的编程技巧（作者：StudyingFather）
https://studyingfather.blog.luogu.org/some-coding-tips-for-oiers
#85 图论的小技巧以及扩展（作者：chengni）
https://www.luogu.org/blog/chengni5673/tu-lun-di-xiao-ji-qiao-yi-ji-kuo-zhan
#84 数字组成的奥妙——数位dp（作者：Mathison）
https://www.luogu.org/blog/virus2017/shuweidp
#83 Vim的使用、配置与简单拓展（作者：小老虎3018）
https://www.luogu.org/blog/Tiger3018/vim-basic-learning
#82 聊聊动态规划与记忆化搜索（作者：interestingLSY）
https://interestinglsy.blog.luogu.org/memdfs-and-dp
#81 轻量级编辑器透彻指南--Notepad++（作者：ghj1222）
https://www.luogu.org/blog/user13091/ghj1222-likes-npp
#80 马拉车（manacher） 算法（作者：codesonic）
https://www.luogu.org/blog/codesonic/manacheralgorithm
#79 二进制与位运算（作者：chengni）
https://www.luogu.org/blog/chengni5673/er-jin-zhi-yu-wei-yun-suan
#78 浅谈算法——博弈论（从零开始的博弈论）（作者：Wolfycz）
https://www.luogu.org/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zong-ling-kai-shi-di-bo-yi-lun-post
#77 2-SAT略解（作者：守望）
https://www.luogu.org/blog/user9012/post-2-sat-lve-xie
#76 差分数组 and 树上差分（作者：顾z）
https://rpdreamer.blog.luogu.org/ci-fen-and-shu-shang-ci-fen
#75 浅谈C++指针（作者：zhouwc）
https://zwc.blog.luogu.org/qian-tan-c-zhi-zhen
#74 贪心讲解(I)（作者：LCuter）
https://www.luogu.org/blog/83547/tan-xin-jiang-xie
#73 尺取法小结（作者：Fuko_Ibuki）
https://www.luogu.org/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie
#72 X Window系统简明介绍（作者：尘息）
https://www.luogu.org/blog/chenxijun/x-window-system
#71 傅里叶变换(FFT)学习笔记（作者：command_block）
https://www.luogu.org/blog/command-block/fft-xue-xi-bi-ji
#70 NOIP2018初赛提高组解析（作者：zcysky&kkksc03）
https://www.luogu.org/blog/zcysky/noip2018-chusai-tg-sol
#69 当小球遇上盒子（作者：chengni）
https://www.luogu.org/blog/chengni5673/dang-xiao-qiu-yu-shang-he-zi
#68 克鲁斯卡尔重构树略解（作者：守望）
https://www.luogu.org/blog/user9012/ke-lu-si-ka-er-zhong-gou-shu-lve-xie
#67 铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演（作者：铃悬）
https://lx-2003.blog.luogu.org/mobius-inversion
#66 浅析中国剩余定理（从CRT到EXCRT）（作者：ztz11）
https://www.luogu.org/blog/ztz11/qian-xi-zhong-guo-sheng-yu-ding-li-zong-crt-dao-excrt
#65 树上启发式合并（作者：codesonic）
https://www.luogu.org/blog/codesonic/dsu-on-tree
#64 真正的全真虚拟机：VmWare Workstation（作者：ztz11）
https://www.luogu.org/blog/ztz11/zhen-zheng-di-quan-zhen-xu-ni-ji-vmware-workstation
#63 洛谷用户的福利！美化洛谷界面（作者：哔哩哔哩）
https://www.luogu.org/blog/41868/material-luogu-material
#62 Splay简易教程（作者：tiger0132）
https://tiger0132.blog.luogu.org/slay-notes
by Prurite @ 2018-12-04 09:05:34
20楼前排资瓷
by blackfrog @ 2018-12-09 14:08:27
建议洛谷出一个比较好查询的目录索引，这样子文章多了还能找到地址
by 滑蒻稽 @ 2018-12-15 14:55:22
by TEoS @ 2018-12-17 20:39:16
资瓷
by Alphaban @ 2018-12-22 13:20:51
【动态规划】最长公共子序列与最长公共子串
X=<x1,x2,⋯,xm> , Y=< y 1 , y 2 ,⋯, y n
Y=<y1,y2,⋯,yn> ，求LCS与最长公共子串。 暴力解法 假设 m<n m<n ， 对于母串 X X ，我们可以暴力找出 2 m 2m 个子序列，然后依次在母串 Y Y 中匹配，算法的时间复杂度会达到指数级 O(n∗ 2 m ) O(n∗2m) 。显然，暴力求解不太适用于此类问题。 动态规划 假设 Z=< z 1 , z 2 ,⋯, z k
Z=<z1,z2,⋯,zk> 是 X X 与 Y Y 的LCS， 我们观察到 如果 x m
y n xm=yn ，则 z k
x m
y n zk=xm=yn ，有 Z k−1 Zk−1 是 X m−1 Xm−1 与 Y n−1 Yn−1 的LCS； 如果 x m ≠ y n xm≠yn ，则 Z k Zk 是 X m Xm 与 Y n−1 Yn−1 的LCS，或者是 X m−1 Xm−1 与 Y n Yn 的LCS。 因此，求解LCS的问题则变成递归求解的两个子问题。但是，上述的递归求解的办法中，重复的子问题多，效率低下。改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。这就是动态规划（DP)的核心思想了。 DP求解LCS 用二维数组c[i][j]记录串 x 1 x 2 ⋯ x i x1x2⋯xi 与 y 1 y 2 ⋯ y j y1y2⋯yj 的LCS长度，则可得到状态转移方程 c[i,j]= ⎧ ⎩ ⎨ ⎪ ⎪ 0 c[i−1,j−1]+1 max(c[i,j−1],c[i−1,j]) i=0 or j=0 i,j>0 and
x iy j i,j>0 and x i ≠ y j c[i,j]={0i=0 or j=0c[i−1,j−1]+1i,j>0 and xi=yjmax(c[i,j−1],c[i−1,j])i,j>0 and xi≠yj 代码实现 public static int lcs(String str1, String str2) { int len1 = str1.length(); int len2 = str2.length(); int c[][] = new int[len1+1][len2+1]; for (int i = 0; i <= len1; i++) { for( int j = 0; j <= len2; j++) { if(i == 0 || j == 0) { c[i][j] = 0; } else if (str1.charAt(i-1) == str2.charAt(j-1)) { c[i][j] = c[i-1][j-1] + 1; } else { c[i][j] = max(c[i - 1][j], c[i][j - 1]); } } } return c[len1][len2]; } DP求解最长公共子串 前面提到了子串是一种特殊的子序列，因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要，糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性，将二维数组 c[i,j] c[i,j] 用来记录具有这样特点的子串——结尾为母串 x 1 x 2 ⋯ x i x1x2⋯xi 与 y 1 y 2 ⋯ y j y1y2⋯yj 的结尾——的长度。 得到转移方程： c[i,j]= ⎧ ⎩ ⎨ ⎪ ⎪ 0 c[i−1,j−1]+1 0 i=0 or j=0 x i
y j x i ≠ y j c[i,j]={0i=0 or j=0c[i−1,j−1]+1xi=yj0xi≠yj 最长公共子串的长度为 max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n} max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n} 。 代码实现 public static int lcs(String str1, String str2) { int len1 = str1.length(); int len2 = str2.length(); int result = 0; //记录最长公共子串长度 int c[][] = new int[len1+1][len2+1]; for (int i = 0; i <= len1; i++) { for( int j = 0; j <= len2; j++) { if(i == 0 || j == 0) { c[i][j] = 0; } else if (str1.charAt(i-1) == str2.charAt(j-1)) { c[i][j] = c[i-1][j-1] + 1; result = max(c[i][j], result); } else { c[i][j] = 0; } } } return result; }
by 灵光一闪 @ 2019-01-02 19:58:17
前排
by MeteorFlower @ 2019-01-06 21:14:28
后排
by team109 @ 2019-02-07 18:47:51
末排
by czyczyczyczyczy @ 2019-02-15 16:57:06
I can AK IOI!
I can AK IOI!
I can AK IOI!
by t162 @ 2019-02-25 17:04:54
@sgun30 花式作死