当前位置：首页 > news >正文

丁真杯理塘大赛题解

news 来源：原创 2025/7/22 3:00:30

前言：部分代码思路可能与题解思路不同，~~请勿强行带入~~

真蛰虫

原题链接

1.一道非常基础的数学题。

2.主要就是在考察分解质因数。首先看真蛰虫的质因数是不是包含了容器的所有质因数，如果没有，那么就不能放入容器中。如果全部包含，那么最终值就是质因数次数之差的最大值+1。

#include<bits/stdc++.h>
using namespace std;
int m1,m2,s[10001],k=0x7fffffff;
int prime[30010],cnt[30010];
int divide(int n){int m=0;for(int i=2;i<=n/i;i++){if(n%i==0){prime[++m]=i;cnt[m]=0;while(n%i==0){n/=i;cnt[m]++;}}}if(n>1){prime[++m]=n;cnt[m]=1;}for(int i=1;i<=m;i++) cnt[i]*=m2;return m;
}
int main(){int n;scanf("%d%d%d",&n,&m1,&m2);for(int i=1;i<=n;i++){scanf("%d",&s[i]);}if(m1==1){//特判cout<<0<<endl;return 0;}int mz=divide(m1);for(int i=1;i<=n;i++){int ans=0;for(int j=1;j<=mz;j++){if(s[i]%prime[j]){ans=0x7fffffff;break;}int c=0;while(!(s[i]%prime[j])) s[i]/=prime[j],c++;int tmp=cnt[j]%c==0?0:1;ans=max(ans,cnt[j]/c+tmp);}k=min(ans,k);}cout<<(k==0x7fffffff?-1:k)<<endl;return 0;
}

忆者与梦泡

原题链接

1.字典树 / st表（线段树也可）

2.理解一下题意：如果一个数在经过若干次或 0 次除以 $d$ 并向下取整后与一个被称作“原数”的数相等，则说这个数能被这个原数消除。

给定 $n$ 个数 $a$ 、 $m$ 个“原数” $b$ 、 $d$ 和 $q$ 组形如 $l, r$ 的询问，求在用原数尽可能多的消除 $a_l,a_{l+1} ,…,a_r$ 的情况下最少需要几个原数。原数可以重复使用且不会发生变化。

3.首先，有一个肥肠煎蛋的结论，如果 $b_i$ 能消灭 $b_j$ ， $b_j$ 能消灭 $a_i$ ，那么 $b_i$ 能消灭 $a_i$ ，简单来说就是 3>2 2>1 则 3>1，（不需要证明，如果这都不会的话建议重开）可以利用这个性质来消灭一些“原数”，使得每个 $a_i$ 能且只能被一个“原数”消灭。

那么枚举每个 $a_i$ 能被哪个原数消灭。若 $a_i$ 能被 $b_j$ 消灭，则把 $f_{i,j}$ 设为 1。然后对 f 数组做一遍前缀和或者 st 表。查询时扫一遍判断每个原数是否被用到即可。

tips:注意数据范围： $a$ 和 $b≤2^{63}$ （约等于 $10^18$ ）需要开 $l o n g$ $l o n g$ ，不开小心见祖宗。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10; 
int n,m,d,q;
long long a[N],b[110];
int ans[N],qz[N][65];
int main(){cin>>n>>m>>d>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int j=1;j<=m;j++)cin>>b[j];for(int i=1;i<=m;i++)for(int j=1;j<=m;j++){long long tp=b[i],ttp=b[j];while(tp<ttp){ttp/=d;if(tp==ttp)b[j]=b[i];}}sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){long long tp=a[i],tp2=b[j];if(tp<tp2)continue;while(tp>tp2)tp/=d;if(tp==tp2){ans[i]=j;break;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(j==ans[i])qz[i][j]=qz[i-1][j]+1;else qz[i][j]=qz[i-1][j];}while(q--){int l,r,cnt=0;cin>>l>>r;for(int i=1;i<=m;i++)if(qz[r][i]-qz[l-1][i]>0)cnt++;cout<<cnt<<"\n";}return 0;	
}

为了世间的美好而战

原题链接
双倍经验（弱化版）

1.贪心+二分+搜索（随机化也可以）

2.贪心策略很容易想到：对于同样的蛋糕，相比于给嘴大的人吃，给嘴小的人吃可以满足更多人。优先将蛋糕喂给嘴小的人可以获得局部最优解，所以可以先将嘴的大小排序。

通过搜索判断一下该局部最优解是不是整体最优解，但是可能会浪费不少时间，因为经过排序后答案的可行区域是连续的，所以可以用二分查找来确定答案，然后再通过搜索验证答案的合理性来缩小区间以确定最优解。

为了避免TLE，需要剪枝，比如嘴比最大的蛋糕大的人是不可能满足的，应当直接剪掉（应该有其他的剪枝）。

3.思考 how to 搜索

before we 搜索，根据分析，将所有的人根据嘴的大小进行升序排列。如果有 n 个人可以被满足，那么这 n 个人一定是数组的前 n 个元素。

during we 搜索，对待检验值进行 dfs 搜索。如果满足了它的需求，就递归搜索它的前一个人是否可以被剩下来的蛋糕满足。如果嘴最小的人的需求也可以被满足，那么递归中止，验证通过；如果中途出现某人的需求不能被满足，那么就回溯到上一级递归。如果找到了满足测试值人数的蛋糕分配方式，就直接退出查找，以避免不必要的性能浪费。

4.consider下优化

预处理求值：排列嘴大小之后要计算前缀和，可以方便后续的使用；读入蛋糕的时候需要计算最大的蛋糕和蛋糕总值以备使用。（使用优先级队列存储蛋糕）

缩小区间：如果某人的嘴比最大的蛋糕还要大，那么根据题意，他的需求将永远无法得到满足。此时可以收紧二分查找区间以减少查找次数。

浪费蛋糕：如果某块蛋糕（或者被吃过的蛋糕）小于当前嘴最小的人的需求，那么此蛋糕将无法再发挥任何作用了，可以存储起来。

等大需求：因为对嘴的大小进行了排序，确保了先查找的嘴不小于后查找的嘴。若相邻两嘴的大小相等，后者已经遍历了部分蛋糕数组才求出结果，也就是说已遍历部分的蛋糕一定不能满足要求。为了减少遍历，可以将此时的数组坐标传给下一级递归，在需求相等的下一级递归中跳过这些不可能的部分，以节约时间。

5.总之，贪心思路非常好想，难点是二分和搜索可能不容易想到，也是这道题评蓝的原因。

tips：提供一种随机化代码：

#include<bits/stdc++.h>
using namespace std;
int c[51],p[1100],n,m,b[51];
priority_queue<int> tmp;
bool cmp(int x,int y){return x>y;
}
bool check(int N){int i,j,time=1000;while(time--){for(i=1;i<=n;i++)b[i]=c[i];//复制一份蛋糕副本 random_shuffle(b+1,b+n+1);//把一段区间打乱 int flag;for(i=N;i>=1;i--){//对要满足的人从大到小枚举 flag=0;for(j=1;j<=n;j++){//暴力枚举蛋糕 if(b[j]>=p[i]){flag=1;b[j]-=p[i];break;}}if(!flag) break;//如果找不到可以满足这个嘴的蛋糕，说明不行 }if(flag) return true;}return false;
}
int main(){int i,j,l,r,mid,ans=0;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&c[i]);scanf("%d",&m);for(i=1;i<=m;i++)scanf("%d",&p[i]);sort(p+1,p+m+1);//贪心，嘴小的人优先 l=0;r=m;while(l<=r){//二分 mid=l+r>>1;if(mid>=0&&check(mid)){ans=mid;l=mid+1;}else r=mid-1;}printf("%d",ans);return 0;
}

相逢是问候，离别是祝愿

原题链接
1.一道 dp+期望题。

2.先理解一下题意：有一个长度为 $n$ 的 01 串，下标编号 1 到 $n$ 。对位置 $p$ 操作一次可以使所有编号为 $p$ 的约数的位置 0 变 1，1 变 0。目标是使所有位置变成 0。银狼先随机操作若干次，等到当前局面可以在 $k$ 次操作以内达成目标时就使用最优策略，达成目标后结束操作。求期望操作次数。

3.容易证明，一种最优的操作策略是每次操作最右边的为 1 的位置，直到达成目标。而且操作的先后顺序并不重要。设 $f_i$ 表示当前最优策略需要 $i$ 步，从当前局面达到目标的期望步数。

接下来分类讨论：
当 $i \leq k$ 时， $f_i=i$
当 $i > k$ 时， $f_i=(i/n)*f_{i-1}+(n-i)/n*f_{i+1}+1$

如果是暴力高斯消元的话复杂度会爆的。
$I$ $ha v e$ $an$ $i d e a$ !
设 $f_i=f_{i-1}+b_i$ ，可以发现 $b_i$ 比较好求。
已知 $f_i=(i/n)*f_{i-1}+(n-i)/n*f_{i+1}+1$
代入可得 $f_i=(i/n)*(f_i-b_i)+(n-i)/n*(f_i+b_{i+1})+1$
整理一下就可以得到： $b_i=((n-i)*b_{i+1}+n)/i$
边界条件是 $b_n=1$
预处理数组 $b$ 之后再代入数组 $f$ 就简单多了
然后就无了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+3;
int n,m,c,a[N],inv[M],f[N],b[N];
inline int F(int n){return n?1ll*F(n-1)*n%M:1;
}
int main(){inv[1]=1;for(int i=2;i<M;i++) inv[i]=1ll*inv[M%i]*(M-M/i)%M;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=n,j;i;i--)if(a[i]){for(j=1;j*j<i;j++)if(i%j==0) a[j]^=1,a[i/j]^=1;if(j*j==i) a[j]^=1;c++;}if(m==n||m==n-1){printf("%lld",1ll*F(n)*c%M);return 0;}for(int i=0;i<=m;i++)f[i]=i;b[n]=1;for(int i=n-1;i>m;i--)b[i]=(1ll*(n-i)*b[i+1]+n)%M*inv[i]%M;for(int i=m+1;i<=n;i++) f[i]=(f[i-1]+b[i])%M;printf("%lld",1ll*F(n)*f[c]%M);return 0;
}

整体来说，码量偏小，思路不算很难（部分思路不易想到），整体偏简单。

在此鸣谢：赞助商：丁真和他的雪豹，友商：瑞克五代。

粉丝福利：美图一张
在这里插入图片描述

真蛰虫

忆者与梦泡

为了世间的美好而战

相逢是问候，离别是祝愿

相关文章：