分类目录归档：计算机

程序员的巴别塔问题

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)UVa Live 6039 Let’s Go Green题意：有n个城市，城市与城市构成树形结构（每个城市之间只有唯一一条路）简单起见，自行车不会走同样的路两次（一个城市路过一次），给出每条路上自行车经过的次数，求自行车最少能有多少。解法1：先求所有边的权的和sum，sum肯定是大于等于总单车数的，一辆车可以增加很多边权。把输入的单向边变为双向的，这样来遍历每一个点，这里把边权定义为经过边的单车数，让点权值等于经过该点的单车数，发现：点权和 = 边权和 + 最少单车数（难不成这是图论的某个定理？），点权的计算：如果有一条边的权比其余边权的和还要大，即maxm > esum - maxm，那么让这条边的单车往其他边走，点权（经过该点的单车）最少是maxm；如果没有出现这种情况，只能让边上的自行车的一半，经过该点然后去抵消另一半边，偶数自行车一半到另一半，奇数有一个在该点经过就不走了，剩下的一半去抵消另一半，对于整形除法都是(esum + 1) / 2。

STL学习总结

发表评论
这段时间的学习之后，掌握了容器、string类还有几个算法函数的基本用法，知道更多的字符串处理方法。其中，不懂的题有：K Smallest Sums仍然还有bug的题有：BorrowersUpdating a DictionaryPGA Tour Prize MoneyBug Hunt未做的题有：The Letter Carrier's RoundsDo You Know the Way to San Jose?Boring GameUSACO ORZUse of Hospital FacilitiesRevenge of FibonacciExchangeQueue 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;
}