1 短尾黑猫

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 19w+

火车进出栈序列问题(Catalan数+高精度压位)

题面:Acwing 130思路先假设每一个入栈的操作为 111,出栈的操作为 000。这样就抽象出一个 nnn 个 111 和 nnn 个 000 的排列问题。因为每次出栈操作都必须保证栈里有火车,所以入栈的次数一定都不少于出栈的次数(出栈次数包括当前出栈)。于是有一个很强的性质:序列任意前缀中的 111 的个数都不少于 000 的个数于是该问题就转化成了 求第 nnn 项的卡特兰数,即 :C2nnn+1=(2n)!n!n!(n+1)\cfrac{C_{2n}^n}{n+1}=\cfrac{(2

2020-09-06 18:20:51

【POJ 3714】Raid(分治、平面最近点对)

题面:Raid题目大意有 N 个核电站能源供应点需要被摧毁。将军派出了 N 位特工去摧毁这些供应点。由于受到了帝国空军的袭击,特工分散到了几个位置,每个位置有坐标给出。将军想哪个特工离任意一个核电站的距离最小。请你求出这个最小距离。思路分治。将所有点按 xxx 坐标从小到大先排好序,之后可以分成左右两部分进行分别的计算最短距离,再进行计算中间部分可能的最短距离。但是这题是由两个不同的阵营组成,我们可以先将阵营标记出来,同阵营之间的距离就给赋值成 “无穷大”。左右两边我们只要运用归并的思想

2020-09-03 18:35:53

【POJ 1723】SOLDIERS(排序、中位数)

题面:SOLDIERS题目大意有 nnn 个士兵,并且知道每个士兵在二维坐标图上的位置。士兵可以进行移动,但是每个士兵每次只能向上、向下、向左或向右移动一个单位,因此,他的 xxx 或 yyy 坐标也将相应的加 1 或减 1。现在希望通过移动士兵,使得所有士兵彼此相邻的处于同一条水平线内,即所有士兵的y坐标相同并且x坐标相邻。请你计算满足要求的情况下,所有士兵的总移动次数最少是多少。注意:两个或多个士兵不能占据同一个位置。思路分析题目,可以发现,每个士兵的横纵坐标对于他们的移动是彼此独立的,

2020-09-03 16:32:39

【HDOJ 4864】Tack(贪心)

题面:Tack题目大意今天某公司有 mmm 个任务需要完成。每个任务都有自己相应的难度级别和完成任务所需的时间,记作 (y,x)(y,x)(y,x)。公司若完成第 iii 个任务,可以获得 (500∗xi+2∗yi)(500*x_i+2*y_i)(500∗xi​+2∗yi​) 美元的报酬。现在,公司有 nnn 台机器,每台机器都有相应的最长工作时间和级别。如果任务所需时间超过机器的最长工作时间,则机器无法完成此任务。如果任务难度级别超过机器的级别,则机器无法完成次任务。每台机器一天内只能完成

2020-09-03 11:39:40

【POJ 1050】To the Max(降维,贪心,最大子区间和)

题面:To the Max题目大意给定一个整数 nnn ,代表的是方形区间的边长,之后再输入所有格子内的数。求该区间内的最大子区间的和。思路暴力要搞到 O(n4)O(n^4)O(n4)。考虑一下降维和动归。正常动归,要用到二维动态规划,可能会超时。这里可以将每一列的前缀和算出来,即把每一列当作一个数,在确定好上下界之后,就可以用一维动归来解决这个问题了。算法的时间复杂度就降到了 O(n3)O(n^3)O(n3)贪心思想在做一维动归的时候,需要一些贪心思想。遍历到第 kkk 个数时,如果

2020-09-03 10:33:59

【POJ 3045】Cow Acrobats(贪心)

题面:Cow Acrobats题目大意相当于有 nnn 头奶牛在叠罗汉。每头牛都有两个特质,一个是重量 www,一个是强壮度 sss。每头牛都有一个崩溃风险,该风险等于在她上面的所有奶牛的总重量减去她本身的强壮度。所以每头牛都要找到合适自己的位置。求:确定所有奶牛的位置,从而使任何奶牛中的最大风险最小。思路芜湖~~先贪心试一下。将每头牛按照 w+sw+sw+s 从小到大排序,这样就得到正确的答案啦哈哈哈哈哈哈。贪心证明:设最优解为 real_ansreal\_ansreal_ans,自己方

2020-09-02 23:36:44

NUMBER BASE CONVERSION(高精度模拟短除法+思维)

题面:POJ 1220题目大意给定两个整数 a,ba,ba,b,且 0<a,b<620<a,b<620<a,b<62,并给出一个 aaa 进制的数。要我们将该数转化成 bbb 进制的数。思路高精度模拟短除法。第一反应会想到高精度先将 aaa 进制转化成 101010 进制数,最后转化成 bbb 进制数,其中过程要不断求余。这里其实只要转变一下思路,让被除数上的每一位先加上之前的余数乘以 aaa 进制数,再去除以除数 bbb ,最后得出的数就是 aaa 进制

2020-09-02 16:16:21

糖果传递(环形均分/中位数)

题面:糖果传递【Acwing】思路我们可以假定糖果是单向传递的,即都是逆时针(顺时针)传给某个孩子。#mermaid-svg-waRziq1ZTt8vNIUH .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-waRziq1ZTt8vNIUH .label text{fill:#333}#mermaid-sv

2020-09-02 14:53:32

【POJ2083】Fractal(分形、递归)

题面:Fractal题目大意分形,具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状,可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状”,即具有自相似的性质。现在,定义“盒子分形”如下:一级盒子分形: X\\XX二级盒子分形:X X  XX X\\X\ X\\\ \ X\\X\ XX X  XX X如果用B(n - 1)代表第n-1级盒子分形,那么第n级盒子分形即为:B(n

2020-09-02 10:12:07

占卜DIY(模拟)

题面:占卜DIY思路:没什么好说的,就纯粹的模拟。注意:000 代表的是 101010代码:#include <bits/stdc++.h>#define sc scanf#define pf printfusing namespace std;deque<string> q[20];map<string, int> vis;int check(string x){ if(x == "A") return 1; if(x ==

2020-09-02 09:55:11

The Pilots Brothers‘ refrigerator(思维)

题面:The Pilots Brothers’refrigerator代码#include <bits/stdc++.h>#define sc scanf#define pf printfusing namespace std;typedef pair<int, int> PII;string str[5];bool mark[5][5];vector<PII> ans;int main(){ memset(mark, false, size

2020-09-01 23:56:21

Corral the Cows(二分、前缀和、离散化)

题面:Corral the Cows【牛客】题目大意有 nnn 个单位的三叶草,每单位三叶草占据一个 1×11×11×1 的土地,每块土地的位置由其左下角的下标确定,并且下标 xxx 和 yyy 都是整数,且 1≤x,y≤100001\leq x,y\leq100001≤x,y≤10000。农夫约翰希望为他的奶牛们建立一个畜栏。其中畜栏必须是正方形,且至少要包含 CCC 单位的三叶草。要求出至少包含 CCC 单位的三叶草情况下,畜栏的最小边长。注意:每个区域可能会有多个单位的三叶草,所以输入的时候

2020-09-01 22:52:08

Running Median(动态维护中位数问题,对顶堆)

题面:Running Median题目大意顺序输入 nnn 个数,当下标为奇数时,就输出一次当前序列的中位数。例如,当遍历或输入到第 iii 个数时,iii 恰好为奇数,则就要在序列 a[1]a[1]a[1] 到 a[i]a[i]a[i] 之间找到一个中位数,并输出出来。思路这题是对顶堆的板子题。用两个小根堆和大根堆来动态维护序列。其中,大根堆维护较小的一半元素,小根堆维护较大的一半元素。即:序列中从小到大次序为 [1,len/2][1,len/2][1,len/2] 的整数存储在大根堆中

2020-09-01 21:43:25

防线(二分)

原题链接:防线题意给定 NNN 组防具,并给出每组防具放置的起始点 startstartstart 、终点 endendend 和防具与防具之间的距离 ddd。每个位置的防具数量可以由不同组的防具叠加。求防具数量为奇数的位置和该位置的防具数量。(题目给定防具数量为奇数的位置唯一)思路题目给出起始点、终点和防具之间的距离,可以很直观的看出,每组防具的位置分布是一个等差数列 an=a1+(n−1)∗da_n=a_1+(n-1)*dan​=a1​+(n−1)∗d。所以,在一维坐标上,我们可以很快的算出每

2020-09-01 09:53:03

HDOJ 6867 Tree

原题链接:Tree题面:思路:只能添加一条有向边由题意可知,所建出来的树,父节点到子结点之间都是一条由父节点指向子结点的有向边。要想得到最大对数的 (x,y)(x,y)(x,y),只能从叶子节点添加一条有向边到根节点。所以,可以先暴搜求出每个节点可以到达的节点数,并求和得到 tottottot,然后更新最大值。其中每个叶子节点连接到根节点后得到的可行对数为 n+tot−cnt[i]n+tot-cnt[i]n+tot−cnt[i]。代码:#include <bits/stdc++.h&gt

2020-08-19 23:10:29

CH0503 奇数码问题(逆序对)

题面:奇数码问题思路:找了好久,没有找到奇数码问题和 n∗mn*mn∗m 数码问题的详细证明。先记个结论。奇数码游戏两个局面可达,当且仅当两个局面下网络中的数依次写成不含零的 111 到 n∗n−1n*n-1n∗n−1 的序列后,逆序对个数的奇偶性相同。结论必要性证明:空格(即 000 )左右移动的时候,我们列出出来的序列是不变的;空格上(下)移动时,相当于某个数与它后(前)边 n−1n-1n−1 个数交换了位置,因为 n−1n-1n−1 是偶数,所以逆序对数的变化也是一个偶数。拓展到 nnn 为

2020-08-08 11:00:02

HDU 6835 Divisibility

原题链接:Divisibility题目大意:对于任意 bbb 进制的正整数 y=c1c2...cn‾y=\overline{c_1c_2...c_n}y=c1​c2​...cn​​,如果有 c1+c2+...+cn≡0(modx)c_1+c_2+...+c_n\equiv 0\pmod xc1​+c2​+...+cn​≡0(modx),那么有 y≡0(modx)y\equiv 0\pmod xy≡0(modx),否则 y≢0(modx)y\not\equiv 0\pmod xy​≡0(modx)。

2020-08-07 16:13:12

HDU 6827 Road To The 3rd Building(前缀和+乘法逆元+数学推导)

原题链接:Road To The 3rd Building题面:题目大意:有 nnn 棵银杏树,每棵树都有可爱价值,当从第 iii 棵树走到第 jjj 棵树,则他们的平均可爱价值为 1j−i+1∑k=ijs[i]\cfrac{1}{j-i+1}\sum_{k=i}^{j}s[i]j−i+11​∑k=ij​s[i]。最后求这些可爱价值的数学期望。即 ∑i=1nE[i]\sum_{i=1}^{n}E[i]∑i=1n​E[i]。数学推导:我们可以先考虑每一个数对于期望值的贡献。以 n=4n=4n=

2020-08-07 11:33:17

HDU 6825 Set1(组合数学+数学推导)

原题链接:Set1题面:题目大意:给定一个集合 S={1∼n}S=\{1\sim n\}S={1∼n},对集合进行如下操作直到 ∣S∣=1|S|=1∣S∣=1。首先会先删除集合中最小的数,之后以相同的概率删除其他的数。求集合中每一个数被保留下来的概率。数学推导:令操作111为删除最小的元素,操作222为随机删除一个元素。假设元素 iii 会被保留下来,则它的前面有 i−1i-1i−1 个元素,后面有 n−in-in−i 个元素。我们需要考虑保留下元素 iii 的所有方案数。显然,保留下

2020-08-06 23:28:39

HDU 6822 Paperfolding(数学推导)

原题链接:Paperfolding题面:题目大意:给你一张纸,可以进行四种操作,向上向下向左向右对折,实际上向上向下为一种,即竖直对折;向左向右一种,即水平对折。对折完后可以进行横竖一刀切的操作,将纸张分成 sss 张。现在给定一个 nnn,问经过 nnn 次四种操作后,期望 E(s)E(s)E(s) ,即最终切割后得到的纸张数 sss 的期望是多少。数学推导:用纸张模拟 (我脑子不太好使,撕了几张纸)。可以发现,水平和竖直的对折,对于结果的影响都是独立的,即水平对折只影响水平的切痕,竖直的

2020-08-06 22:47:48

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。