Doraemon's Blog

A. Cards for Friends给一个宽度和一个长度的蛋糕，只有为长或宽为偶数时才能切一刀数量乘以2，问给定尺寸的蛋糕能否分够k块。 分别对宽和长除2，只要是偶数就除，看看能除几次，得到两个次数相乘就是能分的最大数量，和k比较一下 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;typedef long long ll;const int SUP=0x800000;const int MAXN=1e5;const int INF=0x3f3f3f3f;const double eps=1e-4;int num[MAXN];int main(){ ios; int t; cin>>t; while(t--){ int w,h,k; cin>>w> ...

朴素版的线段树只能实现单点修改区间查询，修改和查询的时间复杂度都是O(logn) 懒标记问题加上懒标记后的线段树就可以实现区间修改了，比如我要把[a,b]的值加上k，肯定不会傻到n次单点修改，是个人都会想到假如递归到一个包含在[a,b]的区间时就不用继续往下递归了，直接告诉这个区间的管理员，把这个区间的和直接给修改了，但是假如你上面第一次增加时增加区间为[c,d]，并且区间[c,d]是包含在[a,b]中间的，现在又要在[e,d]增加k，e>c的，这个时候你就会发现[e,d]这个区间增加了两次，因为第一次增加时你根本没有递归到[e,d]，而是递归到这个区间的上一层就直接返回了，现在你再在[e,d]区间增加值就会出错，因为少加了第一次的增值，所以应该找一个东西记录下来第一次增值，并且把他带到下面去，这时懒标记就出来了，新开一个数组lazy[i]，表示编号为i的区间的累计增值，那么第一次修改[c,d]时，lazyu\就会记录下来增值，lazy[u]+=c，第二次修改经过这个已经修改过的区间时，就要顺带着把这个区间的修改值一起带过去，正所谓父亲欠下的债儿子去偿还，当修改[e,d]时，经过 ...

2020年度总结 转眼间已是2021，想一想我的大学生活已经过去将近一半，真是快呀！总结一下我的2020年叭~ 成就 ACM 天梯赛(铜奖) CCPC省赛银奖 CET 成绩还没出，不过感觉是考的不错 体测 79，已经非常满意了，只要过了75就满足了~ 学业 比较满足了，相比于上学期确实进步了好多，可能是因为新图书馆建好了的缘故叭~ 想说的话寒假​ 2020年寒假在家，对视频剪辑，PS，特效制作兴趣比较大，就学了十多天吧，当时还去淘宝上买了好几个教学视频呢，现在都还在百度网盘存着，就是做特效的时候才发现AE对电脑的配置需求太大了！5千多的电脑根本带不起来…CPU在燃烧🔥~最后也是做出来了一个爱情公寓版的开头片，个人感觉还是不错的，做了两天呢！遗憾的是最后失误把源文件了导致图片链接不上了，最后也是啥也没做成，现在也忘了软件咋用了。 接触Hexo​ 从过年开始疫情就开始了，过年的那两天啥也没干，亲戚也不敢串，都窝在家里，当时一整天有半天多都是躺在被窝里玩游戏或者看爱情公寓5，好慵懒😶~然后就是因为疫情一直没有开学，从2月底开始上网课，记得刚听说要上网课 ...

原来使用的Sakura主题已经没人维护了，写作时因为没有集成插件很多标签都没有，因此写出来的文章就比较丑，最重要的原因还是shoka这个主题太好看了，个人实在是喜欢(❤ ω ❤)，忍不住就咕哝了两天，在这里记录一下迁移过程遇到最棘手的问题Algolia的配置吧。 :::success 主题优点 先给新主题shoka打个广告，继承了许多优秀插件，尤其是写作标签非常多，写作标签介绍，就光这一点就足够吸引我了，其次就是好看，贼好看，这个布局确实是让人看着赏心悦目，而且配置简单，因为很多东西都集成了，就方便了很多操作。 ::: 回归主题，由于以前没用过algolia，导致我还得去网上查资料一点一点学，好在最后弄好了。 Algolia配置 首先第一步就是安装hexo-algolia，右击博客根目录输入npm i hexo-algolia 打开网页algolia，注册账户，新建一个Indice，名字随便起，然后根据提示完成后续工作，大致就是让你选择根据什么来搜索 之后在左侧导航栏中找到Api Keys 点击All API Keys，然后点击右上角New API Key，新建一个API ...

你是否还在为这丑陋的window10界面而叹气(win10界面其实还可以)，你是否还在为怎么美化界面而烦恼？不用叹气，不用烦恼！这篇博客可以解决你的问题 众所周知，一个简单漂亮的界面对人的心情也是有很大影响的，假如一个人不整理文件，桌面上乱七八糟，什么都往桌面上放，那迟早是受不了的，将来一定有一天你都不想开电脑 先来放一张美化过后的图片吧 效果还不错吧 强烈推荐 致美化（里面什么都有） Mydock仿MAC-dock栏，官网，随便选择一个下载渠道，下载后安装 找到一个空白地方右击可以设置大小，图标，开机启动等等，还可以设置最小化动画 Translucent(汉化版)任务栏透明化，在桌面时可以使任务栏变得透明，点击左下角windows图标，选择所有应用，找到M开头的应用，找到Micrsoft Store，打开后搜索Translucent(汉化版)一定要是汉化版除非您是英语大佬 下载就可以了 雨滴皮肤雨滴是一款占内存非常小的软件，里面有桌面时钟效果，可以添加到桌面动态时钟 皮肤下载地址: Here 自行设置效果吧 本人还是觉得简约效果最好: 任务栏图标居中 找一个安全位置新 ...

课程设计 问题描述: 用十字链表存储稀疏矩阵，实现两个可进行矩阵之间的乘法运算。  基本要求: （1）要对两个矩阵能否进行乘法进行判断。（2）对能够进行乘法运算的稀疏矩阵进行乘法运算并输出正确的结果。 参考博客 大致思路一般矩阵中会有很多值为0的元素，十字链表把这些值给忽略掉了，只存有值不为0的元素，每一行都是一个链表，每一列也是一个链表，用一个行指针、一个列指针指向它们，形成矩阵形式 数据类型123456789typedef struct OLNode{ //元素类型 int row,col; //行列 ElemType val; //数值 OLNode *right,*down; //行指针、列指针}*OLink; struct CrossList{ //矩阵结构 int n,m,num; OLink *Rhead,*Chead; //指向行链表、列链表的指针}; 初始化指针每次都要先把矩阵指针置为空 1234void InitCrossList(CrossList &CL){ CL.n=CL.m=CL ...

实验目标：1、创建二叉树2、用非递归算法先中后序遍历二叉树 (难点)3、分别求出二叉树中度为 0、1、2的结点个数4、求出树的高度 参考博客:Article_1Article_2 难点在于非递归遍历，用栈来模拟递归的过程 二叉树结构1234typedef struct node{ char data; struct node *lchild, *rchild;}BiTNode,*BiTree; 创建二叉树12345678910void CreateBiTree(BiTree &t){ char ch; cin>>ch; if(ch=='#') t=NULL; else{ t=new node; t->data=ch; CreateBiTree(t->lchild); //创建左子树 CreateBiTree(t->rchild); //创建右子树 }} 层序遍历1234567891011121314void Level(BiTree L){ ...

倍增 以倍增方式向上跳，时间复杂度是O(q*logn) tarjan 树上算法，实现过程通过dfs+并查集来离线求出lca(最近公共祖先)，时间复杂度O(n+q)，n是结点数，q是查询数 算法实现过程倍增算法流程: 用一个dfs得出每一个点的父亲节点还有它的深度，用数组保存起来，其中保存父亲的数组用dp[i][j]表示，意义是i节点向上跳2^j^步后到达的节点，父亲节点保存在dp[i][0]中 12345678void dfs(int u,int fa,int d){ //得到每一个点的深度和父亲节点 dp[u][0]=fa; dep[u]=d; for(int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v!=fa) dfs(v,u,d+1); }} 然后倍增预处理出每一个节点向上跳2^i^步到的的节点 1234567void bz(){ //预处理 for(int i=1;i<=22;i++){ for(int u=1;u<=n;u++){ ...

暑假学习了KMP，奈何掌握不深，现在又来复习，结果又是从零开始 什么是KMP？现在有一个原字符串，再给你一段模式串，问你在原字符串中是否存在一段子串等于模式串，或者模式串在原串中出现几次？ BF算法，也就是人人都会的指针回朔暴力算法，略过 原串： ABABABAABA （i） 模式串： ABAA （j） 当匹配时第一个失配的位置是3(下标从0开始)，然后朴素做法是把i和j指针都回朔，但其实可以利用之前已经匹配的信息的，可以找到当前失配字符之前的最大公共前后缀长度，假设长度为k，则s[i-k]…s[i-1]==t[j-k]…t[j-1]，而t[0]…t[k-1]==t[j-k]…t[j-1]，所以s[i-k]..s[i-1]==t[0]…t[k-1]，所以只需要把j移到k位置就可以了，i指针不回朔，这样一来就只要j指针回朔，而且大概率没有回朔到0，省去大量时间，那么问题就来了，怎么找到模式串中每一个位置的k呢？ 前面已经说了，k是每一个位置之前字符串(不包括k位置)的最长公共前后缀长度，而公共前后缀与原串无关，只是在模式串中求即可 求解NEXT用next[i]表示i位置之前字符串的 ...

2020年10月18日，这一天是我第一次打比赛的日子，非常有纪念意义，但是时至今日我才补了这篇文章 2020年注定是不平凡的一年，突如其来的疫情改变很多人的生活轨迹，原本该在这一年大展拳脚的学长们无奈只能在家里打着练习赛，然而对我们而言，有好也有坏吧，好的是我们有更多时间去提升自己(当然全靠自觉)，坏的是少了许多阅历，不管怎样，终于在2020年8月29日我们开学了，开学后经过一个星期的过渡，又回到了算法的训练中去，在下面也打了许多训练赛，每次都紧紧抱着大佬的大腿，每次成绩也都还不错(不错指的是会的都比较快的做出来了)，然而只要是dp只要是新算法我们就止步于此了 又过了一个月，我们迎来的这一年的CCPC邀请赛，首先是出线问题，最终学长们也都打进去了，我们19级的因为时间还多，机会就都留给学长们了，不过一星期后，老师跟我们说可以办外卡，也可以参赛拿奖，高兴了我一天，当时我以为是线下赛，想着终于可以出去涨涨见识了，然而第二天就丧了，因为疫情，这一年几乎所有比赛都是线上举行的！一下子感觉气氛都不对了，不过毕竟是比赛，比赛前我还是有去多刷题的，然而因为好多新算法都没学，有很多题目都是干瞪眼 ...