J.Ball(数学) 时间复杂度：$O(T)$ 题意 有一根水平放置且左端点位于$(0,0)$点的木棍，长度为$L$,在该木棍上选择一个支点进行旋转，请问其是否能经过给定的点$(x,y)$,如果能，则输出”Yes”并给出任意满足条件的支点横坐标$x’(x’ \in [1,L])$;如果不能，则输出”No”.
数据范围
$1 \le T \le 10^4$
$1 \le l \le 10^5,-10^5 \le x,y \le 10^5$
思路 签到模拟题，取两端点的极端情况，其实就是找点$(x,y)$是否在$a^2+b^2=l^2$和$(a-l)^2+b^2=l^2$的圆内，直接比较判断.
Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include<bits/stdc++.h> #define endl '\n' using i64 = long long; using namespace std; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t; cin >> t; while(t--){ i64 l, x, y; cin >> l >> x >> y; if (x * x + y * y <= l * l){ cout << "Yes" << endl; cout << "0" << endl; }else if((x - l) * (x - l) + y * y <= l * l){ cout << "Yes" << endl; cout << l << endl; }else cout << "No" << endl; } return 0; }
I.Fight Against the Monster(二分) 时间复杂度：$O(T \cdot \log_2 h)$ 题意 制造若干机器人来对抗怪兽，怪兽的初始血量为$h$，当怪兽的血量等于$0$或者低于$0$时，怪兽成功机器被打败。对于机器，我们有”战斗”和”创造”两种模式可选择：
战斗——每个机器可以降低怪兽的1滴血量，但同时该机器直接报废；
创造——在所有可用的机器中挑选$m$个机器用以新建$k$个机器，每个机器只有一次使用机会.
请问初始最少使用多少个机器可以成功击败怪兽？
数据范围
$1 \le T \le 2 \cdot 10^5$
$1 \le k \le m \le 10^6, 0 \le h \le 10^9$
思路 从贪心的角度出发，想要以最少的初始机器击败怪兽，应该事先最大程度地创造，直到无法生成后再统一攻击。
当$k = m$时，如果怪兽的血量$h$高于$m$时，我们只需要制造$m$个机器即可，每次均可以等量复制相同数量的可用机器，造成的伤害是无穷大的；如果怪兽血量$h$不超过$m$，那么根本无法进行”创造”操作，只能制作$h$台机器。故答案为$min(h,m)$.
当$k < m$时，我们考虑最大程度地”创造”机器，当起始值为$x$时，每次生成操作所消耗的可用机器数是$m-k$(包含新生成的),设最大生成次数为$cnt$，不可继续”创造”的条件是机器数严格小于$m$，即
所以最终的机器总数应为$x+cnt \times k$.
由于答案具有单调性，可以通过二分答案的方式求得，判定条件就是$x+cnt \times k \ge h$.
Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include<bits/stdc++.h> #define endl '\n' using i64 = long long; using namespace std; void solve(){ int m, k, h; cin >> m >> k >> h; if(h==0){ cout << "0" << endl; return; } if(m==k){ cout << min(h, m) << endl; return; } int l = 1, r = h, ans; auto check = [&](int x) -> bool { if (x < m) return x >= h; i64 cnt = (x - m) / (m - k) + 1; i64 res = x + cnt * k; return res >= h; }; while(l<=r){ int mid = l + r >> 1; if(check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } cout << ans << endl; } signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t; cin >> t; while(t--) solve(); return 0; }
K. Strings,Subsequences,Reversed Subsequences,Prefixes(动态规划，字符串哈希) 时间复杂度：$O(M)$ 题意 给定两个字符串$S$ 和 $T$, $S$ 的长度为 $N$ , $T$ 的长度为 $M$ ,请问有多少个不同的非空的字符串子序列满足 $T$ 是子序列的前缀且 $T$ 也是子序列的反串的前缀，对答案进行$10^9 + 7$取模.
数据范围
$1 \le N,M \le 10^6$
$S_i,T_i \in [a,z]$
前置思考 ：如何使用动态规划求解字符串 $S$ 中本质不同的子序列数量 设 $dp[i]$ 为前 $i$ 个字符的本质不同的子序列个数
——转移方程 : $dp_{i} = 2 \cdot dp_{i-1}-dp_{last_{s_i}-1}$ ，其中$last_{s_i}$表示当前字符 $s_i$ 上次出现的下标
Code: 1 2 3 4 5 6 7 for (int i = 1; i <= len; i++){ if (!last[s[i] - 'a' + 1]) dp[i] = 2 * dp[i - 1] + 1; else dp[i] = 2 * dp[i - 1] - dp[last[s[i] - 'a' + 1] - 1]; last[s[i] - 'a' + 1] = i; }
思路 要使得子序列及其反串的前缀恰为 $T$ ，可分为两种情况 :
Case1 前后缀在 $T$ 不交叉 eg: $S = adbc [xxxxx] colba$ ，$T=abc$ ,该字符串 $S$ 中前缀和后缀恰好匹配了 $T$ ,得到的子序列及其反串的前缀一定为 $abc$ ,满足条件的子序列数量恰为中间$[xxxxx]$的本质不同的子序列种类加上空字符串。
设$pre_last[i]$表示在$S$ 中正向第一次出现第$i$个字符的下标，$suf_last[i]$ 则表示反向，此时正向和反向遍历 $S$ ,维护 $T$ 每一位第一次出现的下标即可。显然，对 $i \in[ pre_last[M]+1, suf_last[M]-1 ]$ 进行动态规划求解该子串的不同子序列数量加一就是满足条件的数量，将其贡献加入答案。
Case2 前后缀在 $T$ 交叉 eg: 当 $T=fecddc$ 时，$T$ 本身就有潜质作为子序列，只需要找到子序列$fecddcef$即可，这时候并不需要找到完整的前后缀$fecddc$ ，只需要在找到前缀$fecddc$后找到相应的后缀$ef$ ，就能构造出不同的子序列，对答案产生贡献。
观察上述例子，不难发现，当$T$中找到有效的后缀回文串时，可以将回文串的前面视为$S$ 中需要寻找的后缀，然而，这个后缀出现的下标我们恰巧在$Case 1$中用$suf_last$ 数组维护过了！
Code： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 #include <bits/stdc++.h> #define endl '\n' using i64 = long long; using namespace std; const i64 p1 = 1e9 + 7, p2 = 1e9 + 9; const i64 base1 = 1313131, base2 = 233333; signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; string s, t; cin >> s >> t; s = " " + s, t = " " + t; vector<int> last_pre(m + 1, 1E9), last_suf(m + 2, 0); vector<i64> dp(n + 1); vector<int> last(30); // 当前字母在之前出现的最近下标 for (int i = 1, j = 1; i <= n && j <= m; i++, j++){ while (i <= n && s[i] != t[j]) i++; if (i == n + 1) break; last_pre[j] = i; } for (int i = n, j = 1; i && j <= m; i--, j++){ while (i && s[i] != t[j]) i--; if (i == 0) break; last_suf[j] = i; } //cout << last_pre[m] << ' ' << last_suf[m] << endl; i64 ans = 0; if(last_pre[m]<last_suf[m]){ for (int i = last_pre[m] + 1; i < last_suf[m]; i++){ if (!last[s[i] - 'a' + 1]) dp[i] = (2 * dp[i - 1] % p1 + 1) % p1; else dp[i] = (2 * dp[i - 1] % p1 - dp[last[s[i] - 'a' + 1] - 1] % p1 + p1) % p1; last[s[i] - 'a' + 1] = i; } ans = (dp[last_suf[m] - 1] + 1) % p1; //加上中间是空子序列 } //Hash判回文 vector<vector<i64>> Hash1(m + 1, vector<i64>(2)), Hash2(m + 1, vector<i64>(2)); vector<i64> pw1(m + 1), pw2(m + 1); pw1[0] = pw2[0] = 1; for (int i = 1; i <= m; i++){ Hash1[i][0] = (Hash1[i - 1][0] * base1 % p1 + (t[i] - 'a' + 1)) % p1; Hash1[i][1] = (Hash1[i - 1][1] * base2 % p2 + (t[i] - 'a' + 1)) % p2; Hash2[i][0] = (Hash2[i - 1][0] * base1 % p1 + (t[m - i + 1] - 'a' + 1)) % p1; Hash2[i][1] = (Hash2[i - 1][1] * base2 % p2 + (t[m - i + 1] - 'a' + 1)) % p2; pw1[i] = (pw1[i - 1] * base1) % p1; pw2[i] = (pw2[i - 1] * base2) % p2; } auto getHash1 = [&](int a, int b, int cnt) -> i64 // 正向哈希值 { if(cnt==0) return (Hash1[b][0] - Hash1[a - 1][0] * pw1[b - a + 1] % p1 + p1) % p1; else return (Hash1[b][1] - Hash1[a - 1][1] * pw2[b - a + 1] % p2 + p2) % p2; }; auto getHash2 = [&](int a, int b, int cnt) -> i64 // 逆向哈希值，a < b { if(cnt==0) return (Hash2[b][0] - Hash2[a - 1][0] * pw1[b - a + 1] % p1 + p1) % p1; else return (Hash2[b][1] - Hash2[a - 1][1] * pw2[b - a + 1] % p2 + p2) % p2; }; last_suf[0] = n + 1; for (int i = m; i; i--){ // 判断[i,m]是不是回文串 int len = m - i + 1; if (getHash1(i, m, 0) == getHash2(1, len, 0) && getHash1(i, m, 1) == getHash2(1, len, 1) && last_pre[m] < last_suf[i - 1]) ans = (ans + 1) % p1; } cout << ans << endl; return 0; }
微信
支付宝