从六年级开始学习OI至今，已经快四年了。即便在最后一年我因此感到很痛苦，很烦恼，但是这也是非常宝贵的一段经历。“少年不知愁滋味”预备到初二这段时间是无忧无虑的，没有升学的压力，作业也很少，有着大...

C考虑从后往前推，即若此数为14，发现能被而除尽，则/2。7不能除尽，则-1。同时将这些步骤存在stack中，输出即可。#include<bits/stdc++.h> using n...

D题意：给n个数字，求m以内的所有对于一切$a_i$都成立的$gcd(a_i,k)=1$的所有k。我们很容易得到一个推论，如果$k_1$,$k_2$都成立，则$k_1*k_2$成立，若有一个不成...

前言【基础】类文章是我在较忙的时候，无法提升能力，从而打牢基础的文章。此类文章不会写的很详细，大佬们可以直接略过此类文章。经典例题——滑动窗口本题树状数组和线段树是可解的，但是这里单调队列无疑是...

题目链接解题思路本题难度和CSP-S 2020 T1（弱数据）相近不难得到一个推论：如果你t时刻出发走某一条路径，被某个洪水挡住了，无论你走其他什么路径，总会被挡住。然后之后又得到一条推论：如果...

题目链接解题思路本题dpi表示的是有i个数字和为j，由于每个i都是不断更新的，不会访问之前的i，所以可以直接滚动数组：dp[j]代表当前数字和为j。代码#include<bits/stdc...

序我的rp大概真的爆int了。。。考前我把所有2012-2019pj真题共44题刷了43题。考前本来有时间做最后一题，但看这玩意儿是后缀表达式，我看过的题里就这一道要用，又懒得写，于是。。就跳过...

题目链接解题思路这题挺有意思的，看一看是可以在20分钟内想到解法，但是在实现的过程中会遇到很多阻碍。乍一看题面，问的是“至少”，那可以判断出这题大概率是道二分答案题。然后看子任务，在二分的答案下...

题目链接解题思路请见李煜东的蓝书，里面的讲解比任何博客都好。说白了就是一个“覆盖”，然后用树上查分O(1)维护树上边被覆盖的次数，以点代边，边所连的子节点作为这条边的“配套点”。代码#inclu...

请输入密码访问

题目链接解题思路正解是斜率优化，但是我不会很容易想到是以时间作为下标dp的。但是由于时间复杂度会超，我们发现有用时间只有nm。所以对于其他的t-nm的时间可以用O(1)直接求出。为了快速求出i-...

题目链接解题思路我们先看数据范围，是1e9。一般人都会反应到：1e61e92=2e15，没有爆long long。但如果测大样例的话会发现这明显不只，不是这样算的，而证明我也懒得不会证了，所以只...

题目链接解题思路这道题目中，我们为了更快的排除一些不可选的磁力块，可以选择分块。总体以m从大到小排序，块内以dis排序（颠倒过来应该也可以）。即以两个对于吸引的决定项排序。我们设k是大小交替的一...

题目链接解题思路本题有一个引理：在满足S最小化的前提下，一定存在一种构造序列B的方案，使得B中的数值都在A中出现过。若想证明，请看《算法竞赛进阶指南》268页。如果去掉之前的推论，那么只有绿题难...

A语法题#include<bits/stdc++.h> using namespace std; const int inf=1e9+7; int main(){ doubl...

一句话思路我们求割点和割边，只要知道其子节点能否通过不经过其父节点（割点）或父节点所在的边（割边）到达父节点的祖先节点的位置即可。

题目链接解题思路递推我们可以递推，枚举1在每一个位置的可能，于是整个数列就被划分成了两部分，然后再在两部分中继续递推，时间复杂度为 $O(n^2)$$$ S_n=\sum^{N}_{k=1}S_...

题目链接解题思路对于每一条边，其贡献为断开它后两部分的siz的乘积乘以边权。所以我们对于每一个siz的乘积排序，对p排序，小的对小的，大的对大的，最大的将剩下所有全拿走即可。其中siz在树上DF...

A#include<bits/stdc++.h> using namespace std; int main(){ int n,x,t; cin>>n&g...

题目链接解题思路设A为原数组， $X_i$ 为从i向i-1传递了 $X_i$ 个糖果。$$ A_1+X_2-X_1=ave \\A_2+X_3-X_2=ave \\. \\. \\. \\A_i...

先放上我的惨烈提交界面题目链接解题思路nodeee于2020/8/20退役这道题目写的我看了几篇OI退役的文章，在想该怎么写。。。作为一道二分，其实无非就是枚举。最开始我的思路是二位前缀和，结果...

解题思路可以肯定的是对于每一个lightning法术，一定要加在最大攻击上。但我们发现所加的spell肯定要有一个是fire，否则会浪费一个spell，于是我们将最大的fire单独处理，将它从平...

A#include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; ...

题目链接解题思路我们将 $>m$ 和 $<=m$ 的数字归为两组a,b，两组可独立考虑。对于每一组中，都取最大的几个。如果我们取了 $i$ 个b，则b只能取 $(n-i-1)/(d+...

题目链接解题思路设最大点为b，其父节点为a，c为其他任意点如果先染 $a,b$ ，再染 $c$ ，分值是 $a+2b+3c$ ；如果先染 $c$ ，再染 $a,b$ ，分值是 $c+2a+3b$...

题目链接解题思路既然是有已定的t，那可以想到要么倍增要么二分。对于二分，如果每次T很小会造成很多不必要的时间浪费，所以我们选择倍增而每一次询问我们都要找到区间内最小的几个和最大的几个做方差。每次...

题目链接解题思路我们将整个数组看成aaaaaaaaa bbbbcccddddeeff....其中a为出现次数最多的数字。然后将数字插入每一个a的空档中。可以保证一定有插法不会在不是出现次数最大的...

题目链接解题思路考虑每一个i，如果a[i]>0，则先取a[i]再取b[i]，否则先取b[i]再取a[i]。但是会有一种情况：a[i]原来是负数，然后经过一系列加法之后变成了正数。这种情况应...

题目链接前置知识：分块解题思路本题是一道计算区间出现次数最多的数字的题目。如果我们想用主席树做会发现时间复杂度和暴力没有什么不同，甚至还慢一点。这时我们可以想到另一种维护区间的思想：分块。我们可...

HH的项链前言如果评测机再好一点，主席树能卡过去（这不是你不会离线树状数组做法的借口！）解题思路本题是一道主席树，由于记录的是种数，所以是不满足直接区间加的。于是就考虑其他的操作：我们用was记...

A给一个N，如果 $N\ge 30$，输出"Yes"，否则输出"No"。#include<bits/stdc++.h> using namespace std; int main()...

前置知识权值线段树可持久化线段树当我们要保存每一个版本的线段树的时候，最暴力的算法就是开n个版本的整个线段树，但是由于n可能到2e5，所以空间肯定不够。于是我们考虑可以将一些不变的节点合并，就变...

题目链接做题感受这道题目对于我这种没学过线性代数的初中生来说烧脑至极，什么坐标旋转啥的都不会，就在acwing上听y总讲。最要命的是y总还用数组坐标代替直角坐标系的坐标讲，于是我就云里雾里的。。...

引入这是一道让我记忆深刻的题目。是上海市某知名信息学教练虐待刚学OI半年的萌新的题目。（强烈谴责此类行为！）传送门解题思路既然是区间问题，很容易想到线段树。但是该如何维护线段树呢？我们令每一个结...

题意概述给你一棵树，求出树的直径长度并找到树上所有直径都经过的边有多少条。解题思路本题求树的直径就只需要用DP或DFS都可以（注意DP可以求出负权边而若DFS求则很困难）。这里没有负权所以用DF...

快三个月没更了。。。（没有理由，就是懒）道路与航线这道题目是一道神题，一个小错误能查半天，但是如果做出来，代码能力应该可以有显著提升。总共调了我一个星期，里面有很多个坑点。（我最后做出来是随便改...

关于平衡树平衡树是一棵二叉搜索树，但是它比二叉搜索树好的地方是可以避免一些情况下树退化成链而造成的O(n)的单词查找。而平衡树可以可以稳定在约O(logn)级别。但是这也并不是一定的，平衡树退化...

Nim博弈题意简述有n堆棋子，每一次可以从一堆中取走不少于1的任意个棋子。不能取的一方输。问先手是否必胜。（所有博弈的前提是两者都采取最优策略）定理设第i堆中有 $a_i$个棋子。若 $a_1 ...

关于K短路理解很难，但是懂了之后真的发现很简单。主要是大家脑海里没有一个正确的运行的图。大家要想出是如何跑的就行。前置知识：一次反向最短路（其他都算不上知识，要自己慢慢悟出来）知识重点：反向最短...

突然发现自己连LCA的博客都没写。。。赶忙补起来关于LCA理解起来动态LCA及其简单，静态的就难了一些。写起来静态比动态可能要少1/3。前置知识：树上倍增（动态）、并查集（静态）知识重点：LCA...

给自己立个flag，哪天有空做了这题关于树链剖分虽然这是个省选的知识点，但是其实不算特别难以理解。最多花5小时的功夫就能理解，不过要是想写出来的话对于码力的门槛还是挺高的。前置知识：线段树、LC...

这场比赛和机房speedcoder神犇一起打真的不容易啊。。。T3，T4，T5被瞬间拉开差距AA水的一匹，20秒写完正解。。。由于那位神犇似乎用了if，而我是直接6-a-b，顺利夺取30秒#in...

题目链接下面的代码由于是比赛时写的不甚美观，如有疑问欢迎在下方评论区评论。解题思路其实这道题目想起来真的很简单很简单，但是特别容易取模的时候写挂。这道题目的思路就是先将每一个数字转化成二进制，例...

问：为什么不写预流推进？答：我不会正文开始：最大流是什么网络流是求出在一个网络内从s点到t点的最大流量的算法。题目中告诉你s点（起始点），t点（结束点），边以及这条边能流多少流量。我们最开始并不...

[Meting][Music server="netease" id="509313150" type="song"/][/Meting]从开始打atcoder已经一年多了，一直在不断进步呢。一...

初赛篇在那之前从初赛一个月之前，我就开始复习初赛内容，每节文化课下课、每一个中午都会拿出初赛一本通看。当然，我花这么多时间肝初赛的主要原因是NOIP2018因为初赛炸了，就根本没拿到复赛机会。J...

简介查找一个序列中的逆序对个数。逆序对：如果i<j&&a[i]>a[j]则为一对逆序对。朴素算法暴力枚举每两个数并进行比较，如果符合i<j&&a[i]>a[j]则ans+...

别急别急，先放完战歌再开战[Meting][Music server="netease" id="491757212" type="song"/][/Meting]不懂并查集者勿入，因为。。。我...

传送门解题思路乍一看还真没有啥思路，只能想到爆搜~ ~（本人过于智障）~~。看了别的大佬的思路后发现这题无比简单。首先，因为题目说距离为2，我们可以枚举每一个点i，那个点的两条不同的边所连的点就...

快速排序快速排序是以分治（分而治之）为基本思想。分治就是把一个大问题分成多个子问题逐个解决并最终合并。1.从所有元素中选出任意一个数字作为基准数。2.找出所有小于基准数的元素并将其放到左边，找出...

（大神勿进，本博客写给建站新手们看）关于服务器1.购买一台服务器我是在阿里云购买3年，5折优惠。2.安装宝塔宝塔的版本最好和之前版本一样。这次我用6.9的数据转不过去。3.在宝塔中安装与之前一样...

乌龟棋解题思路大佬们可能会疑惑为什么我放一道这么简单的dp在这里。首先是因为我dp特别弱，普及dp都做不出。。。第二是因为这道题有一个特点：数据范围很小。写这篇博客最大的知识点就是懂得看数据范围...

题目链接：P3386 【模板】二分图匹配什么是二分图？二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边...

仅以此题，纪念我的智障先把注意点说了：C(0,0)=1;C(1,0)=1;C(1,1)=1;C(2,0)=1;C(2,1)=2;C(2,2)=1列成数组就是n\m01234501~~~~~111...

[Meting][Music server="netease" id="528751907" type="song"/][/Meting]拓扑排序使用范围在不存在互相指向的节点的有向图中。如何操...

又写了一篇博客嘿嘿~没想到吧？最小环是什么？最小环是求一个图中最小的环（说了和白说一样）Dij求法每一次除去一条边(u,v)然后再求u到v的最短路径时间复杂度： $O(m(n+m)log n)$...

题目链接这么好的一道二进制题怎么能不写呢？解题思路既然题目中这么明显地有二进制了，肯定要想到将每个数拆成二进制形式看。答案的某一位的大小取决于初始攻击那一位的大小，与更高位和更低位没有任何关系。...

欧拉定理$$ a^{\varphi(m)} \equiv 1 \pmod{m} $$扩展欧拉定理$$ a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},&...

算法目标最小生成树是找出一个图中总边权最小的那棵树的算法。在其中分为Prim和Kruskal两种算法。经典例题：浇地Prim先选任意节点为树的根节点，然后找到所有在已选择的节点中找到最短的一条和...

acwing189破例发道简单题题目描述由于作者太懒，请自行看题。解题思路乍一看是一个非常简单的BFS，然后我就写了一边，测试数据一遍就过了。可能是出题人想增加一下题目难度，脑子一抽，x变成了列...

裸题：直方图中最大的矩形解题思路用单调栈求解最大矩形。操作流程初始化所有元素的宽度为11.每一次入栈一个元素2.如果前面有比这个元素更高的元素，就将其弹出（由于前面的都是单调递增的，所以如果前面...

算法用途在O(n)的时间判断最长回文子串。算法思想由于我们不想当母串字符个数为偶数和母串为奇数时分别写一个程序，所以我们将这个串的字符个数强行变成奇数个。只要保证在每个字符两边都有一个“#”就可...

算法思路现在有s1，s2两个字符串，其中s2是短串，s1是长串。试问s2是否是s1的字串？朴素算法：设s1长度为n，s2长度为m。s2字符串首位从s1字符串首位到n-m为一一比较，比较时一个字符...

题面描述给定一张 $n$ 个点的带权无向图，点从 $0$ 到 $n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。Hamilton路径的定义是从 $0$ 到 $n-...

Material是我最喜欢的博客主题，之前一直想用。但是一直弄得是viosey的material，有很多bug。最近找到了 黎明余光 大佬的material，bug少了，感觉也更精美了一些。安装...

莫斯科在举办一场重要的有 $n$ 个不同国家的珂学家参与的国际会议，每个珂学家都只会一种语言。为了方便起见，我们规定一种语言用 $1$ 到 $10^9$ 的数来描述。 在会议之后的晚上，珂学家们...

[Meting][Music server="netease" id="32166628" type="song"/][/Meting]线段树的构成线段树中每一个节点都是其父节点的左一半或右一半...

telephone lines题目描述多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000...

Problem StatementThere are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain ...

请输入密码访问

这场比赛在东华大学举办，基于我上次普及组初赛没有过（本人过于蒟蒻），这算是我的第一场正式线下比赛。我们学校信息组总共有九个人报名参加，我是其中第八名，但是在整场比赛中大约五五开。以下是我的比赛心...

数的划分解题思路这道题可以用dp也可以用dfs做，因为这道题目的数据范围很小。我们用$ dp[i][j] $表示将i划分成j份的可能数我们将状态转移方程列为dp[i][j]=dp[i-j][1]...

介绍“二分思想”顾名思义就是将一个数组（或数字）平均分成两份。有的时候不能完美地分为两份，那么只需要用 $mid=(l+r)/2$ 即可。二分查找题目类型：现在有一个有序序列，找一个数值。每一次...

最短路径最短路径是图论中带权图求两点之间最短路线的长度的问题。现在有三种主要的解题算法。floyd算法介绍&适用范围floyd算法是多源最短路，即只能求出一个点到其余点的路程，三重循环也算是一种...

题目描述（自己粗略描述一下）现在有一堆数字，你可以再其中删掉一个，然后剩下的做GCD。数据范围$ 2≤数字数量≤10^5 $解题思路看到数量就知道暴力过不了，那么肯定要优化咯。我最开始想的是用二...

【纪念】第一次AtCoder棕名[Meting][Music server="netease" id="451126088" type="song"/][/Meting]

定义状态Fi表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。状态转移方程：①Fi = Fi-1 (a[i] != b[j])②Fi = max(Fi-1+1) (...

英文题面Problem StatementYou are given N integers. The i-th integer is ai. Find the number, modulo 99...

英文题面Problem StatementThere are N stones arranged in a row. Every stone is painted white or black....

传送门题面描述【问题描述】一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是$ W_1，W_2，...,W_n $，它们的价值分别为$ C_1,C_2,...,C_n $。有...

如果有一个状态，是由很多（<20)个状态组合起来的，就可以用状态压缩减少空间复杂度。我们把每一个子状态作为二进制的一位，可以表示其是和否。例题传送门解题思路我们把每一种组合作为一种状态，例...

表达式$$ X=\left| \begin{matrix} x_{11} & x_{12} & \cdots & x_{1d}\\ ...

[Meting][Music server="netease" id="31654455" type="song"/][/Meting]传送门——金明的预算方案解题思路一共有三种可能一、没有附件...

题目描述即0-1背包，把每个物品只能拿一次改为能拿无数次。

采药0-1背包是动态规划中背包问题的一种，也是最简单的一种。

朴素现在要取a^b/c的余数，而a,c都很大。如果直接pow然后取余肯定会爆。所以出现了一个定理：ab%c=a%cb%cfor(int i=0;i<b;i++){ a*a%c; }快速幂现...

数学游戏：24点进阶版（36点）52张扑克牌，任选四张，可有重复。其中每张卡牌代表的数字为1-13（A=1,J=11,Q=12,K=13）游戏者需要将四张卡牌的数字运用如下运算使其运算结果成为3...

queue队列，一个先进先出的容器。声明：queue<typename> name;函数作用push()入队front()获取队首元素（最先入队的元素）back()获取队尾元素（最后...

流浪地球【题目描述】2075年，不久太阳即将毁灭，太阳系将不适合人类生存。面对绝境，人类将开启“流浪地球”计划。他们使用行星发动机转移地球。再转移过程中，本应该借助木星的引力为地球加速，但是因为...

深搜深搜是一种一条路走到黑，到达边界就返回的算法。运用递归思想，如果到了不符合条件的节点就撤回一步，然后再选择另一条路走下去。如果这个节点的所有路径都走完了，再撤回一步。//最简单的模板 int...

gcd使用辗转相除法解决最大公因数72/45=1……2745/27=1……1827/18=1……918%9==0即最大公因数为9int gcd(int a,int b){ if(a%b=...

突发奇想，借鉴了百度上多为dalao的代码整理出来的。#include <bits/stdc++.h> #include<direct.h> #include <f...

题目描述给一n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有...

源代码//（由于dev-C++很难图像化，所以输出有一定误差。敬请谅解） #include <iostream> #include <cmath> #include &l...

祝大家新年快乐！

字符串匹配题目描述字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入:...

题目：忠诚解题思路代码里有代码#include <iostream> #include <cmath>//cmath库下有log()和log2()等 #include &...

题目座位管理员.pdf解题思路这道题只要用暴力就可以做出来把每一个点赋值为后面连续的空着的座位的数量。之后的操作请大家自己头脑风暴一下吧！也可以用线段树，不过写起来非常麻烦代码暴力：#inclu...

pow()和连乘当次数比100小的时候，用for当次数大于100时用powpow的格式:pow(指数,底数);sqrt()sqrt()一般都是要用很长时间的，所以没有特殊需要时一般都先用tmp保...

int a[100]//数组无法返回数组 void change(int n){ int cnt=0; while(n!=0){ a[cnt]=n%jin; ...

编号 a1234567891011121314151617b～～～～～～～～10111213～～～～～现在要从a数组中截取b数组知道b的和1000000次，而且不...

lowbit（重要！）lowbit是用来取出二进制中最低位数的1所代表的二进制的值。只需要记下代码就行了int lowbit(int x){ return x&(-x); }ad...