LB_tq - 个人主页动态

2020-03-30 11:53

已编辑

T1 Solution 的部分可以用 的 解决。 到一个点 的所有方案数等于 。 先将障碍点按坐标排序，记 为到第 个点的合法方案数，则 当且仅当 由 的定义可知不会重复排除非法情况。所以可以线性求逆元，再进行 的 。 Code #include <iostream> #include <cstdio> #include <algorithm> #define ll long long using namespace std; const int maxn=2e5+10; const int mod=998244353; struct n...

0 点赞评论收藏

2020-03-30 18:35

已编辑

德州市第一中学 C++

【每日一题】城市网络

Solution 题目中有两个关键信息： 1号节点是根节点。 节点 在节点 到根节点的最短路径上。 由于是树形结构，所以从 到 一定是不断地将 ，也就是 是 的祖先。 于是可以先进行一次 预处理出每个节点的父节点，之后回答询问。只有当某个节点的珠宝比手中的都值钱是才会采购，所以一旦出现更有价值的，其他珠宝就没有比较的价值了。于是可以联系到单调栈。 具体来说，遇到比栈顶更有价值的珠宝时进行弹栈。如果弹完后栈中没有元素，则证明比当前的所有珠宝更有价值，就可以使答案加 ，再将此珠宝加入栈中即可。 时间复杂度： 。 Code #include <iostream> #...

0 点赞评论收藏

2020-03-29 22:37

德州市第一中学 C++

【每日一题】滑动窗口

Solution 单调队列模板题。 具体思想：从前到后遍历序列，维护一个队列，使队列的队首一直是窗口中的最值。以最小值为例，若序列当前位置的数比队列中的队尾小，那就意味着当前位置的数贡献更大，即更有可能成为之后的最小值，于是就可以弹出队尾元素将新元素插入。注意及时从队首排除不符合范围的元素。 由于每个数至多进队列一次，出队列一次，所以时间复杂度为 。 Code #include <iostream> #include <cstdio> using namespace std; const int maxn=1e6+10; int n,k,a[maxn],q[maxn]...

0 点赞评论收藏

2020-03-30 10:24

已编辑

德州市第一中学 C++

【比赛】牛客练习赛60

大吉大利 Solution 位运算常用的优化技巧就是按位计算。用 表示第 位为 的数的个数。由与运算的性质可以得到，两个数二进制第 位都为 时，会使答案加 。因此便可以边读入边处理，最后将答案乘 并加上数本身即可。 时间复杂度： Code #include <iostream> #include <cstdio> using namespace std; const int maxn=1e5+10; int n,a[maxn],sum[31],p[31]; long long ans; int main(){ cin>>n; ...

0 点赞评论收藏

2020-03-27 14:48

德州市第一中学 C++

2020-03-27

在牛客打卡2天，今天学习：刷题 77 道

OI圈

0 点赞评论收藏

2020-03-26 12:10

已编辑

德州市第一中学 C++

【每日一题】数学考试

Solution 由题意可知需要求两段不连续区间，使和最大。 区间求和问题可以想到一个常用算法：前缀和。区间 的和可以用 方便地求出。 预处理序列的前缀和后，如何得知某个位置之前和之后的和最大的区间呢？我们可以使用线性 求得。设 表示位置 之前的最大区间和， 表示位置 之后的最大区间和。那么有： {，} {，} 由于数据范围较大，需要开。注意 数组初始化为负无穷。 时间复杂度：。 Code #include <iostream> #include <cstdio> #include <cstring> #define ll long l...

0 点赞评论收藏

2020-03-27 16:25

已编辑

德州市第一中学 C++

【每日一题】合并回文子串

Solution 看到数据范围可以想到区间。 由题意可知字串是连续的。设 为在 中选取 到 ，在 中选取 到 是否能构成回文串。转移方程如下： （，) （，) （，，) （，，） 利用或运算可以方便的转移。当两个字符串最多选出一个字符时，此时显然有 ，作为边界条件。 时间复杂度：。 Code #include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,ans,dp[52][52][52][52]; string a,b; in...

0 点赞评论收藏

2020-03-25 08:20

已编辑

德州市第一中学 C++

【每日一题】tokitsukaze and Soldier

Solution 由题目可知要求一个集合，使集合大小满足元素的限制且元素之和最大。 一个显然的贪心思想：在满足条件的前提下使得和最大。要求和最大，就可以使用堆来维护。 因此，可以先按 从大到小排序，维护一个小根堆，每插入新元素之前，将堆的大小调整至符合条件。再实时维护一个集合内元素的最大值即可。 时间复杂度： 最后，给大家推荐一道类似的题目：Supermarket 也是维护一个小根堆进行贪心。 Code #include <iostream> #include <cstdio> #include <algorithm> #define ll long lo...

0 点赞评论收藏

2020-03-12 16:12

德州市第一中学 C++

2020-03-12

在牛客打卡1天，今天也很努力鸭！

OI圈

0 点赞评论收藏

2019-12-07 22:00

德州市第一中学 C++

周赛13提高组T2单调队列为啥错求指点

#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=1e5+10; int n,n1,n2,a[maxn][2],b[maxn][2]; int p[maxn],t,ans; int fr(){ char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); int sum=ch-'0'; while((ch=getchar())>='0'&&amp...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：