首页 > 其他分享 >CF1993E Xor-Grid Problem

CF1993E Xor-Grid Problem

时间:2024-09-06 09:36:39浏览次数:7  
标签:le int 最小值 异或 continue Grid 一维 CF1993E Problem

结论,异或,状压 DP 2300

Link:https://codeforces.com/problemset/problem/1993/E

先考虑一维的情况。

若只有一维,每次操作的结果和 [AGC016D] XOR Replace 是一样的。对 \(a_i\) 进行一次操作相当于令 \(a_i:=\oplus_{1\le i\le n} a_i\),再对 \(j\) 进行一次操作相当于令 \(a_j:= a_i\)。

则题意等价于有一个长度为 \(n + 1\) 的数列 \(a\),\(a_{n + 1} = \oplus_{1\le i\le n} a_i\),可以任意交换 \(a_i\) 与 \(a_{n + 1}\),对于 \(a_1\sim a_n\) 求相邻两项差的绝对值之和的最小值。

发现数据范围很小,且贡献仅与相邻元素有关,考虑状压 DP 构造数列,记 \(f_{s, i}\) 表示当前填入的数列元素集合为 \(s\),填入的最后一个数是 \(a_i\) 时美丽值的最小值。初始化 \(f_{s, i} = \infin, f_{\{i\}, i} = 0\),则有显然的转移:

\[\forall 1\le i, j\le n + 1, i\not= j, i\in s,\ \ f_{s, i}\rightarrow f_{s \cup \{j\}, j} + |a_{i} - a_{j}| \]

记全集为 \(S\),答案即为:

\[\min_{1\le i,j\le n+1, i\not= j} f_{S - \{i\}, j} \]

总时间复杂度 \(O(n^2 2^n)\) 级别。

扩展到两维,发现若先进行一次行操作再进行一次列操作,等价于将交点位置修改为整个矩阵的异或和。于是考虑扩展上述做法,题意等价于有一个大小为 \((n + 1)\times (m + 1)\) 的矩阵,第 \(n+1\) 行为各列的异或和,第 \(m+1\) 列为各行的异或和(\((n + 1, m + 1)\) 即整个矩阵异或和),每次操作可以交换两行/两列,求左上角 \(n\times m\) 矩阵的美丽值的最小值。

考虑预处理任意两行/两列相邻时的贡献。发现两维的贡献是独立的,不同维的交换并不影响另一维的贡献。发现若枚举了哪一行被放在了 \(n+1\) 行上,则对列的贡献的计算就可以直接套用一维的做法了。于是考虑转移时处理 \(\operatorname{sum}(i, j)\) 表示将第 \(i\) 行第 \(j\) 列时的最小美丽值,取最小值即可。

在一维做法的基础上仅需再多枚举一维即可,总时间复杂度 \(O(n^2m 2^n + nm^2 2^m) \approx O(n^3 2^n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 16 + 2;
const int kS = (1 << 16) + 10;
const LL kInf = 1e18;
//=============================================================
int n, m, a[kN][kN];
LL ans, all, row[kN][kN], col[kN][kN], f[kS][kN];
LL sum[kN][kN];
//=============================================================
void init() {
  a[n + 1][m + 1] = 0;
  for (int i = 1; i <= n; ++ i) {
    a[i][m + 1] = 0;
    for (int j = 1; j <= m; ++ j) {
      a[i][m + 1] ^= a[i][j];
      a[n + 1][m + 1] ^= a[i][j];
    }
  }
  for (int j = 1; j <= m; ++ j) {
    a[n + 1][j] = 0;
    for (int i = 1; i <= n; ++ i) {
      a[n + 1][j] ^= a[i][j];
    }
  }
  for (int i = 1; i <= n + 1; ++ i) {
    for (int j = 1; j <= n + 1; ++ j) {
      row[i][j] = 0;
      for (int k = 1; k <= m + 1; ++ k) 
        row[i][j] += abs(a[i][k] - a[j][k]);
    }
  }
  for (int i = 1; i <= m + 1; ++ i) {
    for (int j = 1; j <= m + 1; ++ j) {
      col[i][j] = 0;
      for (int k = 1; k <= n + 1; ++ k)
        col[i][j] += abs(a[k][i] - a[k][j]);
    }
  }
}
void DP() {
  for (int i = 1; i <= n + 1; ++ i) {
    for (int j = 1; j <= m + 1; ++ j) {
      sum[i][j] = 0;
    }
  }

  all = (1 << (n + 1));
  for (int lst = 1; lst <= m + 1; ++ lst) {
    for (int s = 1; s < all; ++ s) {
      for (int i = 1; i <= n + 1; ++ i) {
        f[s][i] = kInf;
      }
    }
    for (int i = 1; i <= n + 1; ++ i) f[1 << (i - 1)][i] = 0;
    for (int s = 1; s < all; ++ s) {
      for (int i = 1; i <= n + 1; ++ i) {
        if ((s >> (i - 1) & 1) == 0) continue;
        for (int j = 1; j <= n + 1; ++ j) {
          if (i == j || (s >> (j - 1) & 1)) continue;
          f[s | (1 << (j - 1))][j] = std::min(f[s | (1 << (j - 1))][j], 
                                              f[s][i] + row[i][j] - abs(a[i][lst] - a[j][lst]));
        }
      }
    }
    for (int i = 1; i <= n + 1; ++ i) {
      LL minf = kInf;
      for (int j = 1; j <= n + 1; ++ j) {
        if (i == j) continue;
        minf = std::min(minf, f[(all - 1) ^ (1 << (i - 1))][j]);
      }
      sum[i][lst] += minf;
    }
  }
  
  all = (1 << (m + 1));
  for (int lst = 1; lst <= n + 1; ++ lst) {
    for (int s = 1; s < all; ++ s) {
      for (int i = 1; i <= m + 1; ++ i) {
        f[s][i] = kInf;
      }
    }
    for (int i = 1; i <= m + 1; ++ i) f[1 << (i - 1)][i] = 0;
    for (int s = 1; s < all; ++ s) {
      for (int i = 1; i <= m + 1; ++ i) {
        if ((s >> (i - 1) & 1) == 0) continue;
        for (int j = 1; j <= m + 1; ++ j) {
          if (i == j || (s >> (j - 1) & 1)) continue;
          f[s | (1 << (j - 1))][j] = std::min(f[s | (1 << (j - 1))][j], 
                                              f[s][i] + col[i][j] - abs(a[lst][i] - a[lst][j]));
        }
      }
    }
    for (int i = 1; i <= m + 1; ++ i) {
      LL minf = kInf;
      for (int j = 1; j <= m + 1; ++ j) {
        if (i == j) continue;
        minf = std::min(minf, f[(all - 1) ^ (1 << (i - 1))][j]);
      }
      sum[lst][i] += minf;
    }
  }

  ans = kInf;
  for (int i = 1; i <= n + 1; ++ i) {
    for (int j = 1; j <= m + 1; ++ j) {
      ans = std::min(ans, sum[i][j]);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= m; ++ j) {
        std::cin >> a[i][j];
      }
    }
    init();
    DP();
    std::cout << ans << "\n";
  }
  return 0;
}
/*
1
1 2
1 3
*/

标签:le,int,最小值,异或,continue,Grid,一维,CF1993E,Problem
From: https://www.cnblogs.com/luckyblock/p/18399633

相关文章

  • LigerUI 中的 Grid (ligerGrid) 合并单元格
    在网上搜索了很都都没有正确的方法实现合并单元格,LigerGrid不像 EasyUI 中的Grid可以直接合并单元格。我化了点时间,解决了,就分享给大家,我就不做详细的注释,只有有一定基础的都可以看懂,菜鸟就自己去补习吧。<divid="maingrid"style="margin:0;padding:0"></div......
  • MATLAB警告: 桌面配置文件已损坏或格式不正确。 Problem parsing Desktop restore xml
    电脑蓝屏后,重新打开MATLAB,出现此问题解决方案如下:如果您正在启动MATLAB并收到以下错误,则可能使用的是与MATLAB附带的Java版本不同的Java版本。ERROR:Warning:Anerroroccurredwhilereadingthedesktopconfigurationfile为了检查MATLAB使用的Java版本,启动MATLAB并运......
  • DevExpress WinForms中文教程:Data Grid - 如何自定义绘制?
    在本教程中,您将学习如何使用DevExpressgridView(网格视图)的CustomDraw…事件,您将从一个显示普通任务数据的网格开始。首先使用事件来自定义单元格外观,然后修改相同的事件处理程序,来根据网格数据更改单个单元格中显示的文本。接下来将进一步扩展处理程序来在特定单元格中绘制图像,......
  • lazarus DBGridEh标题栏排序
    lazarusDBGridEh标题栏排序按网上(delphi)的方法发现无效,经测试,以下代码可以正常排序:unitUnit1;{$modeObjFPC}{$H+}interfaceusesClasses,SysUtils,DB,Forms,Controls,Graphics,Dialogs,StdCtrls,Uni,DBGridsEh,DBCtrlsEh,LConvEncoding,DBGridEhImpE......
  • lazarus使用dbgrideh时遇到的问题
    问题:lazarus使用unidac+dbgrideh时,发现第一次查询可以正确显示查询的结果,当再次查询时(记录数>1条时),DBGridEH只显示1条记录,如果向下移动时还会出错。 点费率时只显示1条记录:这时向下移动会出错: 解决方法:uniquery查询前设置:dbgrideh.DataSource:=nil查询完成后重新设置Data......
  • WPF UniformGrid contain children auto resize
    //xaml<Windowx:Class="WpfApp332.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.mi......
  • DataGrid绑定item的对象值
    <DataGridTextColumnMinWidth="150"Binding="{BindingConverter={StaticResourceWeightToStringConveter}}"ElementStyle="{StaticResourceCenterTextBlockStyle}"Header="重量"/>namespacePipette.Con......
  • Paper Reading: Multi-class imbalance problem: A multi-objective solution
    目录研究动机文章贡献本文方法问题定义多分类多目标选择集成框架多类样本的客观建模理论分析实验结果数据集和实验设置对比实验结果运行时间优化边界的有效性优点和创新点PaperReading是从个人角度进行的一些总结分享,受到个人关注点的侧重和实力所限,可能有理解不到位的地方。具......
  • WPF access mysql and pass data from datagrid to mysql
    //sqldropdatabaseifexistsmydb;createdatabasemydb;usemydb;droptableifexistsmt;createtablemt(idintauto_incrementprimarykey,namevarchar(50)notnulldefault'',isbnvarchar(50)notnulldefault'',authorvarchar......
  • 白骑士的CSS高级篇之CSS Grid布局进阶 4.1.2 网格模板与区域
            CSSGrid布局是CSS中强大的布局系统之一,它提供了更灵活和更高效的方式来创建复杂的网页布局。通过Grid布局,你可以将网页划分为多个网格区域,并在这些区域中放置内容,这使得布局更加直观和易于维护。本文将深入探讨Grid布局中的网格模板和区域的概念,帮助你掌握如......