第一次组队参赛,再多做三题就能AK了,可惜自己做题不够快,py也不熟练,总是要调好久,还是太蒻了OTZ
题意: 从n个数字中选出k个数字,使得他们乘积后缀0个数最多
算法: 背包dp(贪心被群里大佬 X 了,我太难了)
思路(错误✖): 显然能产生后缀0的乘积只有2和5相乘,因此考虑先将所有数的因子中2和5个数求出,那么题意就转化为:选出k个数,使得$\min(sum2,sum5)$最大,其中$sum2、sum5$分别为这k个数的因子中2和5的总数。可以发现,正向求这个值不太好想,我们可以转换一下思路,逆向求,即先将所有的数选上,然后贪心地不断删去$n-k$个对答案造成影响最小的数,最后的$\min(sum2,sum5)$就是答案
思路(正确✔):定义状态转移方程$dp[i][j][m]$在前$i$个数中选取$j$个数,其中因子为5的个数为$m$时的因子2的最多的个数,发现m最多也就五千多点的样子,可以滚动数组压成二维的跑一遍背包dp,最后求出$\max(\min(dp[j][m],m))$即可
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
| int n,k,dp[205][5205],sum5,ans; pair<int,int> ha[205]; int main(){ read(n),read(k); ll x; rep(i,1,n){ read(x); while(x%2==0){ x/=2; ha[i].first++; } while(x%5==0){ x/=5; ha[i].second++; } } memset(dp,-0x3f,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=k;j>=1;j--){ for(int m=5200;m>=ha[i].second;m--){ dp[j][m]=max(dp[j][m],dp[j-1][m-ha[i].second]+ha[i].first); } } } for(int i=0;i<=5200;i++){ ans=max(ans,min(dp[k][i],i)); } printf("%d\n",ans); return 0; }
|
题意:x轴上有n个人,每个人坐标为$x_i$,同时以速度1/s往0点移动,现在可以在两点建立传送门,问所有人都到达0点时所花最少时间
算法:二分答案
思路:对x排序,然后考虑二分答案,即每次二分出一个最短时间mid,就遍历一遍x数组,找到其中第一个绝对值大于mid的点$x_p$,将传送门的一端设置在$pos=x_p+mid$处(因为这样设置能够给后面的点产生最大的贡献),那么之后如果找到绝对值大于mid的点$x_q$,就判断是否有$|x_q-pos|>mid$,如果是,则这个二分的最短时间mid无法达到,需要扩大这个mid,否则可以缩小这个mid
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
| int _,n; ll x[maxn]; inline bool check(ll k){ ll pos=-1ll<<60; rep(i,1,n){ if(abs(x[i])>k){ if(pos==-1ll<<60) pos=x[i]+k; else if(abs(pos-x[i])>k) return false; } } return true; } int main(){ for(scanf("%d",&_);_;_--){ read(n); rep(i,1,n) read(x[i]); sort(x+1,x+1+n); ll l=-1ll<<60,r=1ll<<60; ll ans; while(l<=r){ ll mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%lld\n",ans); } return 0; }
|