ZOJ 2029 The Intervals (二分查找)

ZOJ 2029 The Intervals

给出数组a,求的最小的一个[ a[i], a[j] )使得b[m]在这个区间内,简单的方法就是排序,然后查找范围。为了练习二分,我学习了lower_bound和upper_bound,哈哈stl好强大,以后做题时不能因为不会用二分而超时了。lower_bound(a.begin(),b.end(),x)返回一个迭代器,使得这个位置的元素>=x,用upper_bound则表示>x

(更多…)

继续阅读 →

UVA 103 Stacking Boxes (DP)

UVA 103 Stacking Boxes

看到了这个题之后思路就无比清晰。矩形嵌套问题,不过这个是多维的。我们判断两个序列a,b的关系的时候,需要枚举a的各种排列,看看有没有可能a的每一个位置上的元素都比b中对应元素小,如果真枚举的话太麻烦了。可以把a和b都排下序,然后再比较。确定元素间的关系之后,就很好构造LIS了。在这道题中,我学会了sort和max_element的用法。。感觉stl挺方便的。

(更多…)

继续阅读 →

ZOJ 2059 The Twin Towers (DP)

ZOJ 2059 The Twin Towers

被成为经典的双塔问题。痛恨死了,我搞了好多天,我真是对dp一点都不开窍啊。。怎么办?看了大黄的思路,dp[i]表示高度差为i时候低的塔的最大值,这个状态定义的很纠结,也不是很好理解。就先拿我的代码来说吧,每输入一个水晶,就更新一下dp。。。这个时候我们需要一个额外的t数组来保存前边所有物品所产生的状态,因为只用一个dp来保存的话,当前物品所产生的状态有可能叠加。。对状态的更新产生影响。。t数组每次更新完就再赋给dp。。dp[0]表示高度相等时的高度。。。
(更多…)

继续阅读 →

ZOJ 2402 Lenny’s Lucky Lotto Lists (DP)

ZOJ 2402 Lenny’s Lucky Lotto Lists

用1-M之间的数,组成一个长度为N的序列,使得每一个数是之前那个数的二倍以上,如对于N=4,M=10:

1 2 4 8
1 2 4 9
1 2 4 10
1 2 5 10

有四种选择,题目给出的范围是N<=10,M<=2000。

设DP[i][j]表示长度为i的序列结尾为j的情况数,从小往大递推就行了。。

(更多…)

继续阅读 →

ZOJ 1524 Supermarket (DP)

ZOJ 1524 Supermarket

Mr. Jones得到一份购物清单,清单上按顺序写出了需要购买的物品,在买东西的时候要按照顺序弄。。。。另外,题目还给出了,超市中的物品排列情况,买东西的时候还要按照物品的顺序进行购买,显然,可能会有各种不同的购买方案,同时花费也是变化着的,要求输出最少的花费。

设一个V[i]表示,购买前i+1件物品所需要的最少费用,L[i]表示列表上商品的类型 ,K[i]表示超市里的商品类型,P[i]商品价格price。由于要随着商品的排列情况进行选择,从第一件商品开始进行选择,层循环因为用到滚动数组,所以要从M-1开始循环。。。。每找到一个便宜的价格就更新,最终V[M-1]就是结果。。。。      如果这样不好理解的话,可以这样V[i][j]表示用超市中前i个物品,买清单上前个j物品所需花费的最少量。。。 好好想想。。好好想想。。。
(更多…)

继续阅读 →

UVA 11408 Count DePrimes (线性筛法)

UVA 11408 Count DePrimes

看到大牛的空间上有贴这个题的,我最近在看数论,所以就看了看O(n)线性筛法,没有花太长时间,不过感觉挺神奇的,我在内层循环里加了个count++来计算它的计算次数,没想到筛200万的素数count只有185万,好神奇。这个算法的思想就是避免重复筛,比如35=5*7,就被筛了两次,我们只让一个和数只被他最小的素因子晒到。1Y了,好高兴~

(更多…)

继续阅读 →

近期被虐,不爽~

昨天晚上做codeforces,第一题因为条件判断错误,WA了,比赛一完就A了。。第二题应该用贪心的方法,我的超时了。。。然后就什么都不会了。。

做了十几次的CF,第一次剃光头,其余每次出2 + 1题,rating始终是绿色范围,看来是一点进步都没有。

寒假看了好多东西,数学方面的,一开学就一直在刷数论题,收获还是蛮大的,不过进步并没有地方体现出来,而且现在看题做题头都晕了,干点其他事吧,又怕路后,哎。。。。

今天下午,做ustc的题目,少了个二分而超时。。。

不由地感觉菜到无助。。

继续阅读 →

ZOJ 2964 Triangle (非常好的一个数论题)

ZOJ 2964 Triangle

题目的描述我感觉有点问题,是看了shi哥空间才知道的.三角形的三边l>m>n,a^l=a^m=a^n(modz),由于三边不等,所以说要使边权和最小,就要找到a生成的子群规模.由于我们知道他肯定是euler(z)的约数,所以枚举约数进行寻找,这个题就亮在这个寻找约数的过程.


(更多…)

继续阅读 →

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

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

#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! (模拟)

ZOJ 1208 Roll the Die!

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

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

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

(更多…)

继续阅读 →