A. 很会dp
出题人： zhber
AC/TOT： 1/50
题解： 因为 V 实在太大了，所以做背包 dp 肯定不行，这一点在题目中已经很明显的提示了。那么另一种做法只能是暴力枚举每一个物品取还是不取。每件物品可以选取或不取，这样方案数会有 2n，是不能接受的。注意到如果 n 变成 2n，暴力枚举似乎就可以接受了。再考虑到如果 n 件物品分成两部分，分别以 22n 枚举这两部分的所有可能的体积之和，合并的时候不需要在两区间枚举各取什么再加起来，因为这样还是 2n，而对于一个区间枚举取的是什么体积（假如取了体积是 sum ），另一个区间排序之后直接二分小等于 V−sum 的最大值即可。显然只有这个值对于 sum 才是有用的，其他值要么加起来超过 V，要么加起来不如它优。因此对 n 个物品折半之后分别暴力处理所有可能体积，然后枚举前半部分，在后半部分二分即可。这个算法有个专门的名字，叫meet-in-middle有兴趣的同学可以去学习一下“折半搜索”！
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,len;
ll a[40],V,ans;
ll s[200010];
inline ll bsearch(int l,int r,ll x)
{
ll t=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (s[mid]<=x)t=s[mid],l=mid+1;
else r=mid-1;
}
return t;
}
int main()
{
scanf(\"%d%lld\",&n,&V);
for (int i=1;i<=n;i++)scanf(\"%lld\",a+i);
for (int i=0;i<(1<<(n/2));i++)
{
ll sum=0;
for (int j=1;j<=n/2;j++)
if (i & (1<<(j-1)) )sum+=a[j];
if(sum<=V)s[++len]=sum;
}
s[++len]=0;
sort(s+1,s+len+1);
ans=s[len];
for (int i=0;i<(1<<(n-n/2));i++)
{
ll sum=0;
for (int j=n/2+1;j<=n;j++)
if (i & (1<<(j-n/2-1)) )sum+=a[j];
if(sum<=V)ans=max(ans,sum+bsearch(1,len,V-sum));
}
printf(\"%lld\\n\",ans);
}
B. 秀外慧中
出题人： zhber
AC/TOT： 0/0
题解： 注意到只要各位有一个零，那么乘积就是零了。因此t是零与非零的情况分类讨论。
- 对于乘积为零的情况，考虑到用总方案数减去不合法方案数，即得到合法的方案数。总方案数是 10k，不合法方案就是 k 位都不是零，共 9k 个。所以答案就是 10k−9k。注意答案取模必须是非负的。
- 对于乘积不为零的情况，注意到填的数字只能是 1...9，那么t分解质因数其实只能有 2、3、5、7 四个质因数，否则一定无解。如果 t=2a3b5c7d，只要取 k 个数，乘起来得到 a 个 2、b 个 3、c 个 5、d 个 7 即可。
考虑动态规划：f[i][j][k][l][m]表示前i个位置、已经有 j 个 2、k 个 3、l 个 5、m 个 7 的方案数，考虑取 1...9 每个数能贡献几个什么数字即可，比如 6 贡献了 1 个 2、1 个 3，因此 f[i][j][k][l][m]+=f[i−1][j−1][k−1][l][m]，其他 8 个式子同理。最后答案即为 f[k][a][b][c][d]。而 227≈317≈512≈710≈108，所以a、b、c、d不会很大。
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,t;
int p[20],q[20],len;
ll f[50][30][20][15][15];
int main()
{
scanf(\"%d%d\",&n,&t);
if (t==0)
{
int s1=1,s2=1;
for (int i=1;i<=n;i++)s1=(s1*10)%mod,s2=(s2*9)%mod;
printf(\"%d\\n\",(s1-s2+mod)%mod);
return 0;
}
for (int i=2;i*i<=t;i++)
if (t%i==0)
{
p[++len]=i;q[len]=1;t/=i;
while (t%i==0)t/=i,q[len]++;
}
if (len==0||t!=1)
{
p[++len]=t;
q[len]=1;
}
for (int i=1;i<=len;i++)if (p[i]!=1&&p[i]!=2&&p[i]!=3&&p[i]!=5&&p[i]!=7){puts(\"0\");return 0;}
int a=0,b=0,c=0,d=0;
for(int i=1;i<=len;i++)
{
if (p[i]==2)a=q[i];
if (p[i]==3)b=q[i];
if (p[i]==5)c=q[i];
if (p[i]==7)d=q[i];
}
f[0][0][0][0][0]=1;
for (int i=1;i<=n;i++)
for (int j=0;j<=a;j++)
for (int k=0;k<=b;k++)
for(int l=0;l<=c;l++)
for (int m=0;m<=d;m++)
{
f[i][j][k][l][m]+=f[i-1][j][k][l][m];//1
if (j>=1)f[i][j][k][l][m]+=f[i-1][j-1][k][l][m];//2
if (k>=1)f[i][j][k][l][m]+=f[i-1][j][k-1][l][m];//3
if (j>=2)f[i][j][k][l][m]+=f[i-1][j-2][k][l][m];//4
if (l>=1)f[i][j][k][l][m]+=f[i-1][j][k][l-1][m];//5
if (j>=1&&k>=1)f[i][j][k][l][m]+=f[i-1][j-1][k-1][l][m];//6
if (m>=1)f[i][j][k][l][m]+=f[i-1][j][k][l][m-1];//7
if (j>=3)f[i][j][k][l][m]+=f[i-1][j-3][k][l][m];//8
if (k>=2)f[i][j][k][l][m]+=f[i-1][j][k-2][l][m];//9
f[i][j][k][l][m]%=mod;
}
printf(\"%lld\\n\",f[n][a][b][c][d]);
}
C. 背着大家偷偷交题
出题人： zhber
AC/TOT： 0/0
题解： 把所有熟人的位置扔进队列，然后做 bfs 往外扩展，即可知道每个点到它最近熟人的距离 dist[i][j]。显然如果存在一条最小距离是 k 的路径，也肯定存在一条最小距离是 k−1 的路径，因此最大的最小距离会在 [k,+∞)。而如果不存在最小距离是 k 的路径，那也一定不存在最小距离是 k+1 的路径，因此最大的最小距离会在 [0,k)。因此可以二分最小距离，不管我们判断某个答案可不可行，一定可以将范围至少缩小一半。考虑判定最小距离 mid 可不可行，此时只能走满足 dist[x][y]≥mid 的点 (x,y)，相当于在原有条件下多了一个合法性的判定。在此条件下，bfs 求 S 到 T 的最短距离即可。
参考代码：
#include<bits/stdc++.h>
#define pa pair<int,int>
#define mkp make_pair
using namespace std;
char mp[1010][1010];
int dist[1010][1010];
int dis2[1010][1010];
int n,m;
int sx,sy,ex,ey;
int mx[4]={1,0,-1,0},my[4]={0,1,0,-1};
inline void bfs1()
{
memset(dist,-1,sizeof dist);
queue<pa>q;while (!q.empty())q.pop();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (mp[i][j]==\'#\')q.push(mkp(i,j)),dist[i][j]=0;
while (!q.empty())
{
int nx=q.front().first,ny=q.front().second;q.pop();
for (int k=0;k<4;k++)
{
int wx=nx+mx[k];
int wy=ny+my[k];
if (wx<1||wx>n||wy<1||wy>m||dist[wx][wy]!=-1)continue;
dist[wx][wy]=dist[nx][ny]+1;
q.push(mkp(wx,wy));
}
}
}
inline int bfs2(int x)
{
memset(dis2,-1,sizeof dis2);
queue<pa>q;while (!q.empty())q.pop();
q.push(mkp(sx,sy));dis2[sx][sy]=0;
while (!q.empty())
{
int nx=q.front().first,ny=q.front().second;q.pop();
for (int k=0;k<4;k++)
{
int wx=nx+mx[k];
int wy=ny+my[k];
if (wx<1||wx>n||wy<1||wy>m||dis2[wx][wy]!=-1||dist[wx][wy]<x)continue;
dis2[wx][wy]=dis2[nx][ny]+1;
q.push(mkp(wx,wy));
}
}
return dis2[ex][ey];
}
int main()
{
scanf(\"%d%d\",&n,&m);
for (int i=1;i<=n;i++)scanf(\"%s\",mp[i]+1);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
if (mp[i][j]==\'S\')sx=i,sy=j;
else if (mp[i][j]==\'T\')ex=i,ey=j;
}
bfs1();
int l=0,r=2*n-1,ans=0,ans2=0;
while (l<=r)
{
int mid=(l+r)>>1,cal=bfs2(mid);
if (cal!=-1)ans=mid,ans2=cal,l=mid+1;
else r=mid-1;
}
printf(\"%d %d\\n\",ans,ans2);
}
D. I Love Diamond Forever.jpg
出题人： konnyaku
AC/TOT： 8/52
题解：
diamond裸 dp，不会就把讲 dp 的学长拖出去枪毙五分钟 。 ——天爸爸
卖完萌还是讲一下吧，分析一下问题，钻石血量多少不会影响它受多少伤害，反而一旦月狗质量确定，则钻石受的伤害是确定的，明白了这一点，这符合动态规划的子问题性质，考虑 f(i) 表示一只血量为 i 的月狗能对钻石造成的最小伤害，它下一轮只会转移到 f(i)→f(i−k)+f(k), 0<k<i 枚举 k 就好了，而且因为有对称性， k 只需要枚举到 [2i] 就好了，由于 N 和 M 都很大我们可以考虑记忆化搜索。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
int a[maxn];
ll f[maxn];
ll DP(int i) {
if (f[i] != -1) return f[i];
if (i == 1) return 0;
ll ans = 1e18;
for (int k = 1; k <= i / 2; k++) ans = min(ans, DP(k) + DP(i - k) + a[k] 继续阅读与本文标签相同的文章
一种基于Lucene的实时搜索服务
-
这款 IDE 插件再次升级，让「小程序云」的开发部署提速 8 倍
2026-05-19栏目： 教程
-
专注于技术能力提升的央企，注定不平凡，我有看点！
2026-05-19栏目： 教程
-
男友力爆棚的Mac电脑办公软件WPS Office
2026-05-19栏目： 教程
-
Kubernetes 入门必备云原生发展简史
2026-05-19栏目： 教程
-
Java B2B2C多用户商城 springcloud架构（一）
2026-05-19栏目： 教程