关于近期遭受一些网络攻击的声明

最近吧,偶然看日志,发现很多莫名其妙的对我这破站的攻击。。。有暴力ssh密码的,爆破admin后台的,xdebug攻击面的,莫名其妙。这只是我的个人网站,90%的文章都是acm算法题的题解,想不明白有什么好玩的。

如果有一些文章侵害到了哪位的利益请直接联系我, kkutis1989@gmail.com ,有话好商量(我不是1989年生的这是个伪装名字不用试密码了

[DP][扫描线][思维] Codeforces 1313D Happy New Year

题目链接

题意:

有 $m$ 个小朋友,圣诞老人有 $N$ 个咒语,第 $i$ 个咒语施展出来的话,可以给 $[Li,Ri]$ 范围内的小朋友一块糖果,对每个小朋友来说,他得到的糖如果是奇数的话就会happy,否则就会不happy。

现在要求求出当圣诞老人采取某种最优的施展咒语的策略(一些用了一些没用,具体不需要求出来)的时候,最多有多少个小朋友可以happy?

题目保证,每个小朋友最多被 k 个咒语覆盖到。

数据范围: $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$

题解:

(先吐槽下这题竟然2600分,这可是个div2D)

用扫描线的思想来做。

假设有一根竖直的扫描线在横轴上扫过去,那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化,我们设置这些点为关键点,当我们采取某种特定的策略的时候,两个关键点之间的数据是不会发生变化的。

由于每个点最多被 $k$ 个线段覆盖,我们可以暴力的枚举出来当前扫描到的点的状态,即它被多少种线段覆盖到了,这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的,而两个关键点之间的数据状态仅由前一个点即可确定,所以我们的dp转移只需要考虑前一个点。

具体的转移:设 $dp[i][S]$ 为考虑到了第i个关键点(按从小到大的顺序),覆盖当前点的线段状态为 $S$ 的时候,最优解是多少。

  1. 当当前点为某线段的起点时,我们考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段;(其中p为当前线段所应在的二进制位,下同)
    • 没包含,那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
  2. 当当前点为某线段的终点时,我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,由于这条线段到此我们认为结束了,所以这种状态根本不合法,直接设置为$-INF$
    • 没包含,那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,因为我们前面一段可能选了大,也可能不选更大,我们需要取个最优解。

然后我们可以发现两个转移都有方向性,我们可以用滚动数组忽略掉第一维,也就是说状态数组可以只开 $dp[1<<8]$ 即可。

继续阅读“[DP][扫描线][思维] Codeforces 1313D Happy New Year”

MathpixCsharp: 每个月可以免费用1000次的Mathpix Windows客户端 支持截图转Word公式 截图转Latex代码

鉴于一个月5美元对于国外友人的消费水平来说应该不是问题。。我就只写中文的readme了。。。

这个小项目的起因就是偶然有一天发现mathpix给开发者用的api的定价策略很神奇。。。

  • First 1000 requests free
  • $0.004/request (1-100K requests)
  • $0.002/request (100-300K requests)
  • $0.001/request (300K+ requests)

emm照这个价格原来每个月5刀的钱能用到秃头了。

于是就自己写了一个客户端,支持图片转word公式,图片转latex代码。申请到开发者接口之后把API key填进去就可以用了。(我愿称之为木兰mathipix)


继续阅读“MathpixCsharp: 每个月可以免费用1000次的Mathpix Windows客户端 支持截图转Word公式 截图转Latex代码”

[娱乐] 一个监控NIKE官网NBA球衣打折的QQ机器人

上次写的微信版机器人的爬虫已经失效了,这次重新搞了爬虫,平常用的qq比较多所以也换成了qq版。

需要准备:

  • Windows服务器一台,阿里云ECS即可(Linux也可以但是需要Wine,不如直接原生Windows)
  • QQ小号一个,用来作为发送消息的载体

首先到coolq的社区下载最新版的coolq air,图灵版或者小i版都行,无所谓,我们不会用到他们的ai。
继续阅读“[娱乐] 一个监控NIKE官网NBA球衣打折的QQ机器人”

JetBrains Quest 免费领取三个月全家桶 解密

首先看官推给出的这串代码

48 61 76 65 20 79 6f 75 20 73 65 65 6e 20 74 68 65 20 73 6f 75 72 63 65 20 63 6f 64 65 20 6f 66 20 74 68 65 20 4a 65 74 42 72 61 69 6e 73 20 77 65 62 73 69 74 65 3f

看上去是十六进制,猜测是ASCII,转码一下试试

得到了

Have you seen the source code of the JetBrains website?

那么根据提示我们来到jetBrains的官网看源代码,就找到了如下注释:

      O
{o)xxx|===============-
      O

Welcome to the JetBrains Quest.

What awaits ahead is a series of challenges. Each one will require a little initiative, a little thinking, and a whole lot of JetBrains to get to the end. Cheating is allowed and in some places encouraged. You have until the 15th of March at 12:00 CET to finish all the quests.
Getting to the end of each quest will earn you a reward.
Let the quest commence!

JetBrains has a lot of products, but there is one that looks like a joke on our Products page, you should start there... (hint: use Chrome Incognito mode)
It’s dangerous to go alone take this key: Good luck! == Jrrg#oxfn$

                 O
-===============|xxx(o}
                 O

看到了hint说使用Chrome的无痕模式,那我们无痕模式打开一下Products 页面。顺便,注意他的一句话:带上这个key Good luck! == Jrrg#oxfn$
继续阅读“JetBrains Quest 免费领取三个月全家桶 解密”

[数学] 向量函数的雅可比矩阵与链式法则

复习一下我的数学知识T_T

1. 回顾高等数学:多元数量函数的梯度

回想高等数学中常见的多元数量函数$f:\mathbb{R}^{n}\rightarrow \mathbb{R}^{1}$,我们可以把他的输入当作一个向量 $\bf{x}\in \mathbb{R}^{n}$,输出$y=f(\bf{x})\in \mathbb{R}^{1}$是一个数字。那么由高数的知识我们知道$f$的梯度定义为
$$
\nabla f_{\boldsymbol{x}} \overset{\underset{\mathrm{def}}{}}{=} \left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right]=\frac{\partial f }{\partial \boldsymbol{x}}
$$

有了上式,我们还可以写出全微分的向量化表示

\[
\begin{aligned}
df &= \frac{\partial f}{\partial x_1}dx_1+\frac{\partial f}{\partial x_2}dx_2+\cdots+\frac{\partial f}{\partial x_n}dx_n \\
&=\left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right] \left[dx_1, dx_2,\cdots,dx_n \right]^T \\
&=\frac{\partial f }{\partial \boldsymbol{x}} d\boldsymbol{x}
\end{aligned}
\]

接下来我们将其推广到向量函数。向量函数的“梯度”其实就是雅可比矩阵
继续阅读“[数学] 向量函数的雅可比矩阵与链式法则”

2019 kali 笔记本电脑 双系统 双显卡 配置nvidia显卡支持外接hdmi显示器

。。。绝大多数人都会照着官方的教程做,但是这个操作是针对只有一张nvidia显卡的台式机来说的,而不是笔记本的双显卡。。。。按照这个教程,装完之后是可以用这个gpu做运算的,但是不能用来做显示。。。插上外接显示器没有任何反应,用xrandr根本检测不到有外界显示器存在。

出现这个问题的原因是官方的配置里缺少了一步配置显示的操作。。。如果只有一张卡的话装系统的时候显示设置就配置好了,双显卡的话默认的显示用的是核显,独显根本没管,所以我们要手动操作一下。

注意:在参考本配置之前请务必先按照官网Doc走一遍,确保gpu驱动已经装好,可以进行运算测试之后再进行。

我的kali版本

Linux 5.3.0-kali2-amd64 #1 SMP Debian 5.3.9-3kali1 (2019-11-20) x86_64 GNU/Linux
  1. 首先安装kernel headers,不然驱动编译可能会出问题
apt install linux-headers-$(uname -r)

继续阅读“2019 kali 笔记本电脑 双系统 双显卡 配置nvidia显卡支持外接hdmi显示器”

[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree

题目链接

题意:

给定一棵树,每个节点上有 $a_i$ 个苹果,两个人轮流操作,每次把一个节点的一部分(或全部)苹果移到他的某个儿子中(如果是叶子节点没有儿子那么就吃掉这些苹果),最后不能走的人输。现在在游戏开始前先手可以选取两个不同的节点交换他们之间的苹果数,问有多少种交换方式可以使得先手必胜。
数据范围: $1\le n \le 10^5,\;1\le a_i \le 10^7$

题解:

博弈本身是很简单的阶梯博弈。由阶梯博弈的知识,求胜负只需要计算奇数位上的SG函数异或和即可,这题只不过把阶梯转移到了树上,但是略微分析就可以发现和链状的阶梯是没有区别的,都是奇数往偶数转移当作拿走,偶数往奇数转移就对称操作。

  • 然后考虑计数:
    • 假设初始状态是必胜态,那么可以先计入奇数层自己内部交换和偶数层自己内部交换的对数,分别为 $C_{num\;of\;odd\;level}^2$ 和 $C_{num\;of\;even\;level}^2$;
    • 然后计算奇偶层之间互换的对数,设异或和结果为 $ans$ ,假设一对数 $a_u$ $a_v$ 交换之后可以使得 $ans=0$ ,那么由亦或的性质可得 $a_v=ans\oplus a_u$,那么我们就可以枚举 $a_u$ 的值,找 $a_v$ 有多少个,而后者利用 $map$ 可以很容易的预处理出来。
      继续阅读“[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree”

[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++实现”

[比赛补题][线段树][连通分量][二分图] 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)”