分类: 算法

15 篇文章

P4072 [SDOI2016]征途
#include<bits/stdc++.h> using namespace std; using cint = const int&; using ll = long long; constexpr ll maxn = 3e3 + 10, inf = 0x3f3f3f3f; int sum[maxn], Q[maxn], n…
P3979 遥远的国度:换根树剖
遥远的国度 题目描述 zcwwzdjn 在追杀 zhx ,而 zhx 逃入了一个遥远的国度。当 zcwwzdjn 准备进入遥远的国度继续追杀时,守护神 RapiD 阻拦了 zcwwzdjn 的去路,他需要 zcwwzdjn 完成任务后才能进入遥远的国度继续追杀。 问题是这样的:遥远的国度有 $n$ 个城市,这些城市之间由一些路连接且这些城市构成了一…
[国家集训队] 数颜色 / 维护队列 – 带修莫队
[国家集训队] 数颜色 / 维护队列 题目描述 墨墨购买了一套 $N$ 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令: $Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。 $R\ P\ Col$ 把第 $P$ 支画笔替换为颜色 $Col$。 为了满足墨墨的要…
P2495 [SDOI2011] 消耗战
[SDOI2011] 消耗战 题目描述 在一场战争中,战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 $1$ 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 $k$ 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能…
简单点分治
Tree 题目描述 给定一棵 $n$ 个节点的树,每条边有边权,求出树上两点距离小于等于 $k$ 的点对数量。 输入格式 第一行输入一个整数 $n$,表示节点个数。 第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ,表示 $u$ 与 $v$ 有一条边,边权是 $w$。 第 $n+1$ 行一个整数 $k$ 。 输出格式 一行一个整数,表示答案…
模拟赛日寄
T3 #include<bits/stdc++.h> #define cint const int& #define lowbit(x) (x & -x) using namespace std; const int maxn = 5e5+10; int n, a, b; struct { int nxt, v; }ed…
Tip
凡是O(log)转O(1),本质都是ST表与单调性 笛卡尔树 #define EL #include<bits/stdc++.h> #define int unsigned long long EL using namespace std; EL #define FIO 0 #define ten(x) (((x)<<1)+…
注意:下标越界
Tip 高维数组,下标越界,没有Error,只是寄 P2761 软件补丁问题 Code #include<bits/stdc++.h> #define int long long #define cint const int& using namespace std; using pii = pair<int, int&g…
P3384 【模板】轻重链剖分/树链剖分
Problem 【模板】轻重链剖分/树链剖分 题目描述 如题,已知一棵包含 $N$ 个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 1 x y z,表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。 2 x y,表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。 3 x z,表示将以 $x…
P1074 [NOIP2009 提高组] 靶形数独
Code #include<iostream> using namespace std; #define uint unsigned #define uch unsigned char #define poi const uch& const unsigned scores[10][10]{ {}, {0,6U,6U,6U,6U…