离线处理 - hzwer.com

「CF528A」Glass Carving
Leonidwantstobecomeaglasscarver(thepersonwhocreatesbeautifulartworksbycuttingtheglass).Healreadyhasarectangularwmm × hmmsheetofglass,adiamondglasscutterandlotsofenthusiasm.Whathelacksisunderstandingofwhattocarveandhow.Inordernottowastetime,hedecidedtopracticethetechniqueofcarving.Todothis,hemakesverticalandhorizontalcutsthroughtheentiresheet.Thisprocessresultsinmakingsmallerrectangularfra...
12015年3月18日907STL,离线处理

「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-67683d1b18254502465675/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日3,420模拟,二分法,并查集,离线处理
「BZOJ2300」[HAOI2011] 防线修建
Description近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：给出你所有的A国城市坐标A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市，修...
42014年12月1日5,759凸包,离线处理
「BZOJ3417」POI2013 Tales of seafaring
DescriptionYoungBytenssonlovestohangoutintheporttavern,whereheoftenlistenstotheseadogstellingtheirtalesofseafaring.Initially,hebelievedthemall,howeverincredibletheysounded.Overtimethough,hebecamesuspicious.Hehasdecidedtowriteaprogramthatwillverifyiftheremaybeanygrainoftruthinthosetallstories.Bytenssonreasonedthatwhilehecannottellifthesailorsindeedweatheredallthosestorms,hecanatleastfindouti...
232014年10月29日4,724广度搜索,离线处理
「CF464C」Substitutes in Number
AndrewandEugeneareplayingagame.Initially,Andrewhasstrings,consistingofdigits.EugenesendsAndrewmultiplequeriesoftype"di → ti",thatmeans"replacealldigitsdiinstringswithsubstringsequaltoti".Forexample,ifs = 123123,thenquery"2 → 00"transformssto10031003,andquery"3 → "("replace3byanemptystring")transformsittos = 1212.AfterallthequeriesEugeneasksAndrewtofindtheremainderafterdivisi...
02014年9月8日4,010快速幂,离线处理
「BZOJ3545」[ONTAK2010] Peaks
Description在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk...
22014年8月26日7,081线段树,离线处理
「BZOJ2594」[Wc2006] 水管局长数据加强版
DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
52014年8月13日8,022kruskal,离线处理,link cut tree
「BZOJ1935」[SHOI2007] Tree 园丁的烦恼
Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道：“最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”“是的，显然这是一道经典的...
22014年8月6日5,652树状数组,离线处理
「BZOJ3626」[LNOI2014] LCA
Description给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出lrz，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）Input第一行2个整数nq。接下来n-1行，分别表示点1到点n-1的父节点编号。接下来q行，每行3个整数lrz。Output输出q行...
102014年7月28日11,849树链剖分,离线处理
「czy系列赛」czy的后宫3
czy的后宫3「题目描述」上次czy在机房妥善安排了他的后宫之后，他发现可以将他的妹子分为c种，他经常会考虑这样一个问题：在[l,r]的妹子中间，能挑选出多少不同类型的妹子呢？注意：由于czy非常丧尸，所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数，你懂得。问题简述:n个数，m次询问，每次问[l,r]区间有多少个数恰好出现正偶数次「输入格式」第一行3个整数，表示n,c,m第二行n个数，每个数Ai在[1,c]之间，表示一个Ai类型...
42014年7月19日10,158树状数组,离线处理,莫队算法
「BZOJ2506」calc
Description 给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Aimodp=k的值i的个数。Input 第一行两个正整数n和m。第二行n个数，表示A1,A2,…,An。以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。Output 对于每个询问，输出一行，表示可行值i的个数。SampleInput521...
12014年5月28日4,007离线处理
「BZOJ3585」mex
Description　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r。Output　　一行一个数，表示每个询问的答案。SampleInput55210213323241235SampleOutput12303HINT数据规模和约定对于100%的数据：1<=n,m<=2000000<=ai<=1091<=l<=r<=n对于30%的数据：1<=n,m<=1000Source此题为...
02014年5月18日7,144线段树,离线处理