NOIP2019模拟赛（二）03.10
T1
题意
题面
给定两个数a,b求出b个a相乘的结果。
数据范围
保证a leq 99.9999 ,b leq 25且a的有效数字不超过6位。
思路
对于20%的数据
你开longquad double就好了呀。
对于100%的数据
你写高精度就好了呀。 说得很轻巧，但是打比赛的时候花了30分钟。。。 差不多分两个步骤： 1. 把a的小数转化为整数，并且求出a^b 2. 然后再点一个小数点就好了 坑：0.52要输出成.52。 其他没啥了。
代码语言：javascript复制#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x '0');
else{
write(x/10);
putchar(x '0');
}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
char A[50010];int b,len,Dot=-1;
int a[5000010];
int t[5000010];
int c[5000010],Len;
int top=0;
void Mul(){//高精度乘法
int lena=top,lent=Len;
for(int i=0;i<lent/2;i ) swap(t[i],t[lent-i-1]);
int u=0;memset(c,0,sizeof(c));
for(int i=0;i<lena;i ){
for(int j=0;j<lent;j ){
c[i j] =a[i]*t[j] u;
u=c[i j]/10;
c[i j]%=10;
}
c[i lent]=u;u=0;
}
Len=lena lent;
while(c[Len]==0) Len--; Len;
memset(t,0,sizeof(t));
for(int i=0;i<Len;i ) t[i]=c[i];
for(int i=0;i<Len/2;i ) swap(t[i],t[Len-i-1]);
}
int main(){
cin>>A;b=read();len=strlen(A);
for(int i=0;i<len;i ){
if(A[i]=='.'){
Dot=i;//寻找小数点
continue ;
}
t[top]=a[top]=A[i]-'0';
top;
}
if(Dot!=-1)
Dot=len-Dot-1;else Dot=0;//计算出小数点离个位多少位
for(int i=0;i<top/2;i ) swap(a[i],a[top-i-1]);
Len=top;
for(int i=1;i<b;i ){
Mul();
}
Dot=Dot*b;//计算出小数点应该点在哪里
if(Dot>=Len){//需要输出成.000xxx的形式
cout<<".";
for(int i=Len;i<Dot;i ) cout<<'0';
for(int i=0;i<Len;i ) cout<<t[i];cout<<endl;
}else{
for(int i=0;i<Len;i ){
if(i==Len-Dot){
cout<<".";//小数点
}
cout<<t[i];
}
cout<<endl;
}
return 0;
}T2
题意
有两个人很无聊地在玩猜数游戏。某个人想出来一个n个正整数的集合，然后选择一个数，让另外一个人猜他选的数的最小质因子。 问：在最优的方案中，最坏情况下需要询问几次，以及最小的询问期望次数？ 注：询问期望次数是所有数需要的询问次数的平均值，最坏情况的询问次数为所有数的询问次数的最大值。
思路
很显然这道题和小学奥数题很像。就比如说问有1~n的数，怎样询问能最少？ 显然是log2次。 就像这样：↓↓↓
那么对于第二个询问呢？和Luogu的合并果子很像。 Luogu 合并果子 其实就是利用哈夫曼树的原理，每次寻找最小的两个像上面一样log2地合并起来就好了。 可以使用priority_queue的小根堆。 注意：这道题会卡时，所以需要预处理出素数。
代码语言：javascript复制#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x '0');
else{
write(x/10);
putchar(x '0');
}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,a[100010],m=0,t[100010],p[100010];
int vis[100010],tot;
priority_queue<int ,vector<int>, greater<int> > Hf;
int GetLog(int x){
int pp=1;
while(x!=1){
pp ;x/=2;
}
return pp;
}
void GetPrime(){//预处理素数
for(int i=2;i<=100000;i ){
if(vis[i]==0){
p[ tot]=i;
for(int j=i;j<=100000;j =i) vis[j]=1;
}
}
}
int main(){
GetPrime();
n=read();
for(int i=1;i<=n;i ) a[i]=read();
for(int i=1;i<=n;i ){
int fst=sqrt(a[i]) 1;
for(int j=1;j<=tot&&p[j]<=fst;j ){
if(a[i]%p[j]==0){
a[i]=p[j];//找到该数的最小质因子
break;
}
}
}
sort(a 1,a n 1);
for(int i=1;i<=n;i ){
if(a[i]!=a[i-1]) m ;//去重
t[m] ;
}
int ans;
if(m<=2) puts("0");
else {
ans=log2((m-1)<<1);
write(ans),putchar('n');
}
for(int i=1;i<=m;i ) Hf.push(t[i]);
ans=0;
for(int i=1;i<m;i ){
int x=Hf.top();Hf.pop();
int y=Hf.top();Hf.pop();
ans =x y;//哈夫曼树思想
Hf.push(x y);
}
printf("%.5lfn",(double)ans/(double)n);
return 0;
}T3
题意
这和Luogu某题很像
题面
有n块石头，有m个询问。首先给出这n块石头的高度。然后对于每一次的询问有两种： 1. 读入一个整数x，询问大于或等于的连续的石头的部分的个数。 2. 读入两个整数x,y，表示将第x块石头的高度修改为y。
样例输入
5 4 8 6 3 5 4 1 5 2 4 1 1 5 1 3
样例输出
2 1 2
样例解释
第一次询问时，洪水高度为5 ，露出水面的岩石的编号为{1,2,4}连续的部分为{1,2}和{4}，答案是2 第二次询问时，洪水高度为5，露出水面的岩石的编号为{1,2}连续的部分为{1,2}，答案是1 第三次询问时，洪水高度为3，露出水面的岩石的编号为{1,2,3,5}连续的部分为{1,2,3}和{5}，答案是2
思路
对于50%的数据
我们可以采用暴力（废话） 所以我们就对于每个查询询问暴力。 结果真的只有50分。。。（出题人也太狠了吧）
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define int long long
#define MAXN 100010*4
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x '0');
else{
write(x/10);
putchar(x '0');
}
}
int n,m,a[200010],c[200010];
signed main(){
n=read();m=read();
for(int i=1;i<=n;i ) a[i]=read();
for(int op,x,y,i=1;i<=m;i ){
op=read();
if(op==1){
x=read();int ans=0;
for(int j=1;j<=n;j ){
if(a[j]>=x) ans ;
}
for(int j=1;j<=n;j ){
if(a[j]>=x&&a[j-1]>=x) ans--;
}
write(ans);putchar('n');
}else{
x=read();y=read();
a[x]=y;
}
}
return 0;
}对于100%的数据
通过观察，我们可以发现，对于每一个询问Q，其实就是寻找满足：h[i-1]<Q leq h[i]h[i-1]<h[i](h[i-1] 1,h[i])这个答案区间就可加1。而对于每一个询问，只需要输出答案区间内的Ans[Q]即可。对于每一个修改，影响到的只有h[i-1]与h[i 1]所以，再重新分别判断一次即可。 注意：每一次的修改需要先清空上一次对于该点的修改。
代码语言：javascript复制#include<bits/stdc .h>
#define MAXN 2000010
using namespace std;
#define int long long
inline int read(){
char ch=getchar();int res=0,f=1;
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x '0');
else{
write(x/10);
putchar(x '0');
}
}
int c[MAXN],h[MAXN];
int n,m,N;
int tree[4*MAXN],add[4*MAXN],num[MAXN],Max;
inline void build(int l,int r,int root){//线段树模板走起
if (l==r){tree[root]=num[l];return;}
int mid=(l r)/2;
build(l,mid,root*2);
build(mid 1,r,root*2 1);
tree[root]=tree[root*2] tree[root*2 1];
}
inline void updata(int l,int r,int root,int x,int ans){
if(r<xl>x) return;
if(l==r&&l==x){tree[root] =ans;return;}
int mid=(l r)/2;
updata(l,mid,root*2,x,ans);
updata(mid 1,r,root*2 1,x,ans);
tree[root]=tree[root*2] tree[root*2 1];
}
inline void modify(int root,int maxl,int maxr,int l,int r,int v){
if (maxl>=l&&maxr<=r){add[root] =v;return;}
tree[root] =(min(maxr,r)-max(maxl,l) 1)*v;
int mid=(maxl maxr)/2;
if (l<=mid) modify(root*2,maxl,mid,l,r,v);
if (mid<r) modify(root*2 1,mid 1,maxr,l,r,v);
}
inline int Search(int maxl,int maxr,int root,int l,int r){
if (maxl>rmaxr<l) return 0;
if (l<=maxl&&maxr<=r) return tree[root] (maxr-maxl 1)*add[root];
int mid=(maxl maxr)/2;
int res=(min(maxr,r)-max(maxl,l) 1)*add[root];
if (l<=mid) res =Search(maxl,mid,root*2,l,r);
if (mid<r) res =Search(mid 1,maxr,root*2 1,l,r);
return res;
}//线段树模板结束
int X,top,x[MAXN],k[MAXN],J[MAXN],Las[MAXN];
struct node{
int x,xx,id,h;
}a[MAXN];
int f[MAXN],g[MAXN],tot,tot2,mx;
bool cmp(node qx,node qy){
return qx.x<qy.x;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i ){
a[i].x=read();
a[i].id=i;
}
for(int i=n 1;i<=m n;i ){
J[i]=read();
if(J[i]==2) Las[i]=read();
a[i].x=read();
a[i].id=i;
}
sort(a 1,a n m 1,cmp);
f[a[1].id]=1;
for(int i=2;i<=n m;i ){
if(a[i].x>a[i-1].x) f[a[i].id]=f[a[i-1].id] 1;
else f[a[i].id]=f[a[i-1].id];
}
Max=f[a[n m].id];
build(1,Max,1);
for(int i=1;i<=n;i )
if(f[i-1]<f[i]) modify(1,1,Max,f[i-1] 1,f[i],1);//预处理
for(int i=n 1;i<=n m; i){
if(J[i]==2){
int j=Las[i];
if(f[j-1]<f[j]) modify(1,1,Max,f[j-1] 1,f[j],-1);
if(j!=n&&f[j]<f[j 1]) modify(1,1,Max,f[j] 1,f[j 1],-1);//清空上一次的修改操作
f[j]=f[i];//进行新的一次操作
if(f[j-1]<f[j]) modify(1,1,Max,f[j-1] 1,f[j],1);
if(j!=n&&f[j]<f[j 1]) modify(1,1,Max,f[j] 1,f[j 1],1);
}else write(Search(1,Max,1,f[i],f[i])),putchar('n');//输出该点的值（单点查询）
}
return 0;
}
