CodeForces Gym 100213F Counterfeit Money

来源:https://www.cnblogs.com/ycx-akioi/archive/2020/02/13/CodeForces-Gym-100213F.html

"CodeForces Gym題目頁面傳送門" 有$1$個$n1\times m1$的字元矩陣$a$和$1$個$n2\times m2$的字元矩陣$b$,求$a,b$的最大公共子矩陣。輸出這個最大公共子矩陣的行數、列數和左上角分別在$a,b$中的坐標。若無解,輸出$``\text{0 0''}$。若 ...


CodeForces Gym題目頁面傳送門

\(1\)\(n1\times m1\)的字元矩陣\(a\)\(1\)\(n2\times m2\)的字元矩陣\(b\),求\(a,b\)的最大公共子矩陣。輸出這個最大公共子矩陣的行數、列數和左上角分別在\(a,b\)中的坐標。若無解,輸出\(\texttt{0 0}\)。若有多解,輸出任意一組。

\(n1,m1,n2,m2\in[1,40]\)

如果你還不知道Gym是什麼,please點擊這個

(以下假設\(n1,m1,n2,m2\)同階,在複雜度里用\(n\)表示)

這是一個二維的字元串匹配問題。而我們只熟悉一維的字元串匹配演算法,所以不妨先將\(2\)個字元矩陣一行行橫著一維處理,然後再將橫著一維處理所得的結果豎著一維合併。

先是橫著一維處理。考慮求出\(lcP\)四維數組,其中\(lcP_{i,j,k,o}\)表示從\(a\)中的\((i,j)\)\(b\)中的\((k,o)\)開始最多能向右延申多少個字元使得覆蓋的字元串相等,即\(lcP_{i,j,k,o}=\max\limits_{a_{i,j\sim j+p-1}=b_{k,o\sim o+p-1}}\{p\}\)。這個用Z演算法就可以輕鬆解決。顯然\(lcP_{i,j,k,o}=z_{a_{i,j\sim m1}+\texttt{!}+b_{k},m1-j+2+o}\)。這樣只需要對\(\forall i\in[1,n1],\forall j\in[1,m1],\forall k\in[1,n2],a_{i,j\sim m1}+\texttt{!}+b_{k}\)\(\mathrm O\left(n^3\right)\)個長度為\(\mathrm O(n)\)的字元串跑Z演算法即可,時間複雜度\(\mathrm O\left(n^4\right)\)

然後考慮如何豎著一維合併。考慮枚舉子矩陣在\(a\)中的坐標\((x1,y1)\)、在\(b\)中的坐標\((x2,y2)\),再枚舉子矩陣的行數\(n'\),給它乘上能使得子矩陣在\(a,b\)中相等的最大列數\(m'\)並更新答案。顯然,要滿足子矩陣在\(a,b\)中匹配,就要滿足在每行都匹配,即\(\forall i\in\left[1,n'\right],m'\leq lcP_{x1+i-1,y1,x2+i-1,y2}\)。那麼\(m'_{\max}=\min\limits_{i=1}^{n'}\left\{lcP_{x1+i-1,y1,x2+i-1,y2}\right\}\)。這樣在\(x1,y1,x2,y2\)固定時可以遞推求出\(m'_{\max}\),時間複雜度\(\operatorname O\left(n^5\right)\)

\(\mathrm O\left(n^5\right)\)有可能能過得去,但我是追求完美的OIer,當然不滿足於這樣卡著時限的複雜度。考慮將一些情況一併處理。不難發現在\(x1,y1,x2,y2\)固定時,\(a\)中的每個字元都唯一對應\(b\)中的\(1\)個字元(有可能越界),而對於\(2\)對左上角\(((x1_1,y1_1),(x2_1,y2_1)),((x1_2,y1_2),(x2_2,y2_2))\),若\(y1_1=y1_2,y2_1=y2_2,x1_1-x2_1=x1_2-x2_2\),則它們的字元對應情況是相等的,我們就可以把它們一起處理。這樣,將可以一起處理的左上角對分到一組,就會有\(\mathrm O\left(n^3\right)\)組,對每一組分別處理。

由於每一組中左上角所在列固定,即對於每一行,從第幾個字元開始匹配是固定的,那麼對於每一組的處理可以看作這樣一個問題:給定一個數列\(s\),求\(\max\limits_{i=1}^{|s|}\left\{\max\limits_{j=i}^{|s|}\left\{(j-i+1)\min\limits_{k=i}^j\{s_k\}\right\}\right\}\),其中\(s_i=lcP_{i,y1,i+x2-x1,y2}\)。考慮到\(\min\limits_{k=i}^j\{s_k\}\)一定等於\(s_{i\sim j}\)中的某一個元素,不妨枚舉這個元素\(s_i\),求出它最多能往左/右延申到哪裡,使得它保持最小值的身份,即設往左、右分別最多能能延申到\(up_i,dwn_i\),那麼\(\forall j\in[up_i,dwn_i],s_j\geq s_i\),此時用\((dwn_i-up_i+1)s_i\)更新答案。

現在討論怎麼求\(up,dwn\)。以\(up\)為例,假設\(j<k\)\(s_j\geq s_k\),如果\(s_k<s_i\),那麼阻止\(i\)往左延申的那個元素肯定在\(k\)處或右邊,不可能是\(j\);否則\(s_k\geq s_i\),結合\(s_j\geq s_k\)可以得到\(s_j\geq s_i\)\(j\)也不可能阻止\(i\)往左延申。根據這個性質,我們可以維護一個從底到頂嚴格單調遞增的單調棧,阻止\(i\)往左延申的元素只可能在棧內。維護單調棧顯然是\(\mathrm O(|s|)\)的。\(\forall i\in[1,|s|]\),可以在單調棧內二分找到阻止\(i\)往左延申的元素,這樣一組中求\(up\)的時間複雜度為\(\mathrm O(|s|\log_2|s|)\)。然而其實根本不用二分,因為我們要找的是棧中最上面的\(j\)使得\(s_j<s_i\),而在將\(i\)入棧之前維護棧頂單調性時將所有棧頂的滿足\(s_j\ge s_i\)\(j\)彈出了,剩下來的棧頂就是我們要找的了(如果棧為空,則沒有可以阻止\(i\)往左延申的元素,可以一直延伸到最左邊)。這樣每組求\(up\)複雜度\(\mathrm O(|s|)\)\(dwn\)類似,所以每組總複雜度\(\mathrm O(|s|)=\mathrm O(n)\)

一共\(\mathrm O\left(n^3\right)\)組,每組\(\mathrm O(n)\),總複雜度\(\mathrm O\left(n^4\right)\)我們要寫複雜度正確的演算法,不能像窩女朋友libra9z一樣寫個\(\mathrm O\left(n^6\right)\)演算法加剪枝水過去。。。

下麵貼代碼:(記得文件輸入輸出)

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int N=40;
int n1,m1,n2,m2;//2個字元矩陣大小 
char a[N+1][N+5],b[N+1][N+5];//2個字元矩陣 
int s;//c的長度 
char c[2*N+6];//臨時字元串 
void con(int x,int y,int z){//令c=a[x][y~m1]+'!'+b[z] 
    s=0;
    for(int i=y;i<=m1;i++)c[++s]=a[x][i];
    c[++s]='!';
    for(int i=1;i<=m2;i++)c[++s]=b[z][i];
}
int z[2*N+6];//c的z數組 
void z_init(){//對c跑Z演算法 
    int zl=0,zr=0;
    z[1]=s;
    for(int i=2;i<=s;i++)
        if(zr<i){
            z[i]=0;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            if(z[i])zl=i,zr=i+z[i]-1;
        }
        else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
        else{
            z[i]=zr-i+1;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            zl=i;zr=i+z[i]-1;
        }
}
int lcP[N+1][N+1][N+1][N+1];//lcP[i][j][k][o]表示從a中的(i,j)、b中的(k,o)開始最多能向右延申多少個字元使得覆蓋的字元串相等
int up[N],dwn[N];//從i開始最多能往左、右延伸到up[i],dwn[i] 
int stk[N],top;//單調棧 
int main(){
    freopen("money.in","r",stdin);freopen("money.out","w",stdout);
    cin>>n1>>m1;
    for(int i=1;i<=n1;i++)cin>>a[i]+1;
    cin>>n2>>m2;
    for(int i=1;i<=n2;i++)cin>>b[i]+1;
    for(int i=1;i<=n1;i++)for(int j=1;j<=m1;j++)for(int k=1;k<=n2;k++){//求lcP數組 
        con(i,j,k);
        z_init();
        for(int o=1;o<=m2;o++)lcP[i][j][k][o]=z[m1-j+1+1+o];
    }
//  for(int i=1;i<=n1;i++)for(int j=1;j<=m1;j++)for(int k=1;k<=n2;k++)for(int o=1;o<=m2;o++)
//      printf("lcP[(%d,%d)][(%d,%d)]=%d\n",i,j,k,o,lcP[i][j][k][o]);
    pair<int,pair<pair<int,int>,pair<pair<int,int>,pair<int,int> > > > ans;//答案(以大小為關鍵字比較) 
    ans.X=0; 
    for(int i=1;i<=m1;i++)/*y1*/for(int j=1;j<=m2;j++)/*y2*/for(int k=-min(n1,n2)+1;k<min(n1,n2);k++)/*x2-x1*/{//枚舉每組 
//      printf("i=%d j=%d k=%d:\n",i,j,k);
        vector<pair<int,int> > v;//數列s,越界不計入 
        for(int o=1;o<=n1;o++)if(1<=o+k&&o+k<=n2)/*判越界*/v.pb(mp(o,lcP[o][i][o+k][j]));
        //求up 
        top=0;//清空單調棧 
        for(int o=0;o<v.size();o++){
            while(top&&v[stk[top-1]].Y>=v[o].Y)top--;//維護棧頂單調性 
            up[o]=top?stk[top-1]+1:0;//棧頂為阻止o向左延伸的元素 
            stk[top++]=o;//將o入隊 
        }
        //求dwn 
        top=0;//清空單調棧
        for(int o=v.size()-1;~o;o--){
            while(top&&v[stk[top-1]].Y>=v[o].Y)top--;//維護棧頂單調性 
            dwn[o]=top?stk[top-1]-1:v.size()-1;//棧頂為阻止o向右延伸的元素 
            stk[top++]=o;//將o入隊
        }
//      for(int o=0;o<v.size();o++)printf("\tup[%d]=%d dwn[%d]=%d\n",o,up[o],o,dwn[o]);
        for(int o=0;o<v.size();o++){//枚舉最小值 
            int u=up[o],d=dwn[o];//左右邊界 
            ans=max(ans,mp((d-u+1)*v[o].Y,mp(mp(d-u+1,v[o].Y),mp(mp(v[u].X,i),mp(v[u].X+k,j)))));//更新答案 
        }
    }
//  cout<<ans.X<<"\n";
    if(ans.X==0)puts("0 0");
    else printf("%d %d\n%d %d\n%d %d",ans.Y.X.X,ans.Y.X.Y,ans.Y.Y.X.X,ans.Y.Y.X.Y,ans.Y.Y.Y.X,ans.Y.Y.Y.Y);
    return 0;
}

您的分享是我們最大的動力!

更多相關文章
  • 1.前提條件 1). 確保已經安裝需要的Python版本 2). 確保已經將Python的目錄加入到環境變數中 2. Python安裝包的幾種常用方式 1). pip安裝方式(正常線上安裝) 2). whl安裝方式(離線安裝),一般是.whl格式的包 3). 源碼安裝方式(離線安裝),tar.gz/ ...
  • 概念: 什麼是REST? REST是Representational State Transfer的縮寫。翻譯為"表現層狀態轉化",restful是一種介面設計風格,它不是一個協議,通常是基於HTTP協議的; 為什麼需要這麼一個風格呢? RESTful的重點之一就是統一的介面命名規則; 每個開發者可 ...
  • 請求限制 一些情況下我們可能需要對請求進行限制,比如僅允許POST,GET等... RequestMapping註解中提供了多個參數用於添加請求的限制條件 value 請求地址 path 請求地址 method 請求方法 headers 請求頭中必須包含指定欄位 params 必須包含某個請求參數 ...
  • 一.用字典映射代替switch case語句 if/else可以代替switch但是非常不合適。 用字典代替switch: day = 5 switcher = { 0:'Sunday', 1:'Monday', 2:'Tuesday' } day_name = switcher.get(day,' ...
  • 我一直想用 Python and Selenium 創建一個網頁爬蟲,但從來沒有實現它。 幾天前, 我決定嘗試一下,這聽起來可能是挺複雜的, 然而編寫代碼從 Unsplash 抓取一些美麗的圖片還是挺容易的。 PS:很多人在學習Python的過程中,往往因為遇問題解決不了或者沒好的教程從而導致自己放 ...
  • 作為非專業的python選手,或者非專業的爬蟲選手,即使我們有一些編程基礎,有時想通過代碼從網上獲取一些信息,也不能徒手就能做,需要借鑒一些成熟的方案、代碼。 ...
  • 前言 亂碼是我們在程式開發中經常碰到且讓人頭疼的一件事,尤其是我們在做javaweb開發,如果我們沒有清楚亂碼產生的原理,碰到亂碼問題了就容易摸不著頭腦,無從下手。 亂碼主要出現在兩部分,如下: 第一,瀏覽器通過表單提交到後臺,如果表單內容有中文,那麼後臺收到的數據可能會出現亂碼。 第二,後端伺服器 ...
  • 資源訪問介面 由於JDK提供的資源訪問類並不能很好的滿足底層資源的訪問需求,所以Spring設計了一個Resource介面。Spring框架使用Resource裝載各種資源,包括配置文件資源、國際化屬性文件資源等 Resource具體的實現類圖 Resource介面的主要方法 1. boolean ...
一周排行
  • 微信公眾號dotnet跨平臺2020年初做的一個關於中國.NET開發者調查收到了開發者近 1400 條回覆。這份調查報告涵蓋了開發者工具鏈的所有部分,包括編程語言、應用架構、應用伺服器、運行時平臺、框架技術、框架配置、IDE、.NET/.NET Core 發行版部署模式、構建工具和Kubernete... ...
  • Winform控制項的雙緩衝。控制項的雙緩衝屬性是隱藏的,可以通過反射改變其屬性值。 lv.GetType().GetProperty("DoubleBuffered", BindingFlags.Instance | BindingFlags.NonPublic).SetValue(lv, true, ...
  • 1. 需求 上圖這種包含多選(CheckBox)和單選(RadioButton)的菜單十分常見,可是在WPF中只提供了多選的MenuItem。順便一提,要使MenuItem可以多選,只需要將MenuItem的 屬性設置為True: 不知出於何種考慮,WPF沒有為MenuItem提供單選的功能。為了在 ...
  • gRPC的結構 在我們搭建gRPC通信系統之前,首先需要知道gRPC的結構組成。 首先,需要一個server(伺服器),它用來接收和處理請求,然後返迴響應。 既然有server,那麼肯定有client(客戶端),client的作用就是向server發送請求,具體就是生成一個請求,然後把它發送到ser ...
  • 區別 OpenId: Authentication :認證 Oauth: Aurhorize :授權 輸入賬號密碼,QQ確認輸入了正確的賬號密碼可以登錄 認證 下麵需要勾選的覆選框(獲取昵稱、頭像、性別) 授權 OpenID 當你需要訪問A網站的時候,A網站要求你輸入你的OpenId,即可跳轉到你的 ...
  • 前言 預計是通過三篇來將清楚asp.net core 3.x中的授權:1、基本概念介紹;2、asp.net core 3.x中授權的預設流程;3、擴展。 在完全沒有概念的情況下無論是看官方文檔還是源碼都暈乎乎的,希望本文能幫到你。不過我也是看源碼結合官方文檔看的,可能有些地方理解不對,所以只作為參考 ...
  • 簡介 基於生產者消費者模式,我們可以開發出線程安全的非同步消息隊列。 知識儲備 什麼是生產者消費者模式? 為了方便理解,我們暫時將它理解為垃圾的產生到結束的過程。 簡單來說,多住戶產生垃圾(生產者)將垃圾投遞到全小區唯一一個垃圾桶(單隊列),環衛將垃圾桶中的垃圾進行處理(消費者)。就是一個生產者消費者 ...
  • 很多時候,需要對類中的方法進行一些測試,來判斷是否能按要求輸出預期的結果。 C#提供了快速創建單元測試的方法,但單元測試不僅速度慢不方便,大量的單元測試還會拖慢項目的啟動速度。 所以決定自己搞個方便的測試用例。 控制台一句話調用。 測試用例.註冊並Print(EnumEx.Name); 結果畫面: ...
  • 常成員函數不能改變數據成員的值,例如定義坐標類Coordinate,成員函數changeX():void Coordinate::changeX(){ x = 10;}雖然changeX()沒有參數,但是它隱含一個參數——this指針:void Coordinate::changeX(Coordin... ...
  • 因為新冠肺炎疫情,診所還沒復工。這是在家用手機敲的,代碼顯示有問題。等復工以後在電腦上改,各位先湊和看吧。 支持向量機(Support Vector Machine, SVM)是一種基於統計學習的模式識別的分類方法,主要用於模式識別。所謂支持向量指的是在分割區域邊緣的訓練樣本點,機是指演算法。就是要找 ...
x