C++博客-西风萧瑟@HDU

Java环境变量设置

西风萧瑟 — Fri, 18 Dec 2009 12:19:00 GMT

在sun官网上载最新的JDK版本，安装；（我的目录是：C:\Program Files\Java\jdk1.6.0_10，系统是WIN7）下面我就这个目录进行环境设置：
1.   右击“计算机”，选择“属性”，弹出对话框：

2.   选择高级环境设置

3.   在系统变量里“新建”
   1）JAVA_HOME    （JDK的安装路径, 值为：C:\Program Files\Java\jdk1.6.0_10）

   2）新建classpath (值为：,;%JAVA_HOME%\lib\tools.jar) 注意前面是 ,; (逗号与分号）

   3）编辑path：在最前面假如 ;%JAVA_HOME%\bin; %JAVA_HOME%\jre\bin;


下面来测试一下环境安装是否成功：
我在D盘下新建java文件夹，在文件夹下新建记事本，编辑如下：

public class Hello
{
    public static void main(String[] args)
    {
        System.out.println("恭喜，配置成功!");
    }
}

另存为：Hello.java

在开始菜单里选择“运行”（如果没有，右击任务栏，在属性里找到“开始菜单”，“自定义”，勾选“运行)

在运行里输入cmd,   然后依次输入
d:
cd java
javac Hello.java
java Hello                        如果显示如下，则配置成功！

西风萧瑟 2009-12-18 20:19 发表评论

HDU 动态规划（46道题目）倾情奉献~ 【只提供思路与状态转移方程】

西风萧瑟 — Sat, 05 Dec 2009 14:34:00 GMT

摘要: Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955 背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=m... 阅读全文

西风萧瑟 2009-12-05 22:34 发表评论

PKU 最短路题目小结【不断更新中...】

西风萧瑟 — Sat, 05 Dec 2009 09:10:00 GMT

昂贵的聘礼 http://acm.pku.edu.cn/JudgeOnline/problem?id=1062

Dijkstra算法就可以了，权非负；

有的物品对应有替代品 + 优惠价格，反过来考虑，即替代物品 + 优惠价格就达到原来的物品，建图；

增加一个顶点，连接每个顶点，权值等于该顶点的价值，相当于你直接支付；

难点在于等级限制M；枚举 + 删顶点；

因为你最后始终要到达顶点1，满足等级限制条件还要访问顶点 1？

一次枚举 (lv[1] - M) ~ lv[1]，……，lv[1] ~ (lv[1] + M) ，把不符合条件的顶点给予visit[i]=1;

Stockbroker Grapevine http://acm.pku.edu.cn/JudgeOnline/problem?id=1125

考察flyod算法，先求出每个点到其他顶点的距离，然后选出其中的最大值，即为这个点到达所有顶点的最大距离；如果最大值为初始化的INF，则该点不能到达所有点；

然后再从能到达所有点中的集合点选出最小值；

Invitation Cards http://acm.pku.edu.cn/JudgeOnline/problem?id=1511

对SPFA邻接表实现的考察，bellman_ford,dijkstra都会超时；

求每个志愿者来回的最短路，ccs -> x -> ccs,前一部分由正向图对顶点1做一次单源最短路即可，建立逆向图再次求解就是第二部分；

Currency Exchange http://acm.pku.edu.cn/JudgeOnline/problem?id=1860

Bellman_ford算法；从银行实现2种货币的兑换可以认为每种货币相当于一个顶点，每家银行相当于连接两个顶点的一条边；求是否存在一条路径u -> a -> b -> …… u，权值之和大于原来的值；

MPI Maelstrom http://acm.pku.edu.cn/JudgeOnline/problem?id=1502

Heavy Transportation http://acm.pku.edu.cn/JudgeOnline/problem?id=1797

Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217

同HDU 1217

Frogger http://acm.pku.edu.cn/JudgeOnline/problem?id=2253

Til the Cows Come Home http://acm.pku.edu.cn/JudgeOnline/problem?id=2387

Wormholes http://acm.pku.edu.cn/JudgeOnline/problem?id=3259

Silver Cow Party http://acm.pku.edu.cn/JudgeOnline/problem?id=3268

Big Christmas Tree http://acm.pku.edu.cn/JudgeOnline/problem?id=3013

Skiing http://acm.pku.edu.cn/JudgeOnline/problem?id=3037

Candies http://acm.pku.edu.cn/JudgeOnline/problem?id=3159

Cow Hurdles http://acm.pku.edu.cn/JudgeOnline/problem?id=3615

Cow Contest http://acm.pku.edu.cn/JudgeOnline/problem?id=3660

西风萧瑟 2009-12-05 17:10 发表评论

HDU 最短路题目小结

西风萧瑟 — Fri, 04 Dec 2009 09:12:00 GMT

最短路 http://acm.hdu.edu.cn/showproblem.php?pid=2544
    赤裸裸的最短路

A Walk Through the Forest http://acm.hdu.edu.cn/showproblem.php?pid=1142
"He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A." 重在理解这句话。先求出所有顶点到顶点2的最短路(以顶点2为源点做一次Dijkstra)，然后从顶点1开始记忆化搜索。
If (d[u] > d[v])
Sum += bfs(v);

Minimum Transport Cost  http://acm.hdu.edu.cn/showproblem.php?pid=1385
    Floyd路径输出，题目要按路径的字典序输出；
    if (p[i][k] + p[k][j] == map[i][j] && path[i][k] < path[i][j])
            path[i][j] = path[i][k];
    即可

Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
    问题是是否可以盈利，如果我们把汇率看成边，当一个点通过某些路径返回到自己后的值大于1，则盈利；

A strange lift http://acm.hdu.edu.cn/showproblem.php?pid=1548
    因为边的权值都为1，BFS，Dijkstra都可以

一个人的旅行http://acm.hdu.edu.cn/showproblem.php?pid=2066

需要构图，另外建立2个点，分别各乘车城市，草儿想去的地方相连，权值为0；则问题转化为单源最短路问题；

The shortest path http://acm.hdu.edu.cn/showproblem.php?pid=2224
    Bitonic path (详见《算法导论》 P217)
    一个人从p1严格地增的走到pn，然后再严格递减的回到p1;求总路径的最小值；
    网上看到很多解题报告看的我直冒汗
    对于1 <= i <= j <= n, 我们定义P(i, j)是一条包含了P1, P2, P3 …… Pj的途径; 这条路径可以分成2部分：递减序列与递增序列，起点是Pi(1 <= i <= j)，拐点是P1，终点是Pj, P[i, j]为其最小值；那么状态转移方程为：
    b[1,2] = |P1P2|,
    i < j-1时， b[i,j] = b[i,j-1] + |Pj-1Pj|    点Pj-1在递增序列中，
    i = j-1时， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 }  点Pj-1在递减序列中
    b[n,n] = b[n-1,n] + |Pn-1Pn|

The Shortest Path http://acm.hdu.edu.cn/showproblem.php?pid=2807
    Floyd与多次Dijkstra都可以；
A*B=C, A,C连同；
我们不妨可以对于每两个城市相乘，把得到的矩阵跟非A，B比较，而不要对于A,C去寻找是否存在这样一个B，结果很容易超时
    另外，这里有个优化是矩阵的比较（2维转化成1维）

西风萧瑟 2009-12-04 17:12 发表评论

矩阵的快速比较 HDU2807 The Shortest Path

西风萧瑟 — Fri, 04 Dec 2009 01:05:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=2807

常规矩阵比较复杂度是O(n^2), 我们可把2维的数组乘以一个一维数组来比较
通过这道题的测试，效果灰常让人吃惊。。。

常规比较的代码用C++提交超时，但是G++可以过掉，1484MS

#include <iostream>
using namespace std;
#define N 81
#define INF 99999999
int map[N][N], n, m;
struct node{
    int Map[N][N];
} rec[N];

struct nnode{
    int Map[N];
}recone[N];

void cmp(int a, int x)
{
    int i;
    for (i=1; i<=m; i++)
        if (recone[x].Map[i] != recone[0].Map[i])
            return;
    map[a][x] = 1;
}

void creat(int a, int b)
{
    int i, j, k, s;
    for (i=1; i<=m; i++)
    {
        recone[0].Map[i] = 0;
        for (j=1; j<=m; j++)
        {
            recone[0].Map[i] += rec[a].Map[i][j] * recone[b].Map[j];
        }
    }

    for (i=1; i<=n; i++)
        if (i != a && i != b)
            cmp(a, i); //判断 a 与 i的关系
}

int main()
{
    int i, j, k;
    while (scanf("%d %d", &n, &m), n+m)
    {
        for (i=1; i<=n; i++)
            for (map[i][i]=0, j=i+1; j<=n; j++)
                map[i][j] = map[j][i] = INF; //初始化矩阵之间关系

            for (k=1; k<=n; k++)
            {
                for (i=1; i<=m; i++)
                {
                    recone[k].Map[i] = 0;
                    for (j=1; j<=m; j++)
                    {
                        scanf("%d", &rec[k].Map[i][j]);
                        recone[k].Map[i] += rec[k].Map[i][j] * j; //   2->1
                    }
                }
            } // 接受矩阵信息

            for (i=1; i<=n; i++)
                for (j=1; j<=n; j++)
                    if (i != j)
                        creat(i, j); // 处理矩阵 i*j

                    for (k=1; k<=n; k++)
                        for (i=1; i<=n; i++)
                            for (j=1; j<=n; j++)
                                if (map[i][k] + map[k][j] < map[i][j])
                                    map[i][j] = map[i][k] +map[k][j];
                                scanf("%d", &m);
                                while (m--)
                                {
                                    scanf("%d %d", &i, &j);
                                    if (map[i][j] != INF)
                                        printf("%d\n", map[i][j]);
                                    else
                                        printf("Sorry\n");
                                }
    }
    return 0;
}

西风萧瑟 2009-12-04 09:05 发表评论

HDU 1787 GCD Again （欧拉函数）

西风萧瑟 — Wed, 02 Dec 2009 12:34:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=1787

/***
count the number of the integers M (01.
即：N - 1 - phi(N)

由于1采用欧拉性质：
    1.若n是质数p的k次幂，φ（n）= （p-1）p^(k-1)
    2.若m，n互质，φ（mn）= φ(m)φ(n)

若 n =p1^a1 * p2^a2 ** pn^an
则   phi(n)    = (p1-1)*p1^(a1-1) * (p2-1)*p2^(a2-1) ** (pn-1)*pn^(an-1)
            = N * (p1-1)*(p2-2)**(pn-1)/(p1*p2**pn)
**/

#include <stdio.h>
#define N 10001
__int64 p[5000];
int hash[10001];
int main()
{
    __int64 i, j, ans, n, m, temp;

    p[0] = 1; //记录素数个数
    p[1] = 2;
    for (i=3; i<N; i+=2)
    {
        if (hash[i])
            continue;
        p[++p[0]] = i;
        for (j=i*i; j<N; j+=i)
            hash[j] = 1;
    } //筛素数


    while (scanf("%I64d", &n), n)
    {
        ans = 1;
        m = n;
        for (i=1; p[i]<=m && i<=p[0]; i++)
            if (m%p[i]==0)
            {
                temp = 1;
                while (m%p[i] == 0)
                {
                    m /= p[i];
                    temp *= p[i];
                }
                temp /= p[i];
                ans*=(p[i]-1)*temp;
            }
        if (m>1)
        {
            ans *= (m-1);
        }    //如果剩下那个数大于1,m为大于10000的质数

        printf("%I64d\n", n-ans-1);
    }
}

西风萧瑟 2009-12-02 20:34 发表评论

想你的时候很幸福幸福的有些难过

西风萧瑟 — Wed, 02 Dec 2009 08:50:00 GMT

听歌的时候总会想到你
想到我们一起去唱歌
唱知心爱人唱蓝莲花
你说我这都敢唱出来
我也被吓到了说真的
只有小亭安慰我唱的不错其实我用心了

吃饭的时候会想到你
想到你带我去吃太谷的油泼麺
我记得当时吃不饱还加了个土豆丝
一下觉得饭菜很便宜呵呵
你总是怕我吃不饱
把你的给我来吃
你总是觉得自己的好吃
让我吃你碗里的

等车的时候会想到你
想到我们去等校车
那么多人还要排队上车
有票你却没座位
我让你坐我位置你还不乐意
心里骂你傻其实我幸福死啦
车上的老师教育我们要好好走下
我们慢慢的听烦了

去食堂吃饭的时候会想到你
想到你带我去你们食堂去吃冷菜
你说很便宜的
我想说你傻
是你吃的太少了
省下钱来看我
其实没有必要
而我却感动的一塌糊涂

坐公交车的时候会想到你
想到我们在家见面的时候总是跟公交车打交道
而我要坐2个小时的车
每每都是让你等我
等的跟我生气
要回去其实你要回去大可不必等我到了再回去的
其实我很内疚
但是我已经赶时间了
车很慢
我又何尝不想马上把你抱在怀你里呢

听到青花瓷的时候会想到你
想到我们晚上一起去建行旁边吃米线
你总是吃小的
我总是担心你吃不饱
出门的时候故意慢下来
因为台阶下面接了冰
我怕你滑到

逛超市的时候我会想到你
好不容易去了趟你们学校
去超市给你买点东西
我那两件你悄悄扔一件
扔的我很心疼
为什么你不会像其他女孩人给我要东要西呢

去公园看到别人划船的会想到你
我们在太古的公园里划船
傻乎乎刚开始不会控制
我使劲儿晃
你怕掉到水里其实那水不深的
也许都没你高
我说要跳上去买冷饮
你就是不让我走

买茉莉花茶的时候会想到你
跟你在一起
买了一瓶希望再中一瓶的时候
它果然中了
真好

看到火车的时候就想哭
想到你送我到杭州的那一刻
我就心碎
其实我也哭了
每次都是我先把你送走的
那一次
却想多看看你
想看着你送我
看着徐徐开动的火车
你骂我不该让你送我的
我心疼得要死

跟朋友一起吃饭喝酒的时候会想到你
身边没有你
记得那个时候我跟你们学校的那个兄弟喝酒的时候
你什么都没说
没有像别人假正经的说少喝点
想起来很幸福
只是你不在我身边的时候才想到
喝酒喝多了
身上过敏
烫伤就会发红
那个烟头留下的伤疤显得格外的刺眼
但如今喝多的时候
看到它却是另一种幸福
不论明天丢失了什么
我还有它
至少我还有它告诉我
我深爱着一个女孩

西风萧瑟 2009-12-02 16:50 发表评论

hdu2824 The Euler function 欧拉函数

西风萧瑟 — Tue, 01 Dec 2009 11:21:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=2824

定义：    对于正整数n，φ(n)是小于或等于n的正整数中，与n互质的数的数目；
                例如: φ(8) = 4, 因为1，3，5，7均和8互质。
性质：  1.    若p是质数，φ（p）= p-1.
               2.    若n是质数p的k次幂，φ（n）= （p-1）p^(k-1)
                        因为除了p的倍数都与n互质
               3.    欧拉函数是积性函数，若m，n互质，φ（mn）= φ(m)φ(n)
               根据这3条性质我们就可以退出一个整数的欧拉函数的公式，因为一个数总可以一些质数的乘积的形式。
               E(k) = (p1-1)(p2-1)…(pi-1)*(p1^(a1-1))(p2^(a2-1))…(pi^(ai-1))
                        = k*(p1-1)(p2-1)…(pi-1)/(p1*p2*…pi)
                        = k*(1-1/p1)*(1-1/p2)…(1-1/pk)
在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素)
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

以下是2种求欧拉函数的算法

1 void init()
2 {
3     __int64 i,j;
4     e[1] = 1;
5     for(i=2;i<=N;i++)
6         if(!e[i])
7         {
8             for(j=i; j<=N; j+=i)
9             {
10                 if (!e[j])
11                     e[j] = j;
12                 e[j] = e[j] / i * (i-1);
13             }
14         }
15 }

利用素数筛选：

void init()
{
    __int64 i, j;

    p[0] = 1; //记录素数个数
    p[1] = 2;
    for (i=3; i<N; i+=2)
    {
        if (hash[i])
            continue;
        p[++p[0]] = i;
        for (j=i*i; j<N; j+=i)
            hash[j] = true;
    } //筛素数

    e[1] = 1;

    for (i=1; i<=p[0]; i++)
        e[p[i]] = p[i] - 1; //初始化素数的phi

    for (i=2; i<N; i++)
    {
        if(!e[i])
        {
            for (j=1; j<=p[0]; j++)
                if (i % p[j]==0)
                {
                    if (i / p[j] % p[j])
                        e[i] = e[i / p[j]] * e[p[j]];
                    else
                        e[i] = e[i / p[j] ]* p[j];
                    break;
                } // 利用上述性质求解
        }
    }
    return ;
}

明显第一种的编程复杂度要低很多
所以，一般情况下（N不是很大），采用第一种即可；
贴在这里供以后复习

西风萧瑟 2009-12-01 19:21 发表评论

PKU2677,HDU2224 经典DP之双调旅行商（TSP）

西风萧瑟 — Mon, 30 Nov 2009 10:38:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=2224
货郎问题(Traveling Salesman Problem，简称“TSP”)也叫货郎担问题，中国邮路问题，旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中，它成为许多重要算法思想的测试平台，同时也促使一些新的理论领域的产生，比如多面体理论和复杂性理论。货郎问题：给定n个结点和任意一对结点{i，j}之间的距离为dist(i，j)，要求找出一条闭合的回路，该回路经过每个结点一次且仅一次，并且该回路的费用最小，这里的费用是指每段路径的距离和。货郎问题求解其精确解是NP难的，并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上，就成为欧氏平面上的货郎问题,也叫欧几里德旅行商问题(Eculid Traveling Salesman Problem)。但是，即使是欧氏平面上的货郎问题也是NP难的。因此通常用来解决TSP问题的解法都是近似算法。其中第一个欧几里德旅行商问题的多项式近似算法是Arora在1996年使用随机平面分割和动态规划方法给出的。

J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。事实上，存在确定的最优双调路线的O(n*n)时间的算法。

/**********************************************************************
*        Bitonic path (详见《算法导论》 P217)
*        一个人从p1严格地增的走到pn，然后再严格递减的回到p1;求总路径的最小值；
*        网上看到很多解题报告。。。看的我直冒汗
*        只好自己看书，翻译。。。
*        对于1 <= i <= j <= n, 我们定义P(i, j)是一条包含了P1, P2, P3 …… Pj的途径;
*        这条路径可以分成2部分：递减序列与递增序列
*        起点是Pi(1 <= i <= j)，拐点是P1，终点是Pj, P[i, j]为其最小值；
*        状态转移方程为：
*        b[1,2] = |P1P2|,
*        i < j-1时， b[i,j] = b[i,j-1] + |Pj-1Pj|    点Pj-1在递增序列中，
*        i = j-1时， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 }  点Pj-1在递减序列中
*        b[n,n] = b[n-1,n] + |Pn-1Pn|
**********************************************************************/

#include <stdio.h>
#include <math.h>
#define INF 0x7fffffff
#define N 201
struct point{
    double x, y;
}point[N];
int n;
double dis[N][N];

double distant(int i, int j)
{
    return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
}

double dp()
{
    int i, j, k;
    double temp, b[N][N];

    b[1][2] = dis[1][2];
    for (j=3; j<=n; j++)
    {
        for (i=1; i<=j-2; i++)
            b[i][j] = b[i][j-1] + dis[j-1][j];

        b[j-1][j] = INF;
        for (k=1; k<=j-2; k++)
        {
            temp = b[k][j-1] + dis[k][j];
            if (temp < b[j-1][j])
                b[j-1][j] = temp;
        }
    }

    b[n][n] = b[n-1][n] + dis[n-1][n];

    return b[n][n];
}

int main()
{
    int i, j;
    double ans;
    while (scanf("%d", &n) > 0)
    {
        for (i=1; i<=n; i++)
            scanf("%lf %lf", &point[i].x, &point[i].y);

        for (j=2; j<=n; j++)
            for (i=1; i<j; i++)
                dis[i][j] = distant(i,j);

        ans = dp();

        printf("%.2lf\n", dp());
    }
}

西风萧瑟 2009-11-30 18:38 发表评论

图论的知识点

西风萧瑟 — Fri, 27 Nov 2009 06:37:00 GMT

路径问题
        0/1边权最短路径
        BFS
        非负边权最短路径（Dijkstra）
            可以用Dijkstra解决问题的特征
        负边权最短路径
        Bellman-Ford
            Bellman-Ford的Yen-氏优化
            差分约束系统
        Floyd
            广义路径问题
            传递闭包
            极小极大距离 / 极大极小距离
        Euler Path / Tour
            圈套圈算法
            混合图的 Euler Path / Tour
        Hamilton Path / Tour
            特殊图的Hamilton Path / Tour 构造

    生成树问题
        最小生成树
        第k小生成树
        最优比率生成树
        0/1分数规划
        度限制生成树

    连通性问题
        强大的DFS算法
        无向图连通性
            割点
            割边
            二连通分支
            有向图连通性
            强连通分支
            2-SAT
            最小点基

    有向无环图
        拓扑排序
            有向无环图与动态规划的关系

    二分图匹配问题
        一般图问题与二分图问题的转换思路
        最大匹配
            有向图的最小路径覆盖
            0 / 1矩阵的最小覆盖
        完备匹配
        最优匹配
        稳定婚姻

    网络流问题
        网络流模型的简单特征和与线性规划的关系
        最大流最小割定理
        最大流问题
            有上下界的最大流问题
                循环流
        最小费用最大流 / 最大费用最大流

    弦图的性质和判定

西风萧瑟 2009-11-27 14:37 发表评论

hdu3215 The first place of 2^n（对数思想）

西风萧瑟 — Fri, 27 Nov 2009 06:25:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=3215
题目大意是计算2^0到2^n中每个数的最左边一位，然后记录1-9每个数字出现的次数并依次打印出来；
考虑到n的范围 [0,10000]，不可能去计算 2^n

hdu 1060 Leftmost Digit http://acm.hdu.edu.cn/showproblem.php?pid=1060 与此题一样

/**
    先看一个例子：

        31415926   最左面那位数是3，如何得来？

        取对数： lg(3.1415926 * 10^7) = lg(3.1415926) + 7
        也就是说，一个整数取对数以后变为2部分，不妨设小数部分为A (0 <= A < 1)，整数部分为B
        所以，一个整数可以写成 10^A * 10^B
        至于 10^B 是大家熟悉的 10000……
        而 10^A 是什么样子的呢？肯定是小于10的小数    (为什么呢，如果大于10了，B的值则加1)
        那么 A 的整数部分就是我们要求的数
        大致思路就是：对一个数x求对数，取出小数部分A，则10^A的整数部分就是x的最左面的那位数

    进入本题：

        x = 2^n
        lg(x) = n * lg(2)
        A = lg(x) - lg(x)的整数部分
        10^A = ……

    其实这道题卡的事精度问题，整数与小数来回转化肯定有精度损失这里的A要加上1.0e-6
*/

#include <stdio.h>
#include <math.h>

#define eps (1.0e-6)

int f[10010][10];

int main()
{
    int i, j, y;
    double A, x, s=log10(2);

    f[0][1]=1;
    for (i=1; i<=10000; i++) {
        for(j=1; j<10; j++)
            f[i][j] = f[i-1][j];

        x = i * s;
        A = x - (int)x;
        y = (int) (pow(10, A)+eps);

        f[i][y]++;
    }

    while (scanf("%d",&y),y+1) {
        printf("%d", f[y][1]);
        for(i=2; i<10; i++)
            printf(" %d",f[y][i]);
        printf("\n");
    }

    return 0;
}

西风萧瑟 2009-11-27 14:25 发表评论

【转】强大的poj分类

西风萧瑟 — Thu, 26 Nov 2009 13:31:00 GMT

摘要: 初期:一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. ... 阅读全文

西风萧瑟 2009-11-26 21:31 发表评论

HDU2809 God of War(动态规划之状态压缩）

西风萧瑟 — Thu, 26 Nov 2009 12:46:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=2809
HH大牛出的题目，比赛的时候被唬住了没有去做，今天兴致来了认真敲了一下，秒杀
这题跟1074doing homework一样，位压缩，没的说，自底向上计算，见图

#include<iostream>
using namespace std;
#define N 1100000
int m,n,hp,ati,def;
struct node{
    int ati;
    int def;
    int hp;
    int lv;
    int exp;
}q[N],tt;
struct man{
    int ati;
    int def;
    int hp;
    int exp;
}man[21];
int max(int a,int b)
{
    return a>b?a:b;
}
int war(int j,int i)
{
    int time;
    time=man[i].hp/max(1,q[j].ati-man[i].def);
    if(man[i].hp%max(1,q[j].ati-man[i].def)==0)
        time--;
    if(time>=0)
        return time;
    return -1;
}

void dp()
{
    int i,j,time,add,temp,next;
    for(j=0;j<m;j++)
    {
        if(q[j].hp<=0)
            continue;
        for(i=0;i<n;i++)
        {
            temp=j>>i;
            if(temp&1)
                continue;
            else
                next=j+(1<<i);
            if((time=war(j,i))==-1)
                continue;//战斗失败，continue
            tt=q[j];
            tt.hp-=time*max(1,man[i].ati-tt.def);
            tt.exp+=man[i].exp;
            if(tt.exp>=100)
            {
                add=tt.exp/100;
                tt.exp%=100;
                tt.ati+=add*ati;
                tt.def+=add*def;
                tt.hp+=add*hp;
                tt.lv+=add;
            }
            if(q[next].hp==0||tt.hp>q[next].hp||(q[next].hp==tt.hp&&(tt.lv*100+tt.exp)>(q[next].lv*100+q[next].exp)))
            {
                q[next]=tt;
            }
        }
        q[j].hp=0;
    }
}

int main()
{
    int i;
    char name[22];
    while(scanf("%d%d%d%d%d%d",&q[0].ati,&q[0].def,&q[0].hp,&ati,&def,&hp)>0)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%s%d%d%d%d",name,&man[i].ati,&man[i].def,&man[i].hp,&man[i].exp);
        m=(1<<n)-1;
        q[0].lv=1;
        q[0].exp=0;
        for(i=1;i<=m;i++)
        {
            q[i].hp=0;
        }
        dp();
        if(q[m].hp>0)
            printf("%d\n",q[m].hp);
        else
            printf("Poor LvBu,his period was gone.\n");
    }
    return 0;
}

西风萧瑟 2009-11-26 20:46 发表评论

Dijkstra算法的优化（堆+邻接表，优先队列+邻接表）hdu2544

西风萧瑟 — Thu, 26 Nov 2009 06:48:00 GMT

摘要: Dijkstra算法的核心：选出一个已经求出最短路的点，加上一条边求出另一个点的最短路；d'[v]=min{d[u]+w(u,v)|u的最短距离已求出且边（u,v)存在} 借助堆取出d[u];http://acm.hdu.edu.cn/showproblem.php?pid=2544堆+邻接表花了一上午。。。 #includeusing ... 阅读全文

西风萧瑟 2009-11-26 14:48 发表评论