首师大附中集训第二天专题测试

专题测试

      第一题：有一个序列，给出序列D满足对于，，现在已知，要你求。

      我一开始做的就是推式子，然后发现我推出来的垃圾式子只能做的情况。后来想了想，这个里面没有二次项，所以，所以就直接二分的值，然后根据di算出来的值，又因为成比例变化，所以就可以直接二分了。

      唯一要注意的一点就是一开始先算一算是正相关还是负相关。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;int n;
double a1,a2,l,r,d[3010];
const double eps=1e-5;double get_last(double x){double last=a1,temp;for(int i=1;i<=n;i++) temp=x,x=2*d[i]-last+2*x,last=temp;return x;
}int main(){freopen("math.in","r",stdin);freopen("math.out","w",stdout);scanf("%d",&n);scanf("%lf %lf",&a1,&a2);for(int i=1;i<=n;i++) scanf("%lf",&d[i]);l=-1000,r=1000;double begin=get_last(l),end=get_last(r);while(r-l>eps){double mid=(l+r)/2;if(begin+eps<end){if(get_last(mid)+eps<a2) l=mid;else r=mid;}else{if(get_last(mid)-eps>a2) l=mid;else r=mid;}}printf("%.2lf",l);
}

      第二题：给出个人，每个人的实力值等于它的编号。A与B比赛，当A的实力值与B的实力值相差不超过k时，A可能获胜。当A的实力值小于B的实力值-k时，A必定获胜，问安排一种方案，每轮两两比赛，问n轮后最大可能获胜的编号的是多少。

      这题稍微想一想就知道了，首先可以二分，其次我们可以贪心从根节点往下bfs，每次将一个点生出两个儿子，一个儿子是它自己，一个儿子取第一个>=自己的编号-k的数。然后放进队列。如果找不到这样的数字，那么就不成立。

      这样正确性显然，因为这样可以使得在较浅层数的编号有更多编号选择，可以证明若这种方案都不行的话其他方案肯定不行。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;int n,k,c;
struct node{int x,size,c;
};
queue<node> f;
bool tf[4110];bool check(int x){memset(tf,false,sizeof(tf));while(!f.empty()) f.pop();f.push((node){x,n,c});tf[x]=true;int next;while(!f.empty()){node now=f.front();now.size/=2;now.c--;f.pop();if(now.c) f.push(now);next=0;for(int i=max(1,now.x-k);i<=n;i++) if(!tf[i]){next=i;break;}if(!next) return false;now.x=next;tf[next]=true;if(now.c) f.push(now);}return true;
}int main(){freopen("contest.in","r",stdin);freopen("contest.out","w",stdout);scanf("%d %d",&n,&k);int temp=n;while(temp!=1) c++,temp/=2;int l=1,r=min(n,n+k-c),ans=0;while(l<=r){int mid=(l+r)/2;if(check(mid)) l=(ans=mid)+1;else r=mid-1;}printf("%d",ans);
}

      第三题：给出一个长度为的一个序列，现在进行n-1次操作，每次操作把原来的序列的每个位置上的数变成相邻位置与本身三个数的中位数，问最后最中间的数是多少。

      这题好难。

      首先一个貌似非常套路的方法就是二分最后最中间的数是多少。接着我们可以把>=该数的数变为1，<该数的变为0.

      我们发现最后的答案就等于从最中间往两边走第一个出现的连续1/0。

      考虑画图证明即可。这个结论很显然但是很难发现。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int n,m;
int a[200010],temp[200010];
bool tf[200010];
int l=2e9,r=0;bool check(int x){for(int i=1;i<=m;i++) if(a[i]>=x) temp[i]=1;else temp[i]=0;int tot=0,now,t1,t2,w1,w2;memset(tf,false,sizeof(tf));if(temp[1]==temp[2]) tf[1]=true;tot=1;for(int i=2;i<=m;i++){tf[i]=true;if(temp[i]==temp[i-1]) tot++;else {if(tot==1) tf[i-1]=false;tot=1;}}if(tf[n]) return temp[n]; t1=t2=0;now=n-1;w1=w2=temp[n];while(tf[now]==false && now>=1) t1++,now--,w1=temp[now];if(now!=0) w1=temp[now];now=n+1;while(tf[now]==false && now<=m) t2++,now++,w2=temp[now];if(now!=m+1) w2=temp[now];if(t1<t2) return w1;else return w2;
}int main(){freopen("3.in","r",stdin);scanf("%d",&n);m=2*n-1;for(int i=1;i<=m;i++) scanf("%d",&a[i]),l=min(l,a[i]),r=max(r,a[i]);int ans=0;while(l<=r){int mid=(l+r)/2;if(check(mid)) l=(ans=mid)+1;else r=mid-1;}printf("%d\n",ans);
}