【POI2012】bzoj刷波兰计划 I

6
11
2015

总感觉最近颓的不对，于是刷刷波兰人的题来平复一下心情：

[6.23] qiancl：已弃疗

剩下的几道题 ↓

Y	2788	[Poi2012]Festival	orzRxd	58	102
Y	2789	[Poi2012]Letters	orzRxd	137	203
Y	2790	[Poi2012]Distance	orzRxd	99	193
	2791	[Poi2012]Rendezvous	orzRxd	60	81
	2792	[Poi2012]Well	orzRxd	41	99
Y	2793	[Poi2012]Vouchers	orzRxd	127	272
Y	2794	[Poi2012]Cloakroom	orzRxd	98	136
Y	2795	[Poi2012]A Horrible Poem	orzRxd	105	186
Y	2796	[Poi2012]Fibonacci Representation	orzRxd	101	170
Y	2797	[Poi2012]Squarks	orzRxd	67	162
Y	2798	[Poi2012]Bidding	orzRxd	27	76
	2799	[Poi2012]Salaries	orzRxd	43	70
	2800	[Poi2012]Leveling Ground	orzRxd	28	40
Y	2801	[Poi2012]Minimalist Security	orzRxd	39	183
Y	2802	[Poi2012]Warehouse Store	orzRxd	102	194
Y	2803	[Poi2012]Prefixuffix	orzRxd	71	150

[2789 Letters]：逆序对

[2793 Vouchers]：考虑1-100w的数，然后last[x]记录x的倍数取到了last[x]，下次取x的倍数就从last[x]+x开始。。。

[2795 A Horrible Poem]：对于每个子串，循环节一定是长度的约数，知道了长度可以Hash O(1)验证。。但是这样O(n√n)是卡常数，于是分解质因数= =

[2796 Fibonacci Representation]：选的一定是最接近的两个数，直接记忆化搜索

[2802 Warehouse Store]：堆维护贪心

[2797 Squarks]：确定a[1]+a[2]，a[1]+a[3],枚举a[2]+a[3]

[2798 Bidding]：赶脚暴力DP就可以了，AC数这么少= =应该不是，然而我看到AC的代码都好诡异，于是我手贱点了Discuss

[2788 Festival]：先构出差分约束的图，然后强连通缩点，ans就是点与点之间距离的max

[2790 Distance]：负责过度的就是两数的最大公约数，向上做就行了

[2803 Prefixuffix]：hash一下。。然而我的hash连自己造的长度为12的串都能卡掉= =|||于是我去膜拜了一下大神

[2794 Cloakroom]：背包= =|||

[2801 Minimalist Security]：每个联通块设个未知数，然后验证每条边

Category: bzoj | Tags: 坑 | Read Count: 4060

此博客停更