CDOJ 1261 被神选中的人

Veröffentlicht am 2015-12-11 | in ACM

模型的转换

尝试回答这样的问题：

现在我有三个球，其中一个抽中就会游戏结束，其中一个抽中了就会中奖，另外一个抽中了会再来一次。那么中奖的概率是多少呢？怎么看待这个问题是解决问题的关键，如果从每一步的决策上来看，似乎是和1/3有关的一个无穷级数。但是我们这样想，来一次的球一点用都没有，这是显然的，那么概率自然就是1/2

让球可以消失

现在这个问题变成了，如果有多个再来一次的球，并且抽中再来一次的球后，这个球就会消失。那么最后中奖的概率是多少呢？很明显也是1/2，这是由于就算会减少，但是也并没有影响到中奖和结束的球，可从上面的模型中得到这个结论。

和此题的关系

此题中抽中神卡，就和球消失一样，并没有影响魔卡。所以我们能得出，神卡在这个游戏中并没有什么卵用。所以这个游戏只和魔卡有关系。

如果$m$是奇数

很明显，无论怎样都会留下奇数张的魔卡，那么方块A必死。

如果$m$是偶数

这时候如果要让方片A活下来，那么方片A必须最后被抽走。我们可以把魔卡排成一排，然后将方片A插入，如果方片A要活下来，当且仅当方片A在最后，而插入的总可能性有$m+1$种，所以最后的概率的倒数就是$m+1$

判断素数及分解质因数

Veröffentlicht am 2015-12-09 | in ACM

如何判断一个数是否是素数

$O(\sqrt{n})$的朴素算法

自然，一个数是素数，则不应该存在一个数能整除它，而一个数$n$的所有因子都是关于$\sqrt{n}$对称分布的，所以只用检测$[1,\sqrt{n}]$的范围内是否有这个数的因子即可。

bool check(int n){
	if(n<=1)return 0;
	for(int i=1;i*i<=n;i++)
		if(n%i==0)
			return 0;
	return 1;
}

埃氏筛法

讲起来很麻烦，所以给个wiki的链接。
这是一个$O(nloglogn)$的算法，算是非常快的了（其实还能去掉一个log，不过效果不明显）
由埃氏筛法的想法，我们先去掉某个素数的倍数再来判断即可。

bool isPrime[MAX_N];
int allPrime[MAX_N],tot=0;
void getPrime(){
	memset(isPrime,1,sizeof(isPrime));
	for(int i=2;i<MAX_N;i++){
		if(!isPrime[i])continue;
		allPrime[tot++]=i;
		for(int j=2*i;j<MAX_N;j+=i)
			isPrime[j]=0;
	}
}

米勒-拉宾素性检验

这是个很奇怪的算法，大家可以不学，此算法用的是一种概率的方式来猜测一个数是不是素数，一般不会出错。还是给个wiki的链接。
代码就不给出了

如何分解质因数

大家小学都学过短除法，现在就只需要用程序来模拟短除法的过程即可。
由于短除法需要遍历素数，所以先用埃氏筛法把素数存起来是很方便的。

int allFac[MAX_N],facNum=0;
void getFac(int x){
	while(x>1){
		if(x%allPrime[i]==0){
			x/=allPrime[i];
			allFac[facNum++]=allPrime[i];
		}
		else i++;
	}
}

第七届ACM趣味程序设计竞赛第二场（正式赛）

Veröffentlicht am 2015-12-06 | in ACM

昊昊爱运动

前缀和

要做这道题首先要会前缀和这个技巧。现在给出一个不变的序列$A$，每次询问$[L,R]$这个区间内的和该怎么做呢？既是求：
$$\sum_{i=L}^RA_i$$
如果每次都从$L$加到$R$将是一个不小的花费，所以我们可以选择间接地求解，即：
$$\sum_{i=L}^RA_i=\sum_{i=0}^RA_i-\sum_{i=0}^{L-1}A_i$$
后面的两项既是前缀和，是可以扫一遍就得到的序列：

1 2	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

每次询问$[L,R]$的和的时候就返回sum[R]-sum[L-1]就好了。

关于这道题

有了前缀和的知识，这道题就迎刃而解了。如果第$i$个位置上有颜色$c$，那么a[c][i]=1，否则a[c][i]=0，然后对每个颜色都构建前缀和。每次询问的时候，只要检查每个颜色在这个区间的和是否是0即可。

代码：

https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1256.cpp

最小二乘法

Veröffentlicht am 2015-12-03 | in 数学讲解

什么是最小二乘法

嗯，通俗的讲，就是让一些数据进行线性的拟合，使得我们找到数据间的线性关系，从而实现预测数据。很多大数据的算法都是基于最小二乘法。

通过最小二乘法，我们就能从上方的数据（红色）中拟合出一条直线（蓝色）。

Codeforces #333 div2

Veröffentlicht am 2015-12-02 | in ACM

代码：

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

Two Bases

题意：

给你两个不同进制的数，让你比较大小。

题解：

直接转换到十进制比较就好。

Approximating a Constant Range

题意：

给你一个序列，这个序列中相邻的元素之间的差值不超过1，求一个最长的子串，使得这个子串中最大值和最小值的差不超过1。

题解：

直接用两个指针$i,j,i\le j$表示这个串的头尾，向后扫如果$j$的位置大于$[i,j]$中的最小值加一，就让$i$跳着往前走就好，如果小于区间最大值减一，也让$i$跳着往前跳。整个过程维护两个RMQ表就好，不过这道题也可以dp。

The Two Routes

题意：

有个完全图，边权都是1，部分边是公路，部分是铁路，现在火车和汽车同时从1号节点出发前往n号节点，中途不能同时在一个节点相遇，可以在n号节点等另外一个交通工具，现在问你最短时间，使得两个交通工具都在n号节点。

题解：

这里有个巧妙地地方，由于边权都是1，并且是完全图，由三角形不等式，两个交通工具绝对无法相遇。所以直接spfa两边就好。

Lipshitz Sequence

题意：

给你个序列，每次询问时$[L,R]$内所有的连续序列的利普希茨常数的和。

题解：

此题做法非常的巧妙，首先我们来想想这样一个问题，对于一个连续函数$f(x)$而言，在区间$[L,R]$中是否一定存在一个斜率的绝对值$|k|$，使得$|k|\ge L,R的连线$？仔细想想后发现这是一定存在的，所以在离散域中，利普希茨常数一定存在与相邻的元素。所以直接维护一个RMQ，然后再二分就好。详见代码。

Codeforces #332 div2

Veröffentlicht am 2015-11-21 | in ACM

代码：

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

Patrick and Shopping

题意：

现在有三个点三条边构成的图，问你从一个点出发访问完另外两个点，再回到当前点的最短路是多少。

题解：

四种情况，讨论讨论就好。

Spongebob and Joke

题意：

现在给你一个映射表，并给你映射后的集合，问你能否得出映射前的集合，是否有多解。

题解：

就瞎比搞搞就好，由于原来的集合保存的是位置的信息，所以把映射表的位置和值反过来存，然后讨论一下就好。不过要注意无解的优先级要高于多解。

Day at the Beach

题意：

给你一个序列，问你最多能将这个序列分成多少个连续的块，使得每个块中排序后，整个序列是有序的。

题解：

这题我们使用贪心的想法，从左往右扫，如果当前能够分，那就分。而能分的前提条件就是当前前缀的最大值小于等于当前后缀的最小值。

Spongebob and Squares

题意：

给你一个$x$，问你有多少组$n,m$使得，以$n*m$构成的长方形中，恰有$x$个正方形。

题解：

令$f(n,m)$为以$n,m$为边长的长方形中正方形的个数。
那么令$n\leqslant m$
$$f(n,m)=\sum_{k=1}^{n}(n-k+1)(m-k+1)$$
展开整理得：
$$f(n,m)=(n^2+n)m+n^2+n+\sum_{k=1}^{n}-(n+m+2)k+k^2$$
收拢整理得：
$$f(n,m)=(\frac{n^2}{2}+\frac{n}{2})m+n^2+n-\frac{(n+2)(n+1)n}{2}+\frac{n(n+1)(n+2)}{6}$$
然后发现这是$m$的一次方程，由于有$n$的三次方项，所以可以通过枚举$n$的方式来计数，不过枚举的上限要仔细计算，不然会挂（我就是这么挂的！悲剧！）

Educational Codeforces Round 1

Veröffentlicht am 2015-11-18 | in ACM

代码：

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/Codeforces/Educational%20Codeforces%20Round%201

Tricky Sum：

题意：

求个和，其中2的指数项都取相反数。

题解：

就等差数列减等比数列就好

Queries on a String：

题意：

给你一个字符串，每次操作可以把一段区间循环滑动若干次，问你最后的串。

题解：

由于数据范围很小，所以直接暴力就好。然后开个数组记录每一位被滑倒哪了

Nearest vectors：

题意：

给你若干向量，问你从中任意选择两个向量能形成的角度最小是多少？

题解：

直接极角排序，然后扫一遍即可。不过注意用long double

Igor In the Museum:

题意：

由一个方格网络构成的博物馆，其中有些是房间，有些是墙，墙上有画，现在询问一个坐标的房间能看几幅画

题解：

直接模拟

Chocolate Bar：

题意：

给你个n*m的巧克力，掰开的花费为掰的长度的平方，问你最少用多少花费能掰出大小和为k的若干方块。

题解：

令$dp[i][j][k]$表示将大小为$i*j$的巧克力得到总和为$k$的巧克力的最少花费，然后向区间dp那样做做就好。

Codeforces #331 div2

Veröffentlicht am 2015-11-16 | in ACM

代码：

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

Wilbur and Swimming Pool

题意：

一开始有4个点构成长方形，现在删除其中的若干点，问恢复原长方形是否是唯一解。

题解：

直接模拟就好，不过算面积的时候最好用最大值减最小值这种方法来计算

Wilbur and Array

题意：

你要构造出一个给定的序列，每次你可以将一个后缀整体加1或者减1，问你最少操作次数。

题解：

很傻逼的贪心，不过要注意别爆int

Wilbur and Points

题意：

给你平面上若干点，现在你要将他们进行排列，使得$y_i-x_i=w_i$，并且若$x_i<x_j,y_i<y_j$，那么$i<j$，其中$w_i$是给定的。

题解：

这道题贪心就好，首先将每个点压到对应的x的vector里面，然后给每个x的vector排个序，然后每次把最小的值弹出即可。最后再check一下答案的合法性即可。

傅里叶变换

Veröffentlicht am 2015-11-14 | in 数学讲解

感谢傅里叶同学做出的杰出贡献

什么是傅里叶变换

这个名字很像中国人的傅里叶同学其实是法国人（好吧，这不是重点）。从数学上来讲，傅里叶变换是将函数（并不是所有的函数）转换成一系列正弦函数的和；从物理上来讲，傅里叶变换是将时间域上的信号转换到频率域上。
这样说其实是很难懂的，接下来笔者尽全力浅显易懂的讲解傅里叶变换，有什么不懂得请评论区留言。

一些你必须知道的知识

微积分

最简单的就好，这个你都不会，那笔者真的没有办法了。。( ▼-▼ )

复数

想必很多同学高中的时候都是学过什么是复数的，但是大家真的理解什么是虚数$i$吗？其实它不仅仅是$\sqrt {-1}$这么简单，我们可以这么理解它：实数乘以$-1$是乘了两次$i$，你可能说这不是废话吗？这确实是废话，但放到数轴上来看，乘以$-1$对应的就是翻转$180^{\circ}$，所以乘以$i$就是旋转$90^{\circ}$，这样就能引入复平面的概念。