A.水仙花数

C++ 代码

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        bool flag = false;
        int cnt = 0;
        for (int i = n; i <= m; i++)
        {
            int a = i / 100, b = i / 10 % 10, c = i % 10;
            if (pow(a, 3) + pow(b, 3) + pow(c, 3) == i)
            {
                if (cnt) printf(" ");
                cnt++;
                flag = true;
                cout << i;
            }
        }
        if (flag) puts("");
        else cout << "no" << endl;
    }
    return 0;
}

B.财务管理

C++ 代码

#include <iostream>

using namespace std;

double sum;

int main()
{
    for (int i = 0; i < 12; i++)
    {
        double x;
        cin >> x;
        sum += x;
    }
    printf("$%.2lf\n", sum / 12);
    return 0;
}

C.绝对值排序

C++ 代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

int n;
int a[N];

bool cmp(int a, int b)
{
    return abs(a) > abs(b);
}

int main()
{
    while (cin >> n && n)
    {
        for (int i = 0; i < n; i++)
            cin >> a[i];

        sort(a, a + n, cmp);

        for (int i = 0; i < n; i++)
        {
            cout << a[i];
            if (i != n - 1) cout << ' ';
        }
        puts("");
    }
    return 0;
}

D.空瓶换饮料

如果用 a 表示换喝饮料的瓶数，用 b 表示原有的空瓶数，用 N 表示换一瓶饮料需要的空瓶数，那么“空瓶换饮料”公式用字母表示是：
b - 1 : 无论换了多少次，最后都至少剩下一个瓶子，先把这个瓶子放一边不管
N - 1 : 三个空瓶换一瓶饮料相当于两个空瓶就能换一瓶饮料

a = (b 一 1) ÷ (N 一 1)

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << n + (n - 1) / (3 - 1) << endl;
    return 0;
}

E.素数判定

C++ 代码

#include <iostream>
#include <cmath>

using namespace std;

int n, m;

bool isprime(int x)
{
    bool flag = true;
    if (x == 1) return false;

    for (int i = 2; i <= sqrt(x); i ++ )
        if (x % i == 0)
        {
            flag = false;
            break;
        }
    return flag;
}

int main()
{
    while (cin >> n >> m && (n != 0 || m != 0))
    {
        bool flag = true;
        for (int i = n; i <= m; i++)
        {
            if (isprime(i * i + i + 41)) continue;
            else
            {
                flag = false;
                break;
            }
        }
        if (flag) cout << "OK" << endl;
        else cout << "Sorry" << endl;
    }
    return 0;
}

F.一只小蜜蜂…

由于蜜蜂每次只能从前1个蜂房或前2个蜂房过来，那么f(n)=f(n-2)+f(n-1)。这不就是一个斐波拉契数列吗？
求a到b的可能路线数量，其实就是求1到(b-a)的斐波那契数。
得出结论：数组可以开成long long，最后输出时用%I64d或%lld输出。
（PS：应该适用所有OJ）

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 60;

LL q[N];
int n;

int main()
{
    q[1] = 1, q[2] = 2;
    for (int i = 3; i < N; i++)
        q[i] = q[i - 1] + q[i - 2];
    while (cin >> n)
    {
        while (n--)
        {
            int a, b;
            cin >> a >> b;
            cout << q[b - a] << endl;
        }
    }
    return 0;
}

G.钱币兑换问题

完全背包

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 32768;

int f[N];
int n;

int main()
{
    int v[3] = { 1, 2, 3 };
    while (cin >> n)
    {
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 0; i < 3; i++)
            for (int j = v[i]; j <= n; j++)
                f[j] += f[j - v[i]];

        cout << f[n] << endl;
    }
    return 0;
}

H.How Many Tables

裸的并查集

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        memset(p, 0, sizeof p);
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) p[i] = i;
        while (m -- )
        {
            int a, b;
            cin >> a >> b;
            int fa = find(a), fb = find(b);
            if (fa != fb) p[fa] = fb;
        }
        int res = 0;
        for (int i = 1; i <= n; i ++ )
            if (p[i] == i)
                res ++ ;
        cout << res << endl;
    }
    return 0;
}

I.寒冰王座

完全背包

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;

int v[3] = { 150, 200, 350 }, w[3] = { 150, 200, 350 };
int f[N];

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        memset(f, 0, sizeof f);
        for (int i = 0; i < 3; i++)
            for (int j = v[i]; j <= n; j++)
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        cout << n - f[n] << endl;
    }
    return 0;
}

J.畅通工程

最小生成树

Prim

#include <stdio.h>
#include <string.h>

#define RANGE 101
#define MAX 0x7fffffff
int cost[RANGE][RANGE];
int mincost[RANGE];
bool used[RANGE];

// n个点，m条边
int n,m;

int Min(int a,int b)
{
    return a<b?a:b;
}

void prim( void )
{
    // sum 记录最小生成树权值
    int i,v,u,sum;
    // 从1到各个点距离，初始化used数组
    for( i=1;i<=n;++i )
    {
        used[i]=false;
        mincost[i]=cost[1][i];
    }
    sum=0;

    while( true )
    {
        v=-1;

        // 从没有连接到的点中，找最近的点
        for( u=1;u<=n;++u )
            if( !used[u] && (v==-1 || mincost[u]<mincost[v]) )
                v=u;

        if( v==-1 ) break;
        if( mincost[v]==MAX )   break;

        used[v]=true;
        sum+=mincost[v];

        // 更新到各个点的距离
        for( u=1;u<=n;++u )
            mincost[u]=Min( mincost[u],cost[v][u] );
    }


    // 判断能否构成最小生成树
    for( i=1;i<=n;++i )
    {
        if( used[i]==false )
        {
            printf("?\n");
            return;
        }
    }
    printf("%d\n",sum);
}

int main()
{
    int i,j;
    int u,v,c;

    while( scanf("%d%d",&m,&n) && m )
    {
        // init cost by MAX
        for( i=1;i<=n;++i )
            for( j=1;j<=i;++j )
            {
                if( i==j )  cost[i][j]=0;
                else    cost[i][j]=cost[j][i]=MAX;
            }
        for( i=0;i<m;++i )
        {
            scanf("%d%d%d",&u,&v,&c);
            cost[u][v]=cost[v][u]=c;
        }

        prim();
    }
    return 0;
}

Kruskal

#include <stdio.h>
#include <algorithm>
using namespace std;
struct EDGE
{
    int u,v,cost;
}eg[100001];
int n,m,father[100001];

bool cmp(EDGE e1,EDGE e2)
{
    return e1.cost<e2.cost;
}

// 并查集 初始化函数
void Init( int m )
{
    int i;
    for(i=1;i<=m;i++)
        father[i]=i;
}
// 并查集 查找函数
int Find(int x)
{
    while(father[x]!=x)
        x=father[x];
    return x;
}
// 并查集 合并函数
void Combine(int a,int b)
{
    int temp_a,temp_b;
    temp_a=Find(a);
    temp_b=Find(b);

    if(temp_a!=temp_b)
        father[temp_a]=temp_b;
}

// 最小生成树 Kruskal 算法
int Kruskal( void )
{
    EDGE e;
    int i,res;
    sort(eg,eg+n,cmp);
    // 并查集 初始化
    Init(m);

    // 构建最小生成树
    res=0;
    for( i=0;i<n;++i )
    {
        e=eg[i];
        if( Find(e.u)!=Find(e.v) )
        {
            Combine(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main()
{
    int i,ans;
    bool bl;
    while( scanf("%d%d",&n,&m) && n )
    {
        for( i=0;i<n;++i )
            scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].cost);
        ans=Kruskal();

        // 是否所有的点都在同一个集合
        bl=true;
        for(i=2;i<=m;++i)
            if( Find(1)!=Find(i) )
            {
                bl=false;
                break;
            }

        if( bl )    printf("%d\n",ans);
        else    printf("?\n");
    }
    return 0;
}