第34次CCF-CSP认证真题解析（目的300分做法）

矩阵重塑（其一）

输入输出及样例：

AC代码及解析

• 1.线性化原矩阵 ：由于cin的特性我们直接把给定的矩阵按照标题的意思转换成一维数组即可
  
• 2.填充新矩阵 ：然后对于新的矩阵 我们只必要按照新的规模p*q重新排版即可
  

1. #include <bits/stdc++.h>
2. using namespace std;
3. int n,m,p,q;
4. const int N=1e4+10;
5. int a[N];
6. int main(){
7.     cin>>n>>m>>p>>q;
8.     for(int i=0;i<n*m;i++) cin>>a[i];
9.     int index=0;
10.     for(int i=0;i<p;i++){
11.         for(int j=0;j<q;j++){
12.             cout<<a[index]<<' ';
13.             index++;
14.         }
15.         cout<<endl;
16.     }
17.     return 0;
18. }

复制代码

矩阵重塑（其二）

输入输出及样例：

AC代码及解析

根本思路：受到第一题启发 我们可以将这个二维矩阵转化成一维数组的情势
对于这三种操纵：

• 1.重塑
  
• 我们对应一维数组中的元素是不变的 只必要将改变之后的矩阵规格更新一下 也就是n=a m=b
  
• 2.转置
  
• 也就是行列交换 详细来说就是 原来重塑的时候 我们是如何找到矩阵上的元素对应数组的下标
  比如说（1,2）
  我们就用【（当前行 1 乘以矩阵的列数 m ）+ 2 】得到对应数组S的下标
  而现在转置之后 行和列的地位交换
  是不是就是 【（用当前列 2 乘以矩阵的行数 n）+1 】这样一个一个计算 得到对应 转置之后新的数组SS 之后再交换我们行和列的数值 这样就完成了一次转置操纵
  
• 3.查询对应位置上的元素
  直接输出对应数组元素就好
  

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N=1e4+10;
4. int n,m,t;
5. int op,a,b;//这是操作格式
6. int s[N];//将重塑前的M转化为一维数组
7. int tmp[N];
8. int main()
9. {
10.    cin>>n>>m>>t;
11.    //构造一维数组
12.    for(int i=0;i<n*m;i++)
13.    {
14.            cin>>s[i];
15.    }
16.    //处理每一个查询
17.    while(t--)
18.    {
19.      cin>>op>>a>>b;
20.      if(op==1)//进行矩阵的重塑 不论怎么重塑都不会改变其对应一维数组的值的顺序
21.          //所以只需要更新一下矩阵大小的规模就行
22.      {
23.          n=a;
24.          m=b;
25.      }else if(op==2)//进行矩阵的转置(行列互换)
26.      {
27.           for(int i=0;i<n;i++)//i表示当前行数
28.           {
29.               for(int j=0;j<m;j++)//j表示当前列数
30.               {
31.                 tmp[j*n+i]=s[i*m+j];//本质上就是行和列的地位互换了 i改成j n改成m
32.               }
33.           }
34.           //更新对应一维数组的值
35.           for(int i=0;i<n*m;i++)
36.           {
37.               s[i]=tmp[i];
38.           }
39.           //更新矩阵规模(本质上就是交换行和列的数值）
40.           int tt=n;
41.           n=m;
42.           m=tt;
43.      }else if(op==3)//进行查询操作(只有查询操作才需要输出)
44.      {
45.          cout<<s[a*m+b]<<endl;
46.      }
47.    }
48.     return 0;
49. }

复制代码

货物调治

输入输出及样例：

AC代码及解析

写了一个世纪 结果只能暴力拿30分 道心破裂 固然感觉这道题满分解是dp 但是真正写起来真的真的好困难 连最根本的选择和状态都很难确定下来 更别说状态转移方程了 哈哈
这里附上大佬解析：文章链接

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
5. int dp[1005][40010];//前i个仓库费用j可以获得的最大总价值
6. vector<int>a[1005];//第i个仓库的第j个货物的价值
7. int b[1005],c[1005];//仓库属性
8. bool dcmp(int a,int b){
9.     return a>b;
10. }
11. int main(){
12.     int n,m,v;
13.     cin>>n>>m>>v;
14.     for(int i=0;i<=40000;i++)dp[0][i]=0;
15.     for(int i=1;i<=n;i++){
16.         cin>>b[i]>>c[i];
17.     }
18.     for(int i=1;i<=m;i++){
19.         int val,t;
20.         cin>>val>>t;
21.         t++;
22.         a[t].push_back(val);
23.     }
24.     for(int i=1;i<=n;i++){
25.         sort(a[i].begin(),a[i].end(),dcmp);
26.     }
27.     for(int i=1;i<=n;i++){
28.         for(int j=0;j<=40000;j++){
29.             dp[i][j]=dp[i-1][j];//不选i
30.             int sum=0;
31.             for(int k=0;k<a[i].size();k++){//选i
32.                 if(b[i]+c[i]*(k+1)>j)break;
33.                 sum+=a[i][k];//收益和
34.                 dp[i][j]=max(dp[i][j],dp[i-1][j-b[i]-c[i]*(k+1)]+sum-b[i]-c[i]*(k+1));
35.             }
36.         }
37.     }
38.     int ans;
39.     for(int i=0;i<=40000;i++){
40.         if(dp[n][i]>=v){
41.             ans=i;break;
42.         }
43.     }
44.     cout<<ans;
45.     return 0;
46. }

复制代码