CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain1 [2020/07/17 15:28]
fyhssgss [训练结果]
+++ 2020-2021:teams:die_java:front_page_summertrain1 [2020/10/17 22:58] (当前版本)
fyhssgss
@@ 行 7: / 行 7: @@
   * 时间:''2020.7.12 12:00~17:00''
   * rank:''43/1116''
-  * 完成情况：''4/6/11''
+  * 完成情况：''4/6/10''
 ===== 题解 =====
-===== 题目名字 =====
+===== A.B-Suffix Array =====
 === 题意 ===
+定义一个字符串的 B 函数为字符串到相同长度非负整数序列的映射，第 $i$ 个整数表示字符串中在 $i$ 前面与 $i$ 字符相同的字符之间的最小距离，如果前面没有和自己一样的字符则记为 0。求每个后缀的 B 序列的排名。字符串只包含a，b两个字母
 === 题解 ===
+solve by wxg
+\\ 两个字符串的B函数如何比较大小呢？
-<code cpp>
+首先，他们的公共前缀字符串的B函数一定是一样的，第一个不一样的字母一定可以比出大小，如果最长公共前缀只包含一个字母，那么和前一个字母不同的串排名小，如果包含两个字母，那么和前一个字母相同的串排名小。
+只需要写一个 cmp 函数，用哈希求一下最长公共前缀，然后比一下，之后直接调用 sort 函数即可，注意 ab 和 ba 没有区别，所以我们比较的时候要把字符串首转化为字母相同的串。
+<hidden 代码>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#define ll long long
+#define ull unsigned long long
+using namespace std;
+int read()
+{
+	int k=0,f=1;char c=getchar();
+	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
+	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
+}
+int n,m,pos[2],head1[100055],v1[100055],v2[100055];
+int a[100055],b[100055],c[100055],sum[100055];
+ull pw[100055],hs[100055],hs2[100055];
+char s[100055];
+ull query1(int x,int l)
+{
+	return hs[x+l-1]-hs[x-1]*pw[l];
+}
+ull query2(int x,int l)
+{
+	return hs2[x+l-1]-hs2[x-1]*pw[l];
+}
+bool cmp(int i,int j)
+{
+	if(s[i]==s[j])
+	{
+		int mid,l=1,r=n-max(i,j)+1,res=0;
+		int len=r;
+		while(r>=l)
+		{
+			mid=l+r>>1;
+			if(query1(i,mid)==query1(j,mid))
+				res=mid,l=mid+1;
+			else r=mid-1;
+		}
+		if(len==res)
+		{
+			if(j>i) return 0;
+			else return 1;
+		}
+		else
+		{
+			if(sum[i+res-1]-sum[i-1]==0||sum[i+res-1]-sum[i-1]==res)
+			{
+				if(s[i+res-1]!=s[i+res]) return 1;
+				else return 0;
+			}
+			else
+			{
+				if(s[i+res-1]!=s[i+res]) return 0;
+				else return 1;
+			}
+		}
+	}
+	else
+	{
+		int mid,l=1,r=n-max(i,j)+1,res=0;
+		int len=r;
+		while(r>=l)
+		{
+			mid=l+r>>1;
+			if(query1(i,mid)==query2(j,mid))
+				res=mid,l=mid+1;
+			else r=mid-1;
+		}
+//		cout<<i<<" "<<j<<" "<<res<<endl;
+		if(len==res)
+		{
+			if(j>i) return 0;
+			else return 1;
+		}
+		else
+		{
+			if(sum[i+res-1]-sum[i-1]==0||sum[i+res-1]-sum[i-1]==res)
+			{
+				if(s[i+res-1]!=s[i+res]) return 1;
+				else return 0;
+			}
+			else
+			{
+				if(s[i+res-1]!=s[i+res]) return 0;
+				else return 1;
+			}
+		}
+	}
+}
+int main()
+{
+	pw[0]=1;
+	for(int i=1;i<=100000;i++)
+		pw[i]=pw[i-1]*31;
+	while(scanf("%d",&n)!=EOF)
+	{
+		scanf("%s",s+1);
+		for(int i=1;i<=n;i++)
+		{
+			c[i]=i;
+			a[i]=s[i]-'a',b[i]=a[i]^1;
+			sum[i]=sum[i-1]+a[i];
+			hs[i]=hs[i-1]*31+a[i];
+			hs2[i]=hs2[i-1]*31+b[i];
+		}
+		sort(c+1,c+1+n,cmp);
+//		cout<<query1(1,1)<<" "<<query2(2,1)<<" ";
+//		cout<<cmp(3,5)<<" ";
+		for(int i=1;i<=n;i++)
+			printf("%d ",c[i]);
+		puts("");
+	}
+	return 0;
+}
 </code>
+</hidden>
 ===== B.Infinite Tree =====
@@ 行 27: / 行 149: @@
 === 题解 ===
+补题byfyh
 题解都说要建一个虚树然后维护啥的，没用那么复杂的做法，方法跟cf#614div2的F有点像
@@ 行 38: / 行 162: @@
 然后开始考虑从1号节点出发走向哪里使得答案变小，设当前的区间为$[l,r]$，表示我当前点所维护阶乘所在的子树区间，那么每走一步其实就是在看$sum[l,r]和sum[1,l-1]+sum[r+1,n]$的大小关系决定改怎么走，总复杂度$O(nlogn)$
+<hidden 代码>
 <code cpp>
 #include<bits/stdc++.h>
@@ 行 104: / 行 229: @@
 }
 </code>
+</hidden>
 ===== D.Quadratic Form =====
@@ 行 115: / 行 241: @@
 === 题解 ===
+补题byfyh
 题目那个两个求和式子是一个二次型，写成这样的形式： $$
@@ 行 126: / 行 254: @@
 故变成： $$
-约束条件：x^TAx\leq1
+约束条件：x^TAx=1
 \\ 目标函数：\{b^T·x\}
 $$ 考虑拉格朗日数乘法 $$
@@ 行 149: / 行 277: @@
 $$ 求逆矩阵即可，复杂度$O(n^3)$
+<hidden 代码>
 <code cpp>
 #include<bits/stdc++.h>
@@ 行 216: / 行 345: @@
 }
 </code>
+</hidden>
+===== F.Infinite String Comparision =====
+=== 题意 ===
+将两个串无限循环，问是否相等
+=== 题解 ===
+solved by hxm
+容易发现，只需要判断最长串的两个周期内是否相等即可
+<hidden 代码>
+<code cpp>
+#include<algorithm>
+#include<iostream>
+#include<cstdlib>
+#include<cstring>
+#include<cstdio>
+#include<vector>
+#include<queue>
+#include<cmath>
+#include<map>
+#include<set>
+#define LL long long int
+#define REP(i,n) for (int i = 1; i <= (n); i++)
+#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
+#define cls(s,v) memset(s,v,sizeof(s))
+#define mp(a,b) make_pair<int,int>(a,b)
+#define cp pair<int,int>
+using namespace std;
+const int maxn = 300005,maxm = 100005,INF = 0x3f3f3f3f;
+inline int read(){
+	int out = 0,flag = 1; char c = getchar();
+	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
+	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
+	return flag ? out : -out;
+}
+char A[maxn],B[maxn];
+int n,m;
+int main(){
+	char *a,*b; int tag;
+	while (~scanf("%s%s",A + 1,B + 1)){
+		tag = 0;
+		n = strlen(A + 1);
+		m = strlen(B + 1);
+		if (n > m) a = A,b = B;
+		else a = B,b = A,swap(n,m),tag = 1;
+		for (int i = 1; i <= n; i++) a[n + i] = a[i];
+		for (int i = 1; i <= m; i++){
+			for (int j = 1; i + j * m <= 2 * n; j++) b[i + j * m] = b[i];
+		}
+		int flag = 0;
+		for (int i = 1; i <= (n << 1); i++){
+			if (a[i] != b[i]){
+				if (a[i] > b[i]) flag = 1;
+				else if (a[i] < b[i]) flag = -1;
+				break;
+			}
+		}
+		if (flag == -1) puts(tag ? ">" : "<");
+		else if (flag == 1) puts(tag ? "<" : ">");
+		else puts("=");
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== H.Minimum-cost Flow =====
@@ 行 224: / 行 423: @@
 === 题解 ===
+solve by fyh hxm
 先考虑无解的情况。$\lceil\frac{v_i}{u_i}\rceil>maxflow$是无解的，因为每一次都是流一次$\frac{u_i}{v_i}$，最多可以流$maxflow$次，如果$\frac{u_i}{v_i}*maxflow$还留不满1显然就是无解。
@@ 行 229: / 行 430: @@
 回忆最小费用最大流的做法，实质就是每次增广之前，在还剩余流量的弧跑最短路，沿着最短路增广，也就是前$k$次增广的费用其实就是前$k$次的最小费用，利用这个性质我们在算最小费用时把每次答案都记录下来即可。
+<hidden 代码>
 <code cpp>
 #include<iostream>
@@ 行 313: / 行 515: @@
 }
 </code>
-=====  =====
+</hidden>
+===== J.Easy Integration =====
+=== 题意 ===
+算 $\int^{1}_{0}{(x-x^2)^ndx}$
+=== 题解 ===
+分部积分即可推出答案为 $\frac{(n!)^2}{(2n+1)!}$
+<hidden 代码>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#define ll long long
+using namespace std;
+int read()
+{
+    int k=0,f=1;char c=getchar();
+    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
+    for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
+}
+const int N=2000005,M=1000000,mod=998244353;
+int n,frac[N];
+int ksm(int x,int k)
+{
+    int ans=1;
+    for(;k;k>>=1,x=1ll*x*x%mod)
+        if(k&1)
+            ans=1ll*ans*x%mod;
+    return ans;
+}
+int main()
+{
+    frac[1]=1;
+    for(int i=2;i<=M*2+1;i++)
+        frac[i]=1ll*i*frac[i-1]%mod;
+    while(scanf("%d",&n)!=EOF)
+    {
+        printf("%lld\n",1ll*frac[n]*frac[n]%mod*ksm(frac[2*n+1],mod-2)%mod);
+    }
+    return 0;
+}
+</code>
+</hidden>
 ===== 训练实况 =====

CVBB ACM Team

用户工具

站点工具

页面工具