月度归档:2017年05月

BZOJ 4195: [Noi2015]程序自动分析(离散化后并查集)

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”表示不可被满足。

Sample Input

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

Sample Output

NO
YES

HINT

 在第一个问题中,约束条件为:x1=x2,x1≠x2。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:x1=x2,x2=x1。这两个约束条件是等价的,可以被同时满足。
1≤n≤1000000
1≤i,j≤1000000000
离散化后直接把相等的连到一个并查集上,然后处理不等关系看能不能满足题意。。。
一开始没注意需要离散化。。。居然wa了。。。

 

BZOJ 2440: [中山市选2011]完全平方数(莫比乌斯函数的应用)

Description

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第 K个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?

Input

包含多组测试数据。文件第一行有一个整数 T,表示测试
数据的组数。
第2 至第T+1 行每行有一个整数Ki,描述一组数据,含义如题目中所描述。

Output

含T 行,分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

HINT

对于 100%的数据有 1 ≤ Ki ≤ 10^9

,    T ≤ 50

最近学了一下莫比乌斯函数,因为没有学多少所以就先不总结了,这个题目就是个莫比乌斯函数的运用,没有反演什么的知识。

我们二分数字的范围,问题就变成了找某个范围内有多少个没有平方因子的数。这个东西可以容斥:

最后的答案就是n-每个质因子的平方的倍数数目+两个质因子的平方的倍数数目….以此类推,发现前面的系数正好对应了莫比乌斯函数\(\mu\)的值,所以\(ans=\sum_{i=1}^{\sqrt(n)}\mu(i)*\frac{n}{i*i}\)

 

BZOJ 1531: [POI2005]Bank notes(单调队列优化多重背包)

Description

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为b1, b2,…, bn. 但是每种硬币有数量限制,现在我们想要凑出面值k求最少要用多少个硬币.

Input

第一行一个数 n, 1 <= n <= 200. 接下来一行 n 个整数b1, b2,…, bn, 1 <= b1 < b2 < … < b n <= 20 000, 第三行 n 个整数c1, c2,…, cn, 1 <= ci <= 20 000, 表示每种硬币的个数.最后一行一个数k – 表示要凑的面值数量, 1 <= k <= 20 000.

Output

第一行一个数表示最少需要付的硬币数

Sample Input

3
2 3 5
2 2 1
10

Sample Output

3
看了一下单调队列优化背包的内容,写了个题练手。
多重背包一般的dp式子:\(dp[i][j]=dp[i-1][j-k*w[i]]+k*v[i],0 \leq k\leq S\),\(S\)是对于第\(i\)种物品可以放的最大个数。
我们可以转化一下对于体积的表示:\(j=a*w[i]+b\),那么带进去原式子:\(dp[i][j]=max\{dp[i-1][(a-k)*w[i]+b]+k*v[i]\}=max\{dp[i-1][(a-k)*w[i]+b]-(a-k)*v[i]+a*v[i]\}\)。假设\(x=a-k\),那么得到最后的dp式子为:\(dp[i][j]=max\{dp[i-1][x*w[i]+b]-x*v[i]\}+a*v[i]\)。这个东西很明显可以通过单调队列来优化的,我们可以让单调队列起到一个滚动数组的作用,省去一维。
贴一下代码,作为个大概的板子吧。一定不要忘记我们在往单调队列放值的时候需要减去\(j*w[i]\)