Pac-man —— 对抗搜索 对Pac-man游戏编写基于minimax搜索的智能体，CS188经典实验：Project Link：CS188-Pacman Github Link:Click here My code download: Click here Problem one: Reflex智能体 一个粗略的评估函数，综合了被Ghost吃到的风险以及吃豆得分，简单评...
LaTeX
入门视频: Click here 在线LaTeX编辑器：https://www.overleaf.com TeX Live下载：https://www.tug.org/texlive/acquire-iso.html MikTeX 下载：https://miktex.org/download LaTeX 公式编辑器：https://latex.codecogs.com/eqneditor/e...
2022湖北省赛 J Palindrome Reversion
Link here 一道我入门的字符串哈希题 说起来也很离谱，我居然现在才学字符串哈希，还是太懒了（不过也就学了30min） 题意 就是一个字符串，反转一个区间使得其成为一个回文串 Solution /* Mario Chan 2022/9/21 Shenzhen University */ #include<bits/stdc++.h> #include<cti...
String Hash
blog 自然溢出 unsigned long long base = 13, hash[MAXN], p[MAXN]; // hash[i]表示[0]-[i]子串的hash值，p[i]表示base^i hash[0] = 0, p[0] = 1; /* hash[i] = hash[i-1]*base + (s[i]-'a'+1), 字符串下标从1开始 */ 单哈希 const lon...
KMP
时间复杂度：O(m+n) static int* getNext(const string& s) { // 对于模式串求失配指针next int j = 0, k = -1, len = s.size(); // 因为后面本来要s.size()-1，所以最好提前用int存储，避免极端数据卡无符号整型 int* next = new int[len]; next[0] = -1...
template
缺省源 /* Mario Chan 2023/02/04 Shenzhen University */ #include <bits/stdc++.h> #define LL long long #define INF 1e9 #define MAXN 100005 //#define mod 998244353 //#define mod 1000000007 /* --D...
STL course
课程内容 课件下载：Click here 链表的数组实现 STL简单介绍 + iterator vector stack sort map 二分 queue list Tips: 如果你的编译器是dev-c++，请点击工具-编译器选项-在第一个代码框内输入-std=c++11，并勾选加入命令，然后确认 推荐预习内容 STL详解: Clic...
珂朵莉树ODT
set实现的珂朵莉树复杂度为 O ( nlog（n）) 珂朵莉树可以用来解决含有区间覆盖(或者是区间统一赋值)的操作，本质上是std::set的数据结构，对于随机数据来说效率很高甚至有时候比正解还高 注意这种数据结构只在数据随机的情况下表现良好 将 [l,r] 区间内所有数加上 x 将 [l,r] 区间内所有数改成 x 求 [l,r] 区间第 k 小的数 求 [l,...
树链剖分
就是个板子没啥好说的。 #include<iostream> #define MAXN 100005 using namespace std; int val[MAXN],n,m,from,to,op_code,x,a; int id[MAXN], top[MAXN], new_val[MAXN], tot=0; // 到时候用va给线段树赋值 //============...
2-sat
2-SAT是k-sat适定性(Satisfiability)问题中，k=2 问题的简称，就是有一些集合，每个集合中有且仅有两个元素，同时每个集合需要选择一个作为代表，集合间的元素存在一定的选择关系，求解可行性及可行方案。 时间复杂度：O(n+m) p||q -> (!p==q) && (!q==p) 我们一般用i表示false，用i+n表示true #in...
LCA
注意树上差分问题是从叶子往上回溯统计，–LCA,–LCA.father, 有时候要注意某个点是另一个点的LCA 还有u->v的路径可能走的是u的儿子节点，不一定是father，想清楚 Code #include<iostream> #include<stdio.h> using namespace std; struct node { int to,next;...
换根dp
日常先上blog 第一次扫描作预处理 第二次递归求解 给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 一个结点的深度之定义为该节点到根的简单路径上边的数量。 #include<iostream> #define MAXN 1000006 using namespace std; struct EDGE { int to, next; }...
拓扑排序
int in[MAXN];//记录入度 vector<int> answer;//记录拓扑序列 void topo() { queue<int> Q; for(int i=1;i<=n;i++) { if(!in[i]) Q.push(i); } while(!Q.empty()) { int now=Q.front(); Q.pop();...
差分约束
blog 1， blog 2， blog2写的好啊 本质上是SPFA（有负边）最短路模型 判断有解： 有负环：无x[t]-x[s]最大值 如果不是弱连通图：最大值无限大 最小值问题 把符号改变一下并跑最长路问题 不等式的标准化 如果既有>=又有<=： 如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路 ...
欧拉回路 —— Euler circuit
欧拉通路： 对于图G来说，如果存在一条通路包含G的所有边，则该通路称为欧拉通路，也称欧拉路径 欧拉回路： 如果欧拉路径是一条回路，那么称其为欧拉回 欧拉图： 含有欧拉回路的图是欧拉图，具有欧拉路径但不具有欧拉回路的图称为半欧拉图 弱连通图： 将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。 (不带重边) blog 有向图欧拉路...
Newcoder Contest-33195 E Reviewer Assignment
题目出自”蔚来杯”2022牛客暑期多校训练营10 Click Here 最小费用最大流解法 最大流解法 二分图匹配解法 题面： gispzjz likes playing DotA2 and has recently become the chair of the celebrated conference SODA (Symposium on DotA2) in the com...
最小生成树 —— Minimum-Spanning Tree，MST
一个图中可能存在多条相连的边,我们一定可以从一个图中挑出一些边生成一棵树。这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。 Key: 一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案...
网络流 —— Network Flow
基础 -> Ford-Fulkerson算法，可以应用于线性规划问题 最大流 最大流：把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。 搬运视频 暴力最大流 —— FF 深搜单路增广，每次只找一条路，这条路还可能绕远路（可能经过 n 个点才到达汇点），而且增加流量是路上最小的权值，容易被卡 #include<...
二分图
二分图判断 二分图又称为二部图，其定义是：设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集，则称图G为二分图。 无向图G为二分图的一个充要条件是： G中至少包含两个顶点 G中所有的回路长度都必须是偶数 也就是说，一个图是二分图的充分必要条件是这个图不包含长度为奇数的圈。 dfs实现 bool d...
CS 61A
Here is the Link Using OK Using OK kjfYou can press`--local`to confirm OK also. **Test specific questions** To test a specific question, use the -q option with the name of the question: `python...