A**B Problem

高精。

1 #include
     
       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
      
       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
       
        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 }
       
      
     

 

猜数游戏

题解：

第一问：

相当于二分。

将这些数的最小质因数集合平均划分为两部分，询问这个数是否为其中一个集合中的数的倍数，这样递归下去。

第二问：

仍用类似第一问的方式询问。将最小质因数相同的数放入一个集合。倒过来考虑，将这些集合两两合并，即每两个集合是由一个大集合通过一次询问划分出来的。越早合并的集合中的数需要的询问次数越多。所以贪心，先合并较小的集合。

1 #include
     
       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
      
       
        ,greater
        
          >s; 7  8 void Prime() { 9     for(int i=2;i
         
          >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\n",ans);38     ans=0;39     for(int i=1;i<=cnt;i++) s.push(t[i]);40     for(int i=1;i
         
        
       
      
     

 

洪水

对于第$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
     
       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
      
       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