2020-2021:teams:wangzai_milk:20200709比赛记录
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200709比赛记录 [2020/07/11 18:17] zars19 创建 |
2020-2021:teams:wangzai_milk:20200709比赛记录 [2020/07/16 15:24] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest ====== | + | ====== 2019 Multi-University Training Contest 2 ====== |
| ===== 比赛情况 ===== | ===== 比赛情况 ===== | ||
| ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K ^L | | ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K ^L | | ||
| - | ^状态 |- |O |- |- |O |- |- |O |- |O |O |O | | + | ^状态 |- |O |- |- |O |- |- |O |Ø |O |O |O | |
| //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | ||
| 行 16: | 行 16: | ||
| ===== 题解 ===== | ===== 题解 ===== | ||
| + | ==== E - Everything Is Generated In Equal Probability ==== | ||
| + | |||
| + | 给一个伪代码，然后给出一个 $N(N\le3000)$ ，等概率的生成一个数 $n\in [1,N]$，再等概率生成 $n$ 的一个排列，让这个排列执行伪代码中的函数，问结果的期望是多少。 | ||
| + | |||
| + | 推，就硬推。考虑 $n$ 一定时，存在 ${ n \choose 2}$ 个逆序对，每个逆序对出现的概率为 $\frac 12$，按照上述函数每个逆序对对期望的贡献为:$\sum_{i=0}^\infty \frac 1{4^i}=\frac 43$，所以总的期望为 ${n \choose 2}\frac12\frac43=\frac{n(n-1)}3$。最后对每个 $n$ 乘 $\frac1N$再相加即可。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 3e5+5; | ||
| + | const ll M = 998244353; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; } | ||
| + | ll res[3005]; | ||
| + | void init() | ||
| + | { | ||
| + | int n = 3000; | ||
| + | ll inv3 = qpow(3,M-2); | ||
| + | rep(i,1,n){ | ||
| + | res[i] = i*(i-1)%M*inv3%M; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | init(); int n; | ||
| + | while(cin>>n){ | ||
| + | ll ans = 0; | ||
| + | rep(i,1,n){ | ||
| + | ans = (ans + res[i])%M; | ||
| + | } | ||
| + | ans = ans * qpow(n,M-2) % M; | ||
| + | cout<<ans<<endl; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> </hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== I - I Love Palindrome String ==== | ||
| + | |||
| + | 给一个字符串，对 $i\in [1,|S|]$ ，统计有多少子串满足长度为 $i$ 、自身是一个回文串，该子串的前半段也是个回文串。 | ||
| + | |||
| + | 回文自动机求出所有回文串，字符串哈希看是否前半部分等于后半部分。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 3e5+5; | ||
| + | const ull base = 19260817; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | ull hs[maxn],bs[maxn]; | ||
| + | char s[maxn];ll ans[maxn]; | ||
| + | inline ull HASH(int l,int r) {return hs[r] - hs[l-1]*bs[r-l+1];} | ||
| + | struct Palindromes_Automation | ||
| + | { | ||
| + | int last,n,sz,trans[maxn][26],fail[maxn],cnt[maxn],len[maxn],s[maxn],pos[maxn]; | ||
| + | char t[maxn]; | ||
| + | void init() | ||
| + | { | ||
| + | memset(trans,0,sizeof(trans)); | ||
| + | memset(cnt,0,sizeof(cnt)); | ||
| + | memset(len,0,sizeof(len)); | ||
| + | memset(ans,0,sizeof(ans)); | ||
| + | last=0,sz=1; | ||
| + | len[0] = 0,len[1] = -1; | ||
| + | fail[0] = 1,fail[1] = 0; | ||
| + | } | ||
| + | int get_fail(int x) {while(s[n]!=s[n-len[x]-1])x=fail[x];return x;} | ||
| + | void extend() | ||
| + | { | ||
| + | int fa = get_fail(last); | ||
| + | int c = s[n]; | ||
| + | if(!trans[fa][c]){ | ||
| + | len[++sz] = len[fa] + 2; | ||
| + | fail[sz] = trans[get_fail(fail[fa])][c]; | ||
| + | trans[fa][c] = sz; | ||
| + | } | ||
| + | last = trans[fa][c]; | ||
| + | cnt[last]++; | ||
| + | pos[last] = n; | ||
| + | } | ||
| + | void solve(char str[]) | ||
| + | { | ||
| + | memcpy(t,str,sizeof(t)); | ||
| + | int l = strlen(t+1); s[0] = 26; | ||
| + | rep(i,1,l) hs[i] = hs[i-1]*base + t[i]; | ||
| + | for(n=1;n<=l;n++){ | ||
| + | s[n] = t[n] - 'a'; | ||
| + | extend(); | ||
| + | } | ||
| + | per(i,sz,0) cnt[fail[i]] += cnt[i]; | ||
| + | rep(i,2,sz){ | ||
| + | int tmp = pos[i]; | ||
| + | if(len[i]%2==0){ | ||
| + | if(HASH(tmp-len[i]+1,tmp-len[i]/2)==HASH(tmp-len[i]/2+1,tmp)) ans[len[i]]+=cnt[i]; | ||
| + | }else{ | ||
| + | if(HASH(tmp-len[i]+1,tmp-len[i]/2)==HASH(tmp-len[i]/2,tmp)) ans[len[i]]+=cnt[i]; | ||
| + | } | ||
| + | } | ||
| + | rep(i,1,l){ | ||
| + | cout<<ans[i]; | ||
| + | if(i==l) cout<<endl; | ||
| + | else cout<<" "; | ||
| + | } | ||
| + | } | ||
| + | }pam; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | bs[0] = 1; rep(i,1,maxn-1) bs[i] = bs[i-1]*base; | ||
| + | while(cin>>s+1){ | ||
| + | pam.init(); | ||
| + | pam.solve(s); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| ===== replay ===== | ===== replay ===== | ||
2020-2021/teams/wangzai_milk/20200709比赛记录.1594462656.txt.gz · 最后更改: 2020/07/11 18:17 由 zars19
