行者无疆 始于足下 - 行走,思考,在路上

zoj 1577

简单题,题目大意是给定两个数a、b,求x、y使得gcd(x, y) = a, lcm(x, y) = b,问由多少对这样的(x, y),其中gcd(x, y)为x, y的最大公约数,lcm(x, y)为x,y的最小公倍数。解题思路主要利用[tex]x \times y = gcd(x, y) \times lcm(x, y)[/tex]就行了。WA了两次是因为没看清楚题意"x and y, one line for each test.",太马虎了。代码如下:

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

long gcd(long a,long b)
{
	return b ? gcd(b, a%b) : a;
}

long lcm(long a, long b)
{
    return a / gcd(a, b) * b;
}

int main(int argc, char *argv[])
{
    long a, b;
    long m;
    int sum;
    
    while(scanf("%ld%ld", &a, &b) != EOF)
    {
        if (a == b)
        {
            sum = 1;
        }
        else
        {
            m = a * b;

            sum = 0;
            int i;
        
            for (i = 1; i < sqrt(m); ++i)
            {
                if (((m % i) == 0) && (gcd(i, m/i) == a))
                {
                    sum += 1;
                }
            }

            sum *= 2;
        }    
        printf ("%d\n",sum);
    }
    return 0;
}

 顺便,用了两个月的fvwm-crystal,感觉虽然轻量,但是有些细节颇有不便之处,比如每次新开窗口的时候窗口的大小和位置都“不太确定”——就是有时候窗口会覆盖底下的panel、有时候整个窗口又比整个屏幕都大……恰逢前天晚上兴奋无眠,因此便邪恶的敲了下面一条命令:

sudo emerge -av gnome-light    

编译过程比较顺利,又陆续装了gdm, gnome-do等小工具,配上Mac4Lin的主题,现在整个桌面看起来还是蛮pp的:

还有一个小问题就是gtk+和QT程序风格二异。我的解决方案是安装kde的control center:

sudo emerge -av systemsettings

然后在widget style中选择gtk+风格,如下图所示:

效果还算不错。其余的解决方案可以参考:

就是这样。嘿。

zoj 1284

简单题。题目大意就是判断一个数是否为Perfect number。可是我竟然三次才ac,原因是没有考虑到数字为1的时候。

求真因数和的时候可以考虑质数判断的算法,循环到[tex]\sqrt{n}[/tex]就行了。代码很长很菜:

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

int get_sum(int number)
{
    int i;
    int sum = 0;

    for (i = 1; i < sqrt(number); ++i)
    {
        if (number % i == 0)
        {
            sum += i + number / i;
        }
    }
    if ((int)sqrt(number) * (int)sqrt(number) == number)
    {
        sum += sqrt(number);
    }

    sum -= number;
    
    return sum;
}

int main(int argc, char *argv[])
{
    int number;

    printf ("PERFECTION OUTPUT\n");
    
    while (scanf("%d", &number) && number)
    {
        int sum = get_sum(number);
        
        if (sum < number)
        {
            printf ("%5.0d  DEFICIENT\n", number);
        }
        else if (sum == number)
        {
            printf ("%5.0d  PERFECT\n", number);
        }
        else
            printf ("%5.0d  ABUNDANT\n", number);
    }

    printf ("END OF OUTPUT\n");
    
    return 0;
}

zoj 1168

模拟递归问题。直接递归肯定不行,最容易想到的方法就是用数组模拟。中途遇到了一个问题,就是c++ iostream库的效率问题。用cin >> a >> b >> c时,TLE;换成scanf("%d%d%d", &a, &b, &c)时,AC,时间80ms。status中最前面的都是60ms,看来优化空间不大。关于c库和c++库的输入输出,还有待研

/**
 * @file   zoj1168.c
 * @author  <lox@freelox>
 * @date   Wed May 19 18:59:59 2010
 * 
 * @brief  zoj1168, 模拟问题。直接查表解决。
 * 但是需要注意的是,此题目用scanf系列,AC,时间80ms,用c++的cin流,则TLE,
 * 莫非cin和scanf真有那么大的时间消耗差别?
 */


#include <stdio.h>

int main(int argc, char *argv[])
{
    int w[21][21][21];

    int a, b, c;
    
    for (a = 0; a <= 20; a++)
    {
        for (b = 0; b <= 20; b++)
        {
            for (c = 0; c <= 20; c++)
            {
                if (a == 0 || b == 0 || c == 0)
                {
                    w[a][b][c] = 1;
                }
                else if (a < b && b < c)
                {
                    w[a][b][c] = w[a][b][c-1] + w[a][b-1][c-1] - w[a][b-1][c];
                }
                else
                    w[a][b][c] = w[a-1][b][c] + w[a-1][b-1][c] + w[a-1][b][c-1] - w[a-1][b-1][c-1];
            }
        }
    }

    while (scanf("%d%d%d", &a, &b, &c))
    {
        if (a == -1 && b == -1 && c == -1)
        {
            return 0;
        }
        if (a <= 0 || b <= 0 || c <= 0)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[0][0][0]);
        }
        else if (a > 20 || b > 20 || c > 20)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[20][20][20]);
        }
        else
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[a][b][c]);
    }
    
    return 0;
}

zoj 1101

毕竟是做题经验不足,开始看题被唬住了。题目大意是给定一个数据a[i],寻找四个数字i, j, k, m, 使得a[m]=a[i]+a[j]+a[k],并求出max(a[m])。

最容易想到的是暴力算法。求出每个三元组的和,然后再搜索,复杂度为O(n^3)级别的。但是我觉得应该会有更好的解法,就去百度上查。事实上最终我用的也是这种暴力方法。参考别人代码,结合STL。思路大体上是先排序,然后再二分搜索。最后通过的时间是50ms。看了下本题目的status,前面的高人通过时间都是0ms,由此看来本题肯定有优化的可能。只是我不知道罢了。暂且放下。

STL应用太过生疏,仿函数和函数指针的应用还经常混淆。需要加强。

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(int argc, char *argv[])
{
    int inta[1000], n, wi;

    while ((cin >> n) && n)
    {
        int i, j, m, u;
        wi = 536870912;
        for (i = 0; i < n; ++i)
        {
            cin >> inta[i];
        }

        sort(inta, inta+n);
        
        if (n < 4)
        {
            goto END;
        }

        for (i = n - 1; i >= 0; i--)
            for (m = n - 1; m >= 0; m--)
            {
                if (i == m)
                {
                    continue;
                }
                for (j = m - 1; j > 0; j--)
                {
                    if (j == i)
                    {
                        continue;
                    }

                    u = inta[i] - inta[m] - inta[j];

                    if (u != inta[i] && u != inta[m] && u != inta[j])
                    {
                        if (binary_search(inta, inta+n, u))
                        {
                            wi = inta[i];
                            goto END;
                        }
                    }
                }
            }
      END:
        if (wi == 536870912)
        {
            cout << "no solution" << endl;
        }
        else
            cout << wi << endl;
    }
    
    return 0;
}

zoj 1312

coding!coding!为什么这么简单的题目愣是做不对呢?

在网上找了相应正确的代码做了测试,没有发现哪里不对。求高人指点一二。

算法是永远的痛。加油加油。

#include <iostream>
#include <vector>
using namespace std;

bool is_prime(int n)
{
    for (int i = 2; i*i <= n; ++i)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

int get_prime_list(int n, vector<int> &prime_list)
{
    prime_list.push_back(1);
    prime_list.push_back(2);
    prime_list.push_back(3);
    
    for (int i = 5; i <= n; i = i+2)
    {
        if (is_prime(i))
        {
            prime_list.push_back(i);
        }
    }

    return 0;
}


int main(int argc, char *argv[])
{
    int N, C;
    int cases = 0;
    
    while (cin >> N >> C)
    {
        vector<int> v;
        get_prime_list(N, v);
        cout << N << " " << C << ":";

        int center = v.size() / 2;

        if (center + C > v.size())
            for (int i = 0; i < v.size(); i++)
                cout << " " << v[i];
        else
            for(int i = center - C + (v.size() % 2 ? 1 : 0); i < center + C; i++)
                cout << " " << v[i];

        cout << endl << endl;
    }
    
    return 0;
}




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee