[刷题记录]POI2000 - jcvb

[刷题记录]POI2000

jcvb posted @ 2013年12月27日 21:02 in 未分类 , 4961 阅读

终于能完整刷完一届POI好高兴= =(其实还剩一道交互题。。)

Where to Build a Brewery?
假设1~n顺时针排列。记选择的地址为x,x+1~p的城市逆时针走,p+1~x-1的城市顺时针走。
首先算x=1时的p值以及答案,再逐步推得x=2,3,…时的答案(需预处理需求与距离的前缀和)。x顺时针移动的过程中p也会顺时针移动,恰好移动一圈,所以复杂度线性。
(从n绕到1的时候细节有些坑要注意)


Skiers
网络流裸题。拆点求最大流。
(标解似乎是贪心,尽可能选择靠右的路线。。因为它是个平面图而且还给定了左右顺序)


Stripes
每放置一条带子就把整条纸带分为左右独立的两个子游戏。
直接递推求出SG函数即可。


Viruses
所有串读进来建成AC自动机(DZY告诉我这其实叫做Trie图),把不允许到达的结点(串末尾字符,或者能fail到串末尾字符)作上标记。然后DFS检查是否有不经过标记的环。


Signatures
从每个commander开始DFS。复杂度O(n)*O(n)=O(n^2)。


Automorphisms
将置换分解成k个轮换。
首先分析同一个轮换内的点之间的连边情况:
考虑某一个轮换,假设其为a_1->a_2->…->a_p。则在所求的图中,边(a_1,a_2),(a_2,a_3),……(a_p-1,a_p),(a_p,a_1)同向,边(a_1,a_3),(a_2,a_4),……,(a_p,a_2)也同向,……。可以发现p必须为奇数,否则能得出(a_p,a_p/2)与(a_p/2,a_p)同向,矛盾。当p为奇数时,按照上面的方法可以把所有这C(p,2)条边分成(p-1)/2组,每组内的边同向,于是有2^((p-1)/2)种方案。
再来分析不同轮换的点之间的连边:
假设两个轮换分别是a_1->a_2->…->a_p,b_1->b_2->…b_q。则边(a_1,b_1),(a_2,b_2),…同向。容易知道所有这p*q条边可分成gcd(p,q)组,每组内的边同向。方案数即为2^gcd(p,q)。
接下来关键在于统计[tex]\sum_{1\leq i < j \leq k}\text{gcd}(p[i],p[j])[/tex]。暴力只有65分。
O(nlogn)统计x[j]表示满足j|x[i]的i的数量。
然后令y[j]=C(x[j],2),即为满足j|gcd(p,q)的无序对(p,q)的数量。
倒过来容斥,O(nlogn)得到z[j],表示j==gcd(p,q)的无序对(p,q)数量。全部加起来即可。


Triple-Arm Crane
令p<=q。
设i是从左到右第一个未被占据的格子,如果此时i+p未被占据,则填上i,i+p,i+p+q(为方便叙述记为“对i进行p操作");否则填上i,i+q,i+p+q("对i进行q操作")。
为证明这个贪心操作可以一直进行下去,只需证明不存在i+p,i+q同时已被占据的情况:
如果是这样,注意到此时i未被占据,则可以证明i+q必是由于对i-p进行了q操作而被填上的。但根据我们的摆放策略,i-p+p=i未被占据时本应该优先进行p操作,出现了矛盾。


Code
首先预处理出Catalan数C[i]。
若确定根结点为某个字母x,则其左右子树大小分别为x-1,n-x,此时的方案数即为C[x-1]*C[n-x]。
由于根是字典序最优先者,于是可以根据K的大小确定根结点的字母x,以及所要求方案在根节点为x的所有方案中的排名K'。
按字典序,左子树是第二优先,右子树是第三优先,所以左子树应该取第K'/C[x-1],右子树应该取第K'%C[x-1],递归处理即可。


The Labyrinth of Wells
题意有点绕,其实就是说颜色相同且三个出口分别对应相同(注意有可能是合并后才相同)两个结点是相同的,可以合并,求最后合并完后剩下几个结点。
题目说明保证了拓扑序,所以可以按拓扑排序逆序枚举结点i,检查i能否与i-1,i-2,…合并,合并时只需对被吞并的结点打一个标记即可。这样复杂度是O(n^2),在main上被卡了。。。
于是把检查的过程改为hash表(用map就行),直接就能找到哪些结点需要合并。注意i和j合并后,需要将其他指向j的结点改为指向i,会导致这些结点hash值的改变。
(低端做法求不鄙视=-=)


Lollobrigida
(突然联想到今年NOIPDAY2第二题。。好吧还是挺不一样的。。)
容易想到一大一小交替放置。容易发现无解总是由于相同的元素不得不相邻摆放而导致的。
将a[1..n]排序。
若n为偶数,按a[n/2+1],a[1],a[n/2+2],a[2],a[n/2+3],a[3],…,a[n],a[n/2]排列。若这个序列不合法,则必然存在a[n/2+i]==a[i],从而有a[i]==a[i+1]==a[i+2]==…=a[n/2+i],即有n/2+1个数相同,此时可由抽屉原理证明必然无解。
n为奇数时也可类似构造,但需要特判前(n+1)/2或后(n+1)/2个数相同的情况。


P-Broken-Line
把所有出现过的X坐标离散化。注意x=-∞和x=+∞也要放入。注意若排序后x0,x1相邻,且x1-x0>=2,则要在x0,x1间加一个点;若x1-x0==1则不用。
Y坐标也一样离散化。然后形成了一个XLEN*YLEN的网格,其中XLEN,YLEN的大小都是O(n)的。把线段占据的位置标为障碍。
为了求得最小转弯次数,BFS即可,对u扩展就是从u向四周伸展的一个十字形(遇到障碍则break),扩展得到的新结点加入队列,转弯次数=u的转弯次数+1。
O(n^2)个结点,每次扩展O(n),总复杂度O(n^3)可过。


Agents
令状态为(v1,v2),表示此时a,b分别处于v1,v2两个点上。状态数O(n^2),于是答案为O(n^2)级别。
BFS,每次转移需要考虑v1的出边和v2的出边,复杂度为O(deg[v1]*deg[v2])=O(n^2)。总复杂度O(n^2)*O(n^2)=O(n^4),TLE。
考虑优化,把一次转移拆成两次转移,a先走一步,b后走一步。把状态表示为(v1,v2,bo),bo=true/false表示下一步轮到a/b走。这样状态数仍然是O(n^2),但每次转移只需考虑其中一个点的出边,O(n)。总复杂度O(n^2)*O(n)=O(n^3)可过。


Repetitions
后缀数组求height以后二分。(数据范围太弱似乎可以暴力)


Promotion
需要支持插入单个元素,查询并删除最大值,查询并删除最小值。
用set能在bzoj上水过,但在main上被卡成80分。改成手写treap依然80。
改用一个小根堆和一个大根堆同时维护这一堆数,数值相同的仅记录出现次数。同时对次数不为零的数值记录其对应结点在堆中的位置,方便删除。
这样在main上是94分,加上fread就能100。(标解应该没那么无耻吧。。也许是某种神奇优化)


 

RBL bank credit card 说:
2022年8月08日 15:20

RBL Bank is one of India’s largest private sector banks which is well known for its vast services to their customers, and in the same context they exemplary provide credit card service to customers delight has been a huge success for both the Bank and customers as well. RBL bank credit card payment If you have your own RBL credit card whose limit is already crossed and the payment date is near then it’s time for you to be ready and be able to make your credit card payment quickly.Its the time for you to follow this guide which will help you understand more about the different ways presented by 25penny.com and learn more information about the process related to RBL card payment.

TBSE Model Paper 说:
2022年8月19日 14:31

Tripura Board Model Paper 2023 Pdf Download for TBSE Sample Model Question Paper for Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, +1 & +2 Arts, Science & Commerce Stream Theory, Objective (MCQ) and Bit Questions to English Medium, Hindi Medium and others. TBSE Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

AP SSC General Scien 说:
2022年9月16日 21:57

All Andhra Pradesh State Class 10th (SSC) Students can download AP SSC Science model paper 2023 with Answer solutions in Chapter by Chapter for Physical Science, Chemistry, Biological Science and Environmental science for AP SSC Science Model Paper 2023 examination test for Unit Test-1, Unit Test-2, AP SSC General Science Question Paper Unit Test-3, Unit Test-4, and Quarterly, Half Yearly, Pre-Final with Annual final examination tests 2023. The Andhra Pradesh State Board of Secondary Education has published the General Science model paper with study material with practice paper with mock test question bank as AP 10th Biology, PS, Chemistry Model Paper 2023 for all examination tests conducted by BSEAP.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee