嘿嘿~_第 1 行包含 2 个整数,依次为 n,m,表示 drd 有 n 扇防御门,atm 的初始攻击力为 -程序员宅基地

1026: [SCOI2009]windy

Time Limit: 1 Sec  MemoryLimit: 162 MB
Submit: 6924  Solved: 3123
[Submit][Status][Discuss]

Description

  windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,
在A和B之间,包括A和B,总共有多少个windy数?

Input

  包含两个整数,A B。

Output

  一个整数

Sample Input

【输入样例一】

1 10

【输入样例二】

25 50

Sample Output

【输出样例一】

9

【输出样例二】

20

HINT

【数据规模和约定】

100%的数据,满足 1 <= A <= B <= 2000000000 。

 

讲道理  这是一道数位 DP 当然数位 dp我不是很擅长,不过这道题目好事原先的套路

f[i][j]表示i位数,以j开头的windy的数量。

首先预处理f[i][j]的值。然后对于到x的windy数的个数我们分三种情况讨论。len为x的位数

1.位数小于len,直接加上f[i][j]

2.位数等于len,j<x的开头,加上f[len][j]

3.位数等于len,枚举每一位的情况。

 

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec  MemoryLimit: 162 MB
Submit: 5032  Solved: 2669
[Submit][Status][Discuss]

Description

  每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这

种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

Input

  第一行两个数N,M。 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可

能出现多个A,B)

Output

  一个数,即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

HINT

100%的数据N<=10000,M<=50000

Source

用强联通分量暴力缩点,找到出度为0的点。如果有多个出度为零的点,那么就不存在受所有牛欢迎的牛。否则答案就为出度为零的点所对应强联通分量的大小。

 

1192: [HNOI2006]鬼谷子的钱袋

Time Limit: 10 Sec  MemoryLimit: 162 MB
Submit: 3340  Solved: 2432
[Submit][Status][Discuss]

Description

鬼谷子非常聪明,正因为这样,他非常繁忙,经常有各诸侯车的特派员前来向他咨询时政。有一天,他在咸阳游历的时候,朋友告诉他在咸阳最大的拍卖行(聚宝商行)将要举行一场拍卖会,其中有一件宝物引起了他极大的兴趣,那就是无字天书。但是,他的行程安排得很满,他他已经买好了去邯郸的长途马车标,不巧的是出发时间是在拍卖会快要结束的时候。于是,他决定事先做好准备,将自己的金币数好并用一个个的小钱袋装好,以便在他现有金币的支付能力下,任何数目的金币他都能用这些封闭好的小钱的组合来付账。鬼谷子也是一个非常节俭的人,他想方设法使自己在满足上述要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数。假设他有m个金币,你能猜到他会用多少个钱袋,并且每个钱袋装多少个金币吗?

Input

包含一个整数,表示鬼谷子现有的总的金币数目m。其中,1≤m ≤1000000000。

Output

只有一个整数h,表示所用钱袋个数

Sample Input

3

Sample Output

2

HINT

就是拆成 2的k次方  就可以啦因为 2的k 次方组合起来可以合成所有的数啊hh

难得一见的水题啊

 

 

1269: [AHOI2006]文本编辑器editor

Time Limit: 10 Sec  MemoryLimit: 162 MB
Submit: 3929  Solved: 1483
[Submit][Status][Discuss]

Description

这些日子,可可不和卡卡一起玩了,原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗?为了明确任务目标,可可对“文本编辑器”做了一个抽象的定义:     文本:由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内,也就是说,这些字符均为可见字符或空格。光标:在一段文本中用于指示位置的标记,可以位于文本的第一个字符之前,文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器:为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。 编写一个程序:l 建立一个空的文本编辑器。l 从输入文件中读入一些操作指令并执行。l 对所有执行过的GET操作,将指定的内容写入输出文件。

Input

输入文件中第一行是指令条数N,以下是需要执行的N个操作。除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。

Output

依次对应输入文件中每条GET指令的输出,不得有任何多余的字符。

Sample Input

10

Insert 13

Balanced eert

Move 2

Delete 5

Next

Insert 7

 editor

Move 0

Get

Move 11

Rotate 4

Get

Sample Output

B

t



HINT

对输入数据我们有如下假定:l MOVE操作不超过50 000个,INSERT、DELETE和ROTATE操作作的总个数不超过6 000,GET操作不超过20 000个,PREV和NEXT操作的总个数不超过20 000。l 所有INSERT插入的字符数之和不超过2M(1M=1 024*1 024)。l DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。l 输入文件没有错误。

Blabla一大堆  其实就是一个 伸展树!!反正用伸展树来处理就好了

那个。。。不过好像有更加简单的处理方式。。

但是我不会说的!!!!感觉自己好ZZ

 

 

1503: [NOI2004]郁闷的出纳员

Time Limit: 5 Sec  MemoryLimit: 64 MB
Submit: 11075  Solved: 3885
[Submit][Status][Discuss]

Description

OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?

Input

Output

输出文件的行数为F命令的条数加一。对于每条F命令,你的程序要输出一行,仅包含一个整数,为当前工资第k多的员工所拿的工资数,如果k大于目前员工的数目,则输出-1。输出文件的最后一行包含一个整数,为离开公司的员工的总数。

Sample Input

9 10

I 60

I 70

S 50

F 2

I 30

S 15

A 5

F 1

F 2



Sample Output

10

20

-1

2



HINT

I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000

Source

概括一下哈  整体加减  然后单个删除或者增加   询问区间第 K 大  用伸展树就可以的,  伸展树真的是个好东西啊  。0.0

 

 

 

 

1507: [NOI2003]Editor

Time Limit: 5 Sec  MemoryLimit: 162 MB
Submit: 3593  Solved: 1463
[Submit][Status][Discuss]

Description

Input

输入文件editor.in的第一行是指令条数t,以下是需要执行的t个操作。其中: 为了使输入文件便于阅读,Insert操作的字符串中可能会插入一些回车符,请忽略掉它们(如果难以理解这句话,可以参考样例)。 除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定: l MOVE操作不超过50000个,INSERT和DELETE操作的总个数不超过4000,PREV和NEXT操作的总个数不超过200000。 l 所有INSERT插入的字符数之和不超过2M(1M=1024*1024),正确的输出文件长度不超过3M字节。 l DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。 l 输入文件没有错误。 对C++选手的提示:经测试,最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。

Output

输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。

Sample Input

15

Insert 26

abcdefghijklmnop

qrstuv wxy

Move 15

Delete 11

Move 5

Insert 1

^

Next

Insert 1

_

Next

Next

Insert 4

.\/.

Get 4

Prev

Insert 1

^

Move 0

Get 22

Sample Output

.\/.

abcde^_^f.\/.ghijklmno

HINT

讲道理和上面那个题目一样  不是么?

所以BZOj是在划水?hhh~~

 

 

1588: [HNOI2002]营业额统计

TimeLimit: 5Sec  Memory Limit: 162 MB
Submit: 15069  Solved: 5897
[Submit][Status][Discuss]

Description

营业额统计 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况: 该天的最小波动值 当最小波动值越大时,就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 l 输入输出要求

Input

第一行为正整数 ,表示该公司从成立一直到现在的天数,接下来的n行每行有一个整数(有可能有负数) ,表示第i天公司的营业额。

Output

输出文件仅有一个正整数,即Sigma(每天最小的波动值) 。结果小于2^31 。

SampleInput

6

5

1

2

5

4

SampleOutput

12

HINT

结果说明:5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

 

该题数据bug已修复.----2016.5.15

Source

每次插入后,插入节点都会被调整带根节点,而且满足中序遍历是个有序集合,类似于二叉搜索树。所以每次插入后,我们只需要查找根节点左子树中的最大值和右子树中的最小值就可以啦!!!

 

 

1798: [Ahoi2009]Seq 维护序列seq

TimeLimit: 30Sec  Memory Limit: 64 MB
Submit: 5973  Solved: 2126
[Submit][Status][Discuss]

Description

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。

Input

第一行两个整数N和P(1≤P≤1000000000)。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN,(0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M,表示操作总数。从第四行开始每行描述一个操作,输入的操作有以下三种形式: 操作1:“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c(1≤t≤g≤N,0≤c≤1000000000)。 操作2:“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3:“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

Output

对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。

SampleInput

7 43

1 2 3 4 5 6 7

5

1 2 5 5

3 2 4

2 3 7 9

3 1 3

3 4 7



SampleOutput

2

35

8

 

这个是线段树区间操作 需要用到懒惰标记的是,然后那 这个题目需要用到乘法!!区间相乘   区间相加的时候懒惰标记 直接记录就好了  那如果先相加再相乘  Add这个懒惰标记怎么搞??难道我们去把Add标记全部更新到叶子节点吗?不需要!!!我们只要正常搞就行了!!加上一个mul 作为乘的懒惰标记  向下更新的时候

Sum = sum * mul + add *区间           

!!!!! 就这昂!!!

 

1854: [Scoi2010]游戏

TimeLimit: 5Sec  Memory Limit: 162 MB
Submit: 4852  Solved: 1908
[Submit][Status][Discuss]

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

SampleInput

3

1 2

3 2

4 5

SampleOutput

2

 

我是二分图跑那个最大匹配跑出来的,wa到我怀疑世界。。。。

最后居然是 输出一个小细节写错了。。。写错了。。。。写错了。。。

不过网上有另外的解法 用并查集 维护连通块 他说的是啥?我没多想。

直接按照武器属性去连边武器就好了,让后跑匈牙利算法。嗯

 

 

 

2243: [SDOI2011]染色

TimeLimit: 20Sec  Memory Limit: 512 MB
Submit: 7035  Solved: 2623
[Submit][Status][Discuss]

Description

给定一棵有n个节点的无根树和m个操作,操作有2类:

1、将节点a到节点b路径上所有点都染成颜色c;

2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m,分别表示节点数和操作数;

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y,表示xy之间有一条无向边。

下面 行每行描述一个操作:

“C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成颜色c;

“Q a b”表示这是一个询问操作,询问节点a到节点b(包括a和b)路径上的颜色段数量。

Output

对于每个询问操作,输出一行答案。

SampleInput

6 5



2 2 1 2 1 1



1 2



1 3



2 4



2 5



2 6



Q 3 5



C 2 1 1



Q 3 5



C 5 1 2



Q 3 5



SampleOutput

3



1



2

 

那个虽然这是一个很显然的树链剖分,但是对我这样的ZZ 来说调个一天完全没问题啊,道理我都懂,我就是写不出来,。。。尤其是维护那个东西的时候,维护当前区间有多少个重复段!!!是从下向上更新,这里特别不好弄!!!但是道理就是很显然的,对不对?但是我就是写不出来,你说气人不气人?!还是用懒标,如果当前区间没被修改过,连续段还是原先那样,如果被修改那就更新呗。Good Game!

 

2761: [JLOI2011]不重复数字

TimeLimit: 10Sec  Memory Limit: 128 MB
Submit: 4389  Solved: 1647
[Submit][Status][Discuss]

Description

给出N个数,要求把其中重复的去掉,只保留第一次出现的数。

例如,给出的数为1 2 18 3 319 2 3 6 5 4,其中2和3有重复,去除后的结果为1 2 18 3 196 5 4。

 

Input

输入第一行为正整数T,表示有T组数据。

接下来每组数据包括两行,第一行为正整数N,表示有N个数。第二行为要去重的N个正整数。

 

Output

 

对于每组数据,输出一行,为去重后剩下的数字,数字之间用一个空格隔开。

SampleInput

2

11

1 2 18 3 3 19 2 3 6 5 4

6

1 2 3 4 5 6

SampleOutput

1 2 18 3 19 6 5 4

1 2 3 4 5 6

 

额  暴力直接 Set 水过了 难得一见。0.0  我好厉害  hhh~

 

 

3224: Tyvj 1728 普通平衡树

TimeLimit: 10Sec  Memory Limit: 128 MB
Submit: 11003  Solved: 4716
[Submit][Status][Discuss]

Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)

Input

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数,表示对应答案

SampleInput

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

SampleOutput

106465

84185

492737

 

 

题目都说了 是一个Splay 裸题目,但是我看到网上好多人用了 Treap 实现的,没啥好说的。

以后不要用指针了!!!!不仅丑 还容易 RE!!!

还有你的 AC 自动机,再用 指针你就是狗!!!!

 

3668: [Noi2014]起床困难综合症

TimeLimit: 10Sec  Memory Limit: 512 MB
Submit: 1959  Solved: 1093
[Submit][Status][Discuss]

Description

21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因:在深邃的太平洋海底中,出现了一条名为drd 的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。正是由于drd 的活动,起床困难综合症愈演愈烈,以惊人的速度在世界上传播。为了彻底消灭这种病,atm决定前往海底,消灭这条恶龙。历经千辛万苦,atm终于来到了 drd 所在的地方,准备与其展开艰苦卓绝的战斗。drd有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd的防御战线由 n扇防御门组成。每扇防御门包括一个运算op和一个参数t,其中运算一定是OR,XOR,AND中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为x,则其通过这扇防御门后攻击力将变为xop t。最终drd受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。由于atm水平有限,他的初始攻击力只能为0到m之间的一个整数(即他的初始攻击力只能在0,1,...,m中任选,但在通过防御门之后的攻击力不受 m的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使drd 受到多少伤害。

Input

第1行包含2个整数,依次为n,m,表示drd有n扇防御门,atm的初始攻击力为0到m之间的整数。接下来n行,依次表示每一扇防御门。每行包括一个字符串op和一个非负整数t,两者由一个空格隔开,且op在前,t在后,op表示该防御门所对应的操作, t表示对应的参数。n<=10^5

Output

一行一个整数,表示atm的一次攻击最多使 drd 受到多少伤害。

SampleInput

3 10

AND 5

OR 6

XOR 7

SampleOutput

1

 

 

那个  位运算相互之间是互不影响的,这个可以说是贪心吧?应该不算  dp 的

所以我们去枚举每一位 0 或者  1 然后最后再比较就可以了 

美滋滋  讲道理  想法能写的都是好题!!!

 

4034: [HAOI2015]树上操作

TimeLimit: 10Sec  Memory Limit: 256 MB
Submit: 3759  Solved: 1197
[Submit][Status][Discuss]

Description

有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个

操作,分为三种:

操作 1 :把某个节点 x 的点权增加 a 。

操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

Input

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 

行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。再接下来 M 行,每行分别表示一次操作。其中

第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。

Output

对于每个询问操作,输出该询问的答案。答案之间用换行隔开。

SampleInput

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3

Sample Output

6

9

13

 

树链剖分!  对于  1 操作  直接加 就可以了,

对于 2 操作 ,加的时候 是写 id[ x ] 到 id [ x ] 嗯 因为这样就表示了以他为根的这个东西啦!

对于操作 3 也是直接用重链进行加速 求和就可以了。嗯 没错 ,就是这样的。

 

 

4195: [Noi2015]程序自动分析

TimeLimit: 10Sec  Memory Limit: 512 MB
Submit: 1793  Solved: 812
[Submit][Status][Discuss]

Description

 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设x1,x2,x3,…代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

Input

输入文件的第1行包含1个正整数t,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第1行包含1个正整数n,表示该问题中需要被满足的约束条件个数。

接下来n行,每行包括3个整数i,j,e,描述1个相等/不等的约束条件,相邻整数之间用单个空格隔开。若e=1,则该约束条件为xi=xj;若e=0,则该约束条件为xi≠xj。

Output

输出文件包括t行。

输出文件的第k行输出一个字符串“YES”或者“NO”(不包含引号,字母全部大写),“YES”表示输入中的第k个问题判定为可以被满足,“NO”表示不可被满足。

SampleInput

2

2

1 2 1

1 2 0

2

1 2 1

2 1 1

SampleOutput

NO

YES

 

一个需要先离散化 再用并查集维护的题目。

因为这样就行了 ,我们先把所有满足相等关系的放到一个并查集中进行维护,然后我们再去看不相等的那些东西,如果他们是在同一个并查集那么就是不满足题目。

所以这个题目最重要是先离散化  对吧?

嗯   感觉这个题目挺好的  简单粗暴!!!  赞一个

 

4196: [Noi2015]软件包管理器

TimeLimit: 10Sec  Memory Limit: 512 MB
Submit: 1478  Solved: 836
[Submit][Status][Discuss]

Description

 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,…,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,Am−1依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。

Input

输入文件的第1行包含1个正整数n,表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,…,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个正整数q,表示询问的总数。

之后q行,每行1个询问。询问分为两种:

installx:表示安装软件包x

uninstallx:表示卸载软件包x

你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。

Output

输出文件包括q行。

输出文件的第i行输出1个整数,为第i步操作中改变安装状态的软件包数。

SampleInput

7

0 0 0 1 1 5

5

install 5

install 6

uninstall 1

install 4

uninstall 0

SampleOutput

3

1

3

2

3

 

 

树链剖分~

设已安装的为1,未安装的为0。

对于安装操作,就是询问x到0的路径上0的个数,然后把这个路径赋为1

对于卸载操作,就是询问x的子树中1的个数,然后把子树赋为0。

感觉树链剖分这里还是需要很厉害的线段树才能搞。。。

啧啧   自己的水平真的是太LLLLLLL了。

 

 

4602: [Sdoi2016]齿轮

TimeLimit: 10Sec  Memory Limit: 512 MB
Submit: 486  Solved: 256
[Submit][Status][Discuss]

Description

现有一个传动系统,包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v,并提供了一个传动比x 

: y。即如果只考虑这两个组合齿轮,编号为u的齿轮转动x圈,编号为v的齿轮会转动y圈。传动比为正表示若编号

为u的齿轮顺时针转动,则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动,则编号为v

的齿轮会逆时针转动。若不同链条的传动比不相容,则有些齿轮无法转动。我们希望知道,系统中的这N个组合齿

轮能否同时转动。

Input

有多组数据,第一行给定整数T,表示总的数据组数,之后依次给出T组数据。每一组数据的第一行给定整数N和

M,表示齿轮总数和链条总数。之后有M行,依次描述了每一个链条,其中每一行给定四个整数u,v,x和y,表示

只考虑这一组联动关系的情况下,编号为u的齿轮转动x圈,编号为v的齿轮会转动y圈。请注意,x为正整数,而y为

非零整数,但是y有可能为负数。

T<=32,N<=1000,M<=10000且x与y的绝对值均不超过100

Output

输出T行,对应每一组数据。首先应该输出标识这是第几组数据,参见样例输出。之后输出判定结果,如果N个组合

齿轮可以同时正常运行,则输出Yes,否则输出No。

SampleInput

2

3 3

1 2 3 5

2 3 5 -7

1 3 3 -7

3 3

1 2 3 5

2 3 5 -7

1 3 3 7

SampleOutput

Case #1: Yes

Case #2: No

 

 

这是个 边为传送比 然后进行 dfs!!如果搜索到矛盾 那么 GG

如果没搜索到矛盾 那就 AC。。。

强行去搜索每条边的权值,如果和之前的冲突那么就说明不可以呗。

但是!!!这里有精度的问题……

我有一组错误样例 不知当讲不当讲

3 3

1 2 1 -1

2 3 1 1

1 3 1 1

这样的话  1  2是相反的    2 3  是相同方向的  1  3 是相同方向的

但是  明显  1  3这个关系和前面矛盾了。所以应该是 NO

但是我的输出 YES  却还是  AC了   我…….

是什么鬼?

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33402621/article/details/58599195

智能推荐

DS212j、DS213+、DS413 找不到 Synology Drive Server 套件_ds212j管理-程序员宅基地

文章浏览阅读2.4k次。其他 NAS 型号,可以于下载中心查询是否支援 Synology Drive Server 套件。_ds212j管理

weka使用_cannot resolve weka:weka:3.6.2-程序员宅基地

文章浏览阅读1.4k次。Weka新手文章(一) 收藏数据仓库,数据分析,不涉及商业方面的高层决策之用,故本篇文章只适合初学数据仓库,为了完成老师作业,且想用weka做简单数据挖掘之用的童鞋。weka版本是3.6.2,数据库库是SQL Server 2005,没办法,老师提供的几万条数据保存在excel表中,如果从excel转为csv格式,再从weka中导入该csv文件,涉及到格式的转换,很是麻烦~况且几万条数_cannot resolve weka:weka:3.6.2

三天搞定射频识别技术(一)1.2_rfid防冲突机制-程序员宅基地

文章浏览阅读1.2k次。电子标签的概念电子标签的概念二、RFID电子标签的分类:三、RFID标签的原理四、RFID标签的组成五、RFID的工作原理阅读器和电子标签之间的射频信号的耦合类型有两种:电感耦合电磁反向散射耦合六、RFID电子标签的数据存储七、RFID低频简介八、RFID高频简介九、RFID超高频简介十、RFID微波段简介RFID电子标签的防冲撞机制面向比特的防冲突机制面向时隙的防冲突机制总结)电子标签的概念电子标签又称射频标签、应答器、数据载体;是一种存储数据识别资料的装置,可以透过无线电波与读写器之间互相传递_rfid防冲突机制

web前端(sublime):将多媒体插入网页(自动播放)_sublime音乐播放器代码-程序员宅基地

文章浏览阅读1.6k次,点赞2次,收藏4次。注意:以下方法是我通过多方查找摸索拼凑出来的出来的,可能和某些书籍或博主给出的不同; 亲测能自动播放音乐,但不知道什么缘故只我再测试时只有360极速游览器可以用。 由于没开网站,效果可以自己试试(很简陋)1:代码如下:<!DOCTYPE html><html><head> <meta charset="UTF-8"> <title>歌曲</title> <style type="text/css"&g.._sublime音乐播放器代码

Android轻松搞定Dialog提示动画效果_android dialog 动画右出出入效果-程序员宅基地

文章浏览阅读8.8k次,点赞3次,收藏7次。抽个中午的时间写一篇博客,想必大家现在正在午饭呢吧,深圳的天气真是变换无常,刚刚大雨倾盆,不一会就晴天高照。打球吗?约起来哇,哈哈。。今天给大家带来一篇Dialog提示附加动画效果的功能。这种Dialog提示效果基本变成了每个App都必不可少功能。例如,退出提示,弹出分享框,App升级提示等等。。其实在Android中实现提示功能由很多种方式:自定义Dialog,AlertDialog,自_android dialog 动画右出出入效果

tff.learning 模块_tff.learning.build_federated_averaging_process-程序员宅基地

文章浏览阅读432次。tff.learning 模块用于使用联合学习算法的模型开发的公共API模块framework模块:面向开发联合学习算法的贡献者的公共API类BatchOutput类: 保存tf .learning. model输出的结构。Model类: 表示TensorFlow联邦中使用的模型。TrainableModel类: 带有用..._tff.learning.build_federated_averaging_process

随便推点

部署springboot的war包到tomcat,静态资源以及bootstrap等的url,以及controller的mapping映射等无法使用的问题_war包 静态资源必须放入 classes文件夹才能被访问到-程序员宅基地

文章浏览阅读1.7k次,点赞2次,收藏3次。最近在部署一个springboot的war文件到tomcat的时候,出现了一大堆的404,找不到的问题,在eclipse调试中不曾出现。后来仔细核实发现,原来确实是路径有问题。在浏览器可以看见他的后台访问路径如下:XHR POST http://127.0.0.1:8080/home/welcome //这是一个mapping映射,到controller......_war包 静态资源必须放入 classes文件夹才能被访问到

IIS搭建网站_iis搭建网站的基本原理-程序员宅基地

文章浏览阅读202次。一. 首先开启Windows功能在这里把你需要的服务都选中,如果你不清楚具体需要哪些,不妨全部选中。二. 进入IIS管理器三. 建站把你的网站资源和文件存到一个合适的位置,为了测试我们只用最简单的示范(稍微正经一点的网页也不会像我这么写...)。<html><body><h1>My IIS Test Page</h1></body></html>..._iis搭建网站的基本原理

pandas的聚合操作: groupyby与agg_pandas group by agg-程序员宅基地

文章浏览阅读9.5k次,点赞4次,收藏9次。pandas提供基于行和列的聚合操作,groupby可理解为是基于行的,agg则是基于列的从实现上看,groupby返回的是一个DataFrameGroupBy结构,这个结构必须调用聚合函数(如sum)之后,才会得到结构为Series的数据结果。 而agg是DataFrame的直接方法,返回的也是一个DataFrame。当然,很多功能用sum、mean等等也可以实现。但是agg更加简洁, 而..._pandas group by agg

JS实现点击下拉框改变背景颜色_js select>option鼠标滑动背景色设置-程序员宅基地

文章浏览阅读4.1k次,点赞3次,收藏25次。使用onchange事件,当点击不同下拉框选项时,改变div背景颜色以及文字效果展示代码演示<!DOCTYPE html><html> <head lang="en"> <meta charset="UTF-8"> <title>onchange()</title> <style type="text/css"> #div { width: 300px; height_js select>option鼠标滑动背景色设置

计算机基础知识+数据类型_计算机中数据的分类-程序员宅基地

文章浏览阅读2.4k次。一、计算机基础知识,Java语言的概述,运行环境及开发工具的下载安装1、计算机基础知识1.1、计算机的概念什么是计算机:(Computer)全称:电子计算机,俗称电脑。是一种能够按照程序运行,自动、高速处理数据的现代化智能电子设备。由硬件和软件所组成,没有安装任何软件的计算机称为裸机。常见的形式有台式计算机、笔记本计算机。按照规模分为微型机、小型机、大型机、巨型机(超级计算机)等。1.2、计算机的组成计算机组成大致由“计算机硬件”和“计算机软件”组成①、计算机硬件:计算机硬件(Computer_计算机中数据的分类

Mac上如何安装SketchUp Mac 2023中文激活版 支持13.x,支持 M1/M2、Intel机型,已解决在Ventura 13.x上一直打不开等问题_sketchup_pro2023 m1-程序员宅基地

文章浏览阅读1.5k次。快速导入和导出DWG,DXF,JPG,3DS格式文件,实现方案构思,效果图与施工图绘制的完美结合。专业用于 3D 建模,设计,创建和交流建筑,施工,工程等方面的创意。方便的推拉功能,设计师通过一个图形就可以方便的生成3D几何体,无需进行复杂的三维建模。适用范围广阔,可以应用在建筑,规划,园林,景观,室内以及工业设计等领域。具有草稿,线稿,透视,渲染等不同显示模式。_sketchup_pro2023 m1

推荐文章

热门文章

相关标签