1001，预处理出所有2的幂次数，然后从最大的开始找就行。但是最大的位置应当是从i=min(tot,m)开始，因为如果m很大，比tot还大，那么2^m根本没存下来，或者说num[i]是0，结果就会出现整数除以0的错误了（我一开始就是这样的= =）；另外如果m很小，如果n同时很大，不能从tot开始找，因为最大的数不是2^tot，必须从2^m开始找。还好当时凭借直觉这么写然后AC了- -，不然又是WA到死。。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <math.h> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <iostream> 8 #include <string.h> 9 #include <math.h> 10 using namespace std; 11 typedef long long ll; 12 typedef pair<int,int> pii; 13 14 int num[100]; 15 int tot = 0; 16 17 int main() 18 { 19 int now = 1; 20 num[0] = 1; 21 while(now<=1e9) 22 { 23 now <<= 1; 24 num[++tot] = now; 25 } 26 27 28 int n,m; 29 int T; 30 cin>>T; 31 while(T--) 32 { 33 scanf("%d%d",&n,&m); 34 int sum = 0; 35 for(int i=min(m,tot);i>=0;i--) 36 { 37 if(num[i]>n) continue; 38 int t = n/num[i]; 39 sum += t; 40 n -= t*num[i]; 41 if(n==0) break; 42 } 43 cout << sum<<endl; 44 } 45 }
1002，想说明的一点是，在for的过程中，如果lower_bound找的是a[i]，那么意义是，以i这个位置结尾的最长的lis的长度；如果找的是inf，那么意义是，从第一个位置到i这个位置为止，最长出现的lis的长度。这两点要搞清楚。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <math.h> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <iostream> 8 #include <string.h> 9 #include <math.h> 10 using namespace std; 11 typedef long long ll; 12 typedef pair<int,int> pii; 13 const int N = 1e5 + 5; 14 const int inf = 0x3f3f3f3f; 15 16 int dp[N],lis[N]; 17 int a[N]; 18 int ans[N]; 19 20 int main() 21 { 22 int T;cin>>T; 23 while(T--) 24 { 25 int n; 26 scanf("%d",&n); 27 for(int i=0;i<n;i++) scanf("%d",a+i); 28 fill(dp,dp+n,inf); 29 memset(lis,0,sizeof(lis)); 30 for(int i=0;i<n;i++) 31 { 32 *lower_bound(dp,dp+n,a[i]) = a[i]; 33 lis[i] = lower_bound(dp,dp+i+n,a[i]) - dp + 1; 34 } 35 36 /*for(int i=0;i<n;i++) 37 { 38 printf("%d !! ",lis[i]); 39 }*/ 40 41 memset(ans,0,sizeof(ans)); 42 ans[0] = 1; 43 /*for(int i=1;i<n;i++) 44 { 45 if(lis[i] > lis[i-1]) 46 { 47 ans[i] = ans[i-1] + 1; 48 } 49 else if(lis[i] == lis[i-1]) 50 { 51 ans[i] = 1; 52 } 53 }*/ 54 for(int i=0;i<n;i++) 55 { 56 printf("%d%c",lis[i],i==n-1?' ':' '); 57 } 58 } 59 }
1004，一开始的思路是找不大于d的质数，并且他俩的乘积小于n，，WA到死。后来看了题解才懂应该找的是小于等于d的最小质因数的质数的个数。原因是我的方法没有考虑到d本身不是质数的情况，例如35，找到5就应该停止了，因为再找7的话，35=5*7，7*7=49，这样35就不是最小的因子了。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <math.h> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <iostream> 8 #include <string.h> 9 #include <math.h> 10 using namespace std; 11 typedef long long ll; 12 typedef pair<int,int> pii; 13 const int N = 400000 + 5; 14 const int inf = 0x3f3f3f3f; 15 16 int prime[N]; 17 bool isprime[N]; 18 int tot = 0; 19 20 // 找x的最小质因数 21 int mp(int x) 22 { 23 for(int i=1;i<=tot;i++) 24 { 25 int p = prime[i]; 26 if(x % p == 0) return p; 27 } 28 return x; 29 } 30 31 int main() 32 { 33 //prime[0] = 2; 34 memset(isprime,true,sizeof(isprime)); 35 for(int i=2;i<N;i++) 36 { 37 if(isprime[i]) 38 { 39 prime[++tot] = i; 40 for(int j=2*i;j<N;j+=i) 41 { 42 isprime[j] = false; 43 } 44 } 45 } 46 // N的范围只要在sqrt(1e9)以内即可 47 48 49 int T;cin>>T; 50 while(T--) 51 { 52 int n,x; 53 scanf("%d%d",&n,&x); 54 int sum=0; 55 56 // 如果直接再加上一个条件，要找的质数还要小于等于x的最小质因数的话，会超时 57 // 因为如果x是质数，mp(x)和for一直找到不大于x的质数，复杂度都是线性的， 58 // 而下面的for复杂度是开了根号的 59 // 而如果x是质数的话，其实只要二分查找不大于x的质数个数有多少个即可，复杂度只有log程度 60 //int t = mp(x); 61 int i; 62 // 如果x不是一个质数，那么，找x的最小的质因数 63 for(i=1;i<=tot && 1LL*prime[i] * prime[i]<= 1LL*x && 1LL*prime[i]*x<(ll)n;i++) 64 { 65 int p = prime[i]; 66 sum ++; 67 if(x % p == 0) break; 68 } 69 // 下面的二分是针对x本身也是一个质数的情况 70 if(1LL*prime[i] * prime[i] > 1LL*x) 71 { 72 int l = 1, r = tot; 73 while(l <= r) 74 { 75 int mid = l + r >> 1; 76 int p = prime[mid]; 77 if(1LL*p * x >= 1LL*n || p>x) 78 { 79 r = mid - 1; 80 } 81 else 82 { 83 sum = mid; 84 l = mid + 1; 85 } 86 } 87 } 88 printf("%d ",sum); 89 } 90 }