差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:die_java:front_page_springtraining5 [2020/05/15 22:25]
fyhssgss update
+++ 2020-2021:teams:die_java:front_page_springtraining5 [2020/05/23 12:10] (当前版本)
fyhssgss [训练详情]
@@ 行 3: / 行 3: @@
 [[https://vjudge.net/contest/373163|比赛网址]]
-===== 训练结果 =====
+===== 训练详情 =====
+  * 时间:2020-5-10 13:00~18:00
-  * rank:算了这个别说了
+  * rank:
-  * 完成情况：3/6/13
+  * 完成情况：''%%3/6/13%%''
 ===== 题解 =====
@@ 行 13: / 行 13: @@
 补题
-==== 题意 ====
+=== 题意 ===
 给了一个序列，要求实现两种操作
@@ 行 22: / 行 22: @@
 === 题解 ===
-开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $a[1...i]$ 的线性基，添加时候则从高位到低位，尽量用当前的基去替换之前的基，这样能使所有的基离r更近。查询的时候只用位置大于 $l$ 的基。
+开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $a[1... i]$ 的线性基，添加时候则从高位到低位，尽量用当前的基去替换之前的基，这样能使所有的基离r更近。查询的时候只用位置大于 $l$ 的基。
+\\
+<hidden B>
 <code cpp>
 #include<iostream>
@@ 行 109: / 行 111: @@
 }
 </code>
+</hidden>
+\\
 ===== D Vacation =====
 solved by wxg
@@ 行 119: / 行 123: @@
 可以想象，最后几辆车一定是贴在一起通过的，我们只需要枚举 $x$ ，计算最后 $x$ 俩车贴贴后通过时间，取一个最大值即可。
+\\
+<hidden D>
 <code cpp>
 #include<iostream>
@@ 行 155: / 行 160: @@
 }
 </code>
+</hidden>
+\\
 ===== E Path =====
@@ 行 166: / 行 173: @@
 求出最短路径的新图，可以看出答案为最小割
+\\
+<hidden E>
 <code cpp>
 #include<iostream>
@@ 行 301: / 行 310: @@
 }
 </code>
+</hidden>
+\\
 ===== F Typewriter =====
 solved by wxg
-### 题意
+=== 题意 ===
 给了一个字符串，你现在要花最小代价构造出该字符串，有两种构造方法
-. 花 $p$ 代价在当前字符串后添加一个字符。
+  - 花 $p$ 代价在当前字符串后添加一个字符。
-. 花 $q$ 代价在当前字符串后添加一个当前字符串的字串
+  - 花 $q$ 代价在当前字符串后添加一个当前字符串的字串
-#### 题解
+=== 题解 ===
 dp ，$dp[i]$ 表示构造出长度 $i$ 的字符串的最小代价，有两种转移
-. $dp[i]=dp[i-1]+p$
+  - $dp[i]=dp[i-1]+p$
-. $dp[i]=dp[j]+q$  , $j$ 为满足 $s[1...j]$ 中存在 $s[j+1...i]$ 的子串
+  - $dp[i]=dp[j]+q$ , $j$ 为满足 $s[1... j]$ 中存在 $s[j+1... i]$ 的子串
 问题是 $j$ 怎么求？
 首先随着 $i$ 增加，$j$ 是单调的
-我们可以构建 $s[1...j]$ 的后缀自动机，当 dp 到 $i$ 时，我们在后缀自动机上匹配 $s[i]$ ,若匹配长度与 $j$ 的和大于等于 $i$ ,说明 $j$ 不用增加，反之则增加 $j$ 直到大于等于为止。
+我们可以构建 $s[1... j]$ 的后缀自动机，当 dp 到 $i$ 时，我们在后缀自动机上匹配 $s[i]$ ,若匹配长度与 $j$ 的和大于等于 $i$ ,说明 $j$ 不用增加，反之则增加 $j$ 直到大于等于为止。
+\\
-````cpp
+<hidden f>
+<code cpp>
 #include<iostream>
 #include<cstdio>
@@ 行 333: / 行 345: @@
 int read()
 {
-	int k=0,f=1;char c=getchar();
+    int k=0,f=1;char c=getchar();
-	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
+    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
-	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
+    for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
 }
 const int N=400055;
@@ 行 344: / 行 356: @@
 void init()
 {
-	for(int i=0;i<=tot;i++) memset(ch[i],0,sizeof(ch[i]));
+    for(int i=0;i<=tot;i++) memset(ch[i],0,sizeof(ch[i]));
-	last=tot=0;len[0]=0;link[0]=-1;
+    last=tot=0;len[0]=0;link[0]=-1;
 }
 void extend(int c)
 {
-	int cur=++tot,p=last;len[cur]=len[last]+1;size[cur]=1;
+    int cur=++tot,p=last;len[cur]=len[last]+1;size[cur]=1;
-	for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur;
+    for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur;
-	if(p==-1) link[cur]=0;
+    if(p==-1) link[cur]=0;
-	else
+    else
-	{
+    {
-		int q=ch[p][c];
+        int q=ch[p][c];
-		if(len[p]+1==len[q]) link[cur]=q;
+        if(len[p]+1==len[q]) link[cur]=q;
-		else
+        else
-		{
+        {
-			int clone=++tot;
+            int clone=++tot;
-			len[clone]=len[p]+1;
+            len[clone]=len[p]+1;
-			link[clone]=link[q];
+            link[clone]=link[q];
-			memcpy(ch[clone],ch[q],sizeof(ch[q]));
+            memcpy(ch[clone],ch[q],sizeof(ch[q]));
-			for(;p!=-1&&ch[p][c]==q;p=link[p])
+            for(;p!=-1&&ch[p][c]==q;p=link[p])
-				ch[p][c]=clone;
+                ch[p][c]=clone;
-			link[q]=clone;link[cur]=clone;
+            link[q]=clone;link[cur]=clone;
-		}
+        }
-	}
+    }
-	last=cur;
+    last=cur;
 }
 int get(int p,int c,int opt)
 {
-	if(ch[p][c])
+    if(ch[p][c])
-	{
+    {
-		p=ch[p][c];
+        p=ch[p][c];
-		if(opt==1) mxlen++;
+        if(opt==1) mxlen++;
-	}
+    }
-	else
+    else
-	{
+    {
-		while(p!=-1&&!ch[p][c])
+        while(p!=-1&&!ch[p][c])
-			p=link[p];
+            p=link[p];
-		if(p==-1) p=0,mxlen=0;
+        if(p==-1) p=0,mxlen=0;
-		else mxlen=len[p]+1,p=ch[p][c];
+        else mxlen=len[p]+1,p=ch[p][c];
-	}
+    }
-	if(opt) return mxlen;
+    if(opt) return mxlen;
-	return p;
+    return p;
 }
 int main()
 {
-	while(scanf("%s",s+1)!=EOF)
+    while(scanf("%s",s+1)!=EOF)
-	{
+    {
-		int l=strlen(s+1);
+        int l=strlen(s+1);
-		init();scanf("%d%d",&P,&Q);
+        init();scanf("%d%d",&P,&Q);
-		int inslen=0,pos=0;mxlen=0;
+        int inslen=0,pos=0;mxlen=0;
-		for(int i=1;i<=l;i++)
+        for(int i=1;i<=l;i++)
-		{
+        {
-			dp[i]=dp[i-1]+P;
+            dp[i]=dp[i-1]+P;
-			if(get(pos,s[i]-'a',1)+inslen>=i)
+            if(get(pos,s[i]-'a',1)+inslen>=i)
-			{
+            {
-				dp[i]=min(dp[i],dp[inslen]+Q);
+                dp[i]=min(dp[i],dp[inslen]+Q);
-				pos=get(pos,s[i]-'a',0);
+                pos=get(pos,s[i]-'a',0);
-			}
+            }
-			else
+            else
-			{
+            {
-				while(get(pos,s[i]-'a',1)+inslen<i)
+                while(get(pos,s[i]-'a',1)+inslen<i)
-				{
+                {
-					extend(s[++inslen]-'a');
+                    extend(s[++inslen]-'a');
-				}
+                }
-				pos=get(pos,s[i]-'a',0);
+                pos=get(pos,s[i]-'a',0);
-				if(inslen<i)
+                if(inslen<i)
-					dp[i]=min(dp[i],dp[inslen]+Q);
+                    dp[i]=min(dp[i],dp[inslen]+Q);
-			}
+            }
-//			cout<<inslen<<" "<<mxlen<<endl;
+//          cout<<inslen<<" "<<mxlen<<endl;
-		}
+        }
-		printf("%lld\n", dp[l]);
+        printf("%lld\n", dp[l]);
-	}
+    }
-	return 0;
+    return 0;
 }
-````
+</code>
+</hidden>
-## I String
+\\
+===== I String =====
 补题 by hxm
-==== 题意 ====
+=== 题意 ===
 给定一个只包含小写字母的字符串，要求选出一个长度为$K$的子序列，满足字典序最小，同时子序列中每个字母的出现次数都在一个各自给定的范围$[L,R]$内
@@ 行 431: / 行 445: @@
 然后就完了。【很不明白比赛是怎么没调出来，，】
+\\
-<code>
+<hidden I>
+<code cpp>
 #include<algorithm>
 #include<iostream>
@@ 行 519: / 行 534: @@
 }
 </code>
+</hidden>
+\\
 ===== K Function =====
 补题 by fyh
-==== 题意 ====
+=== 题意 ===
 $$
@@ 行 555: / 行 572: @@
 注意，读入要用%%__%%int128,但是在开数组的时候都要开int，否则会爆空间。
+\\
+<hidden K>
 <code cpp>
 #include<bits/stdc++.h>
@@ 行 639: / 行 658: @@
 </code>
+</hidden>
+\\
 ===== 训练实况 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具