牛客周赛Round53

A

经过模拟之后会得到答案啊永远都是二分之一。

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
//假如说是只有1的话，
    cout<<"0.500000";
}

B

从头部和尾部进行模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a;
    cin>>a;
    int l=0;
    int r=a.length()-1;
    int ans=0;
    while(l<r)
    {
        int minn=min(a[l],a[r]);
        int maxn=max(a[l],a[r]);
        ans+=min(maxn-minn,26-maxn+minn);
        l++;
        r--;
    }
    cout<<ans;
}

C

经过观察，可以发现，真正有用的只有01操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int x,y,z;
    cin>>x>>y>>z;
    //删除11，01，00
    //只有在0后面的1是有用的
    //0111100001111
    //01011100001110010
    stack<char>a;
    int ans=0;
    for(int i=0;i<s.length();i++)
    {
        char c=s[i];
        if(a.empty())
        {
            a.push(c);
        }
        else
        {
            if(c=='1'&&a.top()=='0')
            {
                a.top();
                ans++;
            }
            else
            {
                a.push(c);
            }
        }
    }
    cout<<min(ans,y);
}

D

本题需要牢记一点：分组背包是可以不选择组内的物品的。

因此本题要处理的话要么按照夏神的每个组内默认选择一个物品，然后去所有物品和的最大值作为上界限。

要么用下面这种可行性dp的写法。

f[i][j] |=f[i-1][j-w[i][k]];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define int long long
int w[1500][1550];
int f[1000][6000];
int ans=1e9;
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 	cin>>w[i][j];
	 int target;
        cin>>target;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
	 for(int j=0;j<=target+1000;j++)
	  for(int k=1;k<=m;k++)//s[i]表示第i组物品的个数
	   if(j>=w[i][k])//剩余的背包容量j大于第i组的第k个物品的体积 
	   {
	   	  f[i][j] |=f[i-1][j-w[i][k]];
	   }
for(int i=0;i<=target+1000;i++)
{
    if(f[n][i])
    {
        ans=min(ans,abs(target-i));
    }
}
    cout<<ans;
    return 0;
}

E

题目描述：

给定一个长度为 n 的序列 a1, a2, ..., an，定义一次操作为：选择任意一个元素 ai，将 ⌊ai / 2⌋ 添加到序列的结尾，并将 ai 从序列中删除。你可以进行任意多次操作（也可以一次都不做），要求使得序列的 MEX 最大。

MEX 是指数组中未出现的最小非负整数。例如，数组 {3, 1, 2} 的 MEX 为 0。

输入描述：

  • 每个测试文件包含多个测试点。第一行输入一个整数 T，代表测试数据组数。
  • 每组测试数据描述如下：
    • 第一行输入一个整数 n，代表序列的长度。
    • 第二行输入 n 个整数 a1, a2, ..., an。

输出描述：

  • 对于每一个测试点，在一行上输出一个整数，代表当前序列的最大 MEX。

思路解析

为了找到序列的最大 MEX，我们需要探索每个可能的 MEX 值，验证其是否可以通过对序列进行操作而实现。因为 MEX 的值是单调递增的，所以可以使用二分搜索来优化查找过程。

二分搜索

  1. 初始化边界：设定左边界 l 为 0，右边界 r 为 n + 1。原因是 MEX 值的最大可能性不会超过 n，因为数组最多有 n 个不同的非负整数。
  2. 中间值判断：取中间值 mid，验证 mid 是否可以成为序列的 MEX 值。
  3. 调整边界：如果 mid 可以成为 MEX 值，则尝试更大的 MEX 值（l = mid + 1）；否则，尝试更小的 MEX 值（r = mid - 1）。
  4. 终止条件：二分搜索结束后，输出最大的可能 MEX 值。

验证函数

定义一个 check 函数来验证给定的 MEX 值 x 是否可以通过对序列进行操作而实现：

  • 初始化一个记录数组 st 来存储已处理的数值。
  • 遍历序列中的每个元素，将其不断右移（除以 2），直到找到一个未标记且小于 x 的值。
  • 如果所有 x 个位置都能找到对应的值，则 x 是有效的 MEX 值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
using ll=long long;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    ll n;cin>>n;
    vector<ll>a(n);
    map<ll,ll>st;
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    ll l=0,r=n+1;
    ll ans=0;
    auto check = [&](ll x)->bool{
        ll res=0;st.clear();
        for(ll i=0;i<n;i++){
            ll t=a[i];
            while(t && t>=x || t && st[t]){
                t>>=1;
            }
            if(!st[t])st[t]++,res++;
        }
        return x==res;
    };
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<endl;
    }
}

  • 输入处理：每组测试数据的读取时间复杂度为 O(n)。
  • 二分搜索：搜索范围是 0 到 n + 1，所以二分搜索的时间复杂度为 O(log n)。
  • 验证函数 check：每次验证的时间复杂度为 O(n log a[i])，其中 a[i] 是数组中的元素，最多为 10^6。

综合分析，最坏情况下总时间复杂度为 O(T * n * log n * log a[i])，可以接受。

F

st[x][y][0]: 标记位置 (x, y) 是否已在不破坏障碍的情况下访问过。

st[x][y][1]: 标记位置 (x, y) 是否已在破坏一个障碍的情况下访问过。

以下为具体流程：

不破坏障碍的 BFS (bbfs):

  • 从起点 (1, 1) 开始，进行标准的 BFS 搜索，计算从起点到终点的最短路径。
  • 如果在没有破坏任何障碍的情况下找到了路径，记录最短路径长度。

破坏障碍并失去一个方向的 BFS (bfs):

  • 对于每个可能的方向（上下左右），调用 bfs 函数。
  • 在搜索过程中，如果遇到障碍且尚未破坏任何障碍，则破坏该障碍并继续搜索，同时失去一个方向的移动能力。
  • 计算破坏障碍并失去一个方向后的最短路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
#define int long long
using ll=long long;
typedef pair<int,int> pii;

int n,m;
char g[N][N];
int st[N][N][2];
int flag=1;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int ans;
void bbfs()
{
	flag++;
	queue<pair<pii,int>> q;
	q.push({{1,1},0});
	st[1][1][0]=flag;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		int x=t.fi.fi,y=t.fi.se,dd=t.se;
		if(x==n&&y==m)
		{
			ans=min(ans,dd);
			continue;
		}
		for(int i=0;i<4;i++)
		{
			int ax=x+dx[i],ay=y+dy[i];
			if(ax<1||ax>n||ay<1||ay>m) continue;
			if(g[ax][ay]=='X'||st[ax][ay][0]==flag) continue;
			st[ax][ay][0]=flag;
			q.push({{ax,ay},dd+1});
		}
	}
	
}

int bfs(int z)
{
	flag++;
	queue<pair<pii,pii>> q;
	q.push({{1,1},{0,0}});
	st[1][1][0]=flag;
	int ans1=1e9;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		int x=t.fi.fi,y=t.fi.se,dd=t.se.fi,op=t.se.se;
		if(x==n&&y==m)
		{
			ans1=min(ans1,dd);
			continue;
		}
		for(int i=0;i<4;i++)
		{
			if(i==z) continue;
			int ax=x+dx[i],ay=y+dy[i],ap=op;
			if(ax<1||ax>n||ay<1||ay>m) continue;
			if(g[ax][ay]=='X')
			{
				if(op==1) continue;
				else ap=1;
			}
			else
			{
				if(st[ax][ay][ap]==flag) continue;
			}
			st[ax][ay][ap]=flag;
			q.push({{ax,ay},{dd+1,ap}});
		}
	}
	return ans1;
}

void solve()
{
	
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> g[i][j];
		}
	}
	
	ans=1e9;
	bbfs();
	
	for(int i=0;i<4;i++)
	{
		ans=min(ans,bfs(i));
	}
    if(ans>=1e9) cout << -1 << endl;
    else
	cout << ans << endl;
	
	
}
signed main()
{
	int t=1;
	while(t--)
	solve();
	
	return 0;
}