2020 HDU Multi-University Training Contest 1

2020 HDU Multi-University Training Contest 1

文章目录

• 2020 HDU Multi-University Training Contest 1
• 过题
• 1004 Distinct Sub-palindromes
• 题意
• 思路
• 结论
• 代码

• 题意
• 思路
• 代码

• 题意
• 思路
• 代码

• 1006 Finding a MEX
• 1011 Minimum Index
• 题意
• 思路
• 代码

过题

1004 Distinct Sub-palindromes

链接：1004 Distinct Sub-palindromes

题意

• TTT 组输入

• 长度为 nnn 的字符串 sss，其中 sss 只包含小写字母；

• 求 sss 中不同的回文子串数量最少的串的个数。

思路

可见：当 n≥3n \\ge 3n≥3 时，sss 是以不同的3个小写字母作为循环节的串；当循环节确定时，剩余的 n−n/3n – n / 3n−n/3 个小写字母同时确定。

结论

当n<3n < 3n<3时，ans=pow(26,n)ans = pow(26, n)ans=pow(26,n);

当n≥3n \\ge 3n≥3时，ans=26∗25∗24ans = 26 * 25 * 24ans=26∗25∗24。

代码

#include <iostream>#include <algorithm>using namespace std;const long long MOD = 998244353;long long ksm(long long n, long long p, long long c){if (c == 1)return 0;long long ans = 1;long long thi = n % c;while (p){if (p & 1){ans = ans * thi % c;}p >>= 1;thi = thi * thi % c;}return ans;}int main(void){int t, n;cin >> t;while (t--){cin >> n;if (n <= 3)cout << ksm(26, n, MOD) << endl;elsecout << 26 * 25 * 24 << endl;}return 0;}

1005 Fibonacci Sum

链接：1005 Fibonacci Sum

作弊器

题意

• TTT组输入

• FibonacciFibonacciFibonacci 数列：F(0)=0F(1)=1,F(n)=F(n−1)+F(n−2)F(0) = 0 \\quad F(1) = 1 \\quad, F(n) = F(n – 1) + F(n – 2)F(0)=0F(1)=1,F(n)=F(n−1)+F(n−2)

• 给定 N,C,K(1≤N,C≤1018,1≤K≤105)N, C, K (1 ≤ N, C ≤ 10^{18},1 ≤ K ≤ 10^5)N,C,K(1≤N,C≤1018,1≤K≤105) ，求F0k+Fck+⋯+FnckF_0^k + F_c^k + \\dots + F_{nc}^kF0k​+Fck​+⋯+Fnck​

• 输出结果对 1e9+71e9 + 71e9+7 取模

思路

感觉榜就是被这题带歪的 应该是我数论太菜了

• FibonacciFibonacciFibonacci 通项：F(n)=15[(1+52)n−1−52)n]F(n) = \\dfrac{1}{\\sqrt{5}} [(\\dfrac{1 + \\sqrt{5}}{2})^n – \\dfrac{1 – \\sqrt{5}}{2})^n]F(n)=5​1​[(21+5​​)n−21−5​​)n]

• 二次剩余：x2≡5(mod1e9+7)x^2 \\equiv 5 (mod \\ 1e9 + 7)x2≡5(mod1e9+7)，的一个解 x=383008016x = 383008016x=383008016

• 对 F(n)F(n)F(n) 进行二项展开，合并同类项后预处理所有的二项式系数

• 每个 casecasecase 中使用快速幂处理 aira^{ir}air 与 birb^{ir}bir

代码

AC 变 TLE ？

#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;typedef long long ll;const int P = 1000000009;const int INV2 = 500000005;const int SQRT5 = 383008016;const int INVSQRT5 = 276601605;const int A = 691504013;const int INVA = 691504012;const int B = 308495997;const int N = 100005;ll n, c, K;ll fac[N], inv[N];ll pa[N], pb[N];inline void Pre(int n){fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i % P;inv[1] = 1;for (int i = 2; i <= n; i++)inv[i] = (P - P / i) * inv[P % i] % P;inv[0] = 1;for (int i = 1; i <= n; i++)inv[i] = inv[i] * inv[i - 1] % P;}inline ll C(int n, int m){return fac[n] * inv[m] % P * inv[n - m] % P;}// 计算组合数inline ll Pow(ll a, ll b){ll ret = 1;for (; b; b >>= 1, a = a * a % P)if (b & 1)ret = ret * a % P;return ret;}// 快速幂inline void Init(int n){pa[0] = 1;long long cA = Pow(A, c);long long cB = Pow(B, c);for (int i = 1; i <= n; i++)pa[i] = pa[i - 1] * cA % P;pb[0] = 1;for (int i = 1; i <= n; i++)pb[i] = pb[i - 1] * cB % P;}inline ll Inv(ll x){return Pow(x, P - 2);}// 费马小定理inline void Solve(){ll Ans = 0;for (int j = 0; j <= K; j++){ll t = pa[K - j] * pb[j] % P, tem;tem = t == 1 ? (n % P) : (t * (Pow(t, n) - 1 + P) % P * Inv(t - 1) % P);if (~j & 1)Ans += C(K, j) * tem % P, Ans %= P;elseAns += P - C(K, j) * tem % P, Ans %= P;}Ans = Ans * Pow(INVSQRT5, K) % P;printf(\"%lld\\n\", Ans);}inline void Add(int &u, int v) {u += v;if (u >= P) u -= P;}int main(){int T;Pre(100000);scanf(\"%d\", &T);while (T--){scanf(\"%lld%lld%lld\", &n, &c, &K);// Init(K);// Solve();// STD code below:int DD = (long long)Pow((long long)INVA * B % P, c) % P;int q = Pow(Pow(A, c), K);int n1 = (n + 1) % P;int n2 = (n + 1) % (P - 1);int Q = Pow(q, n2);int D = Pow(DD, n2);int ans = 0;for (int i = 0; i <= K; i++) {int cur = C(K, i);if (i & 1) cur = P - cur;if (q == 1) Add(ans, (long long)cur * n1 % P);else Add(ans, (long long)cur * (Q + P - 1) % P * Pow(q-1, P-2) % P);q = (long long)q * DD % P;Q = (long long)Q * D % P;}ans = ans * Pow(INVSQRT5, K) % P;printf(\"%lld\\n\", ans);}return 0;}

1009 Leading Robots

链接：1009 Leading Robots

题意

• TTT 组输入
• N(0<N≤50000)N(0 < N≤ 50000)N(0<N≤50000) 个加速度为 aaa，初始位置为 ppp 的机器人 $ (0 < p,a < 2^{31})$
• 求对于任意时刻ppp最大且唯一的机器人数

思路

• 按照 aaa 从小到大排序，aaa 相同则按 ppp 从小到大排序

• 单调栈维护所有 ppp 最大的机器人

• 显然，t=0t = 0t=0 时，p0p_0p0​最大的进栈；t→+∞t \\to + \\infint→+∞ 时，amaxa_{max}amax​ 必然成为 ppp 最大的机器人

• 机器人的位置满足 p(t)=12at2+p0p(t) = \\frac{1}{2} a t^2 + p_0p(t)=21​at2+p0​

• 若 robotirobot_iroboti​ 超过 robottoprobot_{top}robottop​，有：

  pi=ptopp_i = p_{top}pi​=ptop​, ai>atopa_i > a_{top}ai​>atop​

  ti=ttop=2⋅piait_i = t_{top} = \\sqrt{\\dfrac{2 \\cdot p_i}{a_i}}ti​=ttop​=ai​2⋅pi​​​

  如果 robotirobot_iroboti​ 追赶上 robottoprobot_{top}robottop​ 所需要的时间tit_iti​少于 robottoprobot_{top}robottop​ 追赶上前一个栈顶元素的时间ttopt_{top}ttop​，则 robottoprobot_{top}robottop​ 出栈。

代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 5e4 + 7;const double eps = 1e-12;int T;int n;int ans;struct Robot{long long acc;long long pos;double t;bool flg; // Check EqualRobot(){};Robot(long long a, long long p): acc(a), pos(p) {}bool operator < (const Robot& b){if (b.acc == acc)return pos < b.pos;return acc < b.acc;}bool operator == (const Robot& b){return (acc == b.acc && pos == b.pos);}}rbt[MAXN];stack<Robot> st;int main(void){// freopen(\"1009.in\", \"r\",stdin);// freopen(\"1009.out\", \"w\", stdout);scanf(\"%d\", &T);while (T--){scanf(\"%d\", &n);for (int i = 1; i <= n; ++i){scanf(\"%lld%lld\", &rbt[i].acc, &rbt[i].pos);rbt[i].t = 0;rbt[i].flg = true;}sort(rbt + 1, rbt + n + 1);for (int i = 1; i <= n; ++i){if (st.size() == 0){st.push(rbt[i]);continue;}if (rbt[i] == st.top()){st.top().flg = false;rbt[i].flg = false;rbt[i].t = st.top().t;st.push(rbt[i]);continue;}while (!st.empty()){Robot now = st.top();if (rbt[i].pos >= now.pos && rbt[i].acc >= now.acc){st.pop();continue;}long long dp = abs(rbt[i].pos - now.pos);long long da = abs(rbt[i].acc - now.acc);double t = sqrt((double)2 * dp / da);rbt[i].t = t;if (t <= now.t + eps)st.pop();else break;}st.push(rbt[i]);}ans = 0;while (!st.empty()){if (st.top().flg)ans++;st.pop();}printf(\"%d\\n\", ans);}return 0;}

补题

1006 Finding a MEX

链接：1006 Finding a MEX

1011 Minimum Index

链接：1011 Minimum Index

题意

• 在给定长度为 n(1≤n≤2e7)n \\ (1 \\le n \\le 2e7)n(1≤n≤2e7) 字符串 ttt 的每一个前缀字符串 t1…it_{1 \\dots i}t1…i​ 找到字典序最小的后缀子串 tj⋯it_{j \\cdots i}tj⋯i​，为 ans[i]ans[i]ans[i]
• 输出 (∑0≤i≤n−1ans[i]⋅1112i)mod  1e9+7(\\sum\\limits_{0 \\le i \\le n – 1} ans[i] \\cdot 1112^{i})\\mod \\ 1e9 + 7(0≤i≤n−1∑​ans[i]⋅1112i)mod1e9+7

思路

• LyndonLyndonLyndon 分解

  对与字符串t1…it_{1 \\dots i}t1…i​的每一个前缀子串的LyndonLyndonLyndon 串已知的情况，很好解决；

  字符比较	结论
  t[i]==t[i+1]t[i] == t[i + 1]t[i]==t[i+1]	t1…i+1t_{1 \\dots i + 1}t1…i+1​ 仍为 LyndonLyndonLyndon 串，ans[i+1]=ans[i]ans[i + 1] = ans[i]ans[i+1]=ans[i]
  t[i]<t[i+1]t[i] < t[i + 1]t[i]<t[i+1]	t1…i+1t_{1 \\dots i + 1}t1…i+1​ 仍为 LyndonLyndonLyndon 串， ans[i+1]=ans[i]ans[i + 1] = ans[i]ans[i+1]=ans[i]
  t[i]>t[i+1]t[i] > t[i + 1]t[i]>t[i+1]	t1…i+1t_{1 \\dots i + 1}t1…i+1​ 不为 LyndonLyndonLyndon 串， ans[i+1]=i+1ans[i + 1] = i + 1ans[i+1]=i+1

  显然，我们可以递推的求得每一个位置上的 ansansans，计算输出 sumsumsum 即可

代码

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e7 + 7;const int MOD = 1e9 + 7;int t;long long sum;struct LyndonWord{string str;int ans[MAXN];void lyndon(){int i = 0;ans[0] = 1;// Index Start from 0while (i < str.length()){int j = i;int k = i + 1;ans[k] = k + 1;while (k < str.length() && str[j] <= str[k]){if (str[j] == str[k]){ans[k] = ans[j] + k - j;j++;}else{j = i;ans[k] = i + 1;}k++;}while (i <= j){i += k - j;// Lyndon String Right Most Posans[k] = i + 1;}}}}lyn;int main(void){//	freopen(\"1011.in\", \"r\", stdin);//	freopen(\"1011.out\", \"w\", stdout);ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> t;while (t--){cin >> lyn.str;lyn.lyndon();long long tmp = 1;sum = 0;for (int i = 0; i < lyn.str.length(); ++i){sum += ((long long) lyn.ans[i] * tmp) % MOD; sum %= MOD;tmp *= 1112; tmp %= MOD;}cout << sum << endl;}}

1012 Mow

链接：1012 Mow