A題: Browser Games

原題鏈接:https://ac.nowcoder.com/acm/contest/11261/A

題目大意

本題的空間限制只有32MB，
有 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le 10^5) n(1≤n≤105) 個網頁游戲在接下來 n n n 天發布，每天發布一個，用戶必須用指定url打開才能玩游戲，url長度不超過 100 100 100 ，
但服務器設定有問題，一旦用戶以某種方式得到了未發布游戲的url，游戲資料就會泄露，為此決定每天在服務器端設定一組確認前綴，確認前綴是非空字串，當請求的url與游戲的url相同且至少有一個確認前綴是url的前綴時，服務器才會正確回應，否則將回傳未找到游戲，
求出每天所需的最少確認前綴數，

題解

根據題目描述，我們不難發現一個規律:時間越往后，已有的前綴只會變短，
我們可以標記每個前綴可用的時間段(區間修改采用差分的方式)，但顯然直接列舉是不行的，我們可以采取遞回:若我們需要查詢 1 1 1 ~ k k k 位前綴相同的字串，我們可以只在 1 1 1 ~ k ? 1 k-1 k?1 位已經相同的字串中查找，以減少復雜度，
我們初始可以記錄每個游戲發布的時間，然后根據字典序對url進行排序，那么若干位前綴相同的url肯定會構成一個區間，然后每次對于新的一位的相同情況再次劃磁區間(即分治思想)遞回即可(若有區間相同(如 1 1 1 ~ k k k 位均相同的都屬于同一個區間，則對 1 1 1 位相同， 1 1 1 ~ 2 2 2 位相同，…不重復進行差磁區間修改)的適用前綴則去重)，
詳見代碼注釋(注意區間為左閉右開)

參考代碼

#include<bits/stdc++.h>
#define For(i,n,m) for(int i=n;i<=m;i++)
#define FOR(i,n,m) for(int i=n;i>=m;i--)
#define ss(s) scanf(" %s",s)
using namespace std;
void read(int &x){
	int ret=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))ret=ret*10+c-'0',c=getchar();
	 x=last=='-'?-ret:ret;
}

const int MAXN=1e5+5,MAXM=1e2+5;
int n,date[MAXN],ans[MAXN];
char s[MAXN][MAXM];

bool cmp(int a,int b){return strcmp(s[a]+1,s[b]+1)<0;}//字串字典序比較

void solve(int l,int r,int end,int k){//[l,r)表示在date表中查詢的范圍,end表示l~r區間中前k-1位相同的最遲date+1(即差分結束位)
	if(l==r)return;//遞回邊界回傳
	int maxn=0;//maxn存盤1~k位相同的最遲date(相同前綴的字串只有全部出現之后,這個前綴才能使用)
	for(int i=l,last=l;i<=r;i++){//last記錄當前第k位相同的字串的區間起始位
		maxn=max(maxn,date[i]);//記錄最遲date(注意如果1 ~ k位前綴相同和1 ~ k-1位前綴相同的區間相同,則maxn最侄訓與end相等,即最終i=r差分修改時會在同一位加減(相當于沒有修改),實作自動去重)
		if(i==r||s[date[i]][k]!=s[date[i+1]][k]){//若前綴發生改變(注意i=r也是前綴改變,因為區間[l,r)右開,date[l ~ r-1]與date[r]的1 ~ k-1前綴已經不同)
			ans[maxn]++,ans[end]--;//差分處理(右開區間,差分結束位用end即可)
			solve(last,i,maxn,k+1);//對[last,i)區間繼續遞回,差分結束位為maxn(maxn已經歸入上一行代碼的差磁區間中了)
			last=i+1,maxn=0;//新區間的起始位last為i+1,重置maxn
		}
	}
}

int main()
{
	read(n);
	For(i,1,n){
		ss(s[i]+1);//讀入下標從1開始
		date[i]=i;//標記日期
	}
	sort(date+1,date+n+1,cmp);//根據字串字典序對date進行排序(排序的目的是使得相似(字典序相近)的字串的date可以靠的更近(構成區間))
	solve(1,n+1,n+1,1);//solve區間[1,n+1),即[1,n]
	For(i,2,n)ans[i]+=ans[i-1];//差分跑出前綴和
	For(i,1,n)printf("%d\n",ans[i]);
	return 0;
}