238. 银河英雄传说 题目链接：https://www.acwing.com/problem/content/240/ 思路 是否在同一个集合很好维护，边带权记录某个节点到祖先(列的第一个节点)的距离就好。 然后查询两个节点的间隔就是：abs(w[a]-w[b])-1 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freo...

P1621 集合 题目链接：https://www.luogu.com.cn/problem/P1621 思路 发现1e5/2+ 1e5/3 + 1e5/5+1e5/7+....的结果不到1e6，所以可以直接采用暴力，对于每个质因数P把在[L,R]区间的倍数join一下就行 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),fr...

关押罪犯 题目链接：https://ac.nowcoder.com/acm/problem/16591 思路 见此题的视频讲解：https://www.bilibili.com/video/BV1nz411b75c 代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <map> #include <set> #include <deque> #include <queue>...

题解视频正在录制中 A - Candies 二进制 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define PI acos(-1) #define fs first #define sc second using names...

视频题解：https://www.bilibili.com/video/BV1YK41157F7 A-Candies and Two Sisters 签到 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define PI aco...

P2196 挖地雷 题目链接：https://www.luogu.com.cn/problem/P2196 思路 没错，我又再重学dp。又开始做水题了。这个题数据量很小，可以直接把图进行遍历。每次开始的点分别是1～N。dp[v] = max(dp[v],dp[u] + w[v]) 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin)...

P2532 [AHOI2012]树屋阶梯 题目链接：https://www.luogu.com.cn/problem/P2532 题意 N个阶梯，用N个矩阵有多少种摆放方式组合成。 思路 因为，N个梯阶最少需要N个矩形，所以我们摆放的时候，肯定要贪心一下。考虑下面的梯阶，红色矩形必须包括在某个矩形内部。因为只能用N个矩形，所以包含这个红色矩形只能是下面四种颜色框起来的部分。其他部分就在除框起来部分之外找了。比如蓝色框框： 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),c...

P1976 鸡蛋饼 题目链接：https://www.luogu.com.cn/problem/P1976 思路 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define PI acos(-1) #define fs...

P1722 矩阵 II 题目链接：https://www.luogu.com.cn/problem/P1722 思路 首先题目有一点说漏了。总的红色要等于总的黑色数量我们只要把放棋子看成是入栈和出栈就可以了。为啥？因为题目说无论什么时候的i，都要1~i的红大于黑，而任何时候的入栈数量肯定是大于出栈数量的。 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r...

P1044 栈 题目链接：https://www.luogu.com.cn/problem/P1044 思路 本人使用的是递推方式求卡特兰数。如果不懂卡特兰数，自行在B栈上搜卡特兰数 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout...

POJ - 3321 Apple Tree 题目链接：https://vjudge.net/problem/POJ-3321#author=mfdy 题目 卡卡屋前有一株苹果树，每年秋天，树上长了满苹果。卡卡很喜欢苹果。树上有N个节点，卡卡给他们编号1到N，根的编号永远是1.每个节点上最多结一个苹果。卡卡想要了解某一个子树上一共结了多少苹果。 现在的问题是不断会有新的苹果长出来,卡卡也随时可能摘掉一个苹果吃掉。你能帮助卡卡吗? 输入数据：第一行包含一个整数N（N <= 100000）,表示树上节点的数目。 接下来N-1行，每行包含2个整数u和v，表示u和v是连在一起的。 下一行包含一个整...

POJ - 2155 Matrix 题目链接：https://vjudge.net/problem/POJ-2155#author=happypeople 题目 给定 n* n 矩阵A，其元素为0或1. A [i][j] 表示第i行和第j列中的数字。最初全为0. 我们有两个操作: 1. C x1 y1 x2 y2（1 <= x1 <= x2 <= n，1 <= y1 <= y2 <= n）将左上角为(x1,y1)，右下角为(x2,y2)的矩阵翻转（0变成1，1变成0）。 2. Q x y（1 <= x，y <= n）查询A [x][y]，输出答案...

POJ - 2481 Cows 题目链接：https://vjudge.net/problem/POJ-2481 题目大意 在x轴上有很多的线段，问每一个线段是多少个线段的真子集。 思路 我们可以考虑通过排序，让线段的左端点是从左到右的关系排列，每遍历到一个线段的时候，就看之前有多少个右端点是在[r,最大值]这就是答案，如果线段重叠，答案之前继承一下就可以了。 代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <...

POJ-1195 Mobile phones 题目链接：https://vjudge.net/problem/POJ-1195#author=muchen1026 思路 二维树状数组的模板题 代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <map> #include <set> #include <stack> #include <deque> #include &l...