校内OJ 2019.3.10 NOIP 模拟赛

Rating 上了一点,考试时本来可以多得五十分的。。

P1  A^B Problem

题面

给出 $A$ 和 $B$,求 $A^B$ ,其中 $A$ 为浮点数,输出也为浮点数。

思路

高精水题,先去掉小数点求幂,再加上即可。

有 Python 打什么高精

from decimal import *
getcontext().prec=50000
s=input().split()
a=Decimal(s[0])
b=Decimal(s[1])
if a!=0:
	ans=format(pow(a,b))
	if ans[0]=='0' and len(ans)>1:
		ans=ans[1:]
	while ans[-1]=='0' or ans[-1]=='.':
		ans=ans[:-1]
	print(ans)
else:
	if b==0:
		print("1")
	else:
		print("0")

P2 猜数游戏

题面

有一个 $n$ 个数的可重集合,小 A 会选择一个数,但不会告诉你这个数,让 B 猜它的最小质因数。B 每次可以选出一些数,问 A 他选择的数属不属于这个集合,A 只回答 “是” 或 “否”。

B 想知道最优方案中,最坏情况下要询问几次,和最小的期望询问次数。

思路

题目问的是最小质因数,所以和集合内的数没关系,直接处理出每个数的最小质因数。

对于最坏情况下的询问次数,即是二分的次数。设最小质因数有 $k$ 种,答案为 $\left \lceil log_2(k) \right \rceil$。

最优情况下,使用贪心策略,在每种质因数个数的集合中每次取两个最大值,累计期望,然后再插入这两个值的和,直到集合还剩下一个元素为止。(类似于合并果子)

代码

#include<bits/stdc++.h>
using namespace std;
long long n,s[1000000];
long long zs(long long x){
	if (x%2==0){
		return 2;
	}
	int p=sqrt(x);
	for (long long i=3;i<=p+1;i+=2){
		if (x%i==0){
			return i;
		}
	}
	return x;
}
long long top=0,t[1000000];
map<int,int> m;
int main(){
	cin>>n;
	long long x;
	for (long long i=1;i<=n;i++){
		scanf("%d",&x);
		if (!m[x]){
			t[++top]=x;
		}
		m[x]++;
	}
	cout<<ceil(log(top)/log(2))<<endl;
	priority_queue<int,vector<int>,greater<int> > q;
	for (long long i=1;i<=top;i++){
		q.push(m[t[i]]);
	}
	top--;
	long long ans=0;
	while (q.size()>1){
		long long tmp=0;
		tmp+=q.top();
		q.pop();
		tmp+=q.top();
		q.pop();
		ans+=tmp;
		q.push(tmp);
	}
	printf("%.6lf",ans*1.00/n);
}

P3 洪水 (富金森林公园)

题面

洛谷 P3616 – 富金森林公园

思路

因为高度 $h_i <= 10^9$ 所以先离散化一遍。

然后用线段树维护每个高度贡献。(差分思想)

几乎是照着题解打的,有空要再打一遍。

代码

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long sum[MAXN*4],min[MAXN*4],max[MAXN*4],tag[MAXN*4];
void pushup(int rt){
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void build(int l,int r,int rt){
    if(l==r){
        sum[rt]=0;
        return;
    }
    int m=(l+r)/2;
    build(l,m,rt*2);
    build(m+1,r,rt*2+1);
    pushup(rt);
}
void pushdown(int rt,int ln,int rn){
    if(tag[rt]){
        sum[rt*2]+=ln*tag[rt];
        sum[rt*2+1]+=rn*tag[rt];
        tag[rt*2]+=tag[rt];
        tag[rt*2+1]+=tag[rt];
        tag[rt]=0;
    }
}
void update(int L,int R,long long C,int l,int r,int rt){
    if(L<=l&&r<=R){
        sum[rt]+=C*(r-l+1);
        tag[rt]+=C;
        return ;
    }
    int m=(l+r)/2;
    pushdown(rt,m-l+1,r-m);
    if(L<=m){
        update(L,R,C,l,m,rt*2);
    }
    if(R>m){
        update(L,R,C,m+1,r,rt*2+1);
    }
    pushup(rt);
}
long long query(int L,int R,int l,int r,int rt){
    long long ans=0;
    int m=(l+r)/2;
    if(L<=l&&R>=r){
        return sum[rt];
    }
    pushdown(rt,m-l+1,r-m);
    if(L<=m){
        ans+=query(L,R,l,m,rt*2);
    }
    if(R>m){
        ans+=query(L,R,m+1,r,rt*2+1);
    }
    return ans;
}
struct node{
    int x,y,id,p;//要修改的编号(如果当前要修改),高度,读入顺序,离散化后编号 
    int t,a,b;
};
node s[MAXN];
int n,q;
bool cmp(node a,node b){
    return a.y<b.y;
}
bool cmp2(node a,node b){
    return a.id<b.id;
}
int main(){
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        s[i].y=read();
        s[i].id=i;
    }
    for (int i=n+1;i<=n+q;i++){
        s[i].t=read();
        if (s[i].t==2){
            s[i].x=read();
        }
        s[i].y=read();
        s[i].id=i;
    }
    sort(s+1,s+1+n+q,cmp);
    s[1].p=1;
    for (int i=2;i<=n+q;i++){
        if (s[i].y!=s[i-1].y){
            s[i].p=s[i-1].p+1;
        }else{
            s[i].p=s[i-1].p;
        }
    }
    int tot=s[n+q].p;//离散后最大高度 
    build(1,tot,1);
    sort(s+1,s+1+n+q,cmp2);//重新按照id排序 
    s[0].p=0;//修改边界外点的高度便于计算
    for (int i=1;i<=n;i++){
        if (s[i-1].p<s[i].p){
            update(s[i-1].p+1,s[i].p,1,1,tot,1);
        }
    }
    for (int i=n+1;i<=n+q;i++){
        if (s[i].t==1){
            printf("%d\n",query(s[i].p,s[i].p,1,tot,1));
        }else{
            int tar=s[i].x;
            if (s[tar-1].p<s[tar].p){
                update(s[tar-1].p+1,s[tar].p,-1,1,tot,1);
            }
            if (tar!=n&&s[tar].p<s[tar+1].p){
                update(s[tar].p+1,s[tar+1].p,-1,1,tot,1);
            }
            s[tar].p=s[i].p;
            if (s[tar-1].p<s[tar].p){
                update(s[tar-1].p+1,s[tar].p,1,1,tot,1);
            }
            if (tar!=n&&s[tar].p<s[tar+1].p){
                update(s[tar].p+1,s[tar+1].p,1,1,tot,1);
            }
        }
    }
}

 

暂无评论

发送评论 编辑评论


				
上一篇
下一篇