由于实验室坑爹的网络，必须要手动设定IP地址才能联网（可能是某个哥们的路由器开启了DHCP）。但是穷逼如我每天要背着电脑宿舍实验室两头跑，每次都要手动设置实在是蛋疼，于是搞了一个脚本。使用方法：在system32文件夹下新建一个文本文档名为configip.ini，内容为 dynamipc=true 。如果当前为静态ip就设为false。相应的IP地址设置为自己的IP。
|
|
深入理解PageRank
引言
佩奇排名（PageRank），又称网页排名、谷歌左侧排名，是一种由搜索引擎根据网页之间相互的超链接计算的技術，而作为网页排名的要素之一，以Google公司創辦人拉里·佩奇（Larry Page）之姓來命名。 Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是經常被用來評估網頁优化的成效因素之一[1]。
上面是维基百科对PageRank的解释，初看下来还是有点抽象。接下来本文将先介绍什么是中心性以及两个中心性的度量指标，然后介绍PageRank的公式，最后阐述在其背后的数学原理。本文假设读者已经有基本的图论、线性代数、随机过程（特别是Markov Chain）的知识。
中心性
日常生活中我们的关系组成了所谓的社交网络。如果我们把两个人之间的关系看成连边，人看成节点，这样我们就能将我们的社交关系表示为一张图（Graph）。而节点的中心性就是一种度量节点在网络中的重要性的指标。回到社交网络中的例子，一般来说，当一个人认识的人越多，这个人也许就越重要，在相应的图中就表现为节点的度（Degree）越高。这就是第一个中心性——度中心性。写成公式就是$$ r = A\mathscr{L}$$
其中A是邻接矩阵，$\mathscr{L}$ 是元素全为1的列向量。
度中心性非常直观也很好理解，但是仔细想想就会发现有问题。比如A和B认识的人的数量相同，但是A认识的人中重要的人更多，那A的重要性显然要比B高，因为A的关系“质量更高”。（你认识一个小学生和认识一个某高官给你带来的收益肯定是不一样的）。这给了我们一个启发，我们可以根据一个人认识的人的重要性来确定他的重要性，这就成了一个递归的概念，同样写成公式就是 $$ r = cAr $$
其中c是一个常数，A为邻接矩阵，r为中心性向量。这是一个方程，要求出v只要解出这个方程就可以了。仔细观察，发现这个式子和特征向量的定义很像，实际上这里的v就是A的主特征向量（证明略去）。所以这种中心性也被称为特征向量中心性
。
求矩阵的主特征向量可以使用迭代法，也就是给v设定一个非零初始值，然后代入方程右边，得到新的v的值，然后一直这样进行下去，最终得到一个稳定的值，具体的原理请参考数值计算相关书籍。
特征向量中心性看上去已经不错了，但是还是有几个问题，这里提出两个：
1、如果你认识的重要的人本身是一个“社交达人”，那么这个人“贡献”给你的重要性也就没那么多了。毕竟物以稀为贵，一个博爱的人的爱是不值钱的。
2、如果一个节点的所有邻居节点的重要性都为0，那么会发生什么呢？根据公式，这个节点的重要性也将会是0。这显然是不合理的，当然这种情况只会出现在有向图中。比如一个节点的所有邻居节点都只有出度，那么所有的邻居节点的中心性都是0，从而使这个节点的中心性也为0。
PageRank初见
前面提到了特征向量中心性的两个弊端。Katz中心性就是为了解决第二个弊端而提出的，做法就是给每个节点赋予一个初始中心性。而PageRank就是受到第二个弊端的启发（这里其实是我想当然的，但是PR确实很好的解决了第二个问题）而提出的。
这里我们先把PR的计算公式写出来
$$r_i = \sum_j\frac{r_jA_ji}{k_j}$$
这里 $ k_j $ 表示一个节点的出度可以看到PR值实际上就是把邻居节点的中心性除以该节点的出度，也就是说一个节点的出度越高，贡献给邻居节点的中心性被稀释得越多。
写成矩阵形式：
$$ r^T = r^TH $$
这里$H_{ij} = \frac{A_ij}{k_i}$。
这里特意使用了转置的写法，观察一下会发现和Markov Chain的概率转移方程很像，这是后话。PR值和之前的特征向量中心性一样可以使用迭代法进行计算。
PageRank改进
实际上上面的公式并不是PageRank的完全体。首先，使用这个公式进行迭代并不总能够收敛，其次收敛值也不总为正值。在Brin和Page的论文[2]提到了改进的方法，他们使用了一个假象的上网用户。这个用户在网页组成的图中（就像之前提到的社交网络类似，只不过节点变成了网页，连边变成了超链接）进行随机游走。用户处在一个节点中时，进入邻居节点的概率相等，把这个随机过程的概率转移公式写出来就是上文提到的最初的PR计算公式，只不过RP值代表的就是用户处于某个节点的概率值，求PR值也就是求其概率的稳态分布。一个用户处于一个节点的概率越高，代表这个节点的中心性或者说重要性越高，这和之前对PR的阐述本质上是相同的，只是角度不一样。
但是考虑这样一个情况，如果一个网页只有链向它的链接而没有指向其他网页的链接，也就是这个节点的出度为0。那么一旦一个用户进入了这个网页，那么他就会无法再浏览其他网页了，因为这个网页没有超链接让他点击。那么最后的稳态分布就会是零向量。
Brin和Page的解决方案是，当一个用户进入一个死胡同时，将会等概率地进入其他网页，表现在公式上就是将概率转移矩阵全0行替换掉，所有的元素之和为1并且相等。这样新的矩阵就变成了$$ S = H + a(1/ne^T) $$
其中如果节点i是“死胡同”那么$a_i$ 就等于1。
但是即使这样也不能保证收敛。因为你不能保证网页组成的网络是强连通的，如果你一旦进入某个网页，可能就无法再访问到某些网页了。用Markov Chain的术语讲就是可约。
解决办法就是，当上网用户处在一个页面时，给他两个选择，一是遵循页面的链接，或者随机选择其他的网页进行访问。比如你正在刷知乎，突然想起来要去B站看一下视频，虽然知乎的页面并没有B站链接。表现在公式里就是给每一行一个随机权重：$$ G = \alpha S + (1-\alpha)1/nee^T$$
其中 $\alpha$ 代表的是用户做出第一个选择的概率(Goolge设置成0.85)。
从Markov Chain的观点来看PageRank
上面已经提到过，PR的计算公式和Markov Chain的概率转移公式很相似（或者说一模一样）。我们来回顾一下Markov Chain的收敛条件是什么：
1、转移矩阵要是随机矩阵（各行元素之和为1）
2、矩阵要不可约
3、各态历经（ergodic），也即各状态要非周期且是正常返态。
第一次调整，实际上是保证了第一条。第二次调整，让所有状态之间都有了连边，从而保证了第二条。并且所有状态都有自边，所以自然是非周期的。同样，第二次调整使矩阵的所有元素都不为0，所以所有状态必然都是常返态。至此，我们也证明了经过调整的PR公式最终会收敛到一个正值。
写在后面
本文主要参考了[3]这本书，实际上这篇文章更确切的说是这本书的读书笔记。但是[3]看起来还是比较吃力的，写的简略而啰嗦。随机过程和Markov Chain的相关知识可以参考[4]。有关网络的中心性参考了Newman的[5]，这本书深入浅出，是一本不错的入门读物。不过其中的Pagerank计算公式和论文里以及[3]里的公式都不相同，虽然看上去像那么回事，这是一直让我比较疑惑的。由于我比较懒，这篇文章没有配图也没有写例子（矩阵输入太烦了），如果需要直观的感受推荐看这篇文章[6]。
最后，是大言不惭地使用了“深入理解”这个词，实际上写的内容还是比较浅显（简称标题党），并且由于水平实在太渣，可能也有一些错误，相关的定理也没有证明，如果有人有兴趣可以自己去翻一下我推荐的这几本教材。
参考文献
[1]https://www.wikiwand.com/zhhans/%E4%BD%A9%E5%A5%87%E6%8E%92%E5%90%8D
[2]The Anatomy of a Large-Scale Hypertextual Web Search Engine.Sergey Brin and Lawrence Page
[3]Google’s PageRank and Beyond:The Science of Search Engine .RankingsAmy N. Langville and Car l D. Meyer
[4]Introduction to Probability Models Ninth Edition.Sheldon M. Ross
[5]Networks: An Introduction. Mark Newman
[6]浅析PageRank算法.张洋.http://blog.codinglabs.org/articles/intro-to-pagerank.html
Written with StackEdit.
计算全排列
|
|
Codeforces Round #384 (Div. 2) WriteUp
概览
一共5道题，历时2个小时，一共做出两道题，再加上总司翻车，真是不幸的一天（垃圾游戏，毁我青春)。
743A Vladik and flights
从这道题就能看出这套题的整体风格了，就是取巧。。。题目中有两种机场，那么我们知道当两个地方的机场属于同一个公司时，花费是0.那么我们只需要考虑不是同一个公司的情况。当不是同一个公司时，花费的下界是1。而采用一种策略，那么上界也是1。也就是当不属于同一个公司时，花费为1。策略就是，如果不在同一个公司，那么就朝着目标方向迁移，直到遇到目的地一样的公司或者到达目的地。哈。。。123456789101112131415using namespace std;int main(){ int n, a, b; cin >> n >> a >> b; string s; cin >> s; if (s[a-1] == s[b-1]) cout << 0; else cout << 1; return 0;}
743B Chloe and the sequence
仔细观察生成的序列，发现是对称的（废话），那么自然想到折半的方法，中心点就是每次新加入的数。那么什么时候停止呢。我们发现，位置是二的幂次的数我们是能确认他的值的，他的值就是幂次加1。比如4所在位置就是8，也即2的三次方。1234567891011121314151617181920212223using namespace std;int main(){ long long n, k; cin >> n >> k; long long ans = 1; while (n--) { if(k > pow(2, n)) k = pow(2,n)*2 - k; if (k == pow(2, n)) { ans = n+1; break; } } cout << ans << endl; return 0;}
提交了三次才过，被自己蠢哭。
743C Vladik and fractions
一道数论题？开始想了一些可能，也想到因数分解什么的，后来发现我想多了。
$$ \frac2n = \frac1n + \frac1n$$
首先可以像上面这样分解一次，我们就找到了第一个数（n)，接下来就是考虑怎么把$\frac1n$分解开了。
$$ \frac1n = \frac1{n+1} + \frac1{n(n+1)}$$
所以我们只需要输出,n 、n+1和n(n+1)就可以了。
桥豆麻袋。有一种情况无法分解，那就是n为1的情况。因为这么分解能得到的最大值为$ 1+\frac12+\frac13 = \frac53 < 2$。12345678910111213using namespace std;int main(){ int n; cin >> n; if (n == 1) cout << -1 << endl; else cout << n << " " << n+1 << " " << n*(n+1) << endl; return 0;}
这一定是A题吧。吧？
743D Chloe and pleasant prizes
图论加DP。
我们先来考虑不可能的情况。无法得到一种分配方案，当且仅当树没有分支的时候。因为只要有分支，我们总可以取这两个分支。这里维护两个数组。一个保存每个节点及其所有子节点的分数和，另个数组保存每个节点的子树中的最大分数。做一次DFS，每次找出节点的所有子树种分数最大的两个，如果找不出两个，则说明不存在合法的分配。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061using namespace std;typedef long long ll;const ll inf=1LL<<60;ll a[200001], m[200001], sums[200001];ll ans = -inf;vector<ll> g[200001];void dfs(ll r, ll pa){ sums[r] = a[r]; ll m1 = -inf, m2 = -inf; for (int i = 0;i < g[r].size();i++) { ll to = g[r][i]; if (to == pa) continue; dfs(to , r); sums[r] += sums[to]; ll x = m[to]; if (x > m1) swap(x, m1); if (x > m2) swap(x, m2); } if (m1 != -inf && m2 != -inf) ans = max(ans, m1+m2); m[r] = (sums[r] > m1) ? sums[r] : m1;}int main(){ int n; ios::sync_with_stdio(false);cin.tie(false); cin >> n; for (ll i = 1;i <= n;i++) cin >> a[i]; for (ll i = 1;i < n;i++) { ll x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } dfs(1, 0); if (ans > -inf) cout << ans << endl; else cout << "Impossible" << endl; return 0;}
参考答案是做两趟DFS，但其实只需要一趟。
总结
分数下降到了1389T_T，还是太菜。这次题目的代码量都比较小，只要想清楚了解法，都能很快写出代码。所以主要还在于思考，也没有用到复杂的数据结构和算法。还是太菜了。。。
In triangle test
问题
给定一个三角形三个顶点的坐标，另给一个点的坐标，如何判断这个点在三角形的内部？
如下图所示：
仔细观察，会发现点S在图中所有有向线段的一侧（左侧）。实际上，当且仅当点处在三角形内部时，在所有边构成的有向线段的一侧（有向线段都顺时针或逆时针）。
To left test
那么问题就规约（reduction)为了如何判断一个点在一条有向线段的一侧。这里引入To left test。
我们知道三角形有向面积的计算公式如下：
$$
2*Area =
\left|\begin{matrix}
p_x & p_y & 1 \\
q_x & q_y & 1 \\
s_x & s_y & 1 \\
\end{matrix}\right|
$$
我们可以利用三角形有向面积的符号来判定一个点处在一条有向直线的左边还是右边。所以，我们只需要判断一个点与三角形三条边构成的三角形的有向面积的符号是否一致，就可以知道这个点是在三角形内部还是外部了。
$$
\left|\begin{matrix}
p_x & p_y & 1 \\
q_x & q_y & 1 \\
s_x & s_y & 1 \\
\end{matrix}\right|=p_x\times q_y-p_y\times q_x+q_x\times s_y-q_y\times s_x+s_x\times p_y-s_y\times p_x
$$
UVA10047-扩展BFS
这道题一开始没有什么思路，后来上网看了下别人的题解才发现原来就是一种BFS。
之前迷宫类题目（无加权），直接可以用BFS来做，但是这道题加入了另外两个条件——方向和颜色。其实这就相当于将原来的二维空间扩展到了四维空间。我们要做的就是在这四维状态空间中进行搜索。和原来的二维情况不同的是，这个题目加入了转向的要素，也就是说相邻状态的距离间隔不一定是1，这就比较坑爹，不能直接使用队列来进行存储，需要用一个优先队列（小顶堆）。也许有更好的方案，请务必告诉我。
有一个需要注意的点是，每一次转向所处的状态不能漏掉（转向后还没开始行走），我一开始就是没有注意这一点被坑了。
|
|
开始没做出来还是对BFS（搜索）认识不深刻，以后还需要多加练习。(。・・)ノ
Codeforces Round #383 总结
第一次参加codeforeces的线上比赛，最后A了两道水题，事后发现B题因为没有使用long long 而溢出了（汗），所以实际上A了一题。最后排名3561，分数达到1409。
题解在这里http://codeforces.com/blog/entry/48871
这里讲一下前三题思路。
742A - Arpa’s hard exam and Mehrdad’s naive cheat
一道很直白的题，看完题之后写出暴力算法：123456789101112131415using namespace std;int main(){ int n; cin >> n; int ans = 1378; while(--n) { ans *= 1378; ans %= 10; } cout << ans%10 << endl; return 0;}
然后喜闻乐见的TLE了。其实想一下，由于只取最后一位数字，而一共只有10个数字，所以必然会出现循环。观察了一下规律写出第二版12345678910using namespace std;int ans[4] = {8, 4, 2, 6};int main(){ int n; cin >> n; cout << ans[(n-1)%4] << endl; return 0;}
然而由于没有考虑边界条件(n=0)被Hack了。
补上边界条件后终于A了:12345678910111213using namespace std;int ans[4] = {8, 4, 2, 6};int main(){ int n; cin >> n; if (n == 0) cout << 1 << endl; else cout << ans[(n-1)%4] << endl; return 0;}
742B - Arpa’s obvious problem and Mehrdad’s terrible solution
第二题二话不说用Hash:12345678910111213141516171819202122232425262728using namespace std;map<int, int> num;int nums[100001];int main(){ ios::sync_with_stdio(false); int n, x; cin >> n >> x; for (int i = 0;i < n;i++) cin >> nums[i]; long long ans = 0; map<int, int>::iterator iter; for (int i = 0;i < n;i++) { if ((iter = num.find(nums[i] ^ x)) != num.end()) { ans += num[nums[i] ^ x]; } if ((iter = num.find(nums[i])) != num.end()) num[nums[i]] += 1; else num[nums[i]] = 1; } cout << ans << endl; return 0;}
ps:开始ans用的int，然后悲剧了。
但发现由于n的大小不超过$10^5$，所以可以开个数组，直接存：1234567891011121314151617using namespace std;const int maxn = 2e5 + 17;int n, x, cnt[maxn];long long ans;int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n >> x; for(int i = 0, a; i < n; i++){ cin >> a; ans += cnt[a ^ x]; cnt[a]++; } cout << ans << '\n'; return 0;}
741A - Arpa’s loud Owf and Mehrdad’s evil plan
读完题后，以为是用Floyd cycle detection，花了40分钟写好后一直WA。等后面看了Editorial之后才发现是自己理解错了题意。我以为是要找到链中的最小环，结果是要找所有环的最小公倍数，这就很气。1000多分就没了。
后来看了题解后写了一个AC的版本：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677using namespace std;long long S[1000];int G[101];bool vis[101];int ans;bool inedge[101];void dfs(int n){ vis[n] = true; ans++; if (!vis[G[n]]) dfs(G[n]);}int gcd(int a, int b){ if (a < b) return gcd(b, a); if (b == 0) return a; return gcd(b, a%b);}int lcm(int k){ int ret = S[0]; for (int i = 1;i < k;i++) { ret = ret*S[i] / gcd(ret,S[i]); } return ret;}int main(){ ios::sync_with_stdio(false);cin.tie(false); int n; cin >> n; memset(vis, 0, sizeof(vis)); memset(G, 0, sizeof(vis)); for(int i = 0;i < n;i++) { int crush; cin >> crush; G[i+1] = crush; inedge[crush] = true; } bool flag = true; for (int i = 1;i <= n;i++) { if (!inedge[i]) { flag = false; break; } } if (flag) { int k = 0; for (int i = 0;i < n;i++) { ans = 0; if (!vis[i+1]) { dfs(i+1); if (ans%2 == 0) ans /= 2; S[k++] = ans; } } cout << lcm(k) << endl; } else { cout << -1 << endl; } return 0;}
DFS找环，没什么好说的。
总结
虽然达到了一开始设定的目标(1400)，但是结果并不那么让人满意。最后只A了两道水题。但是作为第一次，也许还算不错了。经过这次，暴露出几个问题。
首先就是手速太慢，前两道简单题就花了1个小时的时间，说明还是不够熟练，第二题用map的时候还要去查资料，蛋疼(为什么那么熟练啊）。
然后是对题目理解有偏差。第三题就是这样。直接导致一道很水的题没做出来。
下一个目标就是冲上1600，争取能把Div2都做完。
以后要开始怼论文了，接下来又是期末考试，刷题一刷刷一天的日子看来是一去不复返了，且做且珍惜。
PS：之前说只要CF上了1400就买个静电容键盘，那么问题来了，是买HHKB呢还是Realforce？
Ceil函数实现
Introductio
下取整函数，或高斯函数，记作$\lfloor x \rfloor$，表示不超过$x$的最大整数。
上取整函数，记作$\lceil x \rceil$,表示不小于$x$的整数中最小的那个。
易得如下性质$$-\lfloor -x \rfloor = \lceil x \rceil$$
Python approach
python2中默认的整数除法是向下取整，根据以上性质，可以直接转化成代码：
|
|
C/C++ approach
C++中的整数除法默认是截断小数部分，比如1.5截断后变为1,-1.5截断后变为-1。可见，在正整数时是向下取整， 在负整数时是向上取整。所以简单的实现可以将其变为负数，然后再根据原来的符号输出。但是其实有更简单的做法：1234int ceil(int op1, int op2){ return (op1 + op2 - 1)/op2;}
propositon: $\lceil a/b \rceil = (a+b-1)//b$ 其中//代表截断除，即C++自带的除法。
Proof:
我们可以设 $a=k*b+r$ 其中 $k=\lfloor a/b \rfloor , 0 < r < b$ ,可得
$$(a+b-1)//b = [(k+1)*b+r-1]//b=k+1+(r-1)//b = k+1 = \lfloor a/b \rfloor+1=\lceil a/b \rceil$$
QED
字符串最小表示算法
同构字符串
首先来看下什么是同构字符串。考虑字符串“abc”，将它循环移位，可以得到“bca”,“cab”。这些通过对原字符串进行循环移位得到的字符串以及它自身，成为原字符串的同构字符串。
而字符串的最小表示法就是指它的所有同构字符串中按字典序排列排在最小位置的那个。比如“abc”的最小表示就是它本身（类似可以定义最大表示法）。
Naive Algorithm
要求某个字符串的最小表示，最容易想到的就是对它的所有同构字符串进行穷举。为了说明方便，先规定以下符号：
用一个大写字母，比如S代表一个字符串
S[i] 代表S的第i个字符，并且第一个字符为S[0]。
S[i,j]表示S的一个从i开始到j结束的子串（包含i,j)。
S+T代表将S和T连接并且S在前组成新字符串。
|S|表示S的长度
穷举S所有的同构串有一个技巧。观察S+S,我们会发现其中出现了S的所有的同构串，所以可以对S+S进行穷举可以避免求模运算。
|
|
易得，以上算法的对S+S进行穷举，最坏情况下时间复杂度为$O(n^2)$。
A better approach
上面的暴力算法在小数据情况下已经足够用，但是遇到更大的数据（比如百万级）， 平方级别算法显然是不适用的。
周源利用了字符串之间的信息，提出了一种$O(n)$的算法。
|
|
为了理解这个算法，举个例子。
当比较从i和j开始的子串的大小时，从i开始的子串比从j开始的小，也就意味着对于$ 0\le p \lt k$,$S[i+p]=S[j+p]$并且$S[i+k] < S[j+k]$。那么我们可以得出这么个结论：从j+p开始的子串（$ 0\le p \le k$)不可能是最小表示。因为对于任何从j+p开始的子串，从i+p开始的子串总是比它小 ，因此我们可以跳过这一段，直接从j+k+1开始匹配。
算法的复杂度很好证明，因为每一轮比较都比较k次，并且指针向前移动k个位置，所以时间复杂度是$O(n)$。
算法正确性证明
引理1：设i < j， 所有以i到j之间开头的同构字符串不比以i开头的大。
证明：（一旦$i \gt j$,由于具有对称性，将i和j调换，不影响证明）
以i和j之间的字符个数表示相应的状态，比如考虑初始状态，i = 0,j = 1,k = 0，这时处于状态0。开始有三种情况：
1、$S[i] = S[j]$，k = k + 1，此时i和j之间没有字符，没有离开初始状态。
2、$S[i] < S[j] = S[i+1]$, j = j + 1, 之间的字符为S[i+1],显然成立。
3、$S[i] > S[j] , i = 1,j =2,回到初始状态。
那么接下来有两种情况，
1、 处于状态0。这种情况不需要证明。
2、 离开状态0，到达状态k。
现在考虑第二种情况。假如从0到达k状态，由于之前一直处于状态0，意味着S[i+p] = Si。现在到达了状态1，说明S[i+k] < S[i]（如果S[i+k] > S[i],则将i和j调换）。不变式成立。
那么接下来以状态k为初始状态进行证明。
这时有三种情况：
1、停留在k状态
2、到达t < k状态
3、 到达t > k状态
这三种情况分别对应S[i+k-t]等于，大于，小于S[j+k-t]的情况。
//TODO
爬虫cheet sheet
作者：笑虎
链接：https://zhuanlan.zhihu.com/p/22982208
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
|