4 qq_38232157

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 3w+

洛谷 P1854 花店橱窗布置(算法竞赛进阶指南,线性DP)

算法竞赛进阶指南347页,线性DP题目:每一排选一个数,求一个最大的和,要求前一排选的数比后一排选的数靠左。本题要点:1、状态表示:dp[i][j] 表示前 i朵花,放入前j个花盆中,获得最大值。vis[i][j] = true, 如果 dp[i - 1][j - 1] + mp[i][j] > dp[i][j - 1]2、状态转移dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + mp[i][j]);3、输出方案:每一行从右往左找,找到

2020-10-12 16:16:17

POJ 2777 Count Color(线段树,区间修改)

线段树,区间修改网上老哥思路:线段树节点存储该区间内的颜色,单点区间肯定就是染成的颜色,大区间如果标记为-1则表示该区间由多种颜色的小区间组成,注意初始情况下木板均为同一种颜色,可以记为1。一共有最多30种颜色,所以用bool vis[30]数组标记,在每次查询的时候清空,查询到点或区间颜色相同时,对该颜色标记为true,最后统计1~T这T种颜色使用的个数即vis是true的情况本题要点:1、节点维护的信息:区间范围: [l, r]区间的颜色: color延迟标记: flag2、 套用线

2020-09-29 16:53:08

POJ 2828 Buy Tickets(线段树)

线段树题意:第一行输入一个整数n,代表有n个人,以后的n行每行有两个数x,y代表把值为y的数放在第x个数之后(x==0代表值为y的数在第一个位置),要求按顺序输出这个序列本题要点:1、从后往前插入数字,比如第一个样例40 771 511 332 69最后一个数字 69, 插入到 下标3, 然后这个位置就是最终的位置。 倒数第二个数字 33, 插入到从头数 第 2 个空位,在这里,也就是下标2。倒数第3 个数字 51, 插入到 从头数 第 2 个空位, 此时下标 2, 3 都已经有数子了

2020-09-29 13:07:43

HOJ 1754 I Hate It(线段树,点修改)

线段树,点修改本题要点:1、节点开个 max 表示区间 [l, r] 范围内的最大值。套用线段树 点修改 的模板。执行相应的修改查询操作即可。#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MaxN = 2e5 + 10;int n, m;int score[MaxN];struct segTree{ int l, r; i

2020-09-28 13:03:50

HOJ 1698 Just a Hook(线段树,区间修改,延迟标记)

线段树,区间修改,延迟标记本题要点:1、每个节点都有一个延迟标记 add , 一开始,所有的节点的 add 都初始化为0.2、区间修改,这里的某个区间 [l, r], 一下子改成 某个数值。 所有,节点的额sum 值,直接赋值即可tree[p].sum = d * (tree[p].r - tree[p].l + 1);3、向下扩展完成后,把标记 add 置零。#include <cstdio>#include <cstring>#include <iostre

2020-09-28 12:19:34

HOJ 1394 Minimum Inversion Number(线段树,逆序数)

线段树计算逆序数本题要点:1、本题中n个数,恰好是 0 ~ n - 1,不需要离散化,而且没有任意两个数相同的。2、 先初始化树, 所有节点的sum 赋值为0。 然后每次新加入 一个数 a[i], 先查询 区间 [a[i] + 1, n + 1]这些数出现的总次数。 意味着,查询比 a[i] 先加入的,并且比 a[i] 大的数的总数。 这些数与 a[i] 构成逆序数。然后,执行更新操作, update(1, a[i]), 表示 a[i] 出现的次数加1.3、 求出序列 a[1], a[2], …

2020-09-28 00:04:09

HOJ 1166 敌兵布阵(线段树,点修改区间查询)

线段树,点修改区间查询本题要点:1、套用 线段树模板,使用延迟标记 add. 某点减去值 d, 相当于加上 -d;#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MaxN = 50010;int a[MaxN];int T, n;char cmd[10];struct segTree{ int l, r; long long

2020-09-27 19:06:59

P3373 【模板】线段树 2(线段树,延迟标记)

线段树,延迟标记本题要点:1、同时对某个区间 [L, R] 的每个元素,加上 d, 乘上d。定义结构体时候,加上 add, mul 标记。 struct segTree { int l, r; long long sum; long long add, mul; //区间的加标记,乘标记 }2、细节实现:子树的sum、mulv、addv值分别乘上当前节点的mulv值;当前节点的mulv值还原,即置为1;子树的addv值加上当前节点的addv值;子树的sum值加上(子树包含

2020-09-27 17:56:46

洛谷 P3372 【模板】线段树 1(延迟标记)

线段树,延迟标记本题要点:1、延迟标记:当前的修改或者查询的区间范围是[l, r], 如果某个节点的区间 p 被 [l, r] 所覆盖(l <= tree[p].l && tree[p].r <= r),并且这个节点p ,在后续再也没有访问到,这个节点的子节点的相关信息可以不修改。 如果 p节点后续访问到了,只有在访问到的时候,先更新 p 节点的所有子节点信息。 至于延迟标记,可以在 节点的结构体中,增加 add 标记。查询到某节点 p, 根据 add 标记, 先

2020-09-23 17:26:04

洛谷 P5091 【模板】扩展欧拉定理

扩展欧拉定理本题要点:1、m <= 10^8, 先求出m的欧拉函数 phm. 先求出 m的素因子 p1 ~ pkphm = m * (p1 - 1) / p1 * (p2 - 1) / p2 * … * (pk - 1) / pk2、b 是一个大数, 不过这里需要关注的是 b % phm 的值。所以,可以一个数字一个数字的读累加到一定数量,对 phm求模。3、扩展欧拉定理:a^b(mod m) = a^(b % phm + phm), 如果 b < phm这里涉及快速幂, 用lo

2020-09-22 21:47:13

洛谷 P4549 【模板】裴蜀定理

裴(pei)蜀定理引理:对于给定的正整数a,b,方程ax+by=c有解的充要条件为c是gcd(a,b)的整数倍裴(pei)蜀定理:方程ax+by+cz+…+nm=f(其中a,b,c…n,f为整数)有解的充要条件是f为gcd(a,b,c,…,n)的整数倍定理的应用:给定一个序列{an},求一个整数序列{bn}使得a1b1+a2b2+…+an*bn值最小(要求最小值为正数),求这个最小值解:根据裴蜀定理的推广,原式最小值即为gcd(a1,a2…an)#include <cstdio>

2020-09-22 16:27:12

洛谷 P1516 青蛙的约会(扩展欧几里得)

扩展欧几里得两个青蛙跑步,跑的快的,追上跑得慢的。 并且多跑的路程有 L 的整数倍。本题要点:1、假设 A 青蛙 起点 m, 速度为 a, B 青蛙 起点 n, 速度为 b; 如果 a > b, 跑了 x 步,ax + m - (bx + n) = L * y, 化简为:(a - b) * x + L * (-y) = n - m;这里的 n - m 可能是负数,通过模 L , 使得 方程 右边是正整数。从而得到方程: ax + by = c,(a, b, c 都是正整数)2、 如

2020-09-22 16:09:17

洛谷 P5656 【模板】二元一次不定方程(exgcd)

扩展欧几里得本题要点:1、这里需要解方程 ax + by = c 的所有正整数解。不过,有个前提,a, b, c 都是正整数, 后面方便处理很多。2、记 d = gcd(a, b), 如果 c % d != 0, 说明方程无整数解。3、 用 扩展欧几里得 exgcd 算出 ax + by = gcd(a, b) 的 解 x0, y0;那么原方程 ax + by = c 的所有 整数解可以表示为x = (c/d)x0 + k(b/d)y = (c/d)y0 - k(a/d), 其中,k取遍

2020-09-22 13:26:20

洛谷 P3868 [TJOI2009]猜数字(中国剩余定理, 快速乘法)

中国剩余定理, 快速乘法本题要点:1、 套用 中国剩余定理 模板,但是注意,这里的 乘法会 爆 long long ,因此,用快速乘法来代替。2、 a[i] <= 10^9, 当计算 某数 z 和 a[i] 相乘, 应该是调用 quick_multi(a[i], z, mod),也就是用 a[i] 去依次乘上 z 的 二进制的每一位。(a[i] 数值较大, z的较小)#include <cstdio>#include <cstring>#include <

2020-09-22 11:50:52

洛谷 P1495 【模板】中国剩余定理(CRT)/曹冲养猪(中国剩余定理)

中国剩余定理概念:设 m[1], m[2], m[3], …, m[[n] 是两两互质的整数。 方程组x = a[1](mod m[1]) // 注意,这里的 '=' 表示同余符号x = a[2](mod m[2])...x = a[n](mod m[n])方程 的解 x = sum{a[i] * (m / m[i]) * t[i]} (1 <= i <= n)其中, m = m[1] * m[2] * … * m[n],t[i] 满足同余式子:(m / m[i]) * t[

2020-09-22 00:26:57

洛谷 P3865 【模板】ST表(倍增, ST表)

倍增, ST表ST算法, 在 O(n*log(n)) 的时间预处理后,以 O(1) 的时间回答:数列 A 的区间 [l, r] 之间的最大值。本题要点:1、f[i][j] 表示从i开始,2^j 个数范围内,区间最大值2、把长度是 2^j 的区间,分为左右两半, 各长 2^(j-1), 2^j 的区间的最大值,就是两个区间的较大值。f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])3、查询的时候,寻找到第一个 k, 使得

2020-09-21 12:59:31

洛谷 P2286 [HNOI2004]宠物收养场 (treap 树)

treap 树本题要点:1、建立两棵 treap 树, 一棵用来存 宠物,一棵树用来存 顾客。 题目给出的所有的顾客值和宠物值都不一样。这样结构体 Treap 只需要 多一个 size 来就来子树的节点总数2、套用 treap 树 的模板,写好 以下函数。 因为是两棵树,需要传参数的引用。int New(int val, Treap* a, int& tot)void update(int p, Treap* a)void Build(Treap* a, int& tot,

2020-09-21 12:04:45

洛谷 P3379 【模板】最近公共祖先(LCA)( tarjan算法, 模板题)

最近公共祖先LCA, tarjan算法本题要点:1、tarjan算法 是离线算法,把所有的查询读入,最后统一输出。2、数组 vis[k] 表示 k点的访问状态,vis[k] == 0, 表示未访问vis[k] == 1, 表示已经访问, 但是未回溯vis[k] == 2, 表示已经回溯3、 如果 某次查询 (x, y), 此时点x 正处于 vis[x] == 1 的状态,而y处于 vis[y] == 2 的状态,那么 lca(x, y) 就是 y点一直往上走,直达遇到第一个祖先 z, vis

2020-09-20 17:22:28

洛谷 P2814 家谱(并查集,裸题)

并查集,裸题本题要点:1、 n <= 50000, 把名字离散化为整数,后面就是并查集的操作。压缩路径。#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <string>using namespace std;const int MaxN = 5e4 + 10;int fa[MaxN];map<string, i

2020-09-20 14:28:17

洛谷 P1456 Monkey King(左偏树)

左偏树本题要点:1、首先,每一个节点里需要加入指向父节点的下标 fa。2、这里的左偏树根节点是最大元素, merge 函数里面,if(tree[x].val < tree[y].val) // 根节点是最大元素,这里是小于号 swap(x, y);3、然后每一查找到 点x所在的左偏树的根节点 fax, fax 的 val 减半, 这时候需要调整 fax 的位置:先合并 fax 的左右孩子 merge(tree[fax].lc, tree[fay].rc) (假设为newtree),

2020-09-20 12:45:03

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。