Master of Both —— Trie的應用

来源:https://www.cnblogs.com/o2mouse/p/18209372
-Advertisement-
Play Games

前言 市面上關於認證授權的框架已經比較豐富了,大都是關於單體應用的認證授權,在分散式架構下,使用比較多的方案是--<應用網關>,網關里集中認證,將認證通過的請求再轉發給代理的服務,這種中心化的方式並不適用於微服務,這裡討論另一種方案--<認證中心>,利用jwt去中心化的特性,減輕認證中心的壓力,有理 ...


Trie 樹

所有在老鼠島上的老鼠都應該學習Trie樹!——偉大的吱嘎鼠

Trie樹,就是所有Oier們喜聞樂見的字元串的超級優化的數據結構!

已閱,狗屁不通。——吱嘎鼠

字典樹,顧名思義,是一顆很像字典的樹,將相同首碼的字元串合併在一起,當出現不同時就分支,成為這樣的樹。
Trie樹

在這樣的樹上,我們可以很快地完成關於首碼的問題。

Master of Both 題面

先看題面~

Hui-Bot教授是弦論和高級數據結構的大師,所以他提出了一個有趣的問題。給定一個僅由小寫英文字母組成的 \(n\) 字元串序列,當按字典順序比較字元串時,該序列中有多少個反轉?

作為Hui-Bot最出色的學生,普塔塔和佈達達分別掌握了高超的弦理論和先進的數據結構技能,他們輕鬆地一起解決了這個問題。然而,存在 \(q\) 個不同的平行宇宙,其中字母表中的字元並不按原始順序出現。

形式上,每個宇宙中的字母都是一個字元串,它是26小寫英文字母的排列,表示每個字元出現的順序。

當且僅當以下條件之一成立時,字元串 \(a\) 按字典順序小於字元串 \(b\)

\(a\)\(b\) 的首碼,但 \(a \ne b\)
在a和b不同的第一個位置,字元串a有一個字母在字母表中出現的時間早於b中對應的字母。
長度n的序列a中的反轉次數是滿足 $ 1 \le i \le j \le n$ 、 \(a_j < a_i\) 的有序對(i,j)的數量。

請幫助各個宇宙的普塔塔和佈達達解決問題。

輸入 $1 \le n \le 5 \cdot 10^5 $ , $ 1 \le q \le 5 \cdot 10^4 $

\(1 \le \lvert s_i \rvert \le 10^6\) \(\lvert si \rvert\) 的總和不大於 \(10 ^ 6\)

鼠的思路

這道題要看的是字元串,一個一個比較過去複雜度豈不是會爆炸awa
所以將所有對都記錄下來,看看其他時間的單詞表裡這個對是不是逆序的,用字典樹預處理就好啦!

ll trie[N][37], cnt = 0, sm[N], rel[37][37];
void insert(string s){
	int p = 0;
	for(auto c : s){
		int u = c - 'a' + 1;//為什麼要 + 1,那當然是因為有的壞字元串是別的字元串的首碼,所以要在後面加一個比 $a$ 字典序都小的東西
		if(!trie[p][u]) trie[p][u] = ++cnt;
		for(int j = 0; j <= 26; j++){//看看自己的“同事”,記錄對
			if(j == u)continue;
			rel[j][u] += sm[trie[p][j]];//有時候一個點會擠著很多字元串
		}
		sm[p = trie[p][u]] ++;//鏘鏘,統計一下
	}
}

接下來就是要統計了

while(q--){
		string s; cin >> s;
		ll ret = 0;
		for(int i = 0; i < 26; i++){
			ret += rel[s[i] - 'a' + 1][0];
			for(int j = 0; j < i; j++) ret += rel[s[i] - 'a' + 1][s[j] - 'a' + 1];
		}
		write(ret), putchar('\n');
	}

我知道你們想看什麼——AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
void write(T x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
template<class T>
inline T read(){
    T x = 0, f = 1;char ch = getchar();
    while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
template<class T> inline T read(T &x){ return x = read<ll>();}
int n, q;
const int N = 2e6 + 100;
ll trie[N][37], cnt = 0, sm[N], rel[37][37];
void insert(string s){
	int p = 0;
	for(auto c : s){
		int u = c - 'a' + 1;
		if(!trie[p][u]) trie[p][u] = ++cnt;
		for(int j = 0; j <= 26; j++){
			if(j == u)continue;
			rel[j][u] += sm[trie[p][j]];
		}
		sm[p = trie[p][u]] ++;
	}
}
int main(){
	read(n), read(q);
	for(int i = 1; i <= n; i++){
		string s; cin >> s;
		s += 'a' - 1; insert(s);
	}
	while(q--){
		string s; cin >> s;
		ll ret = 0;
		for(int i = 0; i < 26; i++){
			ret += rel[s[i] - 'a' + 1][0];
			for(int j = 0; j < i; j++) ret += rel[s[i] - 'a' + 1][s[j] - 'a' + 1];
		}
		write(ret), putchar('\n');
	}
}

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

-Advertisement-
Play Games
更多相關文章
  • Qt具有跨平臺的特性,即Qt數據結構與演算法庫本身跨平臺和編譯腳本(.pro)跨平臺。在同時具有Windows下和Linux開發的需求時,最好的建議是使用QtCreator來開發,雖然也可以使用其他的IDE配合CMake等方式,但使用QtCreator更加方便,並且操作環境完全一致。QtCreator ...
  • 使用Spring Boot開發API的時候,讀取請求參數是服務端編碼中最基本的一項操作,Spring Boot中也提供了多種機制來滿足不同的API設計要求。 接下來,就通過本文,為大家總結6種常用的請求參數讀取方式。如果你發現自己知道的不到6種,那麼趕緊來查漏補缺一下。如果你知道的不止6種,那麼告訴 ...
  • 亮數據,適合大模型數據準備的可視化高效率數據採集工具。 一、大模型訓練需要數據 大模型數據處理的流程,分為數據採集、數據清洗、數據評估和指令數據標註四個主要階段,而這些階段中最重要的就是數據採集階段,需要海量的數據才能讓大模型涌現智能。 訪問點擊: 亮數據加速數據採集。 數據採集 涉及多種數據源,包 ...
  • 相關參考 https://leejjon.medium.com/how-to-allow-cross-origin-requests-in-a-jax-rs-microservice-d2a6aa2df484 https://stackoverflow.com/questions/28065963/ ...
  • 配置 NGINX 和 NGINX Plus 作為 Web 伺服器 設置虛擬伺服器 在 NGINX Plus 配置文件中,必須包含至少一個 server 指令來定義一個虛擬伺服器。 當 NGINX Plus 處理請求時,首先選擇將服務於該請求的虛擬伺服器。 http { server { # 伺服器配 ...
  • title: Django與前端框架協作開發實戰:高效構建現代Web應用 date: 2024/5/22 20:07:47 updated: 2024/5/22 20:07:47 categories: 後端開發 tags: DjangoREST 前端框架 SSR渲染 SPA路由 SEO優化 組件庫 ...
  • 在使用Wrapper構建條件時,經常因為需要構建的條件過多需要寫半個多小時,還容易粗心寫錯欄位,所以就想搞個可以直接自動構建QueryWrapper的工具類。 ...
  • 今天使用Thinkphp5做非同步任務傳遞where參數時遇到一個問題: 有一段如下代碼: $where['jst.supplier'] = ['exp', Db::raw('>0 or jst.is_supplier=1')]; 在使用swoole做非同步任務時需要把where參數傳遞給非同步任務處理, ...
一周排行
    -Advertisement-
    Play Games
  • 一個自定義WPF窗體的解決方案,借鑒了呂毅老師的WPF製作高性能的透明背景的異形視窗一文,併在此基礎上增加了滑鼠穿透的功能。可以使得透明窗體的滑鼠事件穿透到下層,在下層窗體中響應。 ...
  • 在C#中使用RabbitMQ做個簡單的發送郵件小項目 前言 好久沒有做項目了,這次做一個發送郵件的小項目。發郵件是一個比較耗時的操作,之前在我的個人博客裡面回覆評論和友鏈申請是會通過發送郵件來通知對方的,不過當時只是簡單的進行了非同步操作。 那麼這次來使用RabbitMQ去統一發送郵件,我的想法是通過 ...
  • 當你使用Edge等瀏覽器或系統軟體播放媒體時,Windows控制中心就會出現相應的媒體信息以及控制播放的功能,如圖。 SMTC (SystemMediaTransportControls) 是一個Windows App SDK (舊為UWP) 中提供的一個API,用於與系統媒體交互。接入SMTC的好 ...
  • 最近在微軟商店,官方上架了新款Win11風格的WPF版UI框架【WPF Gallery Preview 1.0.0.0】,這款應用引入了前沿的Fluent Design UI設計,為用戶帶來全新的視覺體驗。 ...
  • 1.簡單使用實例 1.1 添加log4net.dll的引用。 在NuGet程式包中搜索log4net並添加,此次我所用版本為2.0.17。如下圖: 1.2 添加配置文件 右鍵項目,添加新建項,搜索選擇應用程式配置文件,命名為log4net.config,步驟如下圖: 1.2.1 log4net.co ...
  • 之前也分享過 Swashbuckle.AspNetCore 的使用,不過版本比較老了,本次演示用的示例版本為 .net core 8.0,從安裝使用開始,到根據命名空間分組顯示,十分的有用 ...
  • 在 Visual Studio 中,至少可以創建三種不同類型的類庫: 類庫(.NET Framework) 類庫(.NET 標準) 類庫 (.NET Core) 雖然第一種是我們多年來一直在使用的,但一直感到困惑的一個主要問題是何時使用 .NET Standard 和 .NET Core 類庫類型。 ...
  • WPF的按鈕提供了Template模板,可以通過修改Template模板中的內容對按鈕的樣式進行自定義。結合資源字典,可以將自定義資源在xaml視窗、自定義控制項或者整個App當中調用 ...
  • 實現了一個支持長短按得按鈕組件,單擊可以觸發Click事件,長按可以觸發LongPressed事件,長按鬆開時觸發LongClick事件。還可以和自定義外觀相結合,實現自定義的按鈕外形。 ...
  • 一、WTM是什麼 WalkingTec.Mvvm框架(簡稱WTM)最早開發與2013年,基於Asp.net MVC3 和 最早的Entity Framework, 當初主要是為瞭解決公司內部開發效率低,代碼風格不統一的問題。2017年9月,將代碼移植到了.Net Core上,併進行了深度優化和重構, ...