搜索结果
查询Tags标签： NOIP，共有 143条记录-
Noip模拟40 2021.8.16
T1 送花 按照题解意思说是扫描线题，但我觉得像一个线段树优化$dp$ 主要思想一样，就是暴力枚举右端点，同时维护左端点的最值， 考虑两种情况， 如果左端点在$r$扫到的数$i$上一次出现的位置之前， 那么这个数是无法在区间$[l,r]$中作出贡献的 如果左端点在上次出现的位置…
2021/8/16 6:36:22 人评论 次浏览 -
Noip模拟40 2021.8.16
T1 送花 按照题解意思说是扫描线题，但我觉得像一个线段树优化$dp$ 主要思想一样，就是暴力枚举右端点，同时维护左端点的最值， 考虑两种情况， 如果左端点在$r$扫到的数$i$上一次出现的位置之前， 那么这个数是无法在区间$[l,r]$中作出贡献的 如果左端点在上次出现的位置…
2021/8/16 6:36:22 人评论 次浏览 -
2021.8.15考试总结[NOIP模拟40]
T1 送花线段树。枚举右端点，线段树记录左端点对应的值。 每次对当前颜色上上次出现的位置到上次出现的位置区间减，上次出现的位置到当前位置区间加。 $code:$1 #include<bits/stdc++.h>2 #define LL long long3 using namespace std;4 const int NN=1e6+5;5 int n…
2021/8/16 6:36:21 人评论 次浏览 -
2021.8.15考试总结[NOIP模拟40]
T1 送花线段树。枚举右端点，线段树记录左端点对应的值。 每次对当前颜色上上次出现的位置到上次出现的位置区间减，上次出现的位置到当前位置区间加。 $code:$1 #include<bits/stdc++.h>2 #define LL long long3 using namespace std;4 const int NN=1e6+5;5 int n…
2021/8/16 6:36:21 人评论 次浏览 -
2021.8.14考试总结[NOIP模拟39]
T1 打地鼠全场就俩人没切，还有一个是忘关$freopen$了。 $code:$1 #include<bits/stdc++.h>2 #define rin register signed3 using namespace std;4 const int NN=2e3+5;5 int n,k,pre[NN][NN],ans;6 char ch[NN];7 inline int read(){8 int x=0,f=1; char ch=g…
2021/8/15 6:35:51 人评论 次浏览 -
2021.8.14考试总结[NOIP模拟39]
T1 打地鼠全场就俩人没切，还有一个是忘关$freopen$了。 $code:$1 #include<bits/stdc++.h>2 #define rin register signed3 using namespace std;4 const int NN=2e3+5;5 int n,k,pre[NN][NN],ans;6 char ch[NN];7 inline int read(){8 int x=0,f=1; char ch=g…
2021/8/15 6:35:51 人评论 次浏览 -
[考试总结]noip模拟38
。。。。 \(boom\) 不知道怎么的 \(T1\) 上来我就给跳过了，然后就开始先干\(T3\)，感觉并不是很简单，但是也不是能说是很难。 然后我就突然想到了一种可以过掉一半数据的 \(dp\)，之后居然一下子就成功了。 大样例一测，过了？！ 之后感觉还行，然后回头管 \(T1\)，但是…
2021/8/14 6:35:48 人评论 次浏览 -
[考试总结]noip模拟38
。。。。 \(boom\) 不知道怎么的 \(T1\) 上来我就给跳过了，然后就开始先干\(T3\)，感觉并不是很简单，但是也不是能说是很难。 然后我就突然想到了一种可以过掉一半数据的 \(dp\)，之后居然一下子就成功了。 大样例一测，过了？！ 之后感觉还行，然后回头管 \(T1\)，但是…
2021/8/14 6:35:48 人评论 次浏览 -
NOIP模拟38:a
这是T1。考场上思路与正解就差个前缀，打的线段树，因为其巨大常数快乐挂掉。。。。。。正解复杂度是\(O(n^2m)\)，其实再挂个\(log\)也能过，但是需要用常数极其优秀的树状数组外加大大大大大大大大大大大大大大大大力卡常。有点像之前做的入阵曲一题。首先\(n\)很小，那…
2021/8/13 23:09:27 人评论 次浏览 -
NOIP模拟38:a
这是T1。考场上思路与正解就差个前缀，打的线段树，因为其巨大常数快乐挂掉。。。。。。正解复杂度是\(O(n^2m)\)，其实再挂个\(log\)也能过，但是需要用常数极其优秀的树状数组外加大大大大大大大大大大大大大大大大力卡常。有点像之前做的入阵曲一题。首先\(n\)很小，那…
2021/8/13 23:09:27 人评论 次浏览 -
noip模拟37
期望得分：100+10+15+0=125 实际得分：100+10+10+0=120 T1 签到题，扩欧，然后三分，或者直接\(O(1)\)出解 T2 队长快跑微弱加强版，区别在于这道题需要排序 发现若\(a_i< b_j\)且\(a_j> b_i\)，则\(i\)一定在\(j\)之前，反之则\(i\)在\(j\)之后 剩下的两种情况怎么…
2021/8/13 23:06:05 人评论 次浏览 -
noip模拟37
期望得分：100+10+15+0=125 实际得分：100+10+10+0=120 T1 签到题，扩欧，然后三分，或者直接\(O(1)\)出解 T2 队长快跑微弱加强版，区别在于这道题需要排序 发现若\(a_i< b_j\)且\(a_j> b_i\)，则\(i\)一定在\(j\)之前，反之则\(i\)在\(j\)之后 剩下的两种情况怎么…
2021/8/13 23:06:05 人评论 次浏览 -
NOIP 模拟 $36\; \rm Cicada 与排序$
题解 \(by\;zj\varphi\) 设 \(rk_{i,j}\) 表示第 \(i\) 个数最后在相同的数里排第 \(j\) 位的概率。 转移时用一个 \(dp\)，\(dp_{i,j,0/1}\) 表示归并排序时第一个数组弹了 \(i\) 个，第二个数组弹了 \(j\) 个，最后一个弹的是第一个数组的还是第二个的。 直接模拟归并排…
2021/8/13 6:36:14 人评论 次浏览 -
NOIP 模拟 $36\; \rm Cicada 与排序$
题解 \(by\;zj\varphi\) 设 \(rk_{i,j}\) 表示第 \(i\) 个数最后在相同的数里排第 \(j\) 位的概率。 转移时用一个 \(dp\)，\(dp_{i,j,0/1}\) 表示归并排序时第一个数组弹了 \(i\) 个，第二个数组弹了 \(j\) 个，最后一个弹的是第一个数组的还是第二个的。 直接模拟归并排…
2021/8/13 6:36:14 人评论 次浏览 -
NOIP 模拟 $36\; \rm Cicada 拿衣服$
题解 \(by\;zj\varphi\) 发现右端点固定时，左端点的 \(min-max\) 单调递减，且对于 \(or\) 和 \(and\) 相减，最多有 \(\rm2logn\)个不同的值，且相同的值构成一段连续的区间。 那么就可以在最远的，符合答案的第一个区间二分答案。 具体实现可以用一个链表，每次扫一遍合…
2021/8/13 6:36:07 人评论 次浏览
