官方题解｜ACGO欢乐赛#17

AC君

2024-03-18 14:45:58

发布于：浙江

74阅读

0回复

0点赞

T1、长方形

题目大意

题目问你是否能用 4 个边长组成一个长方形

解题思路

组成长方形的条件就是，短的两条边相等且长的两条边相等。
这道题唯一的坑点就是答案输出的是 $N0$ 而不是 $NO$ 。(惩罚一些不复制粘贴的同学)

参考代码

#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
	
	int t;cin>>t;
	while(t--){
		for(int i=0;i<4;i++)scanf("%d",&a[i]);
		sort(a,a+4);
		if(a[0]==a[1]&&a[2]==a[3])puts("YES");
		else puts("N0");
	}
	return 0;
}

T2、时间旅行

题目大意

问你恰好走 K 步 , 能否从 $(A,B)$ 走到 $(C,D)$

题解思路

首先计算原点到目标点的距离 $D$ ，然后判断一下 $K$ 是否大于 $D$ 。且 $K$ 要整除于 $D$ ，因为多出来的步数是偶数就可以 走一步然后退一步 进行消耗步数，否则不能达到目标点。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
	
	
	int t;scanf("%d",&t);
	while(t--){
		int a,b,c,d,k;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		ll e = (ll)k - (ll)abs(a - c)  - (ll)abs(b - d);//这里会爆int 
		if(e >= 0 && e % 2ll == 0 ){
			puts("Yes");
		}else{
			puts("No");
		}
		
	}
	return 0;
}

T3、月圆之夜

题目大意

在对面卤蛋杀死我们之前，我们先杀死对面就行了。

题解思路

可以先计算出对面杀死我们的次数是多少，我们假设为 K 次。那么我在 K-1 次恰好能杀死对面的最小攻击力，就是我们所要求的。这里还需要特殊判断一下a1 > h2的情况，因为这样ZLH的卤蛋就一定会挂掉。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	
	int t;scanf("%d",&t);
	while(t--){
		int a1,h1,h2;
		scanf("%d%d%d",&a1,&h1,&h2);
		
		int round;
		if(h2 % a1 == 0){
			round = h2/a1 - 1; 
		}else{
			round = h2/a1;
		}
		
		if (round == 0 ){
			cout << -1 <<endl;
			continue;
		}
		
		int ans;
		if(h1 % round == 0 ){
			ans = h1 / round;
		}else{
			ans = h1 / round + 1;
		}
		
		cout << ans <<endl; 
	} 
	
	return 0;
}

T4、海贼宝藏密码

题目大意

为你在一个序列中挖空，能否根据 严格递增 这个特性来还原原序列。求挖空之后剩余序列长度的最小值。

解题思路

很容易想到一点就是，挖的空越长，剩余的数字越少。怎么求挖空的最大值呢？首先我们找到一个最长的连续序列满足相邻的数字相差1 ，那么除开两头，我们中间都可以挖空，此时剩下的数字最少。但是注意样例 2 的情况有点特殊，其实这种情况相当于在序列前面塞了一个 $0$ 。同理序列的后面也要加上个 $1001$ 此时就可以跑出正确答案了。

参考代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int a[1005];
int main(){
	int n;
	cin>>n;
	a[1]=0;//前面塞个0
	a[n+2]=1001; //后面塞个1001
	for(int i=2;i<=n+1;i++)cin>>a[i];
	int cnt=1;
	int maxx=0;
	for(int i=2;i<=n+2;i++){
		if(a[i]==a[i-1]+1){//找到最长的相邻数差为1的序列
			cnt++;
		}
		else cnt=1;
		maxx=max(maxx,cnt);
	} 
	cout<<n-max(0,maxx-2)<<endl;
	return 0;
}

T5、加减乘除

题目大意

通过组合4种数字，然后判断结果是否为 $24$

题解思路

总共 4 个数字。我们可以枚举先运算哪两个数字，运算完之后就变成 3 个数字。然后通过这样不断「融合」的过程就会最终获得 1 个数字，就是我们的答案了。注意，减法和除法没有交换律。所以要分开枚举。实现的方式有很多，这里采用回溯法的方式实现。

参考代码

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

bool dfs(int now , vector<int>b){
	if(now == 1){
		return b[0] == 24;
	} 
	
	int flag = 0;
	for(int i = 0 ;i< now;i++){
		for(int j = i + 1;j < now;j++){
			
			vector<int>tmp;
			for(int k = 0; k <now ;k++){ // 其他数字不用融合
				if(k==i || k == j)continue;
				tmp.push_back(b[k]);
			} 
			
			
			// 加法有交换率 
			tmp.push_back(b[i] + b[j]);
			flag |= dfs(now-1,tmp);
			tmp.pop_back();//回溯
			
			// 减法没有交换律 
			tmp.push_back(b[i] - b[j]);
			flag |= dfs(now-1,tmp);
			tmp.pop_back();
			
			tmp.push_back(b[j] - b[i]);
			flag |= dfs(now-1,tmp);
			tmp.pop_back();
			
			
			// 乘法有交换律 
			tmp.push_back(b[i] * b[j]);
			flag |= dfs(now-1,tmp);
			tmp.pop_back();
			
			
			// 除法没有交换率 ，且这里注意除数不能为0	
			if(b[j]  && b[i] % b[j] == 0){
				tmp.push_back(b[i] / b[j]);
				flag |= dfs(now-1,tmp);
				tmp.pop_back();
			}
			
			if(b[i] && b[j] % b[i] == 0 ){
				tmp.push_back(b[j] / b[i]);
				flag |= dfs(now-1,tmp);
				tmp.pop_back();
			}
		}
	}
	return flag;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		vector<int>a; 
		for(int i=0;i<4;i++){
			int x;scanf("%d",&x);
			a.push_back(x);
		}
		
		if(dfs(4,a))puts("Yes");
		else puts("No");
		
	} 
	
	return 0;
}

T6 强迫症序列

题目大意

一个序列删除一个最小的区间，使得剩下的数俩俩各不相同。

解题思路

对于前 $60\%$ 的数据，可以直接暴力 $O(n^2)$ 枚举。枚举每次删除的长度 $Len$ 然后剩下的数再扫一边，判断有没有重复就可以获取答案。

$100\%$ 数据的解法用二分答案的思想，二分答案然后用 $O(n)$ 的时间确定一下答案是否合法就可以。怎么用 $O(n)$ 时间判断呢。注意到，重复的意思就是出现两次以上，那么只有在出现一次和出现二次之间变化的时候才会影响答案的统计。那么统计一下每个数的出现次数，在扫答案的时候维护就可以了。可以用 $unordered\_map$ 或者离散化处理 1e9 的数据（详细看代码就可以了）

参考代码

(unordered_map)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
int n;
int cnt;// 记录有几个是重复的 
unordered_map<int,int>mp;
bool check(int len){
	bool flag = false;
	for(int i=1;i<=len;i++){
		mp[a[i]]--;
		if(mp[a[i]]==1)cnt--;
	}
	if(cnt == 0) flag = true;
	for(int i=len+1;i<=n;i++){
		mp[a[i-len]]++;
		if(mp[a[i-len]]==2)cnt++;
		mp[a[i]]--;
		if(mp[a[i]]==1)cnt--;
		if(cnt==0)flag = true;
	}
	for(int i=n-len+1;i<=n;i++){
		mp[a[i]]++;
		if(mp[a[i]]==2)cnt++;
	}
	return flag;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mp[a[i]]++;
		if(mp[a[i]]==2){
			cnt++; 
		} 
	}
	int ans = 0;
	int l=0,r=n;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check(mid)){
			ans = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	printf("%d\n",ans);
	return 0; 
}

离散化

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
int n;
int cnt;// 记录有几个是重复的 

int pos[maxn];
int b[maxn];
int mp[maxn];

bool check(int len){
	bool flag = false;
	for(int i=1;i<=len;i++){
		mp[pos[i]]--;
		if(mp[pos[i]]==1)cnt--;
	}
	if(cnt == 0) flag = true;
	for(int i=len+1;i<=n;i++){
		mp[pos[i-len]]++;
		if(mp[pos[i-len]]==2)cnt++;
		mp[pos[i]]--;
		if(mp[pos[i]]==1)cnt--;
		if(cnt==0)flag = true;
	}
	for(int i=n-len+1;i<=n;i++){
		mp[pos[i]]++;
		if(mp[pos[i]]==2)cnt++;
	}
	return flag;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i] = a[i];
	}
	sort(b+1,b+1+n);
	int tot = unique(b+1,b+1+n)-b;
	for(int i=1;i<=n;i++){
		pos[i] = lower_bound(b+1,b+1+tot,a[i])-b;
	}
	for(int i=1;i<=n;i++){
		mp[pos[i]]++;
		if(mp[pos[i]]==2){
			cnt++; 
		} 
	}
	int ans = 0;
	int l=0,r=n;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check(mid)){
			ans = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	printf("%d\n",ans);
	return 0; 
}