挑战程序设计竞赛 —— 蓄势待发(准备篇)

素颜马尾好姑娘i 2022-01-07 12:37 431阅读 0赞

一．蓄势待发——准备篇

1.编写一个程序，判断纸片上缩写的数字是k1，k2, ……，kn时，是否存在抽取4次和为m的方案，如果存在输出Yes，否则输出No

输入：

n= 3

m= 10

k= \{ 1, 3, 5\}

输出：

Yes （例如4次抽取的结果是1，1，3，5时，和为10。）

采取的方法可以遍历所有的可能情况。

#include <iostream>
     
    using namespace std;
     
    const int MAX_N = 3;
     
    int main()
    {
        int n = 3;
        int m = 10;
        int k[MAX_N] = { 1, 3, 5};
     
        bool f = false;
     
        for( int a = 0; a < n;a++)
        {
            for(int b = 0; b <n; b++)
            {
                for(int c = 0; c< n; c++)
                {
                    for(int d = 0;d < n; d++)
                    {
                        if( k[a] +k[b] + k[c] + k[d] == m)
                        {
                            f =true;
                        }
                    }
                }
            }
        }
     
        if( f)
        {
            cout <<"Yes" << endl;
        }
        else
        {
            cout <<"No" << endl;
        }
     
        return 0;
    }

2.最富盛名的程序设计竞赛

世界规模的大赛——Google Code Jam (GCJ)

Google公司几乎每年都会举办的世界规模的程序设计竞赛，参赛者在2-3小时内解决大约4道题目。

向高排名看齐 —— TopCoder

一家策划并举办程序设计竞赛的公司，举办比赛设计多个领域。它还有一年一度的TCP公开赛。

历史悠久的竞赛——ACM-ICPC

美国计算机写会主办的，面向大学生的竞赛，也是历史最悠久的程序设计竞赛。三人一队，要求在5个小时内解决大约10道题目。

面向中学生的信息学奥林匹克竞赛——JOI-IOI

通过网络自动评测——Online Judge(OJ)

PKUOnline Judge(POJ) —— [ http://poj.org][http_poj.org] 题库中有大量题目

ShereOnline Judge(SPOJ) ——http://www.spoj.pl 允许使用各种各样的语言

SGUOnline Contester——http://acm.sgu.ru 具有模拟参加历史比赛的虚拟赛功能

UVaOnline Judge——http://uva.onlinejudge.org

Codeforces——http://codeforces.com 与TopCoder一样定期举办比赛，且维护历年题库

3.以高效算法为目标

运行时间的估算，可以从复杂度进行估算，如果估算的复杂度为O(n)，那么将最大的n带进去，就得到了运行时间的上限，只要上限不超即可。

**简单题目开始**：有n根棍子，棍子i的长度为ai，想要从中选出3根棍子组成周长尽可能长的三角形，请输出最大的周长，若无法组成三角形则输出0。

例如：

输入：

n= 5

a= \{ 2, 3, 4, 5, 10\}

输出：

12（选择3，4，5时）

输入：

n= 4

a= \{4, 5, 10, 20\}

输出：

0（无论怎么选都无法组成三角形）

#include<iostream>
    using namespace std;
     
    int main()
    {
        int n = 5;
        int a[] = { 2, 3, 4, 5,10};
     
        int maxSum = 0;
        for( int i = 0; i < n;i++)
        {
            for( int j = i+1; j< n; j++)
            {
                for( int k = j+1;k < n; k++)
                {
                    int sum = a[i]+ a[j] + a[k];
                    int big = max(a[i], max(a[j], a[k]));
     
                    if( sum - big> big && sum > maxSum)
                    {
                        maxSum =sum;
                    }
                }
            }
        }
     
        cout << maxSum<< endl;
     
        return 0;
    }

POJ的题目Ants：n只蚂蚁以每秒1cm的速度在长为Lcm的杆子上爬行。当蚂蚁爬到杆子的短点时就会掉落下来。由于杆子太细了，两只蚂蚁相遇时，他们不能交错通过，而是只能各自反向爬回去，对于每一只蚂蚁，我们知道它距离杆子最短的距离xi，但不知道它当前的爬向，请计算所有蚂蚁落下杆子所需要的最短时间和最长时间。

输入：

L= 10

n= 3

x= \{2, 6, 7\}

输出：

min= 4 （左，右，右）

max= 8 （右，右，右）

第一种方法：

最容易想到的就是穷举法，即枚举所有蚂蚁的初始朝向的组合，利用递归函数实现。

这样可以知道，每只蚂蚁的初始朝向有两种可能，那么n值蚂蚁就是2 x 2 x 2 ……x 2 =2^n种，当n较小时可以解决。如果n过大，则无法处理。

第二种方法：

首先考虑最短时间，我们可知所有蚂蚁都朝向较近的端点走会比较好。事实上，这种情况下，不会发生两只蚂蚁相遇的情况，而且不可能在比此更短的时间内走到杆子的端点。

在考虑最长时间的情况。当蚂蚁相遇之后，蚂蚁都将反向继续运动。如果不考虑蚂蚁之间的差异性，那么就相当于是两个蚂蚁交错通过后继续运动（蚂蚁的运动速度相同）。这样就可以得到所有的蚂蚁运动其实都是独立的，所以要求最长时间，只要求出蚂蚁到杆子端点的最大距离就好了。

那么求最短时间和最长时间变为：所有蚂蚁中每个蚂蚁运动到端点的最短时间中的最长时间 和 所有蚂蚁中每个蚂蚁运动到端点的最长时间中的最长时间

#include <iostream>
    using namespace std;
     
    int main()
    {
        int L = 10;
        int n = 3;
        int x[] = { 2, 6, 7};
     
        int mintime = 0;
        int maxtime = 0;
        for( int i = 0; i < n;i++)
        {
            mintime = max(mintime,min(x[i], L-x[i]));
     
            maxtime = max(maxtime,max(x[i], L-x[i]));
        }
     
        cout << "min=" << mintime << endl;
        cout << "max=" << maxtime << endl;
     
        return 0;
    }

**难度增加的抽签问题**：

如果将前面抽取n次和为m的题目的限制条件改为 1<= n <= 1000，那么应该如何求解？最初的四重循环的时间复杂度为O(n^4)，如果n=1000，那么复杂度为10^12，这样就过于复杂了。

1.对于四重循环如下：

for( int a = 0; a < n; a++)
    { 
         for(int b = 0; b < n; b++)     {  for(int c = 0; c < n; c++) {
    for(int d = 0; d < n; d++)
    
    
    { if( k[a] + k[b] + k[c] +k[d] == m) {f = true; } } }     } } 
     
     
            最内层是验证k[a] + k[b] + k[c] + k[d] == m，通过处理式子可知，k[d] = m – (k[a] + k[b] +k[c])。就是说最内层循环可变为 判断是否存在m – (k[a] + k[b] + k[c])值，这样可以在最内层采取快速搜索的方法。例如采用二分搜索的方法。二分搜索的时间复杂度为O(logn)。
    
           这样：
    
           排序时间O(nlogn)
    
           循环时间 O(n^3 * logn)
    
           那么总的时间复杂度变为了O(logn*n^3)：
    
     
     #include<iostream>
    using namespace std;
    //
    bool bsearch(int k[], int x, int n)
    {
        int l = 0, r = n;
     
        while(r > l)
        {
            int i = (l + r) / 2;
            if( k[i] == x)
            {
                return true;
            }
            else if(k[i] < x)
            {
                l = i + 1;
            }
            else
            {
                r = i;
            }
        }
     
        return false;
    }
     
    int main()
    {
        int n = 3;
        int m = 10;
        int x[] = { 1, 3, 5};
     
        sort(x, x+n);
     
        bool f = false;
     
        for(int a = 0; a < n;a++)
        {
            for(int b = 0; b <n; b++)
            {
                for(int c = 0; c< n; c++)
                {
                    if(bsearch( x,m-x[a]-x[b]-x[c], n))
                    {
                        f = true;
                    }
                }
            }
        }
     
        if( f)
        {
            cout << "Yes" <<endl;
        }
        else
            cout <<"No" << endl;
     
        return 0;
    }
     
    
          2. O(n^2 * logn)的算法
    
           按照1中的思路，我们可已经内层的两个循环一起考虑，也即k[d] + k[c] = m – (k[a] + k[b])。这个时候就不能直接使用二分搜索了，但是我们如果预先枚举出k[d] + k[c]所得到的n^2个数字，并且排好序，便可以使用二分搜索了。
    
           此时：
    
           排序时间 O(n^2 * 2logn)，常数省略：O(n^2 * logn)
    
           循环时间 O(n^2 * logn)
    
           总时间也就是O(n^2 * logn)：
    
     
     #include<iostream>
    using namespace std;
     
    #define MAX_N 3
    //
    bool bsearch(int k[], int x, int n)
    {
        int l = 0, r = n;
     
        while(r > l)
        {
            int i = (l + r) / 2;
            if( k[i] == x)
            {
                return true;
            }
            else if(k[i] < x)
            {
                l = i + 1;
            }
            else
            {
                r = i;
            }
        }
     
        return false;
    }
     
    int main()
    {
        int n = MAX_N;
        int m = 10;
        int x[] = { 1, 3, 5};
        int xx[MAX_N * MAX_N];
     
        for( int c = 0; c < n;c++)
        {
            for( int d = 0; d <n; d++)
            {
                xx[c*n + d] = x[c]+ x[d];
            }
        }
     
        sort( xx, xx + n*n);
     
        bool f = false;
        for(int a = 0; a < n;a++)
        {
            for(int b = 0; b <n; b++)
            {
                if(bsearch( xx,m-x[a]-x[b], n*n))
                {
                    f = true;
                }
            }
     
        }
     
        if( f)
        {
            cout <<"Yes" << endl;
        }
        else
            cout << "No" << endl;
     
        return 0;
    } 
    
    By  Andy @ 2013年7月22日

[http_poj.org]: http://poj.org/