BZOJ2882: 工藝(尾碼數組)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/11/27/10029287.html
-Advertisement-
Play Games

題意 "題目鏈接" Sol 直接把序列複製一遍 尾碼數組即可 在前$N$個位置中取$rak$最小的輸出 cpp include using namespace std; const int MAXN = 1e6 + 10; inline int read() { char c = getchar() ...


題意

題目鏈接

Sol

直接把序列複製一遍

尾碼數組即可

在前\(N\)個位置中取\(rak\)最小的輸出

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, tax[MAXN], tp[MAXN], rak[MAXN], sa[MAXN], a[MAXN];
void Qsort() {
    for(int i = 0; i <= M; i++) tax[i] = 0;
    for(int i = 1; i <= N; i++) tax[rak[i]]++;
    for(int i = 1; i <= M; i++) tax[i] += tax[i - 1];
    for(int i = N; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
void SuffixSort() {
    for(int i = 1; i <= N; i++) tp[i] = i, rak[i] = a[i];
    Qsort();
    for(int w = 1, p; p < N; w <<= 1, M = p) {
        p = 0;
        for(int i = 1; i <= w; i++) tp[++p] = N - w + i;
        for(int i = 1; i <= N; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
        Qsort(); swap(tp, rak);
        rak[sa[1]] = p = 1;
        for(int i = 2; i <= N; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p; 
    }
}
int main() {
    M = N = read();
    for(int i = 1; i <= N; i++) a[i] = a[i + N] = read(); N <<= 1;  
    SuffixSort();
//  for(int i = 1; i <= N; i++) printf("%d ", rak[i]); 
    int mx; rak[mx = 0] = 1e9 + 10;
    for(int i = 1; i <= N / 2; i++) if(rak[i] < rak[mx]) mx = i; 
    for(int i = mx; i <= mx + N / 2 - 1; i++) printf("%d ", a[i]);
    return 0;
}
/*
4
2 2 1 2

10
10 9 8 7 1 6 5 4 3 2 

20
10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1
*/

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

-Advertisement-
Play Games
更多相關文章
  • 前面介紹的BigInteger只能表達任意整數,但不能表達小數,要想表達任意小數,還需專門的大小數類型BigDecimal。如果說設計BigInteger的目的是替代int和long類型,那麼設計BigDecimal的目的便是替代浮點型float和雙精度型double了。正如它的兄弟BigInteg ...
  • 1.列表定義: 列表由數據構成的有限序列,即按照一定的線性順序排列,排列而成的數據項的集合。 2.創建列表: 使用‘[ ]’括起來就已經創建了一個列表,例: 3.訪問列表中的值: 3.1 通過下標訪問列表中的值: 3.2 通過切片的方式,訪問多個列表值: 3.2.1 切片 格式:[start,end ...
  • 多線程 多個線程等待一個線程的一次性事件 背景:從多個線程訪問同一個std::future,也就是多個線程都在等待同一個線程的結果,這時怎麼處理。 辦法:由於std::future只能被調用一次get方法,也就是只能被某一個線程等待(同步)一次,不支持被多個線程等待。所以std::sharted_f ...
  • php timer.php 每500毫秒執行一次 ...
  • 1、什麼是進程 進程(Process)是電腦中的程式關於某數據集合上的一次運行活動,是系統進行資源分配和調度的基本單位,是操作系統結構的基礎。 同一個程式執行兩次,就會產生兩個進程 ## 進程調度演算法: 先來先服務 短作業優先 時間片輪轉法 多級反饋隊列 2、併發和並行 併發是偽並行,只是看起來是 ...
  • 1.閉包函數也叫匿名函數,一個沒有指定名稱的函數,一般會用在回調部分 2.閉包作為回調的基本使用, echo preg_replace_callback('~-([a-z])~', function ($match) { return strtoupper($match[1]); }, 'hello... ...
  • 1.進程: 進程(Process)是電腦中的程式關於某數據集合上的一次運行活動,是系統進行資源分配和調度的基本單位,是操作系統結構的基礎。在早期面向進程設計的電腦結構中,進程是程式的基本執行實體;在當代面向線程設計的電腦結構中,進程是線程的容器。程式是指令、數據及其組織形式的描述,進程是程式的 ...
  • 思路 首先肯定要樹形dp,一直沒想到怎麼用左偏樹。如果不斷彈出又不斷地合併複雜度不就太高了。瞄了眼題解才知道可以直接用大根樹。然後記錄出當前這棵左偏樹的大小(樹裡面所有點的薪水之和)以及點的個數。然後不斷的刪點。直到薪水滿足條件為止。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...