NOIP2019模拟赛（二）03.10

(Updated: )
oi
, , , , ,

T1

题意

题面

给定两个数$a$,$b$求出$b$个$a$相乘的结果。

数据范围

保证$a \leq 99.9999 ,b \leq 25$且$a$的有效数字不超过$6$位。

思路

对于20%的数据

你开$long\quad double$就好了呀。

对于100%的数据

你写高精度就好了呀。 说得很轻巧，但是打比赛的时候花了30分钟。。。 差不多分两个步骤： 1. 把$a$的小数转化为整数，并且求出$a^b$ 2. 然后再点一个小数点就好了 坑：0.52要输出成.52。 其他没啥了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#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%10+'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$的小根堆。 注意：这道题会卡时，所以需要预处理出素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#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%10+'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("%.5lf\n",(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分。。。（出题人也太狠了吧）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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%10+'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]$所以，再重新分别判断一次即可。 注意：每一次的修改需要先清空上一次对于该点的修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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%10+'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;
}