Miya555

分类

乱七八糟(1) 未归档(7) 笔记qwq(4) 题解(4) 题解 / dp(1)

/ 注册

全部文章（共16篇）

CSP-S 2023 消消乐题解

考虑预处理。处理数组，每次走到一个位置，往前搜索。当前位置不等于则通过这个位置继续往前查找。一直到当前位置等于，或者到达最前端则停止。接下来进行第二次处理。由于已经对进行过预处理，在计算时只需要从有值的点分别往前统计即可。最后求一遍和。感谢学弟 @kibi 的优化！ #i...

C++ 动态规划计数前缀和

2023-10-27

1 556

题解 | #小美的修路#

挺小清新的一道最小生成树。题意：给你一个图，求这个图的最小生成树。其中图中某些边为必选。不难想出只要在 ==1 的时候强制加入边进行更新即可。 #include<bits/stdc++.h> using namespace std; #define int long long con...

C++ 图最小生成树

2023-10-22

13 360

树形dp学习笔记

我们通常采用递归的方式实现树形dp。对于每个节点，先递归在它的每个子节点上进行dp，在回溯时，从子节点向根节点进行状态转移。顺序一般为从叶子结点到根节点递推。以下是写的一些树形dp题目：一. P1352 没有上司的舞会以子树的根作为dp状态的第一维。容易发现，每个员工是...

2023-10-16

0 0

状压dp 学习笔记

"此刻发生的所有事，都是你过去选择的结果。" 最近打模拟赛在状压dp上总是没有一点思路。来重学一遍。状态压缩：通过一串 01 码来清晰地表示一个集合的状态。同时，在确定了最低位的前提下，一串 01 码与一个二进制数一一对应。其本质上是进行了两次操作： ...

2023-10-08

0 0

UVA10054 The Necklace 题解

好可恶一道题，怎么没人告诉我输出之间有空行（思路是先抽象成图，然后跑一边dfs记录边的前后顺序。对于不能成环的情况，只需要再开个数组记录度数判断奇点即可。若存在奇点则break掉，剩下的跑dfs、 //produced by miya555 //stupid mistakes:1...

2023-10-02

0 0

题解 hdu 1269 迷宫城堡

找点图论练习题写，发现hdu又寄了，那就发到blog里吧。思路：tarjan缩点判断DAG中点数是否为1。若是，则该图为强连通图。 //produced by miya555 //stupid mistakes:多测记得清空 //ideas:tarjan模板 #include<...

2023-10-02

0 0

权值线段树学习笔记

8月集训学了权值线段树，当时没怎么加强训练。国庆刚好开始有时间，巩固巩固。补上学习笔记。首先介绍权值树。其本质是一个记录每个数出现次数的线段树，也就是由桶建成的树。接下来介绍各种操作。 1.插入。由于统计的是出现次数，从这个数往上依次加1即可。 void insert(in...

2023-09-29

0 0

9月做题记录

Part 1.图论 1.分层图最短路 P6100 [USACO19FEB] Painting the Barn G #include<bits/stdc++.h> using namespace std; const int N=1e5+5,M=205,K=1e5...

2023-09-21

1 0

HDU 1312 Red and Black 题解

//注意边界判断，调了好久#include <iostream> #include <queue> using namespace std; #define check(x,y)(x<wx&&x>=0&&y<hy&&a...

2023-07-30

0 0

HDU1702 ACboy needs your help again! 题解

#include <iostream> #include <string> #include <queue> #include <stack> using namespace std; int t, n, m; int main() { c...

2023-07-28

0 0