赛时题目(只包含本人做错的)

-T639096 落落的去养植物-

题目描述

落落的去正在养植物。这株植物发芽时的高度为 $0,\mathrm{cm}$。将发芽当天记为第 $0$ 天，从发芽后的第 $i\ (0\leq i)$ 天晚上起，植物的高度会增加 $2^i,\mathrm{cm}$。

落落的去的身高为 $H,\mathrm{cm}$。

落落的去每天早上都会和这株植物比身高。请你求出植物的高度第一次超过落落的去身高是在发芽后的第几天早上。

错误原因

• 把 $i$ 初始设成了 $1$(应该是 $0$)所以只拿了 $76pts$。

错误代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,sum=0,res=1,i;
signed main()
{
	cin>>h;
	if(h<0)
	{
		cout<<"0";
		return 0;
	}
	for(i=1;sum<=h;i++)
	{
		res=pow(2,i);
		sum+=res;
	}
	cout<<i;
	return 0;
}

落落得去说 $pow$ 函数不能随便用,因为 $pow$ 的返回值是 $double$ 类型的,所以用的时候要把结果强制变为 $int$ 类型。

正解

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,sum=0,res=0,i;
signed main()
{
	cin>>h;
	while(res<=h)
	{
		res=(res+1)*sum;
		sum++;
	}
	cout<<sum;
	return 0;
}

-T638482 小梦的铁索连环-

题目描述

小梦成为了曹操的军师！

为了战胜蜀吴联军，小梦建议曹操将战船链接。现在我们可以将战船和铁索组成的集合看做是一张平面图（即任意两条铁索不相交），其中战船可以看做是点，铁索可以看做是边，每艘战船拥有一个点权，代表战船的战力。为了出奇制胜，小梦决定找到一个特种兵团。我们定义一个特种兵团为一个由若干战船和铁索组成的子集，其中任意两点之间都有直接的边链接，并且内部的权值之和是最大的。

现在小梦想请你找到，最大的特种兵团战力是多少。

错误原因

• 没有想出正解

错误代码

没得

正解

思路

• 通过分析题面可以发现每艘船之间相连的铁链不能相交,不难看出,当一个兵团的船数大于 $4$ 时必定会有铁链相交,所以直接枚举四个点来找最大的权值即可。
• 四 $\space$ 重 $\space$ 循 $\space$ 环

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1010],ans;
vector<int> g[1010];//邻接表:优化边的数量
bool vis[1010][1010];//邻接矩阵:表示两个顶点之间的关系
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		vis[x][y]=true;
		vis[y][x]=true;
	}
	for(int i=1;i<=n;i++)//枚举每个顶点(第一个点)
	{
		int len=g[i].size();//len:相邻点的数量
		for(int j=0;j<len;j++)//枚举第一个邻居(第二个点)
		{
			int v=g[i][j];
			if(!vis[i][v])
			{
				continue;
			}
			ans=max(ans,a[i]+a[v]);//a[i]+a[v]:前两个点的权值和
			for(int k=j+1;k<len;k++)//枚举第二个邻居(第三个点)
			{
				int w=g[i][k];
				if(!vis[i][w] || !vis[v][w])
				{
					continue;
				}
				ans=max(ans,a[i]+a[v]+a[w]);//a[i]+a[v]+a[w]:前三个点的权值和
				for(int u=k+1;u<len;u++)//枚举第三个邻居(第四个点)
				{
					int z=g[i][u];
					if(!vis[i][z] || !vis[v][z] || !vis[w][z])
					{
						continue;
					}
					ans=max(ans,a[i]+a[v]+a[w]+a[z]);//a[i]+a[v]+a[w]+a[z]:四个点的权值和
				}
			}
		}
	}
	cout<<ans;
	return 0;
}