Veröffentlicht am | in

代码：

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/Codeforces/%23330(Div%202)

A Vitaly and Night

题意：

很简单，自己看。

题解：

直接按照题目的意思统计答案即可。

B Pasha and Phone

题意：

序列$C$长度为$N$，将其分成$K$块，使得第$i$块都能被$a_i$整除，并且第$i$块的开头不是$b_i$，问你有多少种$C$

题解：

按照乘法原理统计答案即可，需要容斥的计算每一块的答案，需要特判$b_i==0$的情况。

C 被吃了，可恶

D Max and Bike

题意：

就有一个奇怪的圆在数轴上滚，上面有个传感器，当这个传感器的横坐标为$s$的时候开始计时，在横坐标变成$f$的时候停止计时，速度恒定，问你最短的时间。

题解：

将整个过程考虑为中间的整数圈和两头非整数圈两部分，那么现在考虑这样一个策略，在时间一定的时候，怎样让圆走得尽量远，很明显，只要让传感器在开始和结束的时候纵坐标一致即可。
感受一下，发现是可以二分的，所以就对$t$二分，然后由上述策略，可以唯一确定当前能走的最长路径，然后check一下就好。

Veröffentlicht am | in

介绍

这次来讨论一下空间滤波，顾名思义空间滤波就是在空间上，即像素的分布上着手来处理图片。本文会介绍空间滤波在平滑和锐化上的作用，和酷炫叼炸天的效果。(●’◡’●)
这篇讲平滑，下一篇是锐化

一些概念

滤波

滤波是频域上的概念，不过这里借用一下，因为本质上达到一个差不多的效果。

卷积

卷积的说明请参考我前面写的《深入浅出讲解卷积》

模板

一个二维矩阵，作用是加权原图像的像素点来产生新的一个像素点，具体会在后面讲到。

Weiterlesen »

Veröffentlicht am | in

卷积是什么？

离散域

离散域的要简单得多，所以我先讲离散域的。
下文中的$*$表示卷积，而不是乘法。

卷积这名字听着就是高大上，但却是个非常简单实用的概念。
通常意义下，卷积描述的下面这种运算：
$$y[n]=\sum_{a+b=n} x_1[a]x_2[b]$$
其中$x_1$和$x_2$是两个序列，$y$是卷积出来的序列。

是不是发现上面这个公式简单粗暴，比信号书上好看的多，当然信号书上会给你这么一个公式：
$$y[n]=\sum_{a=-\infty}^{a=+\infty} x_1[a]x_2[n-a]$$
你会发现这两个公式说的是同一个东西，但是，却会给出不同的计算卷积的方法。
信号书会告诉你卷积计算要分以下三步：

翻转
平移
求和

Weiterlesen »

Veröffentlicht am | in

本文地址：
http://harryguo.me/2015/11/06/%E6%95%B0%E5%AD%97%E5%9B%BE%E5%83%8F%E5%A4%84%E7%90%86%EF%BC%881%EF%BC%89-%E7%9B%B4%E6%96%B9%E5%9B%BE%E5%9D%87%E8%A1%A1%E5%8C%96/

什么是直方图均衡化？

为方便起见，本文前面讨论的都是黑白图像（灰度图），后面会特别提及彩色图像。

我们知道，一幅图像的灰度值可以看成一个随机变量，不妨设现在图片的灰度值是$r$，直方图均衡化后的灰度值是$s$。
$r$的概率密度函数（PDF）可能是这样一个乱七八糟的样子：
"变换前概率密度"
这样的概率密度是我们不希望看到的，我们希望整个图像能够均匀的占据灰度的整个区间：
"变换后概率密度"
这便是直方图均衡化。

Weiterlesen »

Veröffentlicht am | in

题意：

给你一个排列，每次拿走一个数，并且询问拿走前有多少逆序对。

题解：

明显是不能暴力的。那么想想逆序对是怎么求解的，逆序对的归并排序的方法本质上就是CDQ分治。所以，现在我们将时间作为新的一维加入逆序对的求解过程中。
令$de[i]$表示时间$i$去掉的那个数会减少多少逆序对。
易得
$de[i]=count\{j|x_j < x_i,y_j>y_i,z_j>z_i\}+count\{j|x_j>x_i,y_j < y_i,z_j>z_i\}$
这样就将这个问题变成了一个三维偏序的问题了。得到以下算法：

Veröffentlicht am | in

代码：

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/Codeforces/%23329(Div%202)

A 2Char

题意：

给你一堆单词，然你选一些出来，使得选出来的最多含有两种不同的字母，并且要让总长最长

题解：

直接暴力选出来的字母是什么，然后统计答案就好。

B Anton and Lines

题意：

给你一堆直线，问你在$(L,R)$这个区间是否有交点。

题解：

这是一个经典的逆序对问题，可以参考我以前的做法：
http://harryguo.me/2015/11/03/ZOJ_3157-Weapon/
不过这道题很简单，不用统计有几个交点，所以就不用维护树状数组了，排个序就能知道答案。

D Happy Tree Party

题意：

给你一棵树，树的每条边上都有个权值。现在有一个操作是改变某条边的权值，有种询问是从节点a到节点b的所有的边权，依次除y，结果是什么。

题解：

要做这道题，首先你要明白，$ y/a/b/c=y/(abc) $，接下来就很简单了，就是个树链剖分的问题。不过这道题是个非常恶心的题目，其数据范围一不小心就会爆long long，所以应当使用对数来特判乘积。

Veröffentlicht am | in

题意:

给你一个序列，现在要让它变成递增序列，能进行的操作只能是交换相邻的两个数，并且交换的代价为这两个数的和。

题解：

就是一个升级版的逆序对，不过为了练习CDQ，我不用数据结构。
现在我们要处理的区间是$[L,R]$，令$m=(L+R)/2$那么考虑$[L,m]$已经处理好了，我们用$[L,m]$更新$[m+1,R]$的解。
由于已经将左边处理好了，所以打乱左边的顺序并没有什么影响。
所以现在将两边都从大到小排好序，然后用两个指针扫就能得到每个逆序对的贡献值了。
记得把右边的给排回去。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/HDU/2838.cpp

Veröffentlicht am | in

题意：

就给你一个无序的序列，问你中位数是什么

题解：

从内存限制可以看出来，这不是排个序就能解决的。
现在维护一个堆，这个堆有至少原序列一半的元素。现在采取这样的策略：

  • 如果新进来的数字大于堆中的最大的数字，那么调整中位数的指针
  • 如果新进来的数字在堆的区间内，那么把区间中最小的那个数给pop掉，并且把新来的数给push进去

那么最后就能得到一个把中位数覆盖的数列。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/URAL/1306.cpp