题解：P10692 [SNCPC2024] 表达式矩阵

· · 题解

思路

考虑每一行（列），最多存在两个 11，其余均为 1，对于两个 11，不可让其相乘，故此每一行（列）中若有两个 11，则必须有一个加号。

根据此考虑打表即可，从贪心的思路，满足上述条件的同时使加号尽可能的少，因为 x\times 1\le x+1。

打表

为防止影响阅读，所打出的表放在剪切板内。

代码如下

#include <bits/stdc++.h>
using namespace std;

signed main() {
    string b[100][100];
b[3][3]="1111*1111";
b[3][4]="11111*111111";
b[3][5]="111111*1*111111";
b[3][6]="1111111*1*11111111";
b[3][7]="11111111*1*1*11111111";
b[3][8]="111111111*1*1*1111111111";
b[3][9]="1111111111*1*1*1*1111111111";
b[4][3]="1111111*1111",
b[4][4]="11111*1111*11111";
b[4][5]="111111*1*111+1111111";
b[4][6]="11111111*1*11*1*11111111";
b[4][7]="11111111*1*1*111+1*111111111";
b[4][8]="111111111*1*1*1111*1*1*111111111";
b[4][9]="1111111111*1*1*1*111*1*1+11111111111";
b[5][3]="1111*11111*1111",
b[5][4]="11111*1111+11*111111",
b[5][5]="111111*1*111+111*1*111111";
b[5][6]="1111111*1*1111+1+11*1*11111111";
b[5][7]="11111111*1*1*111+1+111*1*1*11111111";
b[5][8]="111111111*1*1*1111+1+1+11*1*1*1111111111";
b[5][9]="1111111111*1*1*1*111+1+1+111*1*1*1*1111111111";
b[6][3]="1111111*11111*1111",
b[6][4]="11111*1111*11*1111*11111",
b[6][5]="1111111+111*1*111+111*1*111111",
b[6][6]="1111111*1*1111*1*11*1*1111*1*1111111";
b[6][7]="11111111*1*1*111+1*111*1*1*111+1*111111111";
b[6][8]="111111111*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
b[6][9]="1111111111*1*1*1*111*1*1+111*1*1*1*111+1*1*11111111111";
b[7][3]="1111*11111*11111*1111",
b[7][4]="11111*1111*11*1111+11*111111",
b[7][5]="111111*1*111+111*1*111+111*1*111111",
b[7][6]="1111111*1*1111*1*11*1*1111+1+11*1*11111111",
b[7][7]="11111111*1*1*111+1*111*1*1*111*1+111*1*1*11111111";
b[7][8]="111111111*1*1*1111+1*1+11*1*1*1111*1+1*11*1*1*1111111111";
b[7][9]="1111111111*1*1*1*111*1*1+111*1*1*1*111+1+1*111*1*1*1*1111111111";
b[8][3]="1111111*11111*11111*1111";
b[8][4]="111111*11*1111*11*1111*11*111111",
b[8][5]="1111111+111*1*111+111*1*111+111*1*111111",
b[8][6]="11111111*1*11*1*1111*1*11*1*1111*1*11*1*11111111",
b[8][7]="111111111+1*111*1*1*111*1+111*1*1*111+1*111*1*1*11111111",
b[8][8]="111111111*1*1*1111*1*1*11*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
b[8][9]="1111111111*1*1*1*111+1*1*111*1*1*1*111+1*1*111*1*1*1*111*1*1+11111111111";
b[9][3]="1111*11111*11111*11111*1111";
b[9][4]="11111*1111+11*1111*11*1111*11*111111",
b[9][5]="111111*1*111+111*1*111+111*1*111+111*1*111111",
b[9][6]="1111111*1*1111+1*11*1*1111*1*11*1*1111*1+11*1*11111111",
b[9][7]="11111111*1*1*111+1*111*1*1*111*1+111*1*1*111*1+111*1*1*11111111",
b[9][8]="111111111*1*1*1111*1*1+11*1*1*1111*1*1*11*1*1*1111+1+1*11*1*1*1111111111",
b[9][9]="1111111111*1*1*1*111+1*1*111*1*1*1*111*1+1*111*1*1*1*111*1*1+111*1*1*1*1111111111";

    cin.tie(0) -> sync_with_stdio(false);
    int n, m; cin >> n >> m;
        string s = b[n][m]; s = ' ' + s;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                cout << s[(i - 1) * m + j];
            cout << '\n';
        }
    return 0;
}