网站制作收费标准,wordpress加载慢,小程序模板库,互联网优化是什么意思文章目录 写在最前面的复盘B-小天的魔法#xff08;贪心 模拟 双指针#xff09;C-小天的 Minecraft#xff08;概率#xff09;D-小天的子序列#xff08;预处理 排列组合#xff09;E-小天的贪吃蛇#xff08;模拟#xff09;F-小天的 AB#xff08;结论题#xff… 文章目录 写在最前面的复盘B-小天的魔法贪心 模拟 双指针C-小天的 Minecraft概率D-小天的子序列预处理 排列组合E-小天的贪吃蛇模拟F-小天的 AB结论题 写在最前面的复盘 出了ABCD犯的最大错误就是读假题ABE都读假了。赛后一想确实读题太急也没通过用例验证题意 C是一道简单概率题可能是高中数学考试填空第一题吧数学忘的太快概率这块练的也少好在最后推出来了 赛时却wa穿了D没想到正解用了暴力超时发现答案的数量远远低于询问的数量想用记忆化优化接着wa穿。每次读出一个错误就直接交然后继续wa还是太着急了很多代码的细节没有写好就想着交了。赛后看到正解将 O ( n 2 ) O(n^2) O(n2)的枚举优化到 O ( n ) O(n) O(n)的思路很值得学习 E O ( n ) O(n) O(n)找下一个不同字符的下标用set优化成 O ( l n g n ) O(lngn) O(lngn)也值得学习 F补题时wa穿对于我目前的实力还是略难了就算赛时能利用题目性质和数据范围推导出结论最后的代码实现也会漏掉很多细节因为要考虑很多边界和结论的性质。但总的来说推导结论的过程还是值得学习的
B-小天的魔法贪心 模拟 双指针
B-小天的魔法_牛客小白月赛83 (nowcoder.com)
用数组ab存储题目给定的两个序列并对其降序排序。用ij两个指针分别指向ab数组的第一个元素 贪心思路考虑使用 b j b_j bj之前是否要使用 a i a_i ai若 a i a_i ai ! 1则先使用 a i a_i ai再使用 b j b_j bj 证明使用次数相同时比较 a i ∗ b j a_i * b_j ai∗bj与 b j b j 1 b_j b_{j 1} bjbj1的大小。显然 a i a_i ai不为1时有以下关系 a i ∗ b j b j b j b j b j 1 a_i * b_j b_j b_j b_j b_{j1} ai∗bjbjbjbjbj1 显然使用两次b魔法造成的伤害小于等于先使用a再使用b证明完毕
注意若直接使用 b j b_j bj就能击败怪物则直接使用 b j b_j bj
#include bits/stdc.h
using namespace std;const int N 3e5 10;
int a[N], b[N];void solve()
{int n, m, x; cin n m x;for (int i 1; i n; i) cin a[i];for (int i 1; i m; i) cin b[i];sort(a 1, a n 1, greaterint()), sort(b 1, b n 1, greaterint());int i 1, j 1;int cur 0, cnt 0;while (j m){if (cur x) break;// 直接使用b[j]就能击败怪物if (j m cur b[j] x) cur b[j ], cnt ;// 当a[i] ! 1时贪心else if (i n a[i] ! 1) cnt 2, cur a[i ] * b[j ];else if (j m) cnt , cur b[j ];}if (cur x) cout cnt \n;else cout -1\n;
}int main()
{ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);solve();return 0;
}C-小天的 Minecraft概率
C-小天的 Minecraft_牛客小白月赛83 (nowcoder.com)
生成铜稿首先要12个铜粒其次需要一个工作台。工作台有三种情况铜、银、金 铜工作台需要4个铜粒银的需要4个银粒金的需要4个金粒 显然有三种情况能生成铜稿
12个铜粒铜工作台16个铜粒12个铜粒银工作台12个铜粒4个银粒12个铜粒金工作台12个铜粒4个金粒
假设事件发生的概率为p重复m次该事件发生n次p的概率为 C m n ∗ p n C_m^n * p^n Cmn∗pn p a p_a pa、 p b p_b pb、 p c p_c pc分别为掉落铜粒、银粒、金粒的概率那么以上三种情况的概率为 C 16 16 ∗ p a 16 C_{16}^{16} * p_a^{16} C1616∗pa16 C 16 12 ∗ p a 12 C 16 4 ∗ p b 4 C_{16}^{12} * p_a^{12} C_{16}^{4} * p_b^4 C1612∗pa12C164∗pb4 C 16 12 ∗ p a 12 C 16 4 ∗ p c 4 C_{16}^{12} * p_a^{12} C_{16}^{4} * p_c^4 C1612∗pa12C164∗pc4
将三种情况的概率相加即为答案代码丑陋看思路自己写就行
#include bits/stdc.h
using namespace std;void solve()
{int T; cin T;while (T --){double a, b, c; cin a b c;a / 16, b / 16, c / 16;double ans 1;double t 1;for (int i 0; i 12; i) t * a;for (int i 0; i 16; i) ans * a;double t1 1, t2 1, t3 1;for (int i 0; i 4; i) t1 * a, t2 * b, t3 * c;ans t * (t2 t3) * 4 * 5 * 7 * 13; // 4 * 5 * 7 * 13为C_16^4的值printf(%.12lf\n, ans);}
}int main()
{solve();return 0;
}D-小天的子序列预处理 排列组合
D-小天的子序列_牛客小白月赛83 (nowcoder.com)
假设以ch1为开头ch2为结尾的字符串长度为n那么满足条件的子序列数量为 C n − 2 l e n − 2 C_{n-2}^{len-2} Cn−2len−2 根据数据范围需要预处理组合数 C m n C_m^n Cmn1m 500, 1n500 模板为
for (int i 0; i N; i) c[i][0] 1;
for (int i 1; i N; i)for (int j 1; j i; j)c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % 998244353;接着就是找字符串中的满足条件子串以ch1为开头ch2为结尾且长度大于len 由于字符串最大长度为500直接暴力预处理字符串所有子串的情况 用cnt[26][26][500]保存所有子串的出现次数如cnt[0][3][2] 4表示整个字符串中以a(0 a - a)为开头以d(3 d - a)为结尾且长度为2的子串出现了4次
满足条件的子串为cnt[ch1][ch2][t]len t 500 对于每次的询问线性枚举t满足条件的子串出现次数并乘以组合数即可
注意组合数的预处理数组最好开LL
#include bits/stdc.h
using namespace std;const int mod9 998244353;
const int N 510;
long long cnt[30][30][N], c[N][N];void solve()
{int n; cin n;string s; cin s;s s;for (int i 0; i N; i) c[i][0] 1;for (int i 1; i N; i)for (int j 1; j i; j)c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % mod9;for (int i 1; i n; i)for (int j i 1; j n; j)cnt[s[i] - a][s[j] - a][j - i 1] ;int m; cin m; while (m --){long long ans 0;char x, y; cin x y;int len; cin len;for (int i len; i n; i)ans (ans c[i - 2][len - 2] * cnt[x - a][y - a][i]) % mod9;cout ans \n;}
}int main()
{ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);solve();return 0;
}E-小天的贪吃蛇模拟
E-小天的贪吃蛇_牛客小白月赛83 (nowcoder.com)
模拟蛇的轨迹将二维数组转换成一维字符串保存数组下标与字符串下标之间的映射关系同时用pos数组保存每个字符在字符串的出现位置下标。如pos[1]表示字符b (1 b - a)在数组中的下标这些下标用set存储即set pos[26]
对于修改操作将二维坐标转换成字符串的下标并修改字符串同时维护pos数组 对于询问操作也是将二维坐标转换成字符串的下标并且获取该下标对应字符。此时在其他字符的出现位置中找出大于等于lower_bound该下标的最小下标两下标之间的距离为答案
#include bits/stdc.h
using namespace std;typedef pairint, int PII;
typedef long long LL;
typedef unsigned long long ULL;
const int inf 2e9 10;
const LL INF 4e18 10;
const int mod9 998244353;
const int mod7 1e9 7;
const int N 3e5 10;
int n, m;
setint pos1[30], pos2[30];void solve()
{cin n m;vectorvectorchar g(n 1, vectorchar(m 1, 0));vectorvectorint idx1(n 1, vectorint(m 1));vectorvectorint idx2(n 1, vectorint(m 1));for (int i 1; i n; i)for (int j 1; j m; j) cin g[i][j];string s1, s2;int i 1, j 1, dir 1, cnt 0;while (i n){s1 g[i][j], pos1[g[i][j] - a].insert(cnt);idx1[i][j] cnt ;j dir;if (j m 1) j m, i , dir * -1;if (j 0) j 1, i , dir * -1;}i 1, j 1, dir 1, cnt 0;while (j m){s2 g[i][j], pos2[g[i][j] - a].insert(cnt);idx2[i][j] cnt ;i dir;if (i n 1) i n, j , dir * -1;if (i 0) i 1, j , dir * -1;}int Q; cin Q;while (Q --){int t, x, y; cin t x y;if (t 1){char c; cin c;pos1[s1[idx1[x][y]] - a].erase(idx1[x][y]);pos2[s2[idx2[x][y]] - a].erase(idx2[x][y]); s1[idx1[x][y]] c;s2[idx2[x][y]] c;pos1[c - a].insert(idx1[x][y]);pos2[c - a].insert(idx2[x][y]);}else if (t 2){int c s1[idx1[x][y]] - a;int ans inf;for (int i 0; i 26; i)if (i ! c){auto it pos1[i].lower_bound(idx1[x][y]);if (it ! pos1[i].end())ans min(ans, *it);else ans min(ans, n * m);}cout ans - idx1[x][y] \n;}else{int c s2[idx2[x][y]] - a;int ans inf;for (int i 0; i 26; i)if (i ! c){auto it pos2[i].lower_bound(idx2[x][y]);if (it ! pos2[i].end())ans min(ans, *it);else ans min(ans, n * m);}cout ans - idx2[x][y] \n;}}
}int main()
{ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);solve();return 0;
}F-小天的 AB结论题
F-小天的 AB_牛客小白月赛83 (nowcoder.com)
考虑每次操作的特殊性与 a i a_i ai的数据范围对于一个长度为32的序列假设经过运算的答案为ans那么 a n s m a x ( 2 30 a l , 2 30 a l 1 , 2 29 a l 2 , 2 28 a l 3 , . . . , 2 1 a r − 1 , 2 0 a r ) ansmax(2^{30}a_l,2^{30}a_{l1}, 2^{29}a_{l2},2^{28}a_{l3},...,2^1a_{r-1},2^0a_r) ansmax(230al,230al1,229al2,228al3,...,21ar−1,20ar) 每个 a i a_i ai之前都乘上了一个系数并且这个系数随着序列长度的增大而增大当序列长度为32时前两个数的系数已经达到 2 30 2^{30} 230。由于 a i a_i ai的最大值为1e9而 2 30 1 e 9 2^{30}1e9 2301e9所以ans一定大于这个序列之后 a r a_r ar之后的数。总结下若区间[l, r]的前32个数中存在一个正数那么ans就是答案 若前32个数中不存在正数但存在0那么0就是答案 若前32个数中既不存在正数也不存在0由于负数乘2会越来越小所以需要在[l, r]区间的后32数中求ans
实现起来的细节还是很多的
#include bits/stdc.h
using namespace std;typedef long long LL;
const int mod9 998244353;
const int N 1e6 10;
LL a[N], b[N];
setint pos, zr;LL f(int st, int l, int r)
{LL ans (st l ? 1 : 2) * a[st];int pos st;while (pos 1 r pos - st 30)ans 2 * max(ans, a[ pos]);ans % mod9;ans ans * b[r - pos] % mod9;return (ans % mod9 mod9) % mod9;
}void solve()
{int n, m; cin n m; b[0] 1;for (int i 1; i 1000000; i)b[i] b[i - 1] * 2 % mod9;for (int i 1; i n; i) {cin a[i];if (a[i] 0) zr.insert(i);else if (a[i] 0) pos.insert(i);}while (m --){int t; cin t;if (t 1){int x, v; cin x v;if (a[x] 0) zr.erase(x);else if (a[x] 0) pos.erase(x);a[x] v;if (a[x] 0) zr.insert(x);else if (a[x] 0) pos.insert(x);}else{int l, r; cin l r;auto it pos.lower_bound(l);if (it ! pos.end() *it r){cout f(*it, l, r) \n;continue;}it zr.lower_bound(l);if (it ! zr.end() *it r){cout 0\n;continue;}cout f(max(l, r - 30), l, r) \n;}}
}int main()
{ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);solve();return 0;
}
