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;
}