分类目录归档:计算机

程序员的巴别塔问题

巴别塔问题,是圣经故事中,人类企图在示拿之地建塔,来传扬自己的名声,以免他们分散到世界各地。上帝知道之后,将他们的语言打乱,再把他们分散到世界各地。于是巴别塔停止修建,人类也因此发生冲突与战乱。

程序员有很多语言,不同的语言还有不同的代码框架和库。在程序员论坛,你基本上丢上一句「xxx是最好的语言」、「xxx吊打xxx」,热度马上就能上来。一些人乐于造轮子,说的是喜欢创造别人已经创造过的工具。大多数人在业务上重复造轮子,对自己来说可以锻炼代码能力,对别人来说通常是一种灾难,自己的轮子没有社区和团队的支持,没有详尽的文档解释,别人要理解代码完全就是头疼了。

每当看见一个新语言/新框架,我就会感慨,程序员怎么那么命苦。别人发明语言,发明框架,我们来学,又是一套新东西,无非是一些语言特性加加减减。有人就说,这个语言实现了xx特性,这样我们编码的速度/程序的性能/语言的易用性又提高了。程序语言不太可能出现什么革命性的升级,除非有一天自然语言处理技术已经能跟上人类的大脑,人们只需要说话就能写程序。别人出书,我们买书,别人演讲,我们学习,别人用新技术完成了kpi,我们下班继续学习。号称完成了xx特性,提高了多少效率,门槛如何如何低,结果就是大家依然要加班,但是加班的位置都更难抢了。十年前,你会写html,用ps切切图,还知道tomcat弄服务器,你就很牛了。现在招聘要求是,高并发、高可用、多线程编程、高性能分布式系统、容器技术。你工资没变高,但是你要学的东西变多了,你气不气,这大概就是技术革新吧。

Python超简单入门

Python入门非常简单,精通却很难,不过我只需要其中某个功能而已。现学现用,下面代码方便快速回忆:

# coding: utf-8 
# 井号是单行注释
# 数据类型、控制结构、功能、I/O文件
''' 
多行注释是三个单引号 
'''

import os #引入外部库的语句
from math import cos 

#动态类型语言
s = 0   
s = "shit" 

'''Python自带数据结构'''

#list是一种有序的集合,可以随时添加和删除其中的元素。
names = ['Michael', 'Bob', 'Tracy']    
names[-1] = "Jake"   #Tracy
names.pop(0)    #删除Michael
names.insert(1, "Jack")
names.sort()    #排序
L = ["隋辨", 20, 125.5] #不同的数据类型
#嵌套 len(sheet) = 4    sheet[2][1] = 5
sheet = [1, 2, [3, 5], 4]   

#tuple一旦初始化就不能修改
classmates = ('Michael', 'Bob', 'Tracy')
tmp = ()    #定义空tuple
t1 = (5)    #定义变量t1 = 1
t2 = (5,)    #定义只有1个元素的tuple
t3 = (1, 2, [3, 4]) #由于list可变所以tuple看上去可变
t3[2][0] = 4

#dict,在C++叫map
d = {'Michael': 95, 'Bob': 75, 'Tracy': 85}
print(d["Bob"])  #75
print('Bob' in d)   #判断key是否存在
#key必须是不可变对象,如list就不可以作为key

#set
set1 = set([1, 2, 3])   #利用list作为输入
set2 = set([2, 3, 4])
set1.add(4) #添加
set1.remove(1)  #删除
set1 & set2 #2, 3
set1 | set2 #1, 2, 3, 4



'''循环'''
#range(5)相当于[0, 1, 2, 3, 4]
a = 0
for x in range(5):
    a = a + 1
    print(x)
#利用list循环
for name in names:
    print(name)
while(True):
    a = a - 1
    if(a % 2 == 0):
        break

#判断
if a < 0:
    print("负数")
elif a == 0:
    print("零")
else:
    print("正数")

if s:
    print("s是非零数值、非空字符串或非空list")

#输出
print("%.2f" %a)    #类C的输出方法
print("hhh" * 10)   #重复十个hhh
print('{0}成绩提升了{1:.1f}%'.format('小明', 17.125))   #正宗输出方法

#函数
def my_power(x, n = 0):
    s = 1
    while n > 0:
        n = n - 1
        s = s * x
    return s
print(my_power(2, 10))

#定义一个什么事也不做的空函数
def nop():
    pass    

#返回多个值其实就是返回一个tuple
def mul_return():
    return 1, 2, 3

Tarjan算法(C语言实现)


//求割点
int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            //如果lowu==pre[v],光凭这一条u仍然是割点
            //>就更加了

            //lowv ,v及其后代能返回的最小祖先pre值,没有则返回自己 即lowv > pre[u] 则(u,v)是割边
            //而且还知道了u是割点
            if(lowv >= pre[u])
            {
                iscut[u] = true;
            }
        }
        else if(pre[v] < pre[u] && fa != v)//如果访问过就判断是不是后向边,
        {
            lowu = min(pre[v], lowu);
        }
    }
    //if(fa == -1 && child > 1) iscut[u] = true; 不这样判断是因为lowu一开始等于pre[u]
    if(fa < 0 && child == 1) iscut[u] = false;
    //如果是叶子结点,一开始是memset(iscut, 0, sizeof(iscut))

    low[u] = lowu;
    return lowu;
}



//求点双连通分量
struct Edge
{
    int u, v;
};

int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;//bccno记录每个点的bcc编号
vector  G[maxn], bcc[maxn];//bcc储存双连通分量的点
stack S;

int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        Edge e = (Edge){u, v};
        /*栈中存储的是边而不是点!!!*/
        /*因为割顶明显不可能属于任何一个点双,所以割顶的bccno无意义。*/
        if(!pre[v])
        {
            S.push(e);//没有访问过的,就压栈,把沿途遍历到的边都加入栈(也就是第一次遍历所有的点)
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv >= pre[u])//必存在割点  若大于则还存在割边(u, v)
            {
                //若发现了一个割点,说明当前栈中已经保存了点双的所有边。
                iscut[u] = true;
                bcc_cnt++;//从1开始
                bcc[bcc_cnt].clear();//清空准备储存
                for(;;)
                {
                    Edge x = S.top(); S.pop();
                    if(bccno[x.u] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);//第bcc_cnt个连通分量有点加入
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u && x.v == v) break;
                }//把边集中涉及到的点全部取出来,把他们的bccno[]设置成当前的bcc_cnt
            }
        }
        else if(pre[v] < pre[u] && v != fa)//反向边
        {
            S.push(e);//也许割点v此时被push
            lowu = min(lowu, pre[v]);//反向边更新
        }
    }
    if( fa < 0 && child == 1)   iscut[u] = 0;
    return lowu;
}

void find_bcc(int n)
{
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 0; i < n; i++)
        if(!pre[i]) dfs(i, -1);//怕万一有些点是孤立的
}

算法竞赛入门经典 图论部分题解

UVa 10801 电梯换乘

题意:

有5个以内电梯,分别可以到达不同的楼层,且速度不同,同一层次如果有两部电梯,就可以换乘,从一部电梯到任意一部电梯都花60s。求0层到某层花费的时间。

解法:

开始我想到的是把每一层不同的电梯看成一个点,但是建图会非常麻烦。看见网上题解用邻接矩阵,代码很简洁。
把每一层视为一个点,邻接矩阵储存每一个点i到另一个点j的最短距离,这个最短距离是未换乘的最短距离。任意i,j都是用了同一部电梯,但同一行或同一列不一定是同一部电梯。d[]刚好等价于G[0][],接下来就是dijkstra算法,如:G0存在,说明0到i的最短距离就是G0,此时再更新所有邻接点,如果0,j无边,或者换乘后距离小于未换乘的最短距离,那就更新。
原代码在邻接点加了判断vis[y]是为了电梯可以一直向上走。

UVa 1664 Conquer a New Region

题意:

n个城镇,有n-1条路,c(i,j)表示两个城镇之间的交通容量,一条路径的容量的最大值是这条路径所有路的最小值,找出一个中心点,使得它到其他n-1个城镇的容量最大。

解法:

最小生成树的定义是边权总和最小的的生成树。这里并不是求边权总和最大的生成树,而是路径上权最小值,利用Kruskal算法,按照它排序做生成树。怎么求路径最小值?边从大到小排序,如果第一个是(u, v, c),显然u到v的最小权值和v到u的都是等于c,对于新加入的边呢?新加入的(u, v1, c1),和u,v属于同一个连通分量,那么c1肯定是u到v1和v到v1的最小权值,因为是从大到小排序。本来想的是计算每一个点的到其他点的权值和,然后排序找最大的,在每个连通分量添加新点时,更新他们的权值和,结果TLE。
看了网上类似贪心的做法,因为不需要求出具体哪个点作为中心,所以在每次添加新点时,比较两个点(孤立点或者连通分量代表元)谁作为中心时会更大,把并查集的代表元改为中心点。
其依据是:每加入一个点,由于排序,它的权值必然小于等于连通分量内所有边的权值,所以当新点作为中心点时,连通分量的每个点都必须加上新点带来的权值。

UVA 1279 Asteroid Rangers

题意:

n个点在三维空间,每个点会匀速移动,在xyz方向上有恒定速度,相同时间每个点都移动到不同坐标,图有唯一的最小生成树,且最小生成树在10^-6s内不会改变,求最小生成树的个数。

解法:

p1(x1 + dx1 t, y1 + dy1t, z1 + dz1 * t)
p2(x2 + dx2 t, y2 + dy2t, z2 + dz2 * t)
IMG_20180114_194304.jpg

UVa Live 6039 Let’s Go Green

题意:

有n个城市,城市与城市构成树形结构(每个城市之间只有唯一一条路)简单起见,自行车不会走同样的路两次(一个城市路过一次),给出每条路上自行车经过的次数,求自行车最少能有多少。

解法1:

先求所有边的权的和sum,sum肯定是大于等于总单车数的,一辆车可以增加很多边权。把输入的单向边变为双向的,这样来遍历每一个点,这里把边权定义为经过边的单车数,让点权值等于经过该点的单车数,发现:点权和 = 边权和 + 最少单车数(难不成这是图论的某个定理?),点权的计算:如果有一条边的权比其余边权的和还要大,即maxm > esum – maxm,那么让这条边的单车往其他边走,点权(经过该点的单车)最少是maxm;如果没有出现这种情况,只能让边上的自行车的一半,经过该点然后去抵消另一半边,偶数自行车一半到另一半,奇数有一个在该点经过就不走了,剩下的一半去抵消另一半,对于整形除法都是(esum + 1) / 2。

STL学习总结

这段时间的学习之后,掌握了容器、string类还有几个算法函数的基本用法,知道更多的字符串处理方法。

其中,不懂的题有:
K Smallest Sums

仍然还有bug的题有:
Borrowers
Updating a Dictionary
PGA Tour Prize Money
Bug Hunt

未做的题有:
The Letter Carrier’s Rounds
Do You Know the Way to San Jose?
Boring Game
USACO ORZ
Use of Hospital Facilities
Revenge of Fibonacci
Exchange
Queue and A

cin 与 scanf 测试(未完)

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    freopen("dataout.txt","w", stdout);
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        printf("%d", i);
    }
    return 0;
}
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    freopen("dataout.txt","r", stdin);
    int a;
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        scanf("%d\n", &a);
    }
    printf("%.3lf\n",double(clock()-start)/CLOCKS_PER_SEC);
    return 0;
}
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    freopen("dataout.txt","r", stdin);
    int a;
    int start = clock();
    for(int i = 0; i < 1000000; i++)
    {
        cin >> a;
    }
    printf("%.3lf\n",double(clock()-start)/CLOCKS_PER_SEC);
    return 0;
}