准备:

一台境外的服务器/主机;
一个未被ban的域名;
如果没有主机推荐使用免费的境外主机以及其赠送的的二级域名。

搭建:

下载Ghost上传到服务器/主机指定目录即可。
通过域名进行访问。

配置:

访问http://你的域名//_admin进行配置。
默认密码为liming,可在\_admin\data\config.php中自行修改。    
在基本设置中,将需要代理的网址修改为:https://www.google.com/,提交后测试效果。

注意事项:

不建议大规模使用,有被屏蔽的风险。
建议使用垃圾的主机和域名,被ban掉损失较小。

Ghost下载地址:点此下载

二分搜索法,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法。在程序设计竞赛特别是ACM中,经常可以见到二分搜索法和其他算法结合的题目。

本文主要总结了二分的几种常用写法。

lower_bound
给定长度为 nn 的单调不下降数列 a0,a1,…,an−1a0,a1,…,an−1 和一个数 kk,求满足 ai≥kai≥k 条件的最小的 ii。不存在的情况下输出 nn。

满足“二分值越大越容易满足条件”,等同于“最小化最大值”,参见下方描述。

upper_bound
给定长度为 nn 的单调不下降数列 a0,a1,…,an−1a0,a1,…,an−1 和一个数 kk,求满足 ai>kai>k 条件的最小的 ii。不存在的情况下输出 nn。

满足“二分值越大越容易满足条件”,等同于“最小化最大值”,参见下方描述。

最大化最小值
此种题目一般是“二分值越小越容易满足条件”,然后求符合条件的最大值。

区间长度为1时的写法:
解的范围为 lb,rb。

// 计算区间为[lb, rb]
while( rb > lb )  // 区间长度为1时终止循环
{
    // 防止溢出
    int m = lb + (rb - lb + 1) / 2;    // 由于是区间长度为1时终止循环,所以要加1
    if( ok(m) ) lb = m;
    else rb = m - 1;
}
// 跳出循环时 lb == rb

区间长度为2时的写法:
解的范围为 [lb,rb)[lb,rb)。

while( rb - lb > 1 )  // 区间长度为2时终止循环
{
// 防止溢出
int m = lb + (rb - lb) / 2;    // 由于是区间长度为2时终止循环,所以不用加1(不会死循环)
if( ok(m) ) lb = m;
else rb = m;
}
// 跳出循环时 lb + 1 == rb
// 答案为 lb

最小化最大值

此种题目一般是“二分值越大越容易满足条件”,然后求符合条件的最小值。

区间长度为1时的写法:
解的范围为 lb,rb。

while( rb > lb )
{
// 防止溢出
int m = lb + (rb - lb) / 2;     // 这里虽然区间长度为1,但不需要加1(不会死循环)
if( ok(m) ) rb = m;
else lb = m + 1;
}
// 跳出循环时 lb == rb

浮点数的二分

浮点数二分一般直接指定循环次数(100次)作为终止条件。1次循环可以把区间的范围缩小一半,100次的循环则可以达到 2−100≈10−302−100≈10−30 的精度范围,基本上是没有问题的。

for( int i = 0; i < 100; ++ i )
{
double m = (lb + rb) / 2;
...
}
// 跳出循环时 lb 与 rb 近似相等,所以都可作为答案

此外,也可以类比整数的二分,把终止条件设为像 (r−l)/2>EPS(r−l)/2>EPS,依然通过指定一个区间的大小来终止循环。但是,如果 EPSEPS 取得太小了,就有可能因为浮点小数精度的原因导致陷入死循环。因此,对于浮点数,一般还是建议通过指定循环次数来作为终止条件。

总结

其实重点还是 最大化最小值 和 最小化最大值 的区分。可以发现:

  • 对于区间长度为1的写法,两者的解存在范围都是闭区间。即初始化时 lblb 作为解的最小值,rbrb 作为解的最大值就可以了。唯一不同的是,求 最大化最小值 时,中间值的计算需要加1再除以2。这是这种写法的一个特征,可以自己手动验算下区间长度为1时是否能跳出循环。
  • 对于区间长度为2的写法,两者的解存在范围都是半开半闭区间。即初始化时,有一边(左/右)需要加1或减1(以保证能求到解的最值)。答案也不同,一个是左值,一个是右值。

写法记一种就够了,记多了反而容易混淆。当然,归根结底,还是要多做题,多思考…

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int p[N], d[N];

void check(){
    int n;
    cin >> n;
    for(int i = 1; i < n; ++i){
        cin >> p[i];
        d[i] = d[p[i]] + 1;
    }
    int ans = 0;
    for(int i = 0, x; i < n; ++i){
        cin >> x;
        if(d[i]&1) ans ^= x;
    }
    if(ans) cout << "win\n";
    else cout << "lose\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        check();
    }
}