1_1
1_1.PNG
思路
回溯+剪枝，这道题我只想出了回溯的方式，但是具体的优化剪枝还没有想出来，后面再想吧。但是有一个bug的地方还是没想明白,就是为什么不能用注释的那段代码来保留之前的数呢，这样写交上去尽然是0分，这个问题还是等等好好想想，至少应该放在想优化前面吧。
code(7分）
#include <stdio.h>
#include <stdlib.h>
long long max = -1e18, sum;
int n, t, m, temp[30];
int matrix[4][30];
void traceBack(int cur)
{
int i, j;
if(cur == m)
{
sum = 0;
for(i = 0; i < n; i++)
sum += matrix[0][i] * matrix[2][i];
max = sum > max? sum : max;
}
else
{
for(i = 0; i < 2; i++)
{
if(i) //进行操作2
{
/*for(j = 0; j < n; j++) //保存修改前的a数组
temp[cur][j] = matrix[0][j];
for(j = 0; j < n; j++)
matrix[0][j] = matrix[0][matrix[3][j] - 1] + t;
traceBack(cur + 1);
for(j = 0; j < n; j++)
matrix[0][j] = temp[cur][j];*/
for(j = 0; j < n; j++)
temp[j] = matrix[0][j];
for(j = 0; j < n; j++)
matrix[0][j]=temp[matrix[3][j] - 1] + t;
traceBack(cur + 1);
for(j = 0; j < n; j++)
temp[j] = matrix[0][j];
for(j = 0; j < n; j++)
matrix[0][matrix[3][j] - 1] = temp[j] - t;
}
else //进行操作1
{
for(j = 0; j < n; j++)
matrix[0][j] ^= matrix[1][j];
traceBack(cur + 1);
for(j = 0; j < n; j++)
matrix[0][j] ^= matrix[1][j];
}
}
}
}
int main(int argc, char *argv[])
{
int i, j;
scanf("%d%d%d", &n, &m, &t);
for(i = 0; i < 4; i++)
for(j = 0; j < n; j++)
scanf("%d", &matrix[i][j]);
traceBack(0);
printf("%lld\n", max);
return 0;
}
另外附上一份室友提供的10分代码，还没来得及看
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 30;
int temp[MAXN];
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int n,m,t;
LL dfs(int now, int lasto){
if(now==m){
LL ret=0;
for(int i=1;i<=n;i++)
ret+=a[i]*c[i];
return ret;
}
LL ret=-1e18;
if((m-now)%2==0){
ret=0;
for(int i=1;i<=n;i++)
ret+=a[i]*c[i];
}
if(lasto!=1){
for(int i=1;i<=n;i++)
a[i]^=b[i];
ret=max(ret,dfs(now+1,1));
for(int i=1;i<=n;i++)
a[i]^=b[i];
}
for(int i=1;i<=n;i++)
temp[i]=a[i];
for(int i=1;i<=n;i++)
a[i]=temp[d[i]]+t;
ret=max(ret,dfs(now+1,2));
for(int i=1;i<=n;i++)
temp[i]=a[i];
for(int i=1;i<=n;i++)
a[d[i]]=temp[i]-t;
return ret;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
printf("%lld\n",dfs(0,0));
return 0;
}
2_2
image.png
思路
如果真正的去移动二位数组中的元素的话这题是会超时的，所以必须转换思路，即用两个一维数组来记录交换行列交换的记录。row[i]记录的是当前第i行是原始二位矩阵中的第几行，同理对于colum[i]。
code(10分）
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
int i, j, temp, n, m, q;
int op, x, y;
int matrix[1001][1001];
int row[1001], colum[1001];
scanf("%d%d%d", &n, &m, &q);
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
scanf("%d", &matrix[i][j]);
for(i = 0; i < n; i++)
row[i] = i; //用于记录行的交换
for(j = 0; j < m; j++)
colum[j] = j; //用于记录列的交换
while(q--)
{
scanf("%d%d%d", &op, &x, &y);
if(op == 0 && x != y)
{
temp = row[x - 1];
row[x - 1] = row[y - 1];
row[y - 1] = temp;
}
else if(op == 1 && x != y)
{
temp = colum[x - 1];
colum[x - 1] = colum[y - 1];
colum[y - 1] = temp;
}
else
printf("%d\n", matrix[row[x - 1]][colum[y - 1]]);
}
return 0;
}
