sdoi2009专题

【COGS】421 [SDOI2009] HH的项链 树状数组

传送门:【COGS】421 [SDOI2009] HH的项链 题目分析:将区间以右端点为关键字降序排序,然后从左到右依次遍历每个数并插入到树状数组中,如果遍历到一个数的时候在他的前面已经有一个相同的数时,将之前位置上的数从树状数组中删除。然后我们每处理完一个位置上的数后,看这个位置上是否有右端点,如果有则做一次求和,这个右端点属于的区间【L,R】的值即sum(R)-sum(L-1)。

【一百一十】【算法分析与设计】[SDOI2009] HH的项链,树状数组应用,查询区间的种类数,树状数组查询区间种类数

P1972 [SDOI2009] HH的项链 [SDOI2009] HH的项链 题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。 有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答…… 因为项链实在是太长了。

P1972 [SDOI2009]HH的项链(树状数组离线,主席树)

题意: 多次询问 [ l , r ] [l,r] [l,r]中有多少不同的数。 思路: 本题卡了莫队。 树状数组离线:每个点代表这个位置的值,然后每次遇到这个数,就把上次的位置清空。这样当前维护的区间里面就没有重复数了。 可持久化线段树:其实和树状数组离线一样,就是基于上一个前缀的线段树,将当前位置的值设置为 a [ i ] a[i] a[i],同时将 a [ i ] a[i] a[i]上一

BZOJ 1876 [SDOI2009]SuperGCD 高精度 更相减损术

Description Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GCD(最大公约 数)!因此他经常和别人比 赛计算GCD。有一天Sheng bill很嚣张地找到了你,并要求和你比 赛,但是输给Sheng bill岂不是很丢脸!所以你 决定写一个程序来教训他。 Input 共两行: 第一行:一个数A。 第二行:一个数B。 0 < A ,

[SDOI2009]HH去散步 [矩阵乘法+DP] (hard)

传送门 此题较难 , 留一个坑 传送门  #include<bits/stdc++.h>#define N 55#define M 205#define Mod 45989using namespace std;struct Matrix{int a[M][M];Matrix(){memset(a,0,sizeof(a));}};int n,m,t,a,b,ans;

bzoj1880 [Sdoi2009]Elaxia的路线

传送门 Description 最近,Elaxia和w* * 的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w * * 每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w * *所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一

[BZOJ1878] [SDOI2009]HH的项链

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1878 题目大意 给定一个序列,求一个区间内有多少个不同的数 题解 核心是离线处理 我们先定义next[i]表示i后面第一个与i颜色相同的位置 我们先考虑对于初始时处理询问区间[1..R]的情况,我们只对每个颜色第一个位置处赋值为1,其余赋值为0,那么答案就是区间和 当我们把左

SDOI2009

[BZOJ1875] [SDOI2009]HH去散步 题目大意 给定 n(n≤20) n(n\le20)个点, m(m≤60) m(m\le60)条边的无向图(有重边,无自环),要求沿一条边的某一方向走完后不能立即走同一条边的反向,每条边长为1,询问从 S到T S到T路径长度为 P P的方案数题解 有2∗m2*m条有向边,构造矩阵,若从第i条边的终点可以走第j条边,那么 x[i,j]=1

Bzoj 1877: [SDOI2009]晨跑(费用流)

1877: [SDOI2009]晨跑 Time Limit: 4 Sec Memory Limit: 64 MB Submit: 2017 Solved: 1094 [Submit][Status][Discuss] Description Elaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。 现在给出一张学校附

【SDOI2009】bzoj1878 HH的项链【解法一】

Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此, 他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同 的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解 决这个问题。 Input 第一行

BZOJ 1878 [SDOI2009]HH的项链 (莫队算法)

题意: 给你n个数字,然后查询某个区间有多少种数字 思路: 莫队裸题,用一个cnt维护区间数字的数量就能实现o(1)转移了 错误及反思: 代码: #include<bits/stdc++.h>using namespace std;const int maxn= 50000+10;const int maxm= 1000000+10;int pos[maxn];int cnt

[SDOI2009]HH的项链 和 [HEOI2012]采花两题树状数组解法对比分析

https://www.luogu.com.cn/problem/P1972 HH的项链这个题是静态区间查询的问题,如果用树状数组来解决,那么容易想到的方法是比如说问 [ l , r ] 的 [l,r]的 [l,r]的不同贝壳数量,那么我如果用树状数组维护区间的不同贝壳数,那么答案应该是 q u e r y ( r ) − q u e r y ( l − 1 ) query(r)-query(l

洛谷 P1972 [SDOI2009]HH的项链

题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。 输入输出格式 输入格式: 第一行:一个

BZOJ1878 [SDOI2009]HH的项链(莫队算法)

Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一 段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此他的项链变得越来越长。有一天,他突然提出了一 个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只 好求助睿智的你,来解决这个问题。 Input