Yan2u's Blog

Description这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！ Input一行包含两个整数N，M，之间由一个空格隔开。 Output总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。 Sample Input11 3 Sample Output17 Hint样例说明 除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2×2×2-1=7种方案。 数据范围 100%的数据中N和M均不超过100 50%的数据中N和M至少有一个数不超过8 30%的数据中N和M均不超过6 分析首先想到，每一行最多只能塞进 2 门炮，否则就会出现隔山打牛的情况了，那么每一行就只有 2 种合法状态，即放 1 门炮和放 2 门炮 设 $f[i][j][k]$ 表示到了第 $i$ 行，有 $j$ 列只有一门炮，还有 $k$ 列 ...

FHQTreap：函数式平衡树FHQTreap 是一种特殊的平衡树（ Invented By FHQ ），不同于普通平衡树 Splay 的是，它无需旋转操作(Rotate)就可以达到 Splay 的速度，而是用两个基本操作实现序列操作：Merge 和 Split 从名字 Split 就可以发现，它的核心思想是将一颗树分裂，使之两个部分满足堆序，在上面操作之后再合并为一棵树 FHQTreap 的本质还是 BST ，所以区间操作和 Splay 没有多大区别（经过优化后好像还比Splay跑得快？） 基础操作：Split (分裂)Split 分裂 是按照某种规定将当前的树分成两棵子树的操作（当前的树也有可能是分裂之后的树，因此操作具有递归性），分裂操作可以按照给定权值分，也可以按照子树大小分 按照权值分裂将当前树分裂成权值均小于等于 X 的一棵树 A 和权值均大于 X 的一棵树 B A，B 的意义为分裂后两棵树的根结点，需要实时更新，引用传参 空树将会被拆分成 2 棵空树，即A=B=0（边界），然后： 如果正在考虑的点 K 权值比 X 大，说明 K 的右子树的权值均比 X 大，K 的右子 ...

T2.货车运输DescriptionA 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 Input第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。接下来一行有一个整数 q，表示有 q 辆货车需要运货。接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y Output输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1 Sample Input123456784 31 2 42 3 33 1 131 31 41 3 Sample Output1233-13 Hint对于 30%的数据，0 < ...

可持久化线段树可持久化线段树是一种特殊的线段树，不同于普通的线段树，他能够维护一些经过修改之后的不同版本的树，并且能在当前树的某个历史版本上进行操作，包括： 单点查询 单点更新 区间查询 区间更新 创建新的版本 维护不同版本的树，如采用朴素的线段树建新树，时间和空间都会超出限制，但是利用当前版本的线段树和以前版本的线段树的共同结点，我们可以节省很多重复的结点，对旧版本的树进行改造，就能遍历到新的树 Code(可持久化线段树)1234567struct node{ int lc,rc,sumv; #define lc(x) T[x].lc // x 的左儿子 #define rc(x) T[x].rc // x 的右儿子 #define s(x) T[x].sumv // x 的值 #define pushup(x) (T[x].sumv=T[T[x].lc].sumv+T[T[x].rc].sumv) // 上传 }T[MAXN]; 建树可持久化线段树建树和线段树建树没有多大区别，但是为了后面操作的方便，我们不用以前的线段树表示方式（即 $K< ...

Problem 1. 升降梯(Up-Down)Description开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。 塔一共有 N 层，升降梯在每层都有一个停靠点。手柄有 M 个控制槽，第 i 个控制槽旁边标着一个数 Ci，满足 C1

Description七夕祭上，Vani牵着cl的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣，applepi果断闪人，于是cl拿起鼓棒准备挑战。然而即使是在普通难度下，cl的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani十分过意不去，决定帮助工作人员修鼓。 鼓的主要元件是M个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用1和0表示。显然，从不同的位置出发沿顺时针方向连续检查K个传感器可以得到M个长度为K的01串。Vani知道这M个01串应该是互不相同的。而且鼓的设计很精密，M会取到可能的最大值。现在Vani已经了解到了K的值，他希望你求出M的值，并给出字典序最小的传感器排布方案。 Input一个整数K。 Output一个整数M和一个二进制串，由一个空格分隔。表示可能的最大的M，以及字典序最小的排布方案，字符0表示关，1表示开。你输出的串的第一个字和最后一个字是相 ...

T1：欧拉路径Description18世纪著名的数学问题之一：在哥尼斯堡的一个公园里，有7座桥将河中两个岛及河两岸连接起来(如图a)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？　　　 欧拉于1736年研究并解决了此问题。欧拉把每一块陆地考虑成一个点，连接两块陆地的桥以边表示，画出图b的图论模型，由此问题变成：能否从无向图的一个结点出发走出一条路径，每条边恰好经过一次，最后回到出发点。这样的路线称为欧拉回路，也可以称为一笔画。 你的任务与欧拉一样：给出n个顶点（编号为1..n），m条边的无向图。请寻找一条欧拉路径。 Input第1行为整数n，接下来的 m 行，每行两个整数：i,j(1<=i,j<=n)，表示一条无向边。 Output如果不存在欧拉路径，则输出NIE。否则输出应当包含 m+1 个整数，依次表示欧拉路径经过的顶点号。如果把欧拉路径经过的结点序列看成是一个n进制的数，那么当存在多组解的情况下，输出n进制表示法中最小的一个（也就是输出第一个数较小的，如果还有多解，输出第二个数较小的，…，实质就是字典序）。 Sample Input12 ...

Description重庆城里有n个车站，m条双向公路连接其中的某些站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其它车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间和。 佳佳的家在车站1，他有五个亲戚，分别住在车站a、b、c、d、e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？ Input第一行：n（n<=50,000），m（m<=100,000），为车站数目和公路的数目。 第二行：a、b、c、d、e，为五个亲戚所在车站编号（1< a、b、c、d、e <= n） 接下来m行，每行三个整数x、y、t（ 1 <= x、y <= n，1 <= t <= 100），为公路连接的两个车站编号和时间。 Output仅一行，包含一个整数T，为最少的总时间 Sample Input123456786 62 3 4 5 61 2 82 3 33 4 44 5 55 6 21 6 7 Sample Output1 ...

Description 在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的 Alpaca L. Sotomon 是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天 Henry Curtis 故事的起点。Henry 是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。 整座宫殿呈矩阵状，由 R×C 间矩形宫室组成，其中有 N 间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这 N 间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种: “横天门”：由该门可以传送到同行的任一宫室;
 “纵寰门”：由该门可以传送到同列的任一宫室;
 “自由门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室( ...

Description一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在NNN个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。 问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？ Input第一行有两个整数 N,M。 接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x ,例如President同志） 。 注：原文敏感内容已替换 Output仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。 Sample Input123455 4 1 2 1 3 1 4 1 5 Sample Output10.800000 Sample Input 图示： graph LR d1((1));d2((2));d3((3));d4((4));d5((5)) d1---d2 d1---d3 d1---d4 d1---d5 分析 ...