hi微波炉-CSDN博客

原创 CodeForces Gym 101620B Buffalo Barricades

题意在二维平面的第一象限里，有nnn个特殊格子。有QQQ次操作，每次操作都会选择一个格点，向左和向下延申挡板，遇到曾经延申过的挡板就停止。问每次操作形成的闭合区域，框住多少个特殊格子。n,Q<=300000xi,yi<=109n,Q<=300000\\ x_i,y_i<=10^9n,Q<=300000xi,yi<=10...

2019-07-08 22:34:59 165

原创【JZOJ100004】【NOI2017模拟.4.1】 Dice

任务解法我们分开考虑每个骰子的贡献；设XiX_i表示第ii个骰子的点数。显然Ans1=∑ni=1E[Xi]Ans1=\sum_{i=1}^nE[X_i]，又E[Xi]=∑6j=1j∗P[Xi=j]E[X_i]=\sum_{j=1}^6j*P[X_i=j]，但题目要求我们不能连续两次投相同的骰子；所以P[Xi=j]=∑6k=1P[Xi−1=k]∗P[Xi=j|Pi−1=k]P[

2017-04-07 22:18:56 430

原创【JZOJ100005】【NOI2017模拟.4.1】Shoes

任务解法我们考虑将每双鞋按两鞋的中点排序，然后把鞋子放的就是一段连续的区间了。现在我们设f[i][j]f[i][j]表示前ii双鞋子，用了jj个鞋柜，所需要的最小代价，就有 fi,j=mink<i{fk,j−1+w(k+1,i)}f_{i,j}=min_{k<i}\{f_{k,j-1}+w(k+1,i)\} 其中w(k+1,i)w(k+1,i)表示把第k+1k+1到ii双鞋放在一个鞋柜中

2017-04-07 20:55:49 432

原创【JZOJ5037】【NOI2017模拟3.30】轮回

任务掌管着世界的暗流的是一个叫做Samjia的人。他看到所有人的生死，他看见所有人一世又一世的轮回，而他却从未把握过自己的命。在无法估计的命中，他看见那些轮回，他很好奇，这一切的一切，都是如何开始如何结束，他想，就算是他也会堕入这样的轮回中的吧。于是他开始数轮回，他看到的是一个有n个点m条边的无向图（边是带标号的），一个轮回是一个由四条边组成的环，环中不能有重复的边，除了起点和终点外（当

2017-04-06 12:15:46 419

原创【JZOJ5036】【NOI2017模拟3.30】原谅

任务终其一生，我们在寻找一个原谅。犯下了太多错，要原谅的那个人，永远都是自己。 Samjia在深夜中望见了没有边界的人生，他没有想到过自己犯下了这么多的错误，他想在他的一生中寻求一个原谅。他的人生是一个没有边界的平面，平面上有n个错误，每个错误是一个点，每个点i有一定的坐标(x[i],y[i])，有一个参数p 表示每个点有p的概率出现在平面上，注意两个不同的点的出现互相没有影响，Samji

2017-04-06 11:58:02 488

任务有N种物品，每种物品的数量为C1，C2……Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)第2 - N + 1行，每行3个整数，Wi，Pi和

2017-03-29 16:21:06 412

原创【JZOJ3298】【SDOI2013】项链莫比乌斯反演+Polya计数法+欧拉函数+通项公式

任务对于100%的数据：所有的n<=1014，a<=107，T<=10；对于 100\%的数据：所有的n<=10^14 ，a<=10^7，T<=10；解法显然我们可以分两步走： 1.计算珠子的种类数 2.有多少条本质不同的项链Part Ⅰ我们计算珠子的种类数，显然是一个莫比乌斯反演的简单应用。利用Ans′=∑i=1n⌊ni⌋3∗μ(i)Ans'=\sum_{i=1}^n\lflo

2017-03-22 22:47:23 562

原创【JZOJ3737】【NOI2014模拟7.11】挖宝藏(treasure) 状压DP+斯坦纳树+SPFA

任务解法考虑二维时的情况，可以发现是对指定点的最小生成树，被称为斯坦纳树注意到点数很少，我们可以利用状态压缩Dp求解。设f[i][j][s]f[i][j][s]表示，以(i,j)(i,j)为根，连通状态为ss的最小代价。显然有， f[i][j][s]={f[i][j][s′]+f[i][j][s−s′],f[i′][j′][s]+a[i][j],s′⊂s(i′,j′)与(i

2017-03-21 17:47:46 412

原创 2017.3.18【GDOI2017】模拟赛A组比赛总结

前言：刚从教室回来，就开始了垫底之旅。本想在本次比賽一鳴驚人，但比賽成績發下來後，我決定保持沉默。1初看第一题的时候，觉得这一题可以三分。然后就开始打表验证；打了很久，然后只发现了只有当固定了其中一个λ\lambda后，才能够具备三分性质。这性质可以过60%60\%。发现这个性质其实很早，所以我决定深入讨论。然后失败了。匆匆打完60就跑。但此时已经10:00。2

2017-03-18 15:07:41 438

原创【等价的穿越】Burnside引理&Pólya计数法

Problem起源： SGU 294 He’s Circle 遗憾的是，被吃了。 Poj有道类似的：Mission一个长度为n(1≤n≤24)n(1≤n≤24)的环由0,1,20,1,2组成，求有多少本质不同的环。实际上，如果使用高精度，那么n可以到1e6级别群定义一个集合GG，以及一个二元运算∗*。并且满足：封闭性如果a∈G,b∈G

2017-03-16 17:21:51 440

原创【JZOJ4161】于神之怒莫比乌斯反演

任务答案mod 1e9+7.解法容易写出反演： Ans=∑T=1nTk∗∑i=1⌊nT⌋⌊niT⌋⌊miT⌋μ(i)Ans=\sum^{n}_{T=1}T^k*\sum^{\lfloor\frac{n}{T}\rfloor}_{i=1}\lfloor\frac{n}{iT}\rfloor\lfloor\frac{m}{iT}\rfloor\mu(i) ∑⌊nT⌋i=1⌊niT⌋⌊miT⌋

2017-03-14 15:28:07 468

原创【Mobius绮丽的辗转】莫比乌斯反演

Problem对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤500001≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000Sub problem设Ans(i,j)An

2017-03-09 22:24:47 447

原创【BZOJ2301】【HAOI2011】Problem b 莫比乌斯反演

Mission对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤500001≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000Solution裸的莫比乌斯反演。把询问拆分成四个子询问，然

2017-03-09 16:49:23 255

原创【JZOJ3636】【BOI2012】Mobile(mobile)

Mission著名的手机网络运营商Totalphone 修建了若干基站收发台，以用于把信号网络覆盖一条新建的高速公路。因为Totalphone 的程序员总是很马虎的，所以，基站的传功功率不能独立设置，只能将所有新基站的功率设置为一个相同的值。为了让能源的消耗尽量少，公司希望知道公路中任意点到最近基站距离的最大值。输入的第一行包括两个整数N（1<=N<=10^6）和L（1<=L<=10^9）分别表示基

2017-03-07 16:42:07 394

原创【JZOJ3640】【COCI2014】utrka

Mission 2<=N<=300,2<=M<=N∗(N−1)2<=N<=300,2<=M<=N*(N-1)SolutionSPFA。由于只是二元关系，所以条件随便写。具体来说，如果是u⇒vu⇒v。若vv的最大领先时间还不是正数，就要使得vv的最大领先时间尽量大；若vv的最大领先时间已经是正数，就要使得vv的经过道路尽量少；Code#include<iostream>#inclu

2017-03-07 16:28:05 368

原创【JZOJ3598】【CQOI2014】数三角形

Mission 对于100%的数据1<=m,n<=1000对于100\%的数据 1<=m,n<=1000Solution鬼题，ans=C3(n∗m)−Ansans=C^3_(n*m)-Ans，其中AnsAns表示三点共线的数目；枚举最长边的向量(x,y)(x,y)，容易算出贡献及个数。Code#include<iostream>#include<stdio.h>#include<algor

2017-03-07 16:19:10 422

原创【JZOJ3297】【SDOI2013】逃考(escape)

Mission高考又来了，对于不认真读书的来讲真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨…… 小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota，他决定越狱！假设小杨的家是个n*m 的矩阵，左下角坐标为（0，0），右上角坐标为（x1，y1）。小杨有n 个亲戚，驻扎在矩阵里（位置不同，且不

2017-03-07 16:06:47 324

原创【JZOJ3296】【SDOI2013】刺客信条(assassin)

╰(￣▽￣)╭Description故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师，他不仅是个身手敏捷的武林高手，飞檐走壁擅长各种暗杀术。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊

2017-03-07 15:42:16 501

原创【JZOJ3635】【BOI2012】Peaks

╰(￣▽￣)╭有一个居住在多山岛屿的登山家，已经攀上了一座山峰，并且要攀爬另外一座更高的山峰。更精确地说，岛上的每一点都有一个大于零的海拔（海面的海拔为零），并且如果登山家位于海拔Ei的山峰上，那么他的目标是到达其他海拔为Ej（Ej>Ei）的山峰。因为登山家在一个山峰上，所以无法马上向上爬——为了到达一个海拔更高的地点，登山家需要先下山才能上山。下山的路不及上山精彩，因此，登山家想将从当前地点到达更

2017-03-01 21:50:52 349

原创【JZOJ3601】【广州市选2014】Tree(tree)

╰(￣▽￣)╭每个非叶子节点，其左右子树叶子节点的权值之和相等。我们称这种二叉树叫平衡二叉树。我们将一棵平衡二叉树叶子节点的权值从左到右列出来，假如这个权值序列是另一个序列A的子序列，我们称这棵平衡二叉树“隐藏”在序列A当中。在本题中，我们称一个序列S2是另一个序列S1的子序列，当且仅当S2可以由S1中删除0个或多个元素，但不改变S1中剩余元素的相对位置获得。你的任务是对给定的整数序列，寻找当中隐藏

2017-03-01 21:37:45 314

原创【JZOJ3295】【SDOI2013】泉（spring）

╰(￣▽￣)╭济南市“泉历史研究小组”依据济南特有的泉脉关系将济南的泉水分为六个区域，分别是市中区、历下区、天桥区、槐荫区、历城区、长清区。作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上N 个不同年份时不同泉区的泉水流量指数，这个指数是一个小于2^30 的非负整数。第i 个年份时六个泉区的泉水流量指数分别为A(i,1)，A(i,2)，A(i,3)，A(i,4)，A(i,5)与A(i,6)。现

2017-02-23 15:38:54 735

原创【JZOJ3216】【SDOI2013】淘金

╰(￣▽￣)╭小 Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候，所有的整数坐标点上均有一块金子，共 N*N 块。一阵风吹过，金子的位置发生了一些变化。细心的小Z发现，初始在(i, j) 坐标处的金子会变到 (f(i),f(j))坐标处。其中f(x)表示 x各位数字的乘积，例如，例如 f(99)=81，f(12)=2，f(10

2017-02-21 22:42:58 351

原创【JZOJ3215】【SDOI2013】费用流

╰(￣▽￣)╭对于一张给定的运输网络，Alice 先确定一个最大流，如果有多种解， Alice 可以任选一种；之后 Bob在每条边上分配单位花费 (单位花费必须是非负实数)，要求所有边的单位花费之和等于 P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到， Bob在分配单位花费之前，已经知道Alice 所给出的最大流方案。现在 Alice 希望总费用尽量小，而Bob希望总费

2017-02-20 21:59:16 208

原创【JZOJ3214】【SDOI2013】方程

╰(￣▽￣)╭给定方程 X1+X 2+…+Xn=m 我们对第 1.. n1 个变量进行一些限制： X1≤A1 X2≤A2 … Xn1 ≤An1 我们对第 n1+1.. n1+1.. n1+ n2 个变量进行一些限制： X_(n1+1)≥A_(n1+1) X_(n1+2)≥A_(n1+2) … X_(n1+n2) ≥A_(n1+n2) 求：在满足这些限制的前提下，

2017-02-20 20:51:12 353

原创【JZOJ3617】【ZJOI2014】力

╰(￣▽￣)╭ 对于100%的数据，n≤100000;0<qi<1,000,000,000n≤100000;0< q_i <1,000,000,000。(⊙ ▽ ⊙)令ri=1i2r_i=\frac{1}{i^2}，设Fj=∑j−1i=0qi∗rj−1−iF_j=\sum_{i=0}^{j-1}q_i*r_{j-1-i}，Gj=∑j−1i=0qn−1−i∗rj−i−1G_j=\sum_{i=0

2017-02-18 10:53:35 252

原创【51NOD1028】大数乘法 V2

╰(￣▽￣)╭给出2个大整数A,B，计算A*B的结果。 (A,B的长度 <= 100000，A,B >= 0）(⊙ ▽ ⊙)把大整数AA看做一个次数界为lenAlen_A的多项式A(x)A(x)，其中x=10x=10，同样，把BB看做一个次数界为lenBlen_B的多项式B(x)B(x)，其中x=10x=10。然后套上快速傅里叶变换。(￣～￣)#include<iostream>#inclu

2017-02-16 17:29:58 380

原创【JZOJ3213】【SDOI2013】直径

╰(￣▽￣)╭小 Q最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有N个节点，可以证明其有且仅有 N-1 条边。路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点 a 和点 b 的路径上各边长度之和。称 dis(a,b)为 a、b 两个节点间的距离。直径：一棵树上，最长的路径为树

2017-02-14 17:03:12 271

原创【JZOJ3211】【SDOI2013】随机数生成器

╰(￣▽￣)╭小 W喜欢读书，尤其喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小 W准备读一本新书，这本一共有 p页，页码范围为 0..p -1。小 W很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 NOI2012上学习的线性同余法生成一个序列，来决定每天具体读哪一页。我们用 Xi来表示通过这种方法生成出来第 i个数，也即小 W第 i天会读哪一页

2017-02-11 10:27:07 338

原创 BSGS algorithm

原问题求ax≡b(mod p)a^x≡b(mod\ p)的最小正整数解。解法实际上是以空间换取时间的算法。先用散列表把 ai (i∈[0,p√))a^i\ (i∈[0,\sqrt p)) 都储存起来。然后再从小到大枚举 j (j∈[0,p√))j\ (j∈[0,\sqrt p)) ，在散列表中查找bay\frac{b}{a^y}，其中y=j∗p√y=j*\sqrt p，若存

2017-02-11 10:26:16 285

原创【JZOJ2758】【SDOI2012】走迷宫(labyrinth)

╰(￣▽￣)╭Morenan 被困在了一个迷宫里。迷宫可以视为 N 个点 M 条边的有向图，其中 Morena n处于起点 S ，迷宫的终点设为 T 。可惜的是， Morenan 非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样， Morenan 走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大

2017-02-09 17:07:22 501

原创【JZOJ4964】【GDKOI2017模拟1.21】Rhyme

hafy由于多次交换邮票没有满足所有人的需求，小Z被赶出了集邮部。无处可去的小Z决定加入音乐部，为了让音乐部的人注意到自己的才华，小Z想写一首曲子。为了让自己的曲子更好听，小Z找到了一些好听曲子作为模板。曲谱可以表示成只包含小写字母的字符串，小Z希望自己最终的曲谱中任意一个长度为K的子串都是一个模板的子串。现在小Z想知道自己的曲谱最长可以是多长，如果可以无限长的话请输出INF。forget对于30%

2017-02-06 22:20:02 376

原创【JZOJ3875】【NOIP2014八校联考第4场第2试10.20】星球联盟(alliance)

fg在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序

2017-01-19 21:46:34 411

原创【JZOJ3873】【NOIP2014八校联考第4场第2试10.20】乐曲创作(music)

ujfuiaty小可可是音乐学院的一名学生，他需要经常创作乐曲完成老师布置的作业。可是，小可可是一个懒惰的学生。所以，每次完成作业时，他不会重新创作一首新的乐曲，而是去修改上一次创作过的乐曲作为作业交给老师。小可可的乐曲由N个音调不同的音符组成，分别记为音符1…N。因此，他创作的乐曲是由1…N的一个排列构成，例如N=5时，他创作的乐曲可能为：2,1,3,5,4。但是，小可可每一次会按照一定的要求修

2017-01-19 21:19:34 643

原创【JZOJ3887】【长郡NOIP2014模拟10.22】字符串查询

haf给定n个字符串和q个询问每次询问在这n个字符串中，有多少个字符串同时满足 1. 字符串a是它的前缀 2. 字符串b是它的后缀 100%数据满足n，q≤50000，字符串长度丌超过100，任意两串最长公共前缀较短sony十分暴力的做法：先给这nn个字符串排序。对于每个询问，利用二分可以确定包含给定前缀的所有字符串的区间。然后在这个区间中，可以利用可持久化字典树求出包含给定后

2017-01-19 20:51:29 253

原创【JZOJ3886】【长郡NOIP2014模拟10.22】道路维护

CCC最近徆多人投诉说C国的道路破损程度太大，以至亍无法通行 C国的政府徆重视这件事，但是最近财政有点紧，丌可能将所有的道路都进行维护，所以他们决定按照下述方案进行维护将C国抽象成一个无向图，定义两个城市乊间的某条路径的破损程度为该条路径上所有边破损程度的最大值，定义两个城市乊间的破损程度为两个城市乊间所有路径破损程度的最小值然后C国政府向你提问多次，有多少个城市对的破损程度丌超过L，他们

2017-01-19 20:44:10 292

原创【JZOJ3885】【长郡NOIP2014模拟10.22】搞笑的代码

ok在OI界存在着一位传奇选手——QQ，他总是以风格迥异的搞笑代码受世人围观某次某道题目的输入是一个排列，他使用了以下伪代码来生成数据 while 序列长度sloce显然： Ans=n∗∑i=1n1iAns=n*\sum_{i=1}^n\frac{1}{i} 又∑ni=11i=ln(n)+oula\sum_{i=1}^n\frac{1}{i}=ln(n)+oula 其中，oulaoula

2017-01-19 20:41:31 327

原创【JZOJ3824】【NOIP2014模拟9.9】渴

SLAF世界干涸，Zyh认为这个世界的人们离不开水，于是身为神的他要将他掌控的仅仅两个水源地放置在某两个不同的城市。这个世界的城市因为荒芜，他们仅仅保留了必要的道路，也就是说对于任意两个城市有且仅有一条可行的道路。更简单的，城市形成了一棵树。 Zyh要将这两个水源放在两个不同的城市。饥渴的人们会选择一个离他们最近的水源，并向其走去。每个城市的人的速度都是相同的，并且两个相邻（有边直接相连）的城市的

2017-01-15 22:32:30 858

原创【JZOJ3852】【NOIP2014八校联考第2场第2试9.28】单词接龙(words)

DDDBsny从字典挑出N个单词，并设计了接龙游戏，只要一个单词的最后两个字母和另一个单词的前两个字母相同，那么这两个单词就可以有序的连接起来。 Bsny想要知道在所给的所有单词中能否按照上述方式接龙组成一个单词环（可能是多个），若能，求所有环的环中单词平均长度最大值。 100%的数据：n≤100000，每个单词长度不超过1000。输入数据比较大，C/C++的同学用scanf输入。Slai容易看

2017-01-15 08:00:38 373

原创【JZOJ3853】【NOIP2014八校联考第2场第2试9.28】帮助Bsny(help)

EVRTBsny的书架乱成一团了，帮他一下吧！他的书架上一共有n本书，我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30，30，31，31，32，那么混乱值为3；30，32，32，31的混乱值也为3。但是31，32，31，32，31的混乱值为5，这实在是太乱了。 Bsny想尽可能减少混乱值，但他有点累了，所以他决定最多取出k本书，再随意将它们放回到书架上。你能帮助他吗？ 1≤

2017-01-14 22:42:44 546

原创【JZOJ3854】【NOIP2014八校联考第2场第2试9.28】分组(group)

MEiBsny所在的精灵社区有n个居民，每个居民有一定的地位和年龄，ri表示第i个人的地位，ai表示第i个人的年龄。最近社区里要举行活动，要求几个人分成一个小组，小组中必须要有一个队长，要成为队长有这样的条件： 1、队长在小组中的地位应该是最高的(可以并列第一)； 2、小组中其他成员的年龄和队长的年龄差距不能超过K。有些人想和自己亲密的人组在同一个小组，同时希望所在的小组人越多越好。比如

2017-01-14 22:28:59 426

空空如也

空空如也