[线性基][线段树][模板] 牛客多校第四场 B xor

题目链接

题意:

$n$ 个集合,每个集合最多32个unsigned int范围的整数, $m$ 个询问,每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$,每个数字都在 unsigned int 以内。

题解:

线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”

[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论

题目链接

题意:

给定一个长度为 n 的字符串,让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ,$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.

题解:

后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点,反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来,然后在t=1的时候,根据sam的性质,给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序,比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识,他其实无论是slink还是dwag的拓扑序都是一样的,因为无论哪种都一定是从小的子串往大的走。
继续阅读“[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论”

[CV][经典算法] Grab Cut C++实现

暑假时候复现的一篇计算机视觉经典抠图算法grabcut的论文,“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts

代码存一下,虽然我转行了不搞cv了hhh

myGrabCut.h

#pragma once

#include<graph.cpp>
#include<opencv2/opencv.hpp>
#include <opencv2/core.hpp>
#include <opencv2/core/types.hpp>
#include<string>
typedef Graph<double, double, double> GraphType;

using namespace cv;


class GMM {
public:
	Mat model;
	static const int compo_k = 5;
	double coefs[compo_k];
	double mean[compo_k][3];
	double covs[compo_k][3][3];
	double inv_covs[compo_k][3][3];
	double det_covs[compo_k];
	double sums[compo_k][3];
	double prods[compo_k][3][3];
	int sample_num[compo_k];
	int tot_sample_num;

	GMM();
	void calc_inv_det(int ci);
	double prob_GMM(const Vec3d color) const;
	double prob_Gi(int ci, const Vec3d color) const;
	int sle_compo(const Vec3d color) const;
	void init_param();
	void add_pixel(int ci, const Vec3d color);
	void esti_param();

};


static double calcBeta(const Mat& img);
	
/*
  Calculate weights of noterminal vertices of graph.
  beta and gamma - parameters of GrabCut algorithm.
 */
static void calcNWeights(const Mat& img, Mat& leftW, Mat& upleftW, Mat& upW,
	Mat& uprightW, double beta, double gamma);

/*
  Check size, type and element values of mask matrix.
 */
static void checkMask(const Mat& img, const Mat& mask);

/*
  Initialize mask using rectangular.
*/
static void initMaskWithRect(Mat& mask, Size imgSize, Rect rect);

/*
  Initialize GMM background and foreground models using kmeans algorithm.
*/
static void initGMMs(const Mat& img, const Mat& mask, GMM& bgdGMM, GMM& fgdGMM);

/*
  Assign GMMs components for each pixel.
*/
static void assignGMMsComponents(const Mat& img, const Mat& mask, const GMM& bgdGMM,
	const GMM& fgdGMM, Mat& compIdxs);

//论文中:迭代最小化算法step 2:从每个高斯模型的像素样本集中学习每个高斯模型的参数
/*
  Learn GMMs parameters.
*/
static void learnGMMs(const Mat& img, const Mat& mask, const Mat& compIdxs, GMM& bgdGMM, GMM& fgdGMM);

/*
  Construct GCGraph
*/
static void constructGCGraph(const Mat& img, const Mat& mask, const GMM& bgdGMM, const GMM& fgdGMM, double lambda,
	const Mat& leftW, const Mat& upleftW, const Mat& upW, const Mat& uprightW,
	GraphType*& graph);

/*
  Estimate segmentation using MaxFlow algorithm
*/
static void estimateSegmentation(GraphType* graph, Mat& mask, std::vector<double>& result);

void mygrabCut(InputArray _img, InputOutputArray _mask, Rect rect,
	InputOutputArray _bgdModel, InputOutputArray _fgdModel,
	int iterCount, int mode);//,std::vector<double>& result);

主程序代码,其中最大流最小割直接用了maxflow-v3.01的库,其他调用了一些OpenCv的基本接口我不会说我就是照着OpenCv的库函数写的
继续阅读“[CV][经典算法] Grab Cut C++实现”

[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing

题目链接

题意:

要求给一片文章排版,要求每行 $W$ 个格子,每一行的要求是首单词必须顶格,除了最后一行之外的尾单词也必须顶格,然后单词之间至少有 $1$ 个空格,单词内部不能有空格,也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下,单词之间的最大空格最小是多少。数据量: 每一行的格子数: $3\le W \le 80,000$, 总共的单词数:$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
继续阅读“[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing”

[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish

题目链接

题意:

给定一段代码,让模仿出来他的代码缩进风格。缩进风格由三个数字 $R C S$ 确定,分别代表到当前位置有多少个未封闭的圆括号/花括号/方括号 ,然后每多一个 $R/C/S$ 的话,多出来的缩进数是确定的。现在要求用学习到的代码风格对新的一段没有缩进的代码进行缩进,输出每行缩进的空格数。数据范围行数 $N\le 80$ , 每行最多80个字符。

题解:

显然难点在于能不能用已经学到的经验来推断出来现在该缩进多少。把所有 $(r,c,s)$ 的三元组看成一组向量,等于说新的向量能不能被之前出现过的表示出来,也就是是否线性相关。那么我们只需要用高斯消元去解就行了,如果有唯一解那么一定是可以被表示出来的,这是后这个就能解出来了,如果不是的话就把这个新的向量插进去作为一个新的基。

这个题当时的问题就在于没有一个好的高斯消元板子。。。于是很正经的去找了一个好的板子TAT

wa点:没注意到题目说RCS最多只有20个最少至少有1个。。。这个限制导致了在某些情况下方程解不出来但是仍然可以确定RCS的数值。

继续阅读“[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish”

[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)

题目链接

题意:

给定 $N$ 个人,每个人可以选择加入黑暗 $Dark$ 或者光明 $Light$ 两种阵营,他们加入不同的阵营之后获得的力量值是不同的,即 $D_i$ 和 $L_i$ 。然后有些人之间有矛盾,是不能加入同一阵营的,矛盾的对数共有 $M$ 对,现在给出所有的矛盾和所有的 $L_i D_i$,问在所有可能存在的最终阵营分配情况中,力量值最大的人和力量值最小的人之间的差最小可能是多少?如果说不可能分配的话输出$IMPOSSIBLE$。其中 $1\le N\le 2*10^5$, $0\le M\le 2*10^5$, $1\le L_i D_i \le 10^9$ ,共20组test,时限4S

题解:

一个非常有意思的,看上去像是图论其实是数据结构的题目。。其实以前做过类似的?应该是今年西安邀请赛时候,区别在于那个题目应该是一种背包的性质,一个联通分量要么选,要么不选,而这个题是每个连通分量都得选,但是要从两套孪生方案中选择一种,每一种都会有一个最大值和一个最小值。

把两两不能在一起的人之家连一条无向边,那么一堆互相有关系的人就形成了一个连通分量,不在同一个分量里的人互相是完全没有影响的,无论这个人是选择D还是L都跟我的选择没关系。而在同一个联通分量里的情况的话,可以发现只要有一个人的状态确定了就可以用二分染色的方法确定连通分量里其他所有人的状态。因此我们首先用染色法对每个连通分量判定,如果能染色成功那么就说明有可行解存在,否则输出$IMPOSSIBLE$,另外,在dfs的过程中还要顺便把每个连通分量的两种方案的最大值最小值总共四个数分别求出来(这里我当时就写假了emmm)。之后考虑如何让差值最小化,一般让某个东西最小化很容易想到二分,但是这个题目的条件下,如果要二分就必须再 $O(n)$ 枚举一个下界,乘上 $O(n)$ 的check的话就n方了,显然无法接受。这时候观察这个题目,此时的每个元素(连通分量)正好有两个属性,发现我们可以用一个常用的套路来尝试,那就是按照其中一个属性排序然后对另一个属性套某种log的数据结构。。对这个题来说,回想我们刚才考虑的二分,他必须有一个操作就是枚举出一个下界or上界,那么如果我们就着这个操作进行下去会怎么样?如果我们能一边枚举一边很快的计算出来当当前枚举到的最小值是最小值的时候最大值最小是多少,那么这个问题就可以解决了。
继续阅读“[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)”

[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game

题目链接

题意:

题意:有一排 $n$ 个灯,可以是红色或者蓝色,然后k个人投票,每个人投的票会写上他猜测的某三盏灯的颜色。然后现在问是否有一种红蓝灯的安排方式使得每个人投的票至少有2个猜测是对的。

题解:

$2-SAT$ 板子题,但是比赛时候忘记了(主要这东西在中国真的很少考emm)相当于求让每个人的条件都为真的一组二进制向量。那么现在的问题就是怎么把每个人的约束条件转化为 $2-SAT$ 的子句的形式。

首先用 $x_1$ $x_2$ $x_3$ 表示一个人的三个选择,那么代表这个人的子句用文字表达来说就是 $x_1 x_2 x_3$ 中有2个或者3个为真。用条件的知识可以推出来这个说法等价于 $(x_1\lor x_2 )\land(x_1\lor x_3)\land(x_2\lor x_3)$ ,这样就把每个人的条件写成 $2-SAT$ 的形式了,接下来按板子连通分量+拓扑排序求解就OK了。

继续阅读“[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game”

[比赛补题][线段树+][动态维护矩阵乘法][动态dp][区间lr问题] codeforces 750E New Year and Old Subsequence

题目链接

题意:

类似上一题,给定一个长度2e5的字符串,2e5个询问,每次问从区间 [l,r] 里面最少删去多少而可以使得结果中存在2017但是不存在2016。这个是比较好的一道题,之前我从没来遇到过动态维护动态规划的。。。这叫什么,动态动态规划?(雾)

题解:

首先考虑简单版的问题,如果不考虑查询,单次做问整个序列最少去掉多少该怎么做?我当时是考虑了很多,但是如果按照正常的考虑方式的话就会越想越复杂,不知道该维护什么样的一个状态。该以什么作为状态呢?如果按照状压的思路会发现无法转移,因为他这个2016和2017都是有顺序的啊,不能状压搞,但是也不能把前面的所有情况搞出来,复杂度会爆炸。看了题解发现有人提正则表达式和有限状态机才明白了。。。之前做的那个题简单是因为他很好转移,是不包含当前前缀时最少需要删除多少,而这个题目的状态需要定义为包含当前状态机节点对应的前缀且不包含严格包含当前状态机节点对应的前缀最少需要删除多少个字符。。。意思就是20的时候不能有201和2017的时候的需要删除的最少字符。。

然后考虑状态的转移,这个有限状态机可以匹配出来2017,但是匹配出来之后呢?我们应该拒绝掉所有的2016,注意这时候,从状态2017和201都可以转移到2016,所以我们当前如果已经匹配完且达到2017/201的时候,转移回到本身都需要多删掉一个字符,也就是本身。。。其他情况是如果要往下一个节点走的时候,回到自身的代价是1,往下走的代价是0.。。其实也就是一个选择,选择当前的这个字符留还是不留,,,,跟谁匹配的话比较好。。

然后他很妙的一点就是这个转移可以写成矩阵的形式,当然这不是一个矩阵乘法,是一个很怪的操作,类似Floyd最短路的方法,然后这个矩阵操作是满足结合律的(我也不知道为什么满足结合律)。。。。就可以用线段树维护了。。。

甚至说这个题甚至可以改成带修的。。

继续阅读“[比赛补题][线段树+][动态维护矩阵乘法][动态dp][区间lr问题] codeforces 750E New Year and Old Subsequence”

[DP][子序列][有限状态机][正则表达式] codeforces 1096D Easy Problem

题目链接

题意:

给一个长为1e5的串,问至少去掉多少个字符后该串中不包含hard这个子序列。

题解:

连续两场有类似的这样的题目搞砸了,心情复杂。

这个是比较简单的版本,当时真的怎么就没想到用有限状态机来表示呢。。。还是naive,太菜了。。。

用 dp[i][j] 表示到第 i 个位置为止,使得前缀为j长度的hard的子串不出现至少需要删除多少个字符。状态转移很简单,当为char==h&&j==0的时候dp[i][j]=dp[i-1][j]+1;
其他的就是枚举最后一步决策,按照删当前的还是不删当前的来分就行了。

这题搞砸真的非常难过,非常难过

继续阅读“[DP][子序列][有限状态机][正则表达式] codeforces 1096D Easy Problem”

[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem

题目链接

题意:

给一个长度1e5的序列,两种操作:操作1 把区间内元素都乘以一个v,操作2:把区间内元素都变为原来的k次方

然后有1e5个询问,问 $[l,r]$ 之间的区间积

题解:

线段树上双标记问题。维护两个 $lazy tag$ ,一个负责次幂一个负责乘,其实相当一个加法和一个乘法然后求区间和。我这里维护的思路是每次都保证维护的点是一个 $k*(a_l a_{l+1}… a_{r} )^w$ 这样一种形式。这样的话每次标记下传的时候,先把w的次幂传下去,注意这时候儿子的k也要变成 $k_{son}^w$ ,然后再把k传下去,即给儿子的 $k_{son}$ 再乘上 $k$ ,这两个顺序搞清楚之后就很好写了。

wa点是,维护$w$次幂对质数取模的时候不能写 $\%mod$ ,而应该用欧拉定理降幂, $\%(mod-1)$ 貌似我因为这个错过很多次了听说用BSGS预处理的话会更快不过我没试过emmm

继续阅读“[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem”