提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

Online Selection Contest BACS Regional Programming Contest, 2018 And BACS High School Programming Co

and 2018 Online Contest Programming High Selection co
2023-06-13 09:15:43 时间

Online Selection Contest BACS Regional Programming Contest, 2018 And BACS High School Programming Contest, 2018

于2020年6月1日2020年6月1日由Sukuna发布

这一次没什么复杂的算法，但是考验思维。

题目链接

problem A

题目大意：给定你x,l,m。x是你的编号，m是总人数。然后有人在区间[l,m]之间等可能地抽取一个整数作为Y。然后要求编号1到Y的人出列，围成一圈，从编号1开始隔一个人枪毙一个人，直到剩下一个人。

枪毙示意图

问你存活的概率是多少？（没被选出去枪毙的人和枪毙剩下的最后一个人是存活的）

数据范围

由于数据庞大，所以我们能够知道对于拉去枪毙的人数Y，必定存在时间复杂度为1的方法确定枪毙剩下的人的编号。根据这条情报，我们可以通过手动推算（打表）。发现

以Y为2的次方为分割点，呈等差数列。

然后通过暴力枚举符合条件的数。

#include<iostream>
#include<cstdio>
#include<cmath>

#include<bits/stdc++.h>
using namespace std;
int t;
long long x,l,n;
int main(){
	int cnt=1;
	scanf("%d",&t);
	while(t--){
		long long son=0;
		scanf("%lld%lld%lld",&x,&l,&n);
		long long temp1,temp2;
		if(x%2==0){
			son=max(x-l,0ll); 
		} else{
			long long now=1;
			while(now*2<l){
				now*=2;
			}		
			while(now<=n){
				if(now+x/2<now*2&&now+x/2<=n&&now+x/2>=l){
					son++;
				}
				now*=2;
			}
			son+=(max(x-l,0ll));
		}
		printf("Case %d: %lld/%lld\n",cnt,son/__gcd(son,n-l+1),(n-l+1)/__gcd(son,n-l+1));
		cnt++;

		
		
		
		
		
		
	}
	
	
	
	
}

problem F

题目大意：给定N,K,和Q次操作。N表示总位置数，K表示从1到K的位置被人占领。Q次操作，每次操作两个整数X,Y。表示将X位置的人移动到Y。问每次操作后空出的位置数是多少？

1表示有人，0表示没人

1001001有两个空位

11000000只有一个空位

如果我们按照他的要求一步一步操作，然后扫描数组来计算空位数的话，超时警告。所以我们可以放弃整体关注局部，关注改变的东西。比如要移走X，而且当前X-1和X+1位置有人，那么这个操作会产生一个空位。其他情况可类推。

数据规模

由于数据规模庞大，如果使用bool类型长度为1e9的数组，那么初始化会消耗很多时间，所以我这里采用map，用map的clear来初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
int t;
int k,n,q;
map<int,bool> a;
int main(){
	scanf("%d",&t);
	for(int cnt=1;cnt<=t;cnt++){
		int ans=1;
		scanf("%d%d%d",&k,&n,&q);
		a.clear();
		for(int i=1;i<=n;i++){
			a[i]=1;
		}
		a[0]=a[k+1]=1;
		int temp1,temp2;
		printf("Case %d:\n",cnt);
		for(int i=1;i<=q;i++){
			scanf("%d%d",&temp1,&temp2);
	
			ans-=((int)(a[temp1-1]==0)+(int)(a[temp1+1]==0)-1);
			swap(a[temp1],a[temp2]);		
			ans+=((int)(a[temp2-1]==0)+(int)(a[temp2+1]==0)-1);			
			
		
			printf("%d\n",ans);
			
		}
		
		
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
}

problem I

题目大意：给定你N堆石子，要求你尝试把这堆式子合并成一堆。移动石子的操作仅当后一堆的石子因此而加了一倍才能进行。问能否将他们合并为1堆。

首先为了方便，将所有的石子约去公因数。

从结果逆推。设总数为sum，如果可以合并，那么sum/2和sum/2也能被合出来-》sum/4和sum/4也能被和出来。。。。。。。。

得出一个猜想，sum为2的次方才能把石子合并成一堆。

当有两堆石子时，上述猜想成立，三堆也成立，四堆、五堆也成立。

然后当时我没想太多，直接交了，结果AC了。

如果有人能补充严谨证明那就太好了。

#include<bits/stdc++.h>
using namespace std;
int t,n;
long long a[100001];
int main(){
	scanf("%d",&t);
	for(int k=1;k<=t;k++){
		scanf("%d",&n);
		long long sum=0,g=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			sum+=a[i];
		}
		g=a[1];
		for(int i=2;i<=n;i++){
			g=__gcd(g,a[i]);
		}
		sum/=g;
		while(sum%2==0){
			sum/=2;
		}
		if(sum!=1){
			printf("Case %d: NO 1\n",k);
		}
		else{
			printf("Case %d: YES\n",k);
		}
		
		
		
		
	}
	
	
	
	
	
	
}

problem L

题目大意：给定你N个区间，要求你找出一段最短的区间，包含至少P个给定的区间。

实际上呢，区间的左端点和右端点并不是绑定死的。比如区间[x1,y1],[x2,y2]和[x1,y2][x2,y1]在这个题目中时等效的。所以我们不需要纠结区间，直接考虑某时段左端点、右端点数量对结果的影响，发现如果一段区间内左端点数为P，那么该区间符合要求。

因此搞两个递增数组分别存贮左端点和右端点的出现位置。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int in[100001],out[1000001];
int read(){
	int num=0;
	char c=getchar();
	while(c>'9'||c<'0'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		num=num*10+c-'0';
		c=getchar(); 
	}
	return num;
	
}


int t; 
int n,p;

//bool cmp(hehe l,hehe r){
//	return l.num<r.num;
//}

int main(){
	t=read();

	for(int k=1;k<=t;k++){
		n=read();
		p=read();
		for(int i=1;i<=n;i++){
			in[i]=read();
			out[i]=read();
		}
		sort(in+1,in+1+n);
		sort(out+1,out+1+n);
		
	
		int ans=1e9+1;
	//	cout<<ans<<endl;
		for(int i=p;i<=n;i++){
			ans=min(max(in[i]-out[i-p+1],0),ans);
		}
		
		
		
		
		printf("Case %d: %d\n",k,ans);
	}
	
	
	
	
}

相关文章