T1:可以发现a*b=k³，k表示所有不同轮的道具各取一个相乘后的值。

二分枚举³√(a*b)，如能找到输出"YES"，否则输出"NO".注意特判乘积为0的情况。

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define ll long long 5 using namespace std; 6 inline ll in(){ 7     ll x=0;bool f=0; char c; 8     for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');10     return f?-x:x;11 }12 ll pd,ans,res,a,b;13 int n;14 inline ll bis(ll x){15     if (x==1ll) return 1ll;16     ll l=1ll,r=min(x,1000001ll);17     while (l<=r){18         ll mid=(l+r)>>1;19         if (1ll*mid*mid*mid<=x) ans=mid,l=mid+1;20         else r=mid-1;21     }return (1ll*ans*ans*ans==x)?ans:-1;22 }23 int main()24 {25     scanf("%d",&n);for (int i=1;i<=n;++i){26         a=in();b=in();if (!(a*b)){printf(a==b?"YES\n":"NO\n");continue;}27         pd=a*b;ans=0ll;res=bis(pd);28         printf(((res==-1)||(a%res)||(b%res))?"NO\n":"YES\n");29     }return 0;30 }
       
      
     

T2:动态规划。令f[i][j]表示取i个数且这些数的乘积有j个因数5时乘积中因数2的个数。

则f[i][j]=max{f[i-1][j-v5[k]]+v2[k]}，其中v2[i]与v5[i]因数2与因数5的个数。时间复杂度O(nk∑log₅a_i).

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MN 202 5 #define Lg 26 6 #define ll long long 7 using namespace std; 8 inline ll in(){ 9     ll x=0;bool f=0; char c;10     for (;(c=getchar())<'0'||c>'9';f=c=='-');11     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');12     return f?-x:x;13 }14 ll x,t;15 int f[MN][MN*Lg],b2,b5,n,k,cnt,sum,ans=0;16 int main()17 {18     scanf("%d%d",&n,&k);ans=sum=0;19     memset(f,200,sizeof(f));f[0][0]=0;20     for (int i=1;i<=n;++i){21         x=in();b2=b5=0;22         if (!x) {ans=1;continue;} t=x;23         while (!(t&1)) {++b2;t>>=1;}24         while (!(t%5)) {++b5;t/=5;}sum+=b5;25         for (int j=min(k,i);j>=0;--j)26         for (int k=0;k<=sum;++k)f[j+1][k+b5]=max(f[j+1][k+b5],f[j][k]+b2);27     }28     for (int i=0;i<=sum;++i) ans=max(ans,min(i,f[k][i]));29     printf("%d",ans);return 0;30 }
       
      
     

T3:考虑将盘子的左端点与右端点从小到大排序。

从小到大扫描右端点，则该点的答案为与其对应的左端点的相对位置（离散化求得）开始的最长不降子序列。

该操作可以使用线段树维护区间最大值完成。答案即为全局最大值。

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MN 100005 5 using namespace std; 6 inline int in(){ 7     int x=0;bool f=0; char c; 8     for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');10     return f?-x:x;11 }12 struct pla{13     int l,r;14 }p[MN];15 int mx[(1<<19)],a[MN],n,rd,x,cnt,M;16 inline bool cmp(pla a,pla b){
   return a.r==b.r?a.l>b.l:a.r
        
         >=1) mx[x]=max(mx[x],k);19 }20 inline int query(int l,int r){21     int res=0;22     for (l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){23         if (~l&1) res=max(res,mx[l^1]);24         if ( r&1) res=max(res,mx[r^1]);25     }return res;26 }27 int main()28 {29     n=in();for (int i=1;i<=n;++i){30         rd=in();x=in();a[i]=p[i].l=x-rd;p[i].r=x+rd;31     }sort(a+1,a+n+1);cnt=unique(a+1,a+n+1)-a-1;32     sort(p+1,p+n+1,cmp);for (M=1;M
         
          <<=1);33     for (int i=1;i<=n;++i){34         p[i].l=lower_bound(a+1,a+cnt+1,p[i].l)-a;35         add(p[i].l,query(p[i].l,cnt)+1);36     }printf("%d",mx[1]);return 0;37 }