2024.7.4【又苦又甜，也挺好嘛，很像生活】Thursday五月廿九<theme=oi-"graphtheory">P2865[USACO06NOV]RoadblocksG主要就是求一个严格次短路，但是有一定条件，道路可以连续走我们先求解出最短路，基于“次短路与最短路一定只有一条边不同”我们对起点和终点都做一次

基础知识形式化定义：二分图：\(G=(L,R,E)\)，满足\(\forall(u,v)\inE\)都有\(u\inL,v\inR\)或\(u\inR,v\inL\)。可知“图中没有长度为奇数的环”是这个图是二分图的充分必要条件。图的匹配是一个\(E_m\subseteqE\)满足\(\nexistsi\inV(\text{当}G

题目传送门前置知识计数DP解法方案数统计同luoguP2467[SDOI2010]地精部落，但部分写得不太好看的状态转移方程在本题中并不适用，但仍可借鉴其“离散化”思想。考虑试填。设\(f_{i,j,0/1}\)表示用\(i\)块不同的木板构成栅栏，其中最左边的木板的长度从小到大排在第\(j\)

CF453CLittlePonyandSummerSunCelebration生成树+构造看看一个点的奇偶性意味着什么。意味着奇数的点必须经过至少一次，而偶数不用经过。那么所有奇数的点两两路径必须构成一个连通块。然后就可以开始想构造了。考虑连通块上的任意一棵生成树，如果一个非根节点走完子树后次

图论(一)图的存储与遍历方法一：直接存边方法二：邻接矩阵用bool类型二维数组存储\(u是否能到v\)方法三：邻接表以P5318为例。#include<bits/stdc++.h>#defineLLlonglong#definels(p<<1)#definers(p<<1|1)#defineINFINT_MAX#definelowbit(x)(x&-x)#define

考虑找一下走掉的条件:若\(x\)第\(1\)天走掉，那么就说明\(x\)没有知道任何咒语。若\(x\)第\(2\)天走掉，那么就说明应该存在一个\(y\)，按照\(x\)已知的信息，\(y\)应该没有掌握咒语，但是\(y\)第一天没走。若\(x\)第\(3\)天走掉，那么就说明应该存在一个\((y,z)\)

题目大意令mexmexmex为序列中最小的没有出现的数。给你一个长度为

思路首先我们将两种操作分开讨论：Part1加入操作那么，我们可以用一个数组\(vis_i=0/1\)表示\(i\)是关闭/开启状态，\(p_i\)表示因数有\(i\)的数。如果$vis_x=1$，说明此机器在之前已经启动过了，输出Success。然后，对\(x\)分解质因数，将质因数全部塞进一个集合\(a\)

题目描述一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n 的格点组成，每个格点只有 22 种状态：. 和 #，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北（或者说上下左右）四个方向之一的相邻格点上，Extense想要从

思路定义\(vis_i\)表示数\(i\)在序列中出现的次数。如果我们选出\(k\)个数，答案就是（其中\(m\)表示\(\max(c_i)\)）：\[\sum_{i=1}^m\frac{\binom{n}{x}-\binom{n-vis_i}{k}}{\binom{n}{x}}\]显然，我们只枚举序列中存在的元素，时间复杂度\(\Theta(n^2)\)，过不

题意给出一个长度为N的序列A，有Q次询问，每次询问输入两个整数i，k，表示将A[i]赋值为x。每次询问输出序列A的mex。mex是指序列中未出现的最小非负整数。思路由于N是小于等于2e5的，那么说明每次询问的mex结果是无论如何都不会超过2e5+1的。我们先用set将1~2e5+1都存起来。然后每当A数

\(\mathcal{TRIE}\)：用于存储和查询字符串的树形结构，相同前缀的字符串共用节点，每个节点存储一个字符。操作：insert：单次\(O(len)\)search：单次\(O(len)\)性质\(1\)：若一个字符串\(T\)作为前缀，则包含\(T\)的所有字符串的“终止节点”一定在以\(T\)的“终止节点”为根

原题链接题解对于一组相切的圆来说，其中一个圆变大，其相邻的圆变小，然后相邻的相邻的圆变大...而要让总半径和变小，一定得是总的变小的圆更多实施先判断一组圆能不能发生变化，然后再累积变大和变小的圆个数code#include<bits/stdc++.h>usingnamespacestd;#definelllonglo

考虑从高到低位做，不断贪心的一个过程。即假设把当前所有数\(a_i\)看成\(\lfloor\frac{a_i}{2^d}\rfloor\)，有当前最优答案\(ans_d\)；现在把所有数看成\(\lfloor\frac{a_i}{2^{d-1}}\rfloor\)，推出下一步的答案\(ans_{d-1}\)。假设\(/2^d\)时，每一步xor完的序列是\(a_1

时刻多日没打竟然退步了 A.小红的葫芦思路:五个元素三个相同另外两个相同可以通过数组排序写也可以map等等方法很多Code:#include<bits/stdc++.h>usingnamespacestd;map<int,int>mp;intmain(){ios::sync_with_stdio(false);cin.tie(0);

原题链接题解1.只需要求最大值和最小值之差，所以最大值和最小值之间放几个数放什么数都无所谓2.既然只需要求最大值和最小值，那么我们可以把数组升序排序，然后求以每个值为最大值时，与最小值的差3.按照升序排序后，最大值越大，最小值不会更小code#include<bits/stdc++.h>usingnam

P1219[USACO1.5]八皇后CheckerChallenge#includeusingnamespacestd;typedeflonglongll;intn,l[50],r[50],vis[50],a[50];intans;voiddfs(intx){if(x>n){if(ans<3)for(inti=1;i<=n;i++)cout<<a[i]<<''

SPFA判负环大家好，我是Weekoder！今天我要讲的是接上一次SPFA最短路算法衍生而来的一个应用——判断图中是否存在负环。我将介绍两种判负环的方法，都基于SPFA。负环的概念负环是什么？负环就是在图中的一个环，其边权之和为负数。如下图：可以看到，这个环的权值和是\((-2)+(-1)+1

\(\text{update2024/6/9:}\)文中提到了速度较快的\(\text{DFS-SPFA}\)，虽然速度较好，但是容易被卡，例如模板！大家好，我是Weekoder！今天要讲的是负环的一些习题与负环在题目中的应用。一共有\(3\)个例题，分别为：\(\color{#52C41A}\texttt{P2136}\)，\(\color{#9D3DCF}\texttt{P2868

题目由可达鸭提供，本篇够  字，阅读时注意休息和暂停。一、课时提交情（AC情况）T1、武士风度的牛  100/100（老师带着做的。）T2、抓住那头牛100/100T3、仙岛求药  100/100T4、TheCastle 0/100（时间不够了，就看了看题目。）二、目录T1、武士风度的牛T2、抓住那头牛T

题面：给你一个$n$个点$m$条边的有向图，第$i$条边$a_i$，$b_i$，$c_i$，表示一条单向边从$a_i$到$b_i$，长度为$c_i$，可能会有重边和自环。问能否从第$i$号点出发然后回到该点形成一个环？可以则输出最短时间，否则输出$-1$。思路：不难发现本题考查的是最短路。观察题面，发现边数

CF1575E思路点分治，记录当前子树到分治中心的权值和和换车次数。将新子树的答案合并时分类讨论分治中心到子树祖先\(u\tov\)的颜色。树状数组维护前缀和。复杂度\(O(n\log^2n)\)。codeintn,k,a[maxn],ans;inthead[maxn],tot;structnd{ intnxt,to,fl;}e[maxn<<1];

学习目标 引例 深搜遍历     [【图的遍历进阶】有向图中的可达]【算法分析】从a点广搜，并用vis数组标记从a能够到达的点，如果visb​=true，则表示能够到达，否则反之。【参考代码】#include<bits/stdc++.h>usingnamespacestd;constintm

学习C++从娃娃抓起！记录下在学而思小猴编程学习过程中的题目，记录每一个瞬间。侵权即删，谢谢支持！附上汇总贴：小猴编程C++|汇总-CSDN博客【题目描述】六面世界的地图由六边形格子组成，地图一共n行，奇数行有m格，偶数行有m-1格。下图是一个n=5，m=5的地图。小明想从起点S走到终点

题意一个家庭用一颗树来表示。其中有m个人买了保险，x[i]买的保险可以继承y[i]代，请问有多少人至少有一份保险思路感觉是比较水的E题了，我们采取bfs遍历，然后类似于最短路的想法来更新每个点可以继承的最大保险代数。最后扫一遍所有人，看他们的dis有多少大于等于0，即为答案（dis最初所有