挑战程序设计竞赛 练习日记

没用的碎碎念：2022.1.24：我又滚回来看算法了，仿佛回到了一年前……在学校摸鱼了一年，说实话什么都没学到，我的学校只是一个弱鸡一本，专业课程都很水，大一上学了c语言，大一下学了数据结构，大二上学了计算机网络，这就是目前为止一个大二计算机学生学的所有专业课。没了高三那股劲，越来越懒了，看着我以前高中那些985，211，或是一些普通的计算机一本大学的同学，挺担心自己的未来的，我觉得我竞争不过他们。我们学校专业分流了，我选了软件工程，没有什么特殊的原因，只是因为这个专业比计科课少罢了，想考研但是现在对自己没什么信心了，软件工程别人说挺好就业的，大概是为了给自己考不上研究生找了一条退路罢了……
上一年我参加了蓝桥杯，在突击了一个寒假的数据结构后，我拿了省二，今年的愿望，大概就是拿省一吧（做梦ing……），我发现了一本挺好的算法书，叫做《挑战程序设计竞赛》，我想这个寒假看一下里面的题目自己动手写一下，希望我能多勤奋点儿吧，其实寒假已经过了十几天了，这十几天我都在睡觉玩手机熬夜，真的看不下去这样的自己了，真的求求我自己能勤奋一点点吧……
备注：这里的代码不是书上的代码，是自己写的，书上的代码会比我的严谨简洁，这只是一篇小小的练习日记，用的是c和c＋＋语言。

第 1 章：蓄势待发——准备篇

三角形Ants（POJ 1852）抽签部分和问题Lake Counting (POJ 2386)迷宫的最短路径

样例 1
输入
5
2 3 4 5 10
输出
12

样例 2
输入
4
4 5 10 20
输出
0

思路：暴力枚举，枚举三条边长a，b，c，通过a+b>c判断是否能组成三角形，遍历找周长=a+b+c的最大值。
我的代码：

#include 
using namespace std;
int a[105];
int main()
{
    int n;
    cin>>n;
    int max=0;
    for (int i=0;i>a[i];
    }
    for (int i=0;ia[k])
                {
                    int len=a[i]+a[j]+a[k];
                    if (len>max) max=len;

                }
            }
        }
    }
    cout< 
Ants（POJ 1852） 
题目链接：http://poj.org/problem?id=1852
 
翻译：
 
 输入
 第一行整数 T，表示有 T 组测试数据
 每组测试包含以下内容：
 第一行两个整数，分别为 L,n，表示竿子长度和蚂蚁数量
 第二行 n 个整数，表示每个蚂蚁距离左端点的距离 xi
 
输出
 输出 T 行，每行两个整数，表示一组测试数据中所有蚂蚁落下竿子所需的最短时间和最长时间
 
样例 1
 输入
 2
 10 3
 2 6 7
 214 7
 11 12 7 13 176 23 191
 输出
 4 8
 38 207
 
思路要点：蚂蚁是否反向不影响掉落时间，最短时间为每只蚂蚁最短时间的最长时间，最长时间为每只蚂蚁最长时间的最长时间（只有自己才能看懂的笔记，建议去看书上的推导）
 
心情：就挺巧妙的，没思考出来，本来我以为会很难的。
 
我的代码：
 
#include 
using namespace std;
int x[1000005];
int main()
{
    int t;
    cin>>t;
    for (int i=0;i>l>>n;
        int maxt=0,mint=0;
        for (int j=0;j>x[j];
        }
        
        for (int j=0;j 
ac截图：（第一次去POJ提交代码嘻嘻）
 
 
抽签 

 输入
 第一行输入整数 n
 第二行输入整数 m
 第三行输入 n 个整数，表示每个纸片上的数字 ki
 
输出
 一行，Yes 或 No
 
样例 1
 输入
 3
 10
 1 3 5
 输出
 Yes
 
思路：
 法一：暴力枚举 a+b+c+d，看是否等于m，时间复杂度O(n4)
 法二：a+b+c+d=m 改写为 c+d=m-a-b，枚举m-a-b，看是否等于c+d。用数组cd存储c+d的所有值，在cd中利用二分法查找m-a-b，时间复杂度O(n4 logn)
 
心情：我之前认为一定都要枚举abcd才能算出来，没想到一个小小的公式变化就可以把时间复杂度大幅降低
 
我的代码
 
#include 
using namespace std;
int k[1005];
int cd[1000005];
int n,m;
bool cmp(int a,int b)
{
    return a=l)
    {
        int mid=(l+r)/2;
        if (cd[mid]==x) return true;
        if (cd[mid]>x) r=mid-1;
        else l=mid+1;
    }
    return false;
}
int main()
{
    cin>>n>>m;
    for (int i=0;i>k[i];
    }
    for (int c=0;c 
部分和问题 

 输入
 多组测试数据，以 EOF 结束
 每组测试数据由以下部分组成：
 第一行为整数 n
 第二行为 n 个整数 ai
 第三行为整数 k
 数据保证多组测试数据的 n 之和不超过 20
 
输出
 每组测试输出一行，Yes 表示能成功，No 表示失败
 
样例 1
 输入
 4
 1 2 4 7
 13
 4
 1 2 4 7
 15
 输出
 Yes
 No
 
思路：用dfs搜索
 
心情：感觉和上面抽签那题挺像的，但是抽签那题因为它可以重复选，所以用不了dfs，这题能用。好久没搞算法连dfs都写不熟练了，太搞笑了。
 
我的代码：
 
#include 
using namespace std;
int a[25];
int n,k;
bool dfs(int i,int sum)
{
    if (i==n) return sum==k;
    if (dfs(i+1,sum)==true) return true;
    if (dfs(i+1,sum+a[i])==true) return true;
    return false;
}
int main()
{
    
    while (cin>>n)
    {
        for (int i=0;i>a[i];
        }
        cin>>k;
        if (dfs(0,0)==true) cout<<"Yes"< 
Lake Counting (POJ 2386) 
题目链接：http://poj.org/problem?id=2386
 
翻译
 
 输入
 第一行两个整数 N,M,表示 N 行 M 列
 接下来有 N 行，每行 M 个字符，可能是 .， W，. 表示地，W 表示水
 
输出
 一个整数，表示多少个水洼
 
样例 1
 输入
 10 12
 W…WW.
 .WWW…WWW
 …WW…WW.
 …WW.
 …W…
 …W…W…
 .W.W…WW.
 W.W.W…W.
 .W.W…W.
 …W…W.
 输出
 3
 
思路：dfs遍历每个水洼，遍历过的W改为.，大的dfs次数即为水洼个数
 
心情：本来我的想法是不用dfs，从头到尾遍历园子，如果左，上，左上，右上有W则合并为一个水洼，否则水洼个数sum++。然后我的样例没过，但是现在的网站都不能显示没过的具体样例，我通过一行行打印把我没过的一个样例拼出来了，原来是我考虑问题不全面。因为如果出现(0,0),(1,1),(0,2)都是W的情况，我按顺序遍历到(0,2)时它会把自己视为一个水洼。我之前没用考虑到这种情况，所以调了好久。现在这题我懂了，开心，用dfs写也挺简单的，本来dfs那里八个方向我本来打算枚举来着，它的那个dx，dy还挺妙的，以后我遍历周围我也用这个。
 
我的代码：
 
#include 
using namespace std;
char MAP[105][105];
void dfs(int x,int y)
{
	MAP[x][y]='.';
	for (int dx=-1;dx<=1;dx++)
	{
		for (int dy=-1;dy<=1;dy++)
		{
			if (MAP[x+dx][y+dy]=='W')
			{
				dfs(x+dx,y+dy);
			}
		}
	}
}
int main()
{
	int sum=0;
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			cin>>MAP[i][j];			
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (MAP[i][j]=='W')
			{
				dfs(i,j);
				sum++;
			}
		}
	}
	cout< 
ac截图：（第二次去POJ提交代码嘻嘻）
 
 
迷宫的最短路径 

 输入
 第一行两个整数 N, M
 接下来 N 行，每行 M 个字符，表示迷宫
 输出
 输出一行，表示从起点到终点的最少步数
 
样例 1
 输入
 10 10
 #S######.#
 …#…#
 .#.##.##.#
 .#…
 ##.##.####
 …#…#
 .#######.#
 …#…
 .####.###.
 …#…G#
 输出
 22
 
思路：bfs搜索
 
心情：新学了一个pair，以前我用的是结构体。写代码时犯了两个错误：第一个是遍历上下左右四个方向时我用的时上一题Lake Counting的方法，然后忘记了那个方法是八连通的而本题只是四连通，要用回老方法两个数组。第二个是判断入队那里的条件我写的其中一个是MAP[nx][ny]!=’.’ 然后忘记了终点是‘G’，我还纠结了半天为什么最后一步不行，好粗心哦，应该用 MAP[nx][ny]!=’#'才对。
 
我的代码：
 
#include 
using namespace std;
char MAP[105][105];
int d[105][105];
int n,m;
int sx,sy,gx,gy;//起点终点坐标
typedef pair P;
int bfs()
{
    queue 
 que; 
    que.push(P(sx,sy));
    while (que.size())
    {
        P p = que.front();
        que.pop();
        if (p.first==gx&&p.second==gy) break;
        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        for (int i=0;i<4;i++)
        {           
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if (nx=0&&ny>=0&&MAP[nx][ny]!='#'&&d[nx][ny]==-1) 
            {
                d[nx][ny]=d[p.first][p.second]+1;
                que.push(P(nx,ny));
            }          
        }
    }
    return d[gx][gy];
}
int main()
{   
    cin>>n>>m;
    for (int i =0;i>MAP[i][j];
            if (MAP[i][j]=='S')
            {
                sx=i;
                sy=j;
            }
            else if (MAP[i][j]=='G')
            {
                gx=i;
                gy=j;
            }
        }
    }
    for (int i =0;i