解决 brew update Error /usr/local must be writable! 问题

Magic

最近把 rMBP 2015 乞丐版加成了 512G 的 Intel 760P 的硬盘，因为是从 Time Machine 恢复的而不是直接对拷的，导致虽然数据跟过来了，很多系统配置却没有跟过来，总是出现这样那样奇奇怪怪的问题。

今天在执行 brew update 的时候报 Error: /usr/local must be writable!，brew doctor 之，提示我执行 

1
sudo chown -R $(whoami) /usr/local

如果依然不行，执行 

1
sudo chown -R $(whoami) $(brew --prefix)/*

但这并没有什么用，Google 之，stackoverflow 曰，何以解忧，唯有重装。

问题解决，但这样一通操作以后，brew 装过的大多数软件，都就此消！失！了！，比如 proxychains4、node、git 等。（后文讲 Mojave 上装 proxychains4 的又一个坑）

如果前面两个命令不管用，这的确是唯一的办法了，阿Q 一些的想法是提前被告知总比像我这样一脸懵逼好很多，允悲= =

卸载：

1
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"

重装：

1
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
分享到

解决 proxychains4 在 macOS Mojave 无法工作问题

Magic

proxychains4 的作用在此就不多做解释了，相信能找到这篇文章的你都懂的~

虽然是解决问题，还是写一下安装，通过 brew：

1
brew install proxychains-ng

修改配置文件，配合 SS 本地端口：

1
nano /usr/local/etc/proxychains.conf

在文件末尾 [ProxyList] 后面，把原来的 socks4 127.0.0.1 9050 注释掉/删掉，添加 socks5 127.0.0.1 1080

按理安装已经结束了，我们试验一下，开启 SS（建议全局模式），在命令前添加 proxychains4

1
2
proxychains4 curl google.com
curl: (7) Failed to connect to google.com port 80: Operation timed out

？？？

并不 work！

按照网络上的解释，大多是讲配置文件权限不够，去如何修改，但这并没有什么用！原因在于 macOS El Capitan 以上系统完整性保护（SIP, System Integrity Protection）被默认开启，下面介绍如何关闭：

  1. 点击左上方  按钮，选择重启
  2. 长按 Command-R 进入 Recovery System
  3. 点击 Utilities，选择 Terminal
  4. 输入命令 csrutil disable
  5. 点击左上方  按钮，选择重启

此时再次试验：

1
2
3
4
5
6
7
8
9
10
11
proxychains4 curl google.com
[proxychains] config file found: /usr/local/etc/proxychains.conf
[proxychains] preloading /usr/local/Cellar/proxychains-ng/4.13/lib/libproxychains4.dylib
[proxychains] DLL init: proxychains-ng 4.13
[proxychains] Strict chain  ...  127.0.0.1:1080  ...  google.com:80  ...  OK
<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>301 Moved</TITLE></HEAD><BODY>
<H1>301 Moved</H1>
The document has moved
<A HREF="http://www.google.com/">here</A>.
</BODY></HTML>

成功解决√

分享到

It has been so long.

Update

上午因为重装 Homebrew 引发的问题折腾了很久，想写一篇文章 Mark 一下，想来也只能留在这里。

上一次在这里写点什么，是 20160704，而现在已经是 20190228，两年半的时间已经漫长到接近 INF，中间也发生了太多，孤独成了生活的主旋律，欢乐只是其中的点缀，所幸其中的大多数正因为没有记忆，也已经被遗忘殆尽，即使存在的，也只是一些不咸不淡的瞬间。

不知道这个网站的 RSS 地址，还会不会停留在谁的 feed 里。我倒是真心希望可以再次把这里当成树洞，留下一些焦灼、灵感或是才华（如果曾经有过的话）存在过的证明（听起来像 POW？）。

现在的自己被楼下 Tony 老师烫了奇怪的发型，如有必要或是心情合适会梳成背头，和 16 年比起来似乎是胖了一些，依然喝酒会脸红，依然没有烟瘾，依然不会开车。

我离开了南通，来到了上海（的远郊），在 17 年 7 月的时候，那时我并不知道摆在面前的是什么，也幸好那时的我不知道。一年半之后，我并没爱上这里，但之前的岁月终究离我越来越远了。

记得以前看过一个帖子讲，所谓 WSN 者，烂人烂校烂专业，没钱没车没老婆，形容过去半年的处境再合适不过了，说实话，这样的日子实在很难让人不意志消沉。

有了女友。在大二开始的时候，似乎生活中已经没有了任何可以经常见面甚至一起吃饭的异性朋友。遇见傻妞是意外中的意外。小姑娘是那么 shiny，和我这样的 WSN 明明本来是两个世界的人，anyway，缘分这东西，完全没有道理可言。

当她来临的时候，所有的坚持都有了让我继续坚持的必要。

明天就是 20190301 了，江南三月，草长莺飞，好在眼前的大多数路径还算清晰（尽管真正做的时候又是说线做泪了），也能有具体的事可做，猥琐发育、野蛮生长就好——而不是被时间和欲望推着向前。

当你变得足够强大，就不会在意付出的代价。

分享到

NOI OpenJudge 题库 7623 五户共井问题

Algorithms
NOI OpenJudge

描述

有A, B, C, D, E五家人共用一口井，已知井深不超过k米。A, B, C, D, E的绳长各不相同，而且厘米表示的绳长一定是整数。
从井口放下绳索正好达到水面时：
(a)需要A家的绳n1条接上B家的绳1条
(b)需要B家的绳n2条接上C家的绳1条
(c)需要C家的绳n3条接上D家的绳1条
(d)需要D家的绳n4条接上E家的绳1条
(e)需要E家的绳n5条接上A家的绳1条
问井深和各家绳长。

输入

输入只有1行。包括空格分开的6个整数。
第一个整数k（1 <= k <= 20)，代表井的最大深度（单位：米）。
接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。

输出

输出只有1行。
如果找到了可行解，就输出6个整数，用空格分开，分别代表井的深度和A, B, C, D, E的绳长（单位都是厘米）。
如果有多组可行解，输出井的深度最小的那组解。
如果不存在可行解，就输出一行：
not found

样例输入

1
10 2 3 4 5 6

样例输出

1
721 265 191 148 129 76

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
int main()
{
	int k;
	int n1,n2,n3,n4,n5;
	cin >>k>>n1>>n2>>n3>>n4>>n5;
	int H,A,B,C,D,E;
	int ANSH=2147483647,ANSA,ANSB,ANSC,ANSD,ANSE;
	for(A=1;A<=k*100;A++)
		for(B=1;B<=k*100;B++)
		{
            H = A * n1 + B;
            C = H - B * n2;
            D = H - C * n3;
            E = H - D * n4;
            if((E * n5 + A != H) || H>k*100 || C<=0 || D<=0 || E<=0 || A==B || A==C || A==D || A==E || B==C || B==D || B==E || C==D || C==E ||D==E)
            	continue;
            if(H<ANSH)
            {
            	ANSH=H;
            	ANSA=A;
            	ANSB=B;
            	ANSC=C;
            	ANSD=D;
            	ANSE=E;
            }
		}
	if (ANSH==2147483647)
		cout <<"not found"<<endl;
	else cout <<ANSH<<" "<<ANSA<<" "<<ANSB<<" "<<ANSC<<" "<<ANSD<<" "<<ANSE<<endl;
	return 0;
}
分享到

NOI OpenJudge 题库 8211 派

Algorithms
NOI OpenJudge, 二分

描述

我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

输入

第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数，表示每个派的半径。

输出

输出每个人能得到的最大的派的体积，精确到小数点后三位。

样例输入

1
2
3 3
4 3 3

样例输出

1
25.133

分析

先由半径求体积，而后二分查找，区间为(0,最大的单个派的体积)。

个人 WA 的原因：

  • π 的值一开始取 3.141569 ，小数点后 6 位，这样的精度居然还不够，可以用 math 库中的反余弦函数 acos(-1.0)
  • check 函数中表示当前能够分的块数的变量 sum 要用 int

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define loop(i,n) for(int i=0;i<n;i++)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,f;
double a[10010];
const double PI=acos(-1.0);
int check(double x)
{
	int sum=0;
	loop(i,n)
	{
		sum+=a[i]/x;
		if(sum>=f)
			return 1;
	}
	return 0;
}
int main()
{
	double left=0,right=0,mid;
	cin >>n>>f;
	f++;
	loop(i,n)
	{
		cin >>a[i];
		a[i]=a[i]*a[i]*PI;
		if(a[i]>right)
			right=a[i];
	}
	while(right - left>0.000001)
	{
		mid=(left+right)/2;
		if(check(mid))
			left=mid;
		else right=mid;
	}
	printf("%.3lf\n",left);
	return 0;
}
分享到

20160702 自勉

  • 钻研那些最需要脑力的事。

  • 去 SJTU ，去见见更大的世界。

  • 高考可以重来；而 OI ，无论是 Happy Endding 还是 Sad Endding ，真的没有 One More Chance 了。

  • 没有一场胜利的战役是按计划进行的，但是没有计划是打不赢胜仗的。

向上吧，少年！

分享到

NOI OpenJudge 题库 7914 分数线划定

Algorithms
NOI OpenJudge, NOIP 2009

描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入

第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。
第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。

输出

第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。
从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例输入

1
2
3
4
5
6
7
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

样例输出

1
2
3
4
5
6
88 5
1005 95
2390 95
1000 90
1001 88
3239 88

提示

样例说明：m150% = 3150% = 4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88有重分，所以所有成绩大于等于88的选手都可以进入面试，故最终有5个人进入面试。

分析

sort() 函数很强大，需要注意的是 cmp 的写法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define loop(i,n) for(int i=0;i<n;i++)
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int number,score;
}a[10010];
bool cmp(node a,node b)
{
	if(a.score==b.score)
		return a.number<b.number;
	return a.score>b.score;
}
int main()
{
	int n,m;
	cin >>n>>m;
	m=int(m*1.5);
	loop(i,10010)
		a[i].score=0;
	loop(i,n)
		cin >>a[i].number>>a[i].score;
	sort(a,a+10010,cmp);
	int j=m;
	int count=m;
	while(a[j].score==a[m-1].score)
	{
		count++;
		j++;
	}
	cout <<a[m-1].score<<" "<<count<<endl;
	loop(i,m)
		cout <<a[i].number<<" "<<a[i].score<<endl;
	j=m;
	while(a[j].score==a[m-1].score)
	{
		cout <<a[j].number<<" "<<a[j].score<<endl;
		j++;
	}
	return 0;
}
分享到

NOI OpenJudge 题库 1818 红与黑

Algorithms
NOI OpenJudge, 深度优先搜索

描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。

输出

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

1
2
3
4
5
6
7
8
9
10
11
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0

样例输出

1
45

分析

深搜入门题，开始以为是求最大联通块，仔细看发现只要求源点所在的连通块大小。居然没有数据范围，于是我就开了 1100*1100 水过了。另外有一个注意点 -> 给的 W / H 是 列 / 行 ，而正常题目是 行 / 列，循环需要把 W / H 倒过来。

似乎也可以用宽搜写，有空填坑。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define loop(i,n) for(int i=0;i<n;i++)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int w,h;
int ans;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char tile[1100][1100];
int map[1100][1100];
bool flag[1100][1100];
struct node
{
    int x,y;
}start;
bool check(int x,int y)
{
    if(!flag[x][y] && map[x][y] && x>=0 && x<h && y>=0 && y<w)
        return 1;
    return 0;
}
void dfs(int x,int y)
{
    ans++;
    flag[x][y]=1;
    loop(i,4)
    {
        int curx=x+dx[i],cury=y+dy[i];
        if(check(curx,cury))
            dfs(curx,cury);
    }
}
int main()
{
    while(scanf("%d%d",&w,&h)==2 && w && h)
    {
        ans=0;
        memset(map,0,sizeof(map));
        memset(flag,0,sizeof(flag));
        loop(i,h)
            loop(j,w)
            {
                cin >>tile[i][j];
                if(tile[i][j]=='.')
                    map[i][j]=1;
                if(tile[i][j]=='#')
                    map[i][j]=0;
                if(tile[i][j]=='@')
                {
                    map[i][j]=1;
                    flag[i][j]=1;
                    start.x=i;
                    start.y=j;
                }
            }
        dfs(start.x,start.y);
        cout <<ans<<endl;
    }
    return 0;
}
分享到

NOI OpenJudge 题库 6264 走出迷宫

Algorithms
NOI OpenJudge, 宽度优先搜索

描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m(1<=n,m<=100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符’.’表示空地，’#’表示墙，’S’表示起点,’T’表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

1
2
3
4
3 3
S#T
.#.
...

样例输出

1
6

分析

最近在刷 OpenJudge ，怎么说也得拿个 200 分换省三呢。

宽搜入门题，试了一把 STL 队列，写完觉得链表、栈、队列这种东西还是自己实现算了 …… 这些用 STL 写实在太花哨，也并没有方便太多，但是 STL 的优先队列、堆倒还是很有用的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#define loop(i,n) for(int i=0;i<n;i++)
const int INF=2147483647;
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char maze[110][110];
int dis[110][110];
bool map[110][110];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
typedef pair<int,int> matrix;
matrix start,end;
queue<matrix> q;
int n,m;
void init()
{
    memset(map,0,sizeof(map));
    loop(i,110)
        loop(j,110)
            dis[i][j]=INF;
    cin >>n>>m;
    loop(i,n)
        loop(j,m)
        {
            cin >>maze[i][j];
            if(maze[i][j]=='S')
            {
                start.first=i;
                start.second=j;
                map[i][j]=0;
            }
            if(maze[i][j]=='T')
            {
                end.first=i;
                end.second=j;
                map[i][j]=0;
            }
            if(maze[i][j]=='.')
                map[i][j]=0;
            if(maze[i][j]=='#')
                map[i][j]=1;
        }
}
int check(int x,int y)
{
    if(dis[x][y]==INF && !map[x][y] && x>=0 && x<n && y>=0 && y<m)
        return 1;
    return 0;
}
int bfs()
{
    dis[start.first][start.second]=0;
    q.push(matrix(start.first,start.second));
    while(q.size())
    {
        matrix tmp=q.front();
        q.pop();
        if(tmp.first==end.first && tmp.second==end.second)
            break;
        loop(i,4)
        {
            int curx=tmp.first+dx[i],cury=tmp.second+dy[i];
            if(check(curx,cury))
            {
                q.push(matrix(curx,cury));
                dis[curx][cury]=dis[tmp.first][tmp.second]+1;
            }
        }
    }
    return dis[end.first][end.second];
}
int main()
{
    init();
    cout <<bfs()<<endl;
    return 0;
}
分享到

递推、搜索、贪心和动态规划的区别

Algorithms

递推：每个阶段只有一个状态；

搜索：每个阶段的最优状态是由之前所有阶段的状态的组合得到的；

贪心：每个阶段的最优状态都是由上一个阶段的最优状态得到的；

动态规划：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到（最优子结构），而不管之前这个状态是如何得到的（无后效性）。

分享到