首页 > 其他分享 >题解 CF407D【Largest Submatrix 3】/ SS240928C【c】

题解 CF407D【Largest Submatrix 3】/ SS240928C【c】

时间:2024-09-28 21:23:30浏览次数:7  
标签:边界 -- 题解 元素 CF407D int SS240928C buc 指针

题目描述

给定一个 \(n \times m\) 的正整数矩阵,求其中最大的满足其中不存在两个位置数值相等的子矩阵大小。\(1 \leq n , m \leq 400\)。

本题有多种做法,而你需要寻找常数最小的做法才能通过本题。

solution 链表+双指针

枚举上边界,逐渐下移下边界,枚举左边界,尝试双指针获得右边界。困难之处在于,指针移动一次需要加入或删除 \(O(n)\) 个元素。观察一个元素带来的限制,我们需要找出在它之上或左边,与它相同的元素的列位置的前驱与后继,然后要求双指针区间包含这个元素时,不能同时也覆盖到它的前驱和后继。找出前驱、后继后将元素插入。这个前驱后继的部分可以离线逆序,使用双向链表求得。然后是这个元素的限制,我们使用不带删的双指针,每次都要求当前区间包含的元素的所有限制,当前区间的两个端点都满足,而限制之间可以合并,就是不能删除,是不删除双指针的特征。于是可以 \(O(n^3)\) 时间解决这个问题。

需要说明的是,这个算法的链表部分常数很大,这是因为其寻址不连续,过不了这一题。

【模板】不删除双指针 - caijianhong - 博客园 (cnblogs.com)

solution 双指针

设 \(f_{l, r, u}\) 表示固定左、右、上边界分别为 \(l, r, u\) 之后的下边界最大是多少。显然至少应有:

\[f_{l, r, u}\leq\min(f_{l+1, r, u}, f_{l, r-1, u}, f_{l, r, u+1}) \]

你画一个图,缺失的部分是:\(a_{u, l}\neq a_{[u, d], r}\land a_{u, r}\neq a_{[u, d], l}\)(考虑从 \(f_{l, r, u+1}\) 转移而来,再考虑两个缩左右边界的对当前未判定部分造成的影响,发现中间部分已经合法)。于是可以开两个桶,双指针维护限制。

code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, m, a[410][410], f[2][410][410], buc[2][160010], ans;
int main() {
#ifndef LOCAL
#ifndef NF
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) cin >> a[i][j];
  }
  memset(f[0], 0x3f, sizeof f[0]);
  for (int t = 1; t <= m; t++) {
    memset(f[t & 1], 0x3f, sizeof f[0]);
    for (int l = 1, r = t; r <= m; l++, r++) {
      int d = n;
      for (int u = n; u >= 1; u--) {
        int lim = min(f[~t & 1][l][u], f[~t & 1][l + 1][u]);
        ++buc[0][a[u][l]], ++buc[1][a[u][r]];
        while (d >= u && (d > lim || buc[0][a[u][r]] > (t == 1)|| buc[1][a[u][l]] > (t == 1))) --buc[0][a[d][l]], --buc[1][a[d][r]], --d;
        f[t & 1][l][u] = d;
        debug("f[%d][%d][%d] = %d\n", l, r, u, d);
        ans = max(ans, (d - u + 1) * t);
      }
      while (d) --buc[0][a[d][l]], --buc[1][a[d][r]], --d;
    }
  }
  cout << ans << endl;
  return 0;
}

标签:边界,--,题解,元素,CF407D,int,SS240928C,buc,指针
From: https://www.cnblogs.com/caijianhong/p/18438434/solution-CF407D

相关文章

  • 题解 ARC118E【Avoid Permutations】/ SS240928D【d】
    题目描述对于一个排列\(a\),定义其权值如下:生成一个\((n+2)\times(n+2)\)的网格图,行列标号为\(0∼n+1\),每次可以从\((i,j)\)走到\((i,j+1)\)或\((i+1,j)\),且不能走到\((i,a_i)\),权值为从\((0,0)\)走到\((n+1,n+1)\)的方案数。现在排列\(......
  • [USACO22DEC] Making Friends P 题解
    T2[USACO22DEC]MakingFriendsP考虑删除一个点,会有如下的点相连接:题目要求如果两两个点建立联系,只会建立一次。所以,神奇地,我们取出当前待删的点所连接的最小的点,将它和剩下的点连接。手摸一下会发现这样就巧妙地给每个改建的边都建了一次。所以用一个set启发式合并就做完......
  • 2. 两数相加题解
    题目描述给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之外,这两个数都不会以0开头。示例1:输入:l1=[2,4,3],l2=[5,6,4......
  • 【自创题】云梯 题面+题解
    题目描述这是晴练P2876云梯的题面。原链接unicornFairy开始了新的学期。学校换了一个新校长,随之而来的是周五放学的时间由晚上七点半延时到了晚上八点半。unicornFairy认为这很不公平,所以她准备抢先一步回家。晚饭后,unicornFairy来到了一处没有监控的围墙旁。小马将援助unicorn......
  • BLE Audio显示连接成功,但没有音乐播放问题解决方案
    背景最近一直在搞这个问题,和原厂一起分析,背景可以参考前面的文章https://blog.csdn.net/Jzj1234555/article/details/142518444?spm=1001.2014.3001.5501https://blog.csdn.net/Jzj1234555/article/details/142595444?spm=1001.2014.3001.5501解决方案今天原厂承认了他......
  • P5165 xtq的棋盘 题解
    这个题也可以用矩阵加速解决。先考虑70pts的做法,我们设\(f_i\)为从\(i\)位置到达\(0\)的期望步数,并尝试用\(f_n\)表示出所有\(f_i\)并利用\(f_0\)解出\(f_n\)然后回带即可。具体地,设\(f_i=a\timesf_n+b\),\(f_{i-1}=c\timesf_n+d\),则由于:\[f_i=pr......
  • Codeforces Round 975 (Div. 2) 题解:D、E
    第一次进前50,上分最爽的一次D.Speedbreaker对\(a\)按照时间升序排序,不难发现,对于升序排序后的数组,当我们搜到时间\(t\)时,记录已经搜过的时间对应原城市编号最小值为\(l\),最大值为\(r\),则我们一定要在\(a_t\)时间之前走过所有\([l,r]\)之间的城市。则若\(r-l+1>a_t\)则无解,因......
  • [USACO22DEC] Breakdown P 题解
    T1[USACO22DEC]BreakdownP比较显然的一点是,一次加一条边/一次删一条边,显然转化,这是显然的一条套路。这题的\(K\le8\),很有意思的数据范围,然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑\(K\le4\)的情况,令\(\mathit{st}\)表示折半搜索中考虑的起点。维......
  • [NOIP2017 提高组] 奶酪 题解
    题目背景NOIP2017提高组D2T1题目描述现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为 z=0,奶酪的上表面为 z=h。现在,奶酪的下表面有一只小老鼠Jerry,......
  • 洛谷P1827 [USACO3.4] 美国血统 题解
    上题目:题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树,并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和......