hzwer.com _ Home | http://hzwer.com

« 上一页下一页 »Current position : 首页 >> 算法 >> 第44页

• 「BZOJ2300」[HAOI2011] 防线修建

  

  Description近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：给出你所有的A国城市坐标A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市，修...
  42014年12月1日5,922凸包,离线处理

• 「BZOJ2298」[HAOI2011] problem a

  

  Description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)Input第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、biOutput一个整数，表示最少有几个人说谎SampleInput3200222SampleOutput1题解100%的数据满足：1≤n≤100000  0≤ai、bi≤n求最多说真话的人数，答案即为n-ans设dp[i]表示在前i名中最多有多少人说真话dp...
  32014年12月1日5,591递推与动规

• 「BZOJ1055」[HAOI2008] 玩具取名

  

  Description某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。Input第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两...
  12014年12月1日6,035区间动规,记忆化搜索

• 「BZOJ1052」[HAOI2007] 覆盖问题

  

  Description某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。Input...
  22014年12月1日6,270贪心

• 「BZOJ1048」[HAOI2007] 分割矩阵

  

  Description将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。请编程对给出的矩阵及n，求出均方差的...
  02014年12月1日5,325记忆化搜索

• 「BZOJ1049」[HAOI2006] 数字序列

  

  Description现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。Input第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。Output第一行一个整数表示最少需要改变多少个数。第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。SampleInput45235SampleOutput14HINT「数据范围」90%的...
  12014年12月1日5,933递推与动规

• 「BZOJ1060」[ZJOI2007] 时态同步

  

  Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信...
  22014年11月30日5,019树形动规

• 「BZOJ1043」[HAOI2008] 下落的圆盘

  

  Description有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图,所有的红色线条的总长度即为所求.Inputnrixiy1...rnxnynOutput最后的周长，保留三位小数SampleInput2100110SampleOutput10.472HINT数据规模n<=1000题解 每个圆被其它每个圆盖住的部分是一段圆弧求出这段圆弧这图是不是很丑TAT。。。根据r1^2-x^2=r2^2-(d-x)^2得x=(r2^2-r1^2+d^2)/(2*d)通过x和反三角函数就能...
  52014年11月30日6,940贪心,几何

• 「BZOJ1042」[HAOI2008] 硬币购物

  

  Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。Input第一行c1,c2,c3,c4,tot下面tot行d1,d2,d3,d4,sOutput每次的方法数SampleInput1251023231101000222900SampleOutput427HINT数据规模di,s<=100000tot<=1000题解我想起了cf的某道题。。。dp预处理+容斥原理byvoid：设F[i]为不考虑每种硬币的数量限制的...
  32014年11月30日9,154递推与动规,容斥原理

• WC2013糖果公园

  

  DescriptionInputOutputSampleInputSampleOutput841312784HINT题解30分暴力。。。模拟即可第4-5个测试点由于m较小，且在链上，所以可以用前缀和水过。。。对于每个询问统计每种糖果的答案贡献满分做法带修改树上莫队。。。参见vfk的博客http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080但是vfk的这种树分块方式。。。。。。感觉[B,3B]的话把应...
  52014年11月29日9,197莫队算法,最近公共祖先

• 「BZOJ2216」[POI2011] Lightning Conductor

  

  Description已知一个长度为n的序列a1,a2,...,an。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j,aj<=ai+p-sqrt(abs(i-j))Input第一行n，(1<=n<=500000)下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)Outputn行，第i行表示对于i，得到的pSampleInput6532424SampleOutput235354题解倒腾一下式子得出f[i]=max{a[j]+sqrt(abs(i-j))}-a[i]为了把绝对值去掉就正反各做一次取最大值这个式子显...
  52014年11月29日6,344决策单调性

• NOI2009诗人小G

  

  DescriptionInputOutput对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出"Toohardtoarrange"(不包含引号)。每个输出后面加"--------------------"SampleInput4493brysj,hhrhl.yqqlm,gsycl.492brysj,hhrhl.yqqlm,gsycl.110056poet110046poetSampleOutput108--------------------32--------------------Toohardtoarrange--------------------1000000000000000000---...
  02014年11月29日6,281递推与动规,贪心,决策单调性