二分 算法

AtCoder Beginner Contest 236

AtCoder Beginner Contest 236补题

Posted by zhangmh on 2022-01-26
Estimated Reading Time 9 Minutes
Words 1.7k In Total
Viewed Times

第一次在Atcoder上打比赛，，，看到了t神ak的全过程orzorz

A - chukodai

img

给出字符串，交换第a个和第b个字符后输出。

思路：虽然很简单，但是一开始写的代码十分笨比，修改一下，也是第一次用swap()解题。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
string s;
int a,b;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>s;
    cin>>a>>b;
    swap(s[a-1],s[b-1]);
    cout<<s<<'\n';
	return 0;
}

B - Who is missing?

img

一个序列中每个数字有4个，现在随机删掉一个，给出处理后的序列，求删掉的是哪个数字。

思路：排序后遍历数组，哪个数不够4个直接break出循环输出。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=4e5+5;
int n,ans;
int a[N],cnt[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=4*n-1;i++) cin>>a[i];
    sort(a+1,a+n*4);
    for(int i=1;i<=4*n-1;i++)
    {
    	cnt[a[i]]++;
    	if(a[i+1]!=a[i]&&cnt[a[i]]!=4)
    	{
    		ans=a[i];
    		break;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

os：这个题还可以和异或相关？！（偶数个相同数的异或和为0，奇数个为该数）

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int ans,n,x; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n*4-1;i++)
    {
    	cin>>x;
    	ans^=x;
	}
	cout<<ans<<'\n';
	return 0;
}

C - Route Map

img

img

给出所有车站名，再给出所有停靠的车站名，判断每个车站是否停靠。

思路：map应用。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int n,m;
string s[N],t[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>m;
    map<string,int>mp;
    for(int i=1;i<=n;i++) cin>>s[i],mp[s[i]]++;
    for(int i=1;i<=m;i++) cin>>t[i],mp[t[i]]++;
    for(int i=1;i<=n;i++)
    {
    	if(mp[s[i]]!=2)
    	cout<<"No"<<'\n';
    	else cout<<"Yes"<<'\n';
	}
	return 0;
}

D - Dance

img

img

给出任意两人组队的快乐值，怎样组队可以使总的快乐值最大，求最大的快乐值。

思路：DFS应用，注意是可回溯的DFS。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=10;
ll a[N*2][N*2],n;
bool b[N*2];
ll res;

void dfs(int pos,ll now)
{
	if(pos==2*n)
	{
		res=max(res,now);
		return;
	}
	if(b[pos]) dfs(pos+1,now);
	else
	{
		b[pos]=true;
		for(int i=pos+1;i<2*n;i++)
		{
			if(!b[i])
			{
				b[i]=true;
				dfs(pos+1,now^a[pos][i]);
				b[i]=false;
			}
		}
		b[pos]=false;
	}
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=0;i<2*n;i++)
    {
    	for(int j=i+1;j<2*n;j++)
    	cin>>a[i][j];
	}
	dfs(0,0);
	cout<<res<<'\n';
	return 0;
}

os：DFS还是不行啊，多练多尝试

E - Average and Median

img

img

在每个第i和第i+1个数中至少选一个，以该规则选择一个序列，使得平均值最大；再以相同规则选择一个序列，使得中位数最大。

思路：直接在值域上二分查找答案，用两个check两个二分查找，这两个check用到了一点DP，注意数据类型。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int n,a[N],b[N];
double f[N];

bool check1(double mid)
{
	for(int i=1;i<=n;i++) f[i]=max(f[i-1]+a[i]-mid,f[i-2]+a[i]-mid);
	if(max(f[n],f[n-1])>=0) return true;
	else return false;
}

bool check2(int mid)
{
	for(int i=1;i<=n;i++) b[i]=(a[i]>=mid)?1:-1;
	for(int i=1;i<=n;i++) f[i]=max(f[i-1]+b[i],f[i-2]+b[i]);
	if(max(f[n],f[n-1])>0) return true;
	else return false;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    double l=0,r=1e9,ans1=0;
    while(r-l>1e-5)
    {
    	double mid=(l+r)/2;
    	if(check1(mid)) l=mid,ans1=mid;
    	else r=mid;
	}
	int L=1,R=1e9,ans2=0;
	while(R>=L)
	{
		int mid=(L+R)>>1;
		if(check2(mid)) ans2=mid,L=mid+1;
		else R=mid-1;
	}
	printf("%.8lf\n",ans1);
	cout<<ans2<<'\n';
	return 0;
}

os：看了网友的代码我直呼这样也行？二分用法还需要加强掌握。

F - Spices

img

img

香料的辣度是n种香料的异或和，问想要使在1~2^n-1之间的辣度均可实现，最少需要花多少钱买香料。

思路：模拟吧大概是，，，我看懂了回来补题解

AC代码：

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;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=(1<<16)+5;
int n,a[N],pos[N],f[N];
ll ans;

bool cmp(int i,int j)
{
	return a[i]<a[j];
} 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<(1<<n);i++)//1<<n是2的n次方，n<<1是n*2
    	cin>>a[i];
    	pos[i]=i;
	}
	sort(pos+1,pos+(1<<n),cmp);
	f[0]=1;
	for(int i=1;i<(1<<n);i++)
	{
		if(f[pos[i]]) continue;
		ans+=a[pos[i]];
		for(int j=0;j<(1<<n);j++)
		if(f[j]==1&&f[j^pos[i]]==0) f[j^pos[i]]=2;
		for(int j=0;j<(1<<n);j++)
		if(f[j]==2) f[j]=1;
	}
	cout<<ans<<'\n';
	return 0;
}

若有错误请指教

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
二分 算法
FRIENDS
ESC