标签 - 模拟

? 解题记录 ? ? BZOJ ? ? 模拟 ?    2018-12-19 12:10:04    402    0    0
【题目描述】给出一个N个顶点、M条边的无向图,边(u,v)有权值w(u,v),顶点i也有权值p(i), 并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。 现在要将顶点i的权值减去z(i),其中0≤z(i)≤p(i)。 修改后设顶点i的权值p'(i)=p(i)-z(i),对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。 求sum{z(i)}的最小值和最大值。   【输入】第一行两个正整数n,m (n≤500,000, m≤3,000,000)。 第二行n个整数,依次表示p(1),p(2),...,p(n) (0≤p(i)≤10^6)。 下面m行,
? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 模拟 ?    2018-11-04 14:09:05    775    0    0
1.1 题目描述 九条可怜是一个热爱思考的女孩子。 九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法:gobo sort! Gobo sort 的算法描述大致如下: • 1. 假设我们要对一个大小为 n 的数列 a 排序。 • 2. 等概率随机生成一个大小为 n 的排列 p 。 • 3. 构造一个大小为 n 的数列 b 满足 bi = api,检查 b 是否有序,如果 b 已经有序了就结 束算法,并返回 b ,不然返回步骤 2 。 显然这个算法的期望时间复杂度是 O(n × n!) 的,但是九条可怜惊奇的发现,利用量子的 神奇性质,在量子系统中,可以把这个算法
? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 模拟 ?    2018-10-29 23:30:59    633    0    0
题目描述 输入输出格式输入格式:   第一行有一个整数N(3<N<2000),表示登陆地带的大小是2×N。随后的两行每一行有N个整数(其绝对值不超过10^6),表示对应的矩形土地的适用度评估值,各个整数之间用一个空格隔开。   输出格式:   只有一行输出,为整数M,即所确定的实验基地的适用度。   输入输出样例输入样例#1: 复制4 -1 2 -3 4 5 6 7 8 输出样例#1: 复制31​  不知道为什么N会是2000而不是10^6。这道题
? 解题记录 ? ? 洛谷 ? ? 模拟 ?    2018-10-29 23:17:40    628    0    0
题目描述很久以前,有一个传说中的“EWF”部族,他们世代生活在一个N×M的矩形大地上。虽然,生活的地区有高山、有沼泽,但通过勤劳勇敢,渐渐地,他们在自己的地盘上修筑了一条回路。 后来,“EWF”部族神秘地消失了。不过,考古学家在那片他们曾经生活过的地方找到了一份地图。地图是N×M的矩阵,左上角的坐标为(0, 0),右下角的坐标为(N, M)。矩阵中的每个格子,表示高山、沼泽、平地、房屋或是道路其中之一。如果一个格子表示道路,那么经过这个格子的道路要么是直走,要么是拐弯。如下图,左边2幅表示直走格子的,右边4幅表示需要拐弯的格子。一个表示道路的格子只能表示下列情况之一。 可是,由于地图的年代久
? 解题记录 ? ? 洛谷 ? ? 模拟 ?    2018-10-21 14:51:59    481    0    0
题目描述欢乐岛上众多新奇的游乐项目让小可可他们玩的非常开心。现在他们正在玩比赛串项链的游戏,谁串的最快就能得到优厚的奖品。 这可不是普通的项链,而是一种Y型项链,项链的最中间有一颗大珍珠作为结合点,从大珍珠上连出来3条由各种宝石串起来的链子。 比赛的规则是这样的:每次可以从三条链子中某一条的一端取下来一个宝石,或者安上去一个宝石,称为一次操作,经过若干次操作,最终使得三条链子完全相同。想要赢得比赛,那么只能使用尽量少的操作次数。 假设每种宝石都有无数多个以供使用,且链子足够长。你能帮助小可可赢得比赛吗? 注:由于对Y型项链的宝石数没有特殊的要求,所以即使你把所有宝石都取下来,也是一个可以接受的
? 解题记录 ? ? Codeforces ? ? 分块 ? ? 模拟 ?    2018-09-18 08:56:50    361    0    0
The Tree 维护一棵n" role="presentation" style="position: relative;">nnn节点,每个节点为黑色或白色的树,给你q" role="presentation" style="position: relative;">qqq个操作: 1、递归进行如下操作:如果当前节点是白色,那么将它染成黑色;如果当前节点是黑色,对它的所有儿子调用该操作。 2、将一颗子树所有的点染成白色。 3、查询一个点的颜色,是黑色输出"black",白色输出"white"。 n&#x2264;105,q&#x2264;105
? 解题记录 ? ? 洛谷 ? ? 模拟 ?    2017-07-29 17:06:15    355    0    0
题目背景小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。 假设内存中有M个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M-1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M个单词,软件会清空最早进入内存