Online Selection Contest BACS Regional Programming Contest, 2018 And BACS High School Programming Co
Online Selection Contest BACS Regional Programming Contest, 2018 And BACS High School Programming Co
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);
}
}腾讯云开发者
