2 条题解
-
4
这道题看似是一个dfs的遍历，但是数值却很大，所以因该使用动态规划。f[i][j][w]代表第i行第j列w是否存在。可以根据f[i-1][j][w]和f[i][j-1][w]来推理出f[i][j][(w*a[i][j])%mod]的值是true还是false。最后输出即可。
代码
#include <iostream> #include <vector> using namespace std; int main(void){ int n,m,k,sum=0; cin>>n>>m>>k; vector<vector<vector<bool>>> f(n+1,vector<vector<bool>>(m+1,vector<bool>(k+1,false))); vector<vector<int>> a(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; f[1][0][1]=1; f[0][1][1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int w=0;w<k;w++) if(f[i-1][j][w]==1||f[i][j-1][w]==1) f[i][j][(w*a[i][j])%k]=true; for(int i=0;i<k;i++) sum+=f[n][m][i]; cout<<sum<<endl; for(int i=0;i<k;i++) if(f[n][m][i]) cout<<i<<' '; return 0; } -
3
用f[i][j][k]表示走到第i行第j列时w是否存在，题目要求只能向右或向下移动，因此(i,j)对应的状态可以由(i-1,j)和(i,j-1)对应的状态推得。最后统计(n,m)这个位置对应的状态即可。
核心代码
f[0][1][1] = 1; f[1][0][1] = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int w = 0; w < k; w++) { if (f[i - 1][j][w] == 1) f[i][j][(w * a[i][j]) % k] = 1; if (f[i][j - 1][w] == 1) f[i][j][(w * a[i][j]) % k] = 1; } for (int i = 0; i < k; i++) if (f[n][m][i] == 1) cnt++; cout << cnt << endl; for (int i = 0; i < k; i++) if (f[n][m][i] == 1) cout << i << " ";
hetao24883491
LV 10
@ 2023-11-4 17:07:11
- 1