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 洪水 (富金森林公园)
题面
思路
因为高度 $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);
}
}
}
}
