搜索结果
查询Tags标签： NOIP，共有 143条记录-
NOIP模拟47:Prime
线性筛裸题。首先要记住一个结论：对于一个数\(n\)，不大于他的素数不超过\(\sqrt{n}\)然后就直接算出\([2,min(k,\sqrt{R})]\)范围内的素数，将他们在\([L,R]\)范围内的倍数标记，最后没有标记的就是“类素数”。直接异或没被标记的数即可。Code #include<bits/stdc++…
2021/8/25 6:36:19 人评论 次浏览 -
noip模拟47
原版在 \(linux\) 本地写完没保存关机给没了…… 再简单写一下 \(t2\) 用 \(dp\) 转移 \(f[i]=\sum _ {j=last[a[i]]}^{i-1} f[j]\) 用前缀和优化为 \(sum[i]=sum[i-1]*2-sum[i-k-1]\) 贪心选取最后出现位置最靠左的，矩乘优化转移 \(t3\) \(f[i]=(f[i-1]+1)*p[i]+f[i-1]*…
2021/8/25 6:36:00 人评论 次浏览 -
noip模拟47
原版在 \(linux\) 本地写完没保存关机给没了…… 再简单写一下 \(t2\) 用 \(dp\) 转移 \(f[i]=\sum _ {j=last[a[i]]}^{i-1} f[j]\) 用前缀和优化为 \(sum[i]=sum[i-1]*2-sum[i-k-1]\) 贪心选取最后出现位置最靠左的，矩乘优化转移 \(t3\) \(f[i]=(f[i-1]+1)*p[i]+f[i-1]*…
2021/8/25 6:36:00 人评论 次浏览 -
noip模拟46
A. 数数 排好序从两头贪心即可B. 数树 首先很容易想到容斥 如果选择的边集的相关点集有点的度数大于 \(1\) 是不合法的 也就是说一定形成若干条长度不一的链 要给这些链上的点安排排列中的数，方案数其实就是 \((n-k)!\) 因为一条链开头的值确定了整条链的值就确定了 发现…
2021/8/24 6:35:34 人评论 次浏览 -
noip模拟46
A. 数数 排好序从两头贪心即可B. 数树 首先很容易想到容斥 如果选择的边集的相关点集有点的度数大于 \(1\) 是不合法的 也就是说一定形成若干条长度不一的链 要给这些链上的点安排排列中的数，方案数其实就是 \((n-k)!\) 因为一条链开头的值确定了整条链的值就确定了 发现…
2021/8/24 6:35:34 人评论 次浏览 -
[NOIP模拟46]鼠树
神仙题。 首先不考虑把黑点变白，发现每个白点的信息与它的归属点是相同的。可以在线段树中只维护黑点的信息，再记录$DFS$序上每个点之前黑点个数的前缀和，每次操作可以二分出该点的归属点进行操作。 具体维护黑点管辖点的个数与它的权值，及前两者乘积之和。一些其他的…
2021/8/24 6:35:33 人评论 次浏览 -
[NOIP模拟46]鼠树
神仙题。 首先不考虑把黑点变白，发现每个白点的信息与它的归属点是相同的。可以在线段树中只维护黑点的信息，再记录$DFS$序上每个点之前黑点个数的前缀和，每次操作可以二分出该点的归属点进行操作。 具体维护黑点管辖点的个数与它的权值，及前两者乘积之和。一些其他的…
2021/8/24 6:35:33 人评论 次浏览 -
noip模拟46
T1 先排个序，当k=2时，肯定选左右两端的 之后每次贪心地选一个最小值，再选一个最大值，计入答案的话前缀和优化一下就行了 T3 线段树维护dfs序，定义几个变量：fm表示区间的归属点（同一个点就是它，不同为0），depmax表示区间所有点的归属点的最大深度，depmin反之 操作…
2021/8/23 23:09:03 人评论 次浏览 -
noip模拟46
T1 先排个序，当k=2时，肯定选左右两端的 之后每次贪心地选一个最小值，再选一个最大值，计入答案的话前缀和优化一下就行了 T3 线段树维护dfs序，定义几个变量：fm表示区间的归属点（同一个点就是它，不同为0），depmax表示区间所有点的归属点的最大深度，depmin反之 操作…
2021/8/23 23:09:03 人评论 次浏览 -
2021.8.21考试总结[NOIP模拟45]
T1 打表由归纳法可以发现其实就是所有情况的总和。 $\frac{\sum_{j=1}^{1<<k}(v_j-v_{ans})}{2^k}$ $code:$1 #include<bits/stdc++.h>2 using namespace std;3 typedef long long LL;4 5 namespace IO{6 inline int read(){7 int x=0,f=1; char …
2021/8/22 6:36:06 人评论 次浏览 -
2021.8.21考试总结[NOIP模拟45]
T1 打表由归纳法可以发现其实就是所有情况的总和。 $\frac{\sum_{j=1}^{1<<k}(v_j-v_{ans})}{2^k}$ $code:$1 #include<bits/stdc++.h>2 using namespace std;3 typedef long long LL;4 5 namespace IO{6 inline int read(){7 int x=0,f=1; char …
2021/8/22 6:36:06 人评论 次浏览 -
noip模拟42[很有感觉哦哦哦]
noip模拟42 solutions 其实吧，这次考试还是非常成功的，找到感觉， 这才是noip的真正难度吧，前两题足够我切掉。。。 后面两个有一点小小的思路，看题解看一会就会了 不对不对，我真的看了好久题解都没想出来。。。 真的挺难的。。。。哭 T1 卷 这这这这这就是一个一眼就…
2021/8/21 6:36:18 人评论 次浏览 -
noip模拟42[很有感觉哦哦哦]
noip模拟42 solutions 其实吧，这次考试还是非常成功的，找到感觉， 这才是noip的真正难度吧，前两题足够我切掉。。。 后面两个有一点小小的思路，看题解看一会就会了 不对不对，我真的看了好久题解都没想出来。。。 真的挺难的。。。。哭 T1 卷 这这这这这就是一个一眼就…
2021/8/21 6:36:18 人评论 次浏览 -
NOIP模拟41
考场上读错题，直接炸裂。题目中说“任一”的意思是优弧与劣弧中随便一个满足条件即可，不是要求都满足要求。很明显可以用单调栈。常规做法是将环拆开，变成\(2n\)的链，然后直接跑单调栈，会\(T\)。题解的做法是将某个最大值放在端点，因为很明显如果你的某个弧上有最大…
2021/8/17 6:36:00 人评论 次浏览 -
NOIP模拟41
考场上读错题，直接炸裂。题目中说“任一”的意思是优弧与劣弧中随便一个满足条件即可，不是要求都满足要求。很明显可以用单调栈。常规做法是将环拆开，变成\(2n\)的链，然后直接跑单调栈，会\(T\)。题解的做法是将某个最大值放在端点，因为很明显如果你的某个弧上有最大…
2021/8/17 6:36:00 人评论 次浏览
