『校内OJ』NOIP2019模拟赛（二） 洪水
A**B Problem
高精。
1 #include<bits/stdc++.h> 2 using namespace std; 3 char s[10]; 4 int A,B,t,l,a[205]; 5 void work() { 6 for(int i=1;i<=l;i++) a[i]*=A; 7 for(int i=1;i<l;i++) 8 if(a[i]>9) a[i+1]+=a[i]/10,a[i]%=10; 9 while(a[l]>9) a[l+1]=a[l]/10,a[l++]%=10; 10 } 11 12 int main(){ 13 scanf("%s",s); scanf("%d",&B); 14 int len=strlen(s); 15 for(int i=0;i<len;i++) 16 if(s[i]=='.') t=len-i-1; 17 else A=A*10+s[i]-'0'; 18 l=1,a[1]=1; 19 for(int k=1;k<=B;k++) work(); 20 for(int i=l;i>t*B;i--) printf("%d",a[i]); 21 if(t) printf("."); 22 for(int i=t*B;i>=1;i--) printf("%d",a[i]); 23 return 0; 24 }
猜数游戏
题解：IBM Ponder This November 2009
第一问：
相当于二分。
将这些数的最小质因数集合平均划分为两部分，询问这个数是否为其中一个集合中的数的倍数，这样递归下去。
第二问：
仍用类似第一问的方式询问。将最小质因数相同的数放入一个集合。倒过来考虑，将这些集合两两合并，即每两个集合是由一个大集合通过一次询问划分出来的。越早合并的集合中的数需要的询问次数越多。所以贪心，先合并较小的集合。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5,M=31623; 4 int n,tot,cnt,ans,p[M],a[N],t[N]; 5 bool vis[M]; 6 priority_queue<int,vector<int>,greater<int> >s; 7 8 void Prime() { 9 for(int i=2;i<M;i++) 10 if(!vis[i]) { 11 p[++tot]=i; 12 for(int j=i;j<M;j+=i) vis[j]=1; 13 } 14 } 15 16 void dfs(int l,int r,int dep) { 17 if(l==r) {ans=max(ans,dep); return ;} 18 int Mid=(l+r)>>1; 19 dfs(l,Mid,dep+1); dfs(Mid+1,r,dep+1); 20 } 21 22 int main() { 23 Prime(); 24 n=read(); 25 for(int i=1;i<=n;i++) { 26 a[i]=read(); 27 int x=sqrt(a[i]); 28 for(int j=1;j<=tot&&p[j]<=x;j++) 29 if(a[i]%p[j]==0) {a[i]=p[j]; break;} 30 } 31 sort(a+1,a+n+1); 32 for(int i=1;i<=n;i++) { 33 if(a[i]!=a[i-1]) cnt++; 34 t[cnt]++; 35 } 36 dfs(1,cnt,0); 37 printf("%d ",ans); 38 ans=0; 39 for(int i=1;i<=cnt;i++) s.push(t[i]); 40 for(int i=1;i<cnt;i++) { 41 int x=s.top(); s.pop(); 42 int y=s.top(); s.pop(); 43 ans+=x+y; 44 s.push(x+y); 45 } 46 printf("%lf",(double)ans/n); 47 }
对于第$i$块岩石，如果$h[i]>h[i-1]$，那么洪水高度为$h[i-1]+1$~$h[i]$时的答案都各要$+1$。
差分：在$h[i-1]+1$处$+1$，在$h[i]+1$处$-1$。洪水高度为$H$时的答案即为$1$~$h[H]$的和。(采用树状数组实现)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e5+5; 4 int n,m,p,h[N],id[N],ls[N<<1],c[N<<1]; 5 bool k[N]; 6 struct node{int x,id;}t[N<<1]; 7 bool cmp(node x1,node x2) {return x1.x<x2.x;} 8 9 void add(int k,int x) { 10 while(k<=p) c[k]+=x,k+=k&-k; 11 } 12 int getsum(int k) { 13 int tot=0; 14 while(k) tot+=c[k],k-=k&-k; 15 return tot; 16 } 17 18 void work() { 19 sort(t+1,t+n+m+1,cmp); 20 ls[t[1].id]=p=1; 21 for(int i=2;i<=n+m;i++) 22 if(t[i].x>t[i-1].x) ls[t[i].id]=++p; 23 else ls[t[i].id]=p; 24 for(int i=1;i<=n;i++) { 25 h[i]=ls[i]; 26 if(h[i]>h[i-1]) add(h[i-1]+1,1),add(h[i]+1,-1); 27 } 28 } 29 void change(int x,int k) { 30 if(h[x]>h[x-1]) add(h[x-1]+1,k),add(h[x]+1,-k); 31 if(x<n&&h[x]<h[x+1]) add(h[x]+1,k),add(h[x+1]+1,-k); 32 } 33 34 int main() { 35 n=read(),m=read(); 36 for(int i=1;i<=n;i++) 37 t[i].x=read(),t[i].id=i; 38 for(int i=1;i<=m;i++) { 39 k[i]=read()-1; 40 if(k[i]) id[i]=read(); 41 t[n+i].x=read(),t[n+i].id=n+i; 42 } 43 work(); 44 for(int i=1;i<=m;i++) 45 if(!k[i]) printf("%d ",getsum(ls[n+i])); 46 else { 47 change(id[i],-1); 48 h[id[i]]=ls[n+i]; 49 change(id[i],1); 50 } 51 }