2011年02月 存档

ZOJ 2657/POJ 1061 Appointment/青蛙的约会 (扩展欧几里得)

2011年02月21日,星期一

数论入门题目,讲解网上好多的,但是我感觉看完算法导论之后的理解更深刻一些,尤其是用群论来解释的东西,非常好,在此只是贴下模板什么的。。

#include<iostream>
using namespace std;
typedef long long LL;

//欧几里得算法
LL gcd(LL a,LL b) 
{
    if( b == 0 ) return a;
    else return gcd(b,a%b);
} 
//计算机中的模与数论中的不一样,需要转换 
LL geizheng(LL a,LL n)
{
    if( a < 0 ) 
        return n+a%n;
    return a%n;
}
//扩展欧几里得
LL ext_euclid(LL a,LL b,LL &x,LL &y)
{
    LL t,d;
    if( b == 0 )
    {
        x = 1;
        y = 0;
        return a;
    }
    d = ext_euclid(b,a%b,x,y);
    t = x;
    x = y;
    y = t - (a/b)*y;
    return d;
} 
void gao(LL a,LL b,LL l)
{
    LL x,y,t;
    LL d = ext_euclid(a,l,x,y);
    //cout << a << ' '<< b << ' '<< d << endl;
    if( b%d ) cout << "Pat\n";
    else
    {
        x *= b/d;
        cout << geizheng(x,l/d) << endl;
    }
}

int main(void)
{
    LL m,n,a,b,l,i,j;
    while( cin >>a>>b>>m>>n>>l )
    {
        if( m == n )
            cout<<"Pat\n";
        else if( m > n )
            gao(m-n,geizheng(b-a,l),l);
        else
            gao(n-m,geizheng(a-b,l),l);
    }
    return 0;
}

ZOJ 1208 Roll the Die! (模拟)

2011年02月9日,星期三

ZOJ 1208 Roll the Die!

还是筛子在平面坐标上滚动的问题,初始时候色子在(0,0)的位置,每组输入会给出一个top和front值,代表在初始点时候色子的上面和前面的数字,另外还会给出一系列的操作,问最终状态时候的坐标和此时的top,front值~

记得在去年暑假的时候,我们印了一份zoj的分类,照着上面的题目一个一个刷,后来cw说这上面的题目非常难,不是你们能力所能及的。当时模拟题分类的第一个就是他,我读懂了题,当时印象是非常麻烦,之后就放弃这个了,但脑子里始终有个印象:有个关于色子的很难的题我没做。早上A了3059,就是上一篇题解,关于色子的滚动,然后就想到了这题,AC掉之后非常高兴,今天下雪喽~

我用了宏定义,把方向用宏表示出来,理解起来轻松了许多:

(更多…)

ZOJ 3050 Die Board Game (bfs)

2011年02月9日,星期三

ZOJ 3050 Die Board Game

色子在坐标上滚动,给定起始点的位置和状态,看看能不能从起点走到终点并且和题目中给出的终点状态一样,求出最少步数的,n,m<=100.

刚开始我是一点想法都没有,后来看了网上的解题报告,说是每个坐标上都有24种状态,我们可以将带有状态的地图看成一个三维的map[i][j][state],这样就可以通过广搜来解决了,我又无语了,这都是谁想出来的啊,这么巧妙,刚开始由于不知道状态之间怎样转换,昨天想到了,就在今天早上A掉~

(更多…)

ZOJ 1003 Crashing Balloon(dfs)

2011年02月8日,星期二

ZOJ 1003 Crashing Balloon

踩气球,气球上的分值为1-100间的数,参赛者的初始分数为1,每踩一个气球就把气球的分数乘以自己的分数,得到比分,最后选手会声明自己的比分,但是有的人可能计算错误,所以最后的分数可能不正确,判断一下两个分数是否能产生….

刚接触acm的时候就看到这个题了..当时是什么思路也没有,现在又看还是不会,我总是想着把,所有的分解情况都列出来再进行比较,但是貌似不可行.今天忍不住偷偷看了别人的代码(貌似我已经几个月没有看过别人的代码了),顿时就震精了,为什么我想不到呢? :cry:
(更多…)

ZOJ 1107 FatMouse and Cheese(DP)

2011年02月7日,星期一

ZOJ 1107 FatMouse and Cheese

给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.

刚开始我想的搜索,但是无门.但是看题之前已经知道是dp了,就一直往那方面想,一开始就想到了从cheese最大点开始,把他相应范围内的最大数更新一下,也就是dp[i][j] = map[i][j] + (与i,j在合法范围内dp[*][*]最大值),dp[i][j]表示从(i,j)开始所能得到的最多cheese。但是想想实现起来比较麻烦。昨天晚上睡觉上微博的时候,突然想到把这些点按照cheese数排列,然后从前往后进行dp,相当于LIS,只不过中间的限制条件比较多。按照这个思路,我写出代码,并且ac掉:
(更多…)

ZOJ 1953 Advanced Fruits(LCS)

2011年02月5日,星期六

ZOJ 1953 Advanced Fruits

A掉这个题我十分激动,很久没有做dp题了,因为不是很开窍,前两天,累了就趴在床上看算导,翻到动态规划,没想到很顺利地从头到尾看完了,所以就像尝试下dp….这个属于最长公共子序列,以前做过不过这个题需要记录路径,由于路径不唯一,所以是special judge,两个字符串要合并成一个,并且公共部分只输出一次,这其中的细节认真想想就可以做出来..1Y,很高兴~

(更多…)

ZOJ 1694 Shredding Company

2011年02月4日,星期五

ZOJ 1694 Shredding Company

碎纸机,给一个带有数字的纸条,把他剪成几块,每块上的数字保持完整,sum为每一块上数字的加和,要求找到小于target的sum的个数,如果没有输出error,如果大于1输出rejected,如果有一个输出剪切的方式.曾经纠结的题目,现在感到不是那么难了..

(更多…)

ZOJ 1004 Anagrams by Stack

2011年02月3日,星期四

ZOJ 1004 Anagrams by Stack

这个题很早就看到了,但是当时关于栈没有很好的运用,而且还需要用递归所以就放过了。。今天重拾这个题,感觉应付起来很轻松,可能是因为进步了吧,嘿嘿。。1A~

i代表入栈操作,o代表弹出,对于一个字符串,从第一个字符开始,进行一系列的栈操作,问有没有可能出栈的字符可以按顺序组成另外一个字符串。ok函数表示得到的io操作是否能得到另外一个串。

(更多…)

ZOJ 1094 Matrix Chain Multiplication

2011年02月3日,星期四

ZOJ 1094 Matrix Chain Multiplication

矩阵链乘的时候,不同的结合方式所需要的运算次数不同,肯定存在一个乘法次数最少的结合方式(可以用dp求出),此题以此为背景,给出结合方式,求出所需要的乘法次数.算是经典的栈的应用,维护两个栈,KUO是括号的栈,M表示矩阵栈,从每一个表达式的开始,遇到左括号和矩阵就压入相应的栈,遇到右括号就进行栈顶两个元素的运算,直到最后。如果某两个元素不能相乘,输出error

(更多…)