2020-2021:teams:die_java:front_page_summertrain1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain1 [2020/07/17 17:40] fyhssgss [训练结果] |
2020-2021:teams:die_java:front_page_summertrain1 [2020/10/17 22:58] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| === 题解 === | === 题解 === | ||
| - | 两个字符串的B函数如何比较大小呢？ | + | solve by wxg |
| + | \\ 两个字符串的B函数如何比较大小呢？ | ||
| 首先，他们的公共前缀字符串的B函数一定是一样的，第一个不一样的字母一定可以比出大小，如果最长公共前缀只包含一个字母，那么和前一个字母不同的串排名小，如果包含两个字母，那么和前一个字母相同的串排名小。 | 首先，他们的公共前缀字符串的B函数一定是一样的，第一个不一样的字母一定可以比出大小，如果最长公共前缀只包含一个字母，那么和前一个字母不同的串排名小，如果包含两个字母，那么和前一个字母相同的串排名小。 | ||
| 行 253: | 行 254: | ||
| 故变成： $$ | 故变成： $$ | ||
| - | 约束条件：x^TAx\leq1 | + | 约束条件：x^TAx=1 |
| \\ 目标函数：\{b^T·x\} | \\ 目标函数：\{b^T·x\} | ||
| $$ 考虑拉格朗日数乘法 $$ | $$ 考虑拉格朗日数乘法 $$ | ||
| 行 342: | 行 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> | ||
| 行 354: | 行 424: | ||
| === 题解 === | === 题解 === | ||
| - | solved by fyh hxm | + | 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显然就是无解。 | ||
| 行 446: | 行 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.1594978856.txt.gz · 最后更改: 2020/07/17 17:40 由 fyhssgss
