A跑夜路

由于不能选临近的点，所以对于每个补给点有两种选择，首先是不喝第 $i$ 个补给点那么最大体力与前一个位置相同即：$dp[i]=dp[i−1]$喝第 $i$个补给点那么第 $i−1$ 个就不能喝因此最大体力为$dp[i]=dp[i−2]+a_i$ 于是取两者最大值： $dp[i]=max(dp[i−1], dp[i−2]+a_i)$

标砖程序代码如下

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
using u64 = unsigned long long;
constexpr int Nn = 2e5 + 10;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n+1),dp(n+10);
    for(int i=1;i<=n;i++)
        cin >> a[i];
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
        dp[i]=max(dp[i-1],dp[i-2]+a[i]);
    cout << dp[n] << '\n';
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

B贪心的牛

本题即最小区间覆盖，利用贪心的思想，每次选择能够覆盖当前时间点，并且右端点最远的区间，这样才能保证区间数量最少

标准程序代码如下

#include <bits/stdc++.h>
using namespace std;

struct segment{
	int l,r;
	bool operator<(const segment &x) const{
		return l<x.l;
	} // 重载小于号，用于 sort()。也可以用 cmp() 函数实现同样功能。
}range[25005];

int main(){
	int n,ed;
	scanf("%d%d",&n,&ed);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&range[i].l,&range[i].r);
	sort(range+1,range+n+1);
	int st=1,ans=0;
	for(int i=1,j=1;i<=n;){
		int r=0;
		while(j<=n&&range[j].l<=st){ // 左端点要 <= st，即该区间能覆盖 st 
			r=max(r,range[j].r); // 找右端点最大的
			j++;
		}
		if(r<st) break; // 找不到能覆盖 st 的区间
		ans++;
		if(r>=ed){ // 有解，输出
			printf("%d\n",ans);
			return 0;
		}
		st=r+1;i=j;
	}
	printf("-1\n");
	return 0;
}

C深夜巡楼

本题大意就是问一共有多少个互不连通的可通行区域以及最大的连通区域大小 就是基础的dfs搜索连通块，即遍历整个地图，遇到未访问的.就要使连通块数量$+1$，并且dfs搜索整个连通块，最终得到连通块大小比较更新最大值

标准程序代码如下

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
using u64 = unsigned long long;
constexpr int Nn = 2e5 + 10;
char mp[510][510];
int vis[510][510];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
int mx,n,m;
int dfs(int x,int y)
{
    int cnt=1;
    vis[x][y]++;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=n && tx>=1 && ty<=m && ty>=1 && mp[tx][ty]=='.' && vis[tx][ty]==0)
            cnt+=dfs(tx,ty);
    }
    return cnt;
}
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin >> mp[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='.'  && !vis[i][j])
            {
                ans++;
                mx=max(mx,dfs(i,j));
            }
    cout << ans << ' ' << mx << '\n';
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

D 独木桥

因为士兵完全相同，士兵的速率也相同，这道题可以简化成当两个人相撞时不再是方向改变，而是两个人直接穿过去，因为速度完全没有改变，所以到达相同长度的时间就一样，所以就可以忽略相撞，只是当成朝着一个方向走就好了

标准程序代码如下

#include<bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int l,n;
	cin>>l>>n;
	vector<int>a(n+1);
	int ma=-1,mi=1e9+10,ans=ma;
	if(n==0){
		cout<<"0 0"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma=max(a[i],ma);
		mi=min(a[i],mi);
		int t=min(l+1-a[i],a[i]-0);
		ans=max(ans,t);
	}
	cout<<ans<<' ';
	ans=max(l+1-mi,ma);
	cout<<ans<<endl;
}