经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 大数据/云/AI » 人工智能基础 » 查看文章
CF1535F String Distance
来源:cnblogs  作者:lty_ylzsx  时间:2024/4/23 21:33:11  对本文有异议

\(CF1535F\ \ String\ Distance\)

题意

\(n\) 个长度均为 \(len\) 的字符串 \(T_1,T_2,\dots T_n\),定义 \(f(a,b)\) 为将 \(a,b\) 排序后相等的最小排序次数,若无解则为 \(1337\)(这好像是个黑客用语)。求

\[\sum _{i=1}^{n}\sum _{j=i+1}^{n}f(T_i,T_j) \]

其中

\[n\times len \leq 2\times 10^5 \]

思路分析

按照神xrlong的思路模拟即可,%%%%%%

神说,两个 trie 树,二维偏序肆意维护就过了,不过他终于在我的无数发问下补充了一些细节%%%%%

首先发现 \(f\) 是个诈骗函数,其值只可能为 \(1,2,1337\),因为规定没有相同的串,字符集相同时最多对两个串都排一次序就完成了,所以我们计算 \(f=1,2\)\(1337\) 的数量即可。

总操作数显然为

\[kobe=\sum _{i=1}^{n}\sum _{j=i+1}^{n}1= \frac{n\times (n-1)}{2} \]


  • 故事的开始前,先学习一下 \(nb\) 的二维数点:

类似于二维前缀和,只不过我们没有那么大的空间和时间开销,还是一样的思路:

\[ans(x_1,x_2,y_1,y_2)= sum(x_1-1,y_1-1)+sum(x_2,y_2)-sum(x_1-1,y_2)-sum(x_2,y_1-1) \]

然后我们考虑记录每个 \(sum\)\(qx,qy,c.\ c\) 是该 \(sum\) 是应加上还是减去的贡献。然后排序,树状数组扫描线维护即可。

  1. q[++tot]={x1-1,y1-1,1};
  2. q[++tot]={x2,y2,1};
  3. q[++tot]={x1-1,y2,-1};
  4. q[++tot]={x2,y1-1,-1};
  5. sort(q+1,q+tot+1,[](Q a,Q b){return a.qx<b.qx;});
  6. for(int i=1,j=1;i<=tot;i++){
  7. for(;lty[j].x<=q[i].qx&&j<=n;j++)
  8. add(lty[j].y);
  9. ans+=query(q[i].qy)*q[i].c;
  10. }

(建议先做一下P2163园丁的烦恼)


\(sum(f=1337)\)

这个比较水,考虑对新读入的字符串桶排,然后塞到一个 \(trie\) 树里,那么从根节点到每个叶子的路径即为一个字符集,记录字符集的个数和一些乱七八糟的东西,然后肆意求出。

CODE
  1. //求sum(f=1337)
  2. int trk8[N][27],numk8;
  3. int c[30],cnt[N];
  4. vector<int>k8he;
  5. int belong[N];//标记叶子节点属于的字符集
  6. int NUM;//字符集个数
  7. vector<int >order[N];//按照字符集顺序遍历
  8. void jjdw(char str[],int id){
  9. int p=0;for(int i=1;i<=26;++i) c[i]=0;
  10. for(int i=0;i<len;++i) c[str[i]-'a'+1]++;//桶排序
  11. for(int u=1;u<=26;u++){
  12. if(c[u]){
  13. for(int i=1;i<=c[u];++i){
  14. if(!trk8[p][u]) trk8[p][u]=++numk8;
  15. p=trk8[p][u];
  16. }
  17. }
  18. }
  19. if(!cnt[p]){
  20. k8he.push_back(p);
  21. belong[p]=++NUM;
  22. }
  23. order[belong[p]].push_back(id);
  24. lty[id].bel=belong[p];
  25. cnt[p]++;
  26. }
  27. int calc_k8(){//这个计算很好理解
  28. int kk=0,k8sum=n;
  29. for(int i=0;i<k8he.size()-1;++i){
  30. int p=k8he[i];
  31. k8sum-=cnt[p];
  32. if(k8sum>0) kk+=cnt[p]*(k8sum);
  33. }
  34. return kk;
  35. }

\(sum(f=1)\)

这是本题精髓,考虑一个串,找出其中所有的极长不下降子串(这里不是最长,我被坑惨了),例如串 \(abcdcbdfa\) 中的极长串是 \(abcd,c,bdf,a\),对于每个子串,它会将把原串 \(s\) 分成一个前缀 \(s[1\dots l]\) 和后缀 \(s[r\dots len]\),如果存在一个串 \(t\),使得:

  • \(s\)\(t\) 属于同一字符集,\(belong[s]==belong[t]\).

  • \(s,t\) 的前缀和后缀相等,\(s[1\dots l]=t[1\dots l],s[r\dots len]=t[r\dots len]\)

此时 \(f(t,s)=1\)(这很显然,只将 \(t[l+1,r-1]\) 排序即可)

我们发现 \(\sum _{i=1}^{n}\sum _{j=i+1}^{n}f(T_i,T_j)\) 实际就是两两字符串的 \(f\),所以枚举每个字符串的每个极长不下降子串子串,求前缀和后缀和它分别相等的串的个数即可。

我们考虑对所有字符串正反建两遍 \(trie\),对叶子节点进行编号 \(1\)\(n\),那么每个串 \(s\) 就可以表示为一个二元组 \((x,y)\),其中 \(x\)\(s\) 在正 \(trie\) 上结束的叶子节点编号,\(y\) 同理。

我们发现:前缀相同的串在 \(trie\) 树上叶子节点的编号是连续的,考虑将前缀在正 \(trie\) 上跑,得到一个区间 \([l_1,r_1]\),再将后缀在反 \(trie\) 上跑,得到另一个区间 \([l_2,r_2]\),然后在矩形 \([l_1,r_1,l_2,r_2]\) 二维数点即可。直观地,对于 \(9\) 个字符串建出正 \(trie\),如下图:

\(trie\) 同理。

CODE
  1. void ins1(char str[],int id){//正trie
  2. int p=0;
  3. for(int i=0;i<len;++i){
  4. int u=str[i]-'a'+1;
  5. if(!trie1[p][u]) trie1[p][u]=++num1;
  6. p=trie1[p][u];
  7. }
  8. flag1[p]=1;
  9. ed1[id]=p;
  10. }
  11. void ins2(char str[],int id){//反trie
  12. int p=0;
  13. for(int i=len-1;i>=0;i--){
  14. int u=str[i]-'a'+1;
  15. if(!trie2[p][u]) trie2[p][u]=++num2;
  16. p=trie2[p][u];
  17. }
  18. flag2[p]=1;
  19. ed2[id]=p;
  20. }
  21. void dfs1(int x){
  22. if(flag1[x]){
  23. l1[x]=r1[x]=++Id1;return;//给叶子结点编号
  24. }
  25. for(int i=1;i<=26;++i){
  26. int y=trie1[x][i];
  27. if(y){
  28. dfs1(y);
  29. if(!l1[x]) l1[x]=l1[y];
  30. l1[x]=min(l1[x],l1[y]);
  31. r1[x]=max(r1[x],r1[y]);
  32. //求该节点覆盖区间
  33. }
  34. }
  35. }
  36. void dfs2(int x){
  37. if(flag2[x]){
  38. l2[x]=r2[x]=++Id2;return;
  39. }
  40. for(int i=1;i<=26;++i){
  41. int y=trie2[x][i];
  42. if(y){
  43. dfs2(y);
  44. if(!l2[x]) l2[x]=l2[y];
  45. l2[x]=min(l2[x],l2[y]);
  46. r2[x]=max(r2[x],r2[y]);
  47. }
  48. }
  49. }

其中还有不少坑人的sm细节:

  • 对于每个区间的计算,在线算的话单次 \(O(len)\),我们考虑离线所有要查询的 \(al,ar\),这里 \(s[al,ar]\) 是一个极长不下降子串,考虑每个串所有的 \(al\) 都在正 \(trie\) 的一条链上(\(ar\) 同理),然后就可以总复杂度 \(O(n\times len)\) 水过去了。

  • 我们要统计矩形 \([l_1,r_1,l_2,r_2]\) 内的点,这些点必须与当前串在同一字符集里,我们可以预处理出每个串所属的字符集,然后在数点的时候判断与当前字符集是否一致,也就是这样:

  1. for(int i=1,j=1;i<=tot;i++){
  2. for(;lty[j].x<=q[i].qx&&j<=n;j++){
  3. if(lty[j].bel==id)
  4. add(lty[j].y);
  5. }
  6. count1+=query(q[i].qy)*q[i].c;
  7. }

但是这样显然是 \(O(n^2)\) 的复杂度,狂 \(T\) 不止 \(\dots\)

这是xrlong让我打他的trie树清空做法,我看着眼前二百多行代码很是不舍,然后就出来一个跑飞快的优化

一个 \(nb\) 的优化,考虑将点集以字符集编号为第一关键字,横坐标第二关键字排序,这样可以去掉无用的遍历,也就是:

  1. sort(lty+1,lty+n+1,[](Node a,Node b){
  2. if(a.bel==b.bel) return a.x<b.x;
  3. return a.bel<b.bel;
  4. });//玄学优化(不玄学)
  5. for(int i=1;i<=n;i++){
  6. if(lty[i].bel!=lty[i-1].bel){
  7. ql[lty[i].bel]=i;
  8. qr[lty[i-1].bel]=i-1;
  9. //每段字符集对应的左右端点
  10. }
  11. }
  12. qr[lty[n].bel]=n;
  13. //......
  14. for(int id=1;id<=NUM;++id){
  15. //...
  16. for(int i=1,j=ql[id];i<=tot;++i){
  17. for(;lty[j].x<=q[i].qx&&j<=qr[id];++j) add(lty[j].y);
  18. count1+=query(q[i].qy)*q[i].c;
  19. }

这样就跑飞快了。

  • 考虑跑完一个字符集,进行清空,我们当然不能 \(O(n)\) 清空,那么:

你怎么加进去就怎么清空$\ \ \ \ \ \ \ \(——\)xrlong$

  1. int C[N],topc;
  2. void add(int x){
  3. C[++topc]=x;
  4. for(int i=x;i<=n;i+=lowbit(i)) tr[i]++;
  5. }
  6. void clear(){
  7. for(int x=1;x<=topc;x++){
  8. for(int i=C[x];i<=n;i+=lowbit(i)){
  9. if(!tr[i]) break;//剪个小枝
  10. tr[i]=0;
  11. }
  12. }
  13. topc=0;tot=0;
  14. }
  • 每个字符串前缀后缀都相同的串,显然也包括它自己,所以最后要减去算了多少遍自己,即极长不下降子串个数。

\(sum(f=2)\)

小学生问题。


差不多了,拜谢 \(xrlong\)

也就二百多行,我码量大一定是因为我每个函数都写了两遍,dfs1,dfs2,ins1,ins2...

\(AC\ \ Code\)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define k8 1337
  4. #define int long long
  5. #define read read()
  6. #define pt puts("")
  7. inline int read
  8. {
  9. int x=0,f=1;char c=getchar();
  10. while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
  11. while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
  12. return f*x;
  13. }
  14. void write(int x)
  15. {
  16. if(x<0) putchar('-'),x=-x;
  17. if(x>9) write(x/10);
  18. putchar(x%10+'0');
  19. return;
  20. }
  21. const int N = 2e5+10;
  22. int n;
  23. int ans;
  24. int len;
  25. char s[N];
  26. string T[N];
  27. int trie1[N][27],trie2[N][27];
  28. int l1[N],l2[N],r1[N],r2[N];//每个trie树上某节点覆盖的范围[l,r]
  29. int num1,num2;
  30. int Id1,Id2;//给叶子结点编号
  31. int ed1[N],ed2[N];//记录每个串结束的节点
  32. bool flag1[N],flag2[N];//标记为叶子节点
  33. struct Node{
  34. int x,y;
  35. int bel;//所属字符集
  36. }lty[N];
  37. void ins1(char str[],int id){//正trie
  38. int p=0;
  39. for(int i=0;i<len;++i){
  40. int u=str[i]-'a'+1;
  41. if(!trie1[p][u]) trie1[p][u]=++num1;
  42. p=trie1[p][u];
  43. }
  44. flag1[p]=1;
  45. ed1[id]=p;
  46. }
  47. void ins2(char str[],int id){//反trie
  48. int p=0;
  49. for(int i=len-1;i>=0;i--){
  50. int u=str[i]-'a'+1;
  51. if(!trie2[p][u]) trie2[p][u]=++num2;
  52. p=trie2[p][u];
  53. }
  54. flag2[p]=1;
  55. ed2[id]=p;
  56. }
  57. void dfs1(int x){
  58. if(flag1[x]){
  59. l1[x]=r1[x]=++Id1;return;//给叶子结点编号
  60. }
  61. for(int i=1;i<=26;++i){
  62. int y=trie1[x][i];
  63. if(y){
  64. dfs1(y);
  65. if(!l1[x]) l1[x]=l1[y];
  66. l1[x]=min(l1[x],l1[y]);
  67. r1[x]=max(r1[x],r1[y]);
  68. //求该节点覆盖区间
  69. }
  70. }
  71. }
  72. void dfs2(int x){
  73. if(flag2[x]){
  74. l2[x]=r2[x]=++Id2;return;
  75. }
  76. for(int i=1;i<=26;++i){
  77. int y=trie2[x][i];
  78. if(y){
  79. dfs2(y);
  80. if(!l2[x]) l2[x]=l2[y];
  81. l2[x]=min(l2[x],l2[y]);
  82. r2[x]=max(r2[x],r2[y]);
  83. }
  84. }
  85. }
  86. //求sum(f=1337)
  87. int trk8[N][27],numk8;
  88. int c[30],cnt[N];
  89. vector<int>k8he;
  90. int belong[N];//标记叶子节点属于的字符集
  91. int NUM;//字符集个数
  92. vector<int >order[N];//按照字符集顺序遍历
  93. void jjdw(char str[],int id){
  94. int p=0;for(int i=1;i<=26;++i) c[i]=0;
  95. for(int i=0;i<len;++i) c[str[i]-'a'+1]++;//桶排序
  96. for(int u=1;u<=26;u++){
  97. if(c[u]){
  98. for(int i=1;i<=c[u];++i){
  99. if(!trk8[p][u]) trk8[p][u]=++numk8;
  100. p=trk8[p][u];
  101. }
  102. }
  103. }
  104. if(!cnt[p]){
  105. k8he.push_back(p);
  106. belong[p]=++NUM;
  107. }
  108. order[belong[p]].push_back(id);
  109. lty[id].bel=belong[p];
  110. cnt[p]++;
  111. }
  112. int calc_k8(){//这个计算很好理解
  113. int kk=0,k8sum=n;
  114. for(int i=0;i<k8he.size()-1;++i){
  115. int p=k8he[i];
  116. k8sum-=cnt[p];
  117. if(k8sum>0) kk+=cnt[p]*(k8sum);
  118. }
  119. return kk;
  120. }
  121. int kobe;
  122. int L[N],R[N],top;
  123. int x_1[N<<2],x_2[N<<2],y_1[N<<2],y_2[N<<2];
  124. void search1(string a){//离线查询
  125. int p=0;
  126. for(int i=1,j=0;i<=top;++i){
  127. for(;j<L[i];j++){
  128. int u=a[j]-'a'+1;
  129. p=trie1[p][u];
  130. }
  131. x_1[i]=l1[p],x_2[i]=r1[p];
  132. }
  133. }
  134. void search2(string a){
  135. int p=0;
  136. for(int i=top,j=len-1;i;i--){
  137. for(;j>R[i];j--){
  138. int u=a[j]-'a'+1;
  139. p=trie2[p][u];
  140. }
  141. y_1[i]=l2[p],y_2[i]=r2[p];
  142. }
  143. }
  144. int tot;
  145. struct Q{
  146. int qx,qy,c;
  147. }q[N<<3];
  148. int tr[N];
  149. #define lowbit(i) (i&(-i))
  150. int C[N],topc;
  151. void add(int x){
  152. C[++topc]=x;
  153. for(int i=x;i<=n;i+=lowbit(i)) tr[i]++;
  154. }
  155. int query(int x){
  156. int res=0;
  157. for(int i=x;i;i-=lowbit(i)){
  158. res+=tr[i];
  159. }
  160. return res;
  161. }
  162. void clear(){
  163. for(int x=1;x<=topc;x++){
  164. for(int i=C[x];i<=n;i+=lowbit(i)){
  165. if(!tr[i]) break;
  166. tr[i]=0;
  167. }
  168. }
  169. topc=0;tot=0;
  170. }
  171. int ql[N],qr[N];
  172. signed main()
  173. {
  174. n=read;
  175. kobe=(n-1)*n/2;//总操作数
  176. for(int i=1;i<=n;++i){
  177. scanf(" %s",s);
  178. T[i]=string(s);
  179. if(!len) len=strlen(s);
  180. ins1(s,i);ins2(s,i);//正反建trie
  181. jjdw(s,i);
  182. }
  183. dfs1(0);dfs2(0);//编号
  184. int ck8=calc_k8();//1337的个数
  185. ans=k8*ck8;
  186. kobe-=ck8;
  187. if(!kobe){
  188. write(ans);return 0;
  189. }
  190. for(int i=1;i<=n;++i){
  191. lty[i].x=l1[ed1[i]];
  192. lty[i].y=l2[ed2[i]];
  193. }//每个串对应的坐标
  194. sort(lty+1,lty+n+1,[](Node a,Node b){
  195. if(a.bel==b.bel) return a.x<b.x;
  196. return a.bel<b.bel;
  197. });//玄学优化(不玄学)
  198. for(int i=1;i<=n;i++){
  199. if(lty[i].bel!=lty[i-1].bel){
  200. ql[lty[i].bel]=i;
  201. qr[lty[i-1].bel]=i-1;
  202. }
  203. }
  204. qr[lty[n].bel]=n;//处理每个字符集左右边界
  205. int al,ar;
  206. int count1=0;
  207. string a;
  208. int self=n;//减去重复
  209. for(int id=1;id<=NUM;++id){
  210. for(int i:order[id]){
  211. al=0;a=T[i];
  212. for(ar=1;ar<len;++ar){//统计每个极长子串
  213. if(a[ar]<a[ar-1]){
  214. L[++top]=al,R[top]=ar-1;//离线下来一遍求,否则会T
  215. al=ar;++self;
  216. }
  217. }
  218. ar--;
  219. L[++top]=al,R[top]=ar;
  220. search1(a);search2(a);
  221. for(int i=1;i<=top;++i){
  222. int x1=x_1[i],x2=x_2[i],y1=y_1[i],y2=y_2[i];
  223. q[++tot]={x1-1,y1-1,1};
  224. q[++tot]={x2,y2,1};
  225. q[++tot]={x1-1,y2,-1};
  226. q[++tot]={x2,y1-1,-1};
  227. }//离线二维数点
  228. top=0;
  229. }
  230. sort(q+1,q+tot+1,[](Q a,Q b){return a.qx<b.qx;});
  231. for(int i=1,j=ql[id];i<=tot;++i){
  232. for(;lty[j].x<=q[i].qx&&j<=qr[id];++j) add(lty[j].y);
  233. count1+=query(q[i].qy)*q[i].c;
  234. }
  235. clear();
  236. }
  237. count1-=self;
  238. ans+=count1;
  239. kobe-=count1;
  240. ans+=kobe*2;
  241. write(ans);
  242. return 0;
  243. }

唉,我是 \(fw\),感觉这个题真是我现在码力的极限了...

原文链接:https://www.cnblogs.com/lty-ylzsx/p/18151619

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号