目录

挑战程序设计竞赛第一章&第二章例题总结(正在写)

本文主要内容
思维,dfs,bfs,搜索,贪心算法。

思维

POJ-1852 Ants

原题链接

思路
对于最短耗费时间,蚂蚁朝近的端点走即可,此时没有相遇的情况,离自己的近端点最远的蚂蚁行走所耗费时间即是答案。
对于最长耗费时间,显然,两蚂蚁相遇再掉头折返走到端点和两蚂蚁相遇之后继续朝原来的方向走到端点所花费的时间是相同的,所以可将每一只蚂蚁看作是独立的,朝远的端点走即可。离自己的远端点最远的蚂蚁行走所耗费时间即为答案。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	int T;
	cin >> T;
	while(T--)
	{
		int len, n;
		cin >> len >> n;
		int maxTime = 0, minTime = 0;
		for(int i = 0; i < n; i++)
		{
			int posTmp;
			cin >> posTmp;
			minTime = max(minTime, min(posTmp, len-posTmp));
			maxTime = max(maxTime, max(posTmp, len-posTmp));
		}
		cout << minTime << ' ' << maxTime << endl;
	}
	return 0;
}

深度优先搜索

POJ-2386 Lake Counting

原题链接

思路
dfs,需要注意的是,一篇池塘搜索完之后需要停止搜索,另外在标记搜索过的方块时,搜索起点不要忘记标记。
参考代码
#include <cstdio>
using namespace std;

const int maxn = 110;
char field[maxn][maxn];
int n, m, res;
int dx[8] = {-1, 0, 1, 0, -1, 1, -1, 1}, dy[8] = {0, -1, 0, 1, -1, 1, 1, -1};

void dfs(int x, int y)
{
    int flag = 1;	//标记当前这片池塘是否搜完
    for(int i = 0; i < 8; i++)
    {
        int tmpX = x + dx[i], tmpY = y + dy[i];
        if(tmpX >= 0 && tmpX < n && tmpY >= 0 && tmpY < m && field[tmpX][tmpY] == 'W')
        {
            //printf("%d %d\n", tmpX, tmpY);
            flag = 0;	//相邻的方块中还有水,则这片池塘还没被搜完
            field[tmpX][tmpY] = '.';	//搜过的地方标记为没水的土地,防止重复
            dfs(tmpX, tmpY);
            if(flag) return;	//搜完了就结束循环
        }
    }
}

int main(void)
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        getchar();
        for(int j = 0; j < m; j++)
            scanf("%c", &field[i][j]);
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(field[i][j] == 'W')
            {
                res++;	//这个方块可以形成池塘,池塘数加1
                field[i][j] = '.';
                dfs(i, j);
            }
        }
    }
    printf("%d\n", res);

    return 0;
}

贪心

POJ-3617

原题链接

思路

贪心+双指针,比较头尾字符,哪个小取哪个,否则继续往字符串中心位置比较,若比较过程中,靠近头的那边出现了较小的字符,则取头部字符,反之则取尾部。若比较到最中心的位置(两指针相遇了)时字符仍相同,则随便取哪个都可以。
书上的贪心思路是:按照字典序比较S和将S反转后的字符串S';若S更小,则从S头部取字符;若S'更小,则从S尾部取字符;若相同,则从头尾取字符都可以。
两个思路都差不多,书上的办法显然更巧妙,将同一个字符串的顺序字符串和逆序字符串转化为了左起字符串和右起字符串,这样只需要一个数组即可。
如果WA了可以尝试下这类数据:

12
aaabeggcbaaa

上述输入的正确输出应为:
aaaaaabbcegg

参考代码

我的写法:

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 2010;
char s[maxn], t[maxn];

int main(void)
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        for(int i = 0; i < n; i++) cin >> s[i];

        int i = 0, j = n - 1;
        int len_t = 0;
        while(i < j)
        {
            if(s[i] == s[j])    //头部尾部相等,往字符串中心位置比较
            {
                int tmp_i = i, tmp_j = j;
                while(s[tmp_i] == s[tmp_j] && tmp_i < tmp_j)
                {
                    tmp_i++;
                    tmp_j--;
                }
                if(s[tmp_i] < s[tmp_j]) //靠近头部的位置出现了较小的字符
                    t[len_t++] = s[i++];
                else if(s[tmp_i] > s[tmp_j])    //靠近尾部的位置出现了较小的字符
                    t[len_t++] = s[j--];
                else    //靠近两天的位置字符大小相等,则随便取一边都可以
                    t[len_t++] = s[i++];
            }
            else if(s[i] < s[j])    //头部字符更小
                t[len_t++] = s[i++];
            else if(s[i] > s[j])    //尾部字符更小
                t[len_t++] = s[j--];
        }
        t[len_t++] = s[i++];    //两指针相遇的情况,也可以在上面的while循环里把 < 改为 <= 即可

        for(int k = 0; k < len_t; k++)
        {
            printf("%c", t[k]);
            if(((k + 1) % 80 == 0) && k < len_t - 1) printf("\n");
        }
    }

    return 0;
}

书上写法:

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

const int maxn = 2010;
char s[maxn];

int main(void)
{
    int n;
    while(cin >> n)
    {
        memset(s, 0, sizeof(s));
        for(int i = 0; i < n; i++) cin >> s[i];

        int a = 0, b = n - 1;
        int cnt = 0;
        while(a <= b)
        {
            bool left = false;   //标记顺序字符串和逆序字符串哪个更小
            for(int i = 0; a + i <= b; i++) //比较顺序和逆序字符串字典序大小
            {
                if(s[a + i] < s[b - i]) //顺序(左起)的更小
                {
                    left = true;
                    break;
                }
                else if(s[a + i] > s[b - i]) //逆序(右起)的更小
                {
                    left = false;
                    break;
                }
            }
            //根据字典序决定取头还是尾
            if(left) 
            {
                cout << s[a++];
                cnt++;
            }
            else 
            {
                cout << s[b--];
                cnt++;
            }
            if(cnt % 80 == 0 && cnt < n - 1)
                cout << endl;
        }
    }

    return 0;
}

POJ-3069

原题链接

思路
贪心。从最左边的没有被覆盖点开始遍历,距离这个点R以内的最靠右的点标记为放置装置的点。每个点都这样处理,直到所有点都被覆盖,这样就能够使得放置装置的数量最少。
英文题干中palantirs我也不知道是啥意思,翻译器也不认识,我暂且把它翻译为装置😥。
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int a[maxn];

int main(void)
{
    int r, n;
    while(scanf("%d %d", &r, &n) != EOF && (r != -1 && n != -1))
    {
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        sort(a, a + n);
        
        int res = 0;
        int idx = 0;
        while(idx < n)
        {
            //上一个装置(或未安装装置时)不能被覆盖最靠左的点
            int left = a[idx++];   

            //从这个点开始找,放置装置后能覆盖left的最靠右的点
            while(idx < n && a[idx] <= left + r) idx++; 
            
            //标记放置装置的点
            int right = a[idx-1]; 

            //移动到right能覆盖到的最靠右的点,它的右相邻点就是下一个装置需要覆盖的最靠左的点
            while(idx < n && a[idx] <= right + r) idx++;  
            
            res++;
        }
        printf("%d\n", res);
    }

    return 0;
}

POJ-3253

原题链接

思路
贪心。这里使用哈夫曼树的做法效率会高的多,递归做法为$O(n)$的复杂度,哈夫曼树做法的复杂度为$O(nlogn)$。
将数据构建成小根堆,每次取最小的优先合并,就会使得最后的总代价最小。将各堆合并的代价看成一棵树,最后的贪心思路就是,每次取这课树的深度最深,权值最小的两个节点合并,这两个节点可以是兄弟结点,也可以不是。这棵树的结构就是哈夫曼树,它按照节点权值排列,越小的节点深度越深。
参考代码
#include <queue>
#include <iostream>
using namespace std;

typedef long long LL;

int main(void)
{
    int n;
    cin >> n;
    priority_queue<LL, vector<LL>, greater<LL>> heap;
    for(int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        heap.push(t);
    }

    LL cost = 0;
    while(heap.size() > 1)
    {
        LL a = heap.top(); heap.pop();
        LL b = heap.top(); heap.pop();
        cost += a + b;
        heap.push(a+b);
    }

    cout << cost << endl;

    return 0;
}

POJ-2376

原题链接