2020-2021:teams:die_java:front_page_summertrain1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain1 [2020/07/17 15:33] fyhssgss |
2020-2021:teams:die_java:front_page_summertrain1 [2020/10/17 22:58] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| * 时间:''2020.7.12 12:00~17:00'' | * 时间:''2020.7.12 12:00~17:00'' | ||
| * rank:''43/1116'' | * 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> | </code> | ||
| + | </hidden> | ||
| ===== B.Infinite Tree ===== | ===== B.Infinite Tree ===== | ||
| 行 27: | 行 149: | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 补题byfyh | ||
| 题解都说要建一个虚树然后维护啥的，没用那么复杂的做法，方法跟cf#614div2的F有点像 | 题解都说要建一个虚树然后维护啥的，没用那么复杂的做法，方法跟cf#614div2的F有点像 | ||
| 行 117: | 行 241: | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 补题byfyh | ||
| 题目那个两个求和式子是一个二次型，写成这样的形式： $$ | 题目那个两个求和式子是一个二次型，写成这样的形式： $$ | ||
| 行 128: | 行 254: | ||
| 故变成： $$ | 故变成： $$ | ||
| - | 约束条件：x^TAx\leq1 | + | 约束条件：x^TAx=1 |
| \\ 目标函数：\{b^T·x\} | \\ 目标函数：\{b^T·x\} | ||
| $$ 考虑拉格朗日数乘法 $$ | $$ 考虑拉格朗日数乘法 $$ | ||
| 行 217: | 行 343: | ||
| } | } | ||
| return 0; | return 0; | ||
| + | } | ||
| + | </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> | </code> | ||
| 行 228: | 行 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显然就是无解。 | 先考虑无解的情况。$\lceil\frac{v_i}{u_i}\rceil>maxflow$是无解的，因为每一次都是流一次$\frac{u_i}{v_i}$，最多可以流$maxflow$次，如果$\frac{u_i}{v_i}*maxflow$还留不满1显然就是无解。 | ||
| 行 319: | 行 516: | ||
| </code> | </code> | ||
| </hidden> | </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> | ||
| ===== 训练实况 ===== | ===== 训练实况 ===== | ||
2020-2021/teams/die_java/front_page_summertrain1.1594971224.txt.gz · 最后更改: 2020/07/17 15:33 由 fyhssgss
