平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共5篇）

【每日一题】换个角度思考来自专栏

戳我传送题意：思路：离线+值域树状数组，保存每个点和每次询问的编号，每个点按照值的大小升序排序，每次询问按照k值大小升序排序。原理：1.处理k1的答案时（k最小的询问），树状数组中小于k1的位置都会被1标记，k1的答案就是树状数组 [l,r] 中1的个数。2.处理k2时（k2>=k1），之前被...

树状数组离线算法值域树状数组

2020-05-04

1 634

【每日一题】子序列来自专栏

戳我传送思路：传送门看这位大佬的题解看懂了，太秀了。子序列首先我们会想到动态规划，状态dp[i]表示以a[i]结尾符合条件的子序列个数。状态转移方程不难写出是dp[i]=1+ 。建议仔细看清楚a的上下标，a[i]的上标是j，a[i]的下标是i，如果像我一样没看清楚的话，真不知道题目在说什么...

树状数组数论 dp

2020-04-23

1 678

牛客小白月赛20

戳我传送 A、最短路思路： Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define dis(a,b,c,d) sqrt((a-...

贪心模拟前缀和暴力枚举并查集离散化树状数组线段树 dfs序二维差分 Dijkstra DFS 思维 BFS 计算几何

2020-04-18

2 1024

【每日一题】Treepath 来自专栏

戳我传送思路：方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5...

树状数组 DFS LCA dp 树状dp

2020-04-16

0 599

牛客OI周赛15-普及组

嘀咕一下：原本以为和前几次的的题目一样的难度，结果我就会写一题，线段树当时还没学，多组背包还不会，但是其实这个难度还是可以接受的传送门 A-咪咪游戏题目大意：每次询问你一个字符串，判断是否由mq连接而成难度：看懂了题目要你做什么就很好做出来了，一道签到题题目类型：模拟思路： 1.由mq连...

树状数组线段树思维 dp

2020-04-07

2 577