Press "Enter" to skip to content

2020牛客暑期多校训练营(第一场)

第一场

比赛总结

这是我们小队的第一次正式比赛(事实上在这之前我们一次模拟赛都没参加过)。这次比赛我贡献一道签到题(F),WA*2。开场我先读A发现读不懂转跳I,I的题意比较简单,我的第一个想法是贪心但是不敢写。然后刷新一下我看到了F题已经有人过了,然后我就看一下F题,我的第一个想法是通过暴力寻找最小循环节,但是hth说可能会T,所以我套了一个KMP的板子来判断循环节,然后就过了。中间我都不记得我们花了多久来强解J题?。在最后1个小时依靠着图论带师%%zfj,过了H题?。

F.Infinite String Comparision

题意

比较两个以a,b作为循环节的无限长字符串的字典序的大小。

解题思路

在比赛的时候这题我想通过寻找a,b,的最小循环节来对相等的情况进行特判。我们求最小循环节的方法是通过字符串的前缀函数π[i],设k=n−π[n−1],如果nmodk=0那么k就是最小循环节的长度,否则就不存在最小循环节,或者说它的最小循环节就是自身。

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int cmp(string& a,string& b)
{
    int na=a.length();
    int nb=b.length();
    if(a.compare(b)==0)return 0;
    int i,j;
    i=j=0;
    while (1)
    {
        if(a[i]>b[j])return 1;
        else if(a[i]<b[j])return -1;
        i++;
        j++;
        i%=na;
        j%=nb;
    }
 
}
vector<int> prefix_function(string& s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
int getnum(string &a)
{
    vector<int>pre;
    pre=prefix_function(a);
    if(a.length()%(a.length()-pre[a.length()-1])==0)return (a.length()-pre[a.length()-1]);
    else return a.length();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef DONLINE_JUDGE
 
    #endif
    string a,b;
    while (cin>>a>>b)
    {
        a=a.substr(0,getnum(a));
        b=b.substr(0,getnum(b));
        int x=cmp(a,b);
        if(x==0)cout<<"="<<endl;
        else if(x==1)cout<<">"<<endl;
        else cout<<"<"<<endl;
    }
    return 0;
}

J.Easy Integration

题意

这没有什么好说的,就是求一个定积分

解题思路

先matlab打表快速输出前100项,发现所有的分子都是1。
然后一顿操作猛如虎得出通项公式an=n!2(2n+1)!

好吧随便说一点把,数分中有一个叫做贝塔函数的东东
它长这样

$$B(p,q)=\int^1_0x^{p-1}(1-x)^{q-1}=\frac{(p-1)(q-1)}{(p+q-1)(p+q-2)}B(p-1,q-1)$$

如果你还是推不出来(其实单靠贝塔就能推出来了),那就隆重介绍一下贝塔的好朋友(不是舒克?)伽马函数

$$ \Gamma(s)=\int^{+\infty}_{0}x^{s-1}e^{-x}\ \Gamma(n+1)=n!\ B(p,q)=\frac{\Gamma(p)\Gamma(q)}{\Gamma(p+q)} $$

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)2e6+5;
const int MOD=998244353;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
ll s[MAXN];
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef DONLINE_JUDGE
 
    #endif
    s[1]=1;
    rep(i,2,2e6+2)s[i]=(s[i-1]*i)%MOD;
    ll n;
    while (cin>>n)
    {
        ll p =(s[n]*s[n])%MOD;
        ll q=s[2*n+1];
        q=powmod(q,MOD-2,MOD);
        cout<<p*q%MOD<<endl;
    }
    
    return 0;
}

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x