[SNCPC2024] 表达式矩阵 题解

· · 题解

考虑朴素暴力，显然不能有符号相邻或者在边界上。暴力搜小数据答案，发现如果一个位置 (i,j) 满足 i+j\equiv 0\pmod 2，那么这个位置要放符号，否则要放数字。于是可以据此直接打表。

但是这样太不优雅了。直接将这些位置先全部填上 *，发现答案不一定最优。考虑把若干个 * 替换成 +，对照打出来的表发现这样的 + 不超过 6 个，根据第一段提出的方法，* 的个数不超过 24 个；于是直接暴力枚举哪些 * 要变成 +，时间复杂度取决于实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int g(int x){
  int c=0;
  while(x--)c=(c<<1)+(c<<3)|1;
  return c;
}
inline int f0(string s){
  vector<int> t;
  for(int i=0,l=0;i<=s.length();i++)
    if(i==s.length()||s[i]=='*')
      t.emplace_back(i-l),l=i+1;
  int c=1;
  for(int i:t)c*=g(i);
  return c;
} // 计算仅含 * 的表达式的值
inline int f1(string s){
  vector<string> t;
  for(int i=0,l=0;i<=s.length();i++)
    if(i==s.length()||s[i]=='+')
      t.emplace_back(s.substr(l,i-l)),l=i+1;
  int c=0;
  for(auto i:t)c+=f0(i);
  return c;
} // 计算表达式的值
inline int f2(vector<string> a){
  int c=0;
  for(int i=0;i<a.size();i++)
    c+=f1(a[i]);
  for(int i=0;i<a[0].size();i++){
    string s;
    for(int j=0;j<a.size();j++)
      s+=a[j][i];
    c+=f1(s);
  }
  return c;
} // 计算一个矩阵的答案
main(){
  ios::sync_with_stdio(false);
  int n,m,r=6e18; cin>>n>>m;
  vector<string> a(n,string(m,49)),w;
  vector<pair<int,int> > p;
  for(int i=1;i<n-1;i++)
    for(int j=1;j<m-1;j++)
      if(!(i+j&1))a[i][j]='*',p.emplace_back(i,j);
  for(int i=0;i<1<<p.size();i++)
    if(__builtin_popcount(i)<6){
      auto b=a;
      for(int j=0;j<p.size();j++)
        if(i>>j&1)b[p[j].first][p[j].second]='+';
      if(int x=f2(b);x<r)r=x,w=b;
    } // 暴力枚举
  for(auto i:w)cout<<i<<'\n';
  return 0;
}