【题目描述】给出一个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行，
1.1 题目描述
九条可怜是一个热爱思考的女孩子。
九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法：gobo sort！
Gobo sort 的算法描述大致如下：
• 1. 假设我们要对一个大小为 n 的数列 a 排序。
• 2. 等概率随机生成一个大小为 n 的排列 p 。
• 3. 构造一个大小为 n 的数列 b 满足 bi = api，检查 b 是否有序，如果 b 已经有序了就结
束算法，并返回 b ，不然返回步骤 2 。
显然这个算法的期望时间复杂度是 O(n × n!) 的，但是九条可怜惊奇的发现，利用量子的
神奇性质，在量子系统中，可以把这个算法
题目描述 输入输出格式输入格式： 第一行有一个整数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。这道题
题目描述很久以前，有一个传说中的“EWF”部族，他们世代生活在一个N×M的矩形大地上。虽然，生活的地区有高山、有沼泽，但通过勤劳勇敢，渐渐地，他们在自己的地盘上修筑了一条回路。 后来，“EWF”部族神秘地消失了。不过，考古学家在那片他们曾经生活过的地方找到了一份地图。地图是N×M的矩阵，左上角的坐标为(0, 0)，右下角的坐标为(N, M)。矩阵中的每个格子，表示高山、沼泽、平地、房屋或是道路其中之一。如果一个格子表示道路，那么经过这个格子的道路要么是直走，要么是拐弯。如下图，左边2幅表示直走格子的，右边4幅表示需要拐弯的格子。一个表示道路的格子只能表示下列情况之一。 可是，由于地图的年代久
题目描述欢乐岛上众多新奇的游乐项目让小可可他们玩的非常开心。现在他们正在玩比赛串项链的游戏，谁串的最快就能得到优厚的奖品。 这可不是普通的项链，而是一种Y型项链，项链的最中间有一颗大珍珠作为结合点，从大珍珠上连出来3条由各种宝石串起来的链子。 比赛的规则是这样的：每次可以从三条链子中某一条的一端取下来一个宝石，或者安上去一个宝石，称为一次操作，经过若干次操作，最终使得三条链子完全相同。想要赢得比赛，那么只能使用尽量少的操作次数。 假设每种宝石都有无数多个以供使用，且链子足够长。你能帮助小可可赢得比赛吗? 注：由于对Y型项链的宝石数没有特殊的要求，所以即使你把所有宝石都取下来，也是一个可以接受的
The Tree
维护一棵n" role="presentation" style="position: relative;">nnn节点，每个节点为黑色或白色的树，给你q" role="presentation" style="position: relative;">qqq个操作：
1、递归进行如下操作：如果当前节点是白色，那么将它染成黑色；如果当前节点是黑色，对它的所有儿子调用该操作。
2、将一颗子树所有的点染成白色。
3、查询一个点的颜色，是黑色输出"black"，白色输出"white"。
n≤105,q≤105
题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存
Rockdu's Blog