[ZJOI2009]假期的宿舍 题目描述： 学校放假了，有些同学放假回家了，有些同学不回家，而不回家的同学的非本校的朋友要到学校和他一起搞基，但是非本校的学生没有床位，这就需要进行床位转借，人总是会睡自己或自己认识的人的床，问能否存在一个方案使得所有不回家的学生和来和他们搞基的学生都有地方住 思路： 二分图 找出左集合，和右集合，然后连边，跑匈牙利就可以 左集合是需要住的人，右集合是床位 需要住的就是不回家的所有人，床位是所有本校的人 这里就用两个vis数组标记一下，左集合就在去dfs之前判断一下，如果这个人需要住宿，那就去dfs，右集合就在dfs里面的找床位的时候判断一下，看看当前这个...

自适应树游走协议 题目描述： 在计算机网络中，当多个站点试图通过同一个信道同时进行传输时，传输的数据会出现乱码，这称为冲突。自适应树游走协议（Adaptive Tree Walk Protocol**）是一种避免冲突的方法。它将所有使用同一个信道的站点使用一棵完全二叉树组织起来，每个叶子**代表一个站点。 当有站点想要使用信道时，使用深度优先遍历的方法处理冲突：在第一个时隙检查树根，若其所有后代结点中只有唯一的结点请求信道，则直接将信道分配给它；否则依次递归检查左子树、右子树，直到不存在冲突为止。 图中展示了A-H八个共享信道的站点被组织的方式。若某一时刻C、D、H三个站点同时...

什么是拓展欧几里得？简单的说，就是求关于x,y的方程 ax + by = gcd(a,b) 的所有整数解 现在我们来解决四个问题 什么是裴属定理，如何证明裴属定理？ 怎么用扩展欧几里得来求ax + by = gcd(a,b) 的特解？ 怎么求由特解推出其他的所有解？ 扩展欧几里得的三大应用 一、裴蜀定理内容即证明 内容 设a, b是不全为零的整数，则存在整数x, y 使得 ax + by = gcd(a, b). 证明： a, b中假如有一个为0，则上述定理完全吻合，如a = 0, 则gcd(a, b) = b , 显然成立 若a, b 都不等于0 设gcd(a, ...

题目描述： 给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值 数据可能会出现括号情况，还有可能出现多余括号情况 数据可能会出现负数的情况 思路： 分治 通过运算符将整个表达式一次次分割来计算 根据优先度低的运算符来分割表达式，这样分治到最后进行数与数的计算的时候就算的是优先度最高的，也就是逆过来了 对于同样优先级的符号，我们取最后一个位置来分割 而且对于在括号里面的加减乘除乘方我们不用其来分割，待去气括号后再用其进行分割 所以，我们每次跑(l, r)的时候，用pos1来记录+或-的位置，用pos2来记录*或/的位置，用pos3来记录^的位...

P1063 [NOIP2006 提高组] 能量项链 题目描述： 思路： 区间dp 状态： dp[i] [j]表示合并i到j得到的最大能量 转移方程： #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #in...

题目描述： 今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完， 他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间, 即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。 思路： 先用前缀和进行预处理 再维护一个dp数组，dp[i]表示，i 到 n中长度为k的区间的和的最大值 然后就可以枚举第一个区间，通过O(1)的复杂度得到第二区间的最大值 坑点 要开longlong 数组要开够 #include <cstdio&g...

题目描述： 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 思路： 很...

二分答案模版题 题目描述： It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time. Jane wants to perform ...

Stressful Training 题目描述： Berland SU holds yet another training contest for its students today. nnn students came, each of them brought his laptop. However, it turned out that everyone has forgot their chargers! Let students be numbered from 111 to nnn. Laptop of the iii-th student has charge aia_iai...

题目描述： 给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ，0的位数为1。 思路： 分治（递归+二分） 第一反应肯定是暴力，但是一看数据范围直接放弃 接着发现这是区间问题，可以考虑考虑分治，大化小，小化了 [l, r] = [l, mid] + [mid + 1, r] 如何快速的求出h(l, r), 这里肯定不能暴力，我们可以考虑给他排个序，然后就可以去快乐的二分查找，判断比 - r 大的 l 有多少个，统计下来就是答案： #include <cstdio> #include <cstring> #include <s...

Music Notes 题目描述： FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for Bi (1 <= Bi <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will p...

Chocolate Eating 题目描述： Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set...

什么是拓扑排序？ 先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！ 拓扑排序说白了其实不太算是一种排序算法，但又像是一种排序（我是不是说了个废话qwq） 他其实是一个有向无环图（DAG, Directed Acyclic Graph的所有顶点的线性序列，该序列需要满足两个条件： 每个节点只能出现一次 若存在一条A到B到路径，则在拓扑序列中A必然出现在B前面 而有向无环图才具有拓扑排序，非DAG图则没有拓扑排序一说 先看一道拓扑排序的水题趴(>_<) UVa 10305 - Ordering Tasks 题意： 有n个任务要做，有m个要求，每个要求有两个数x，y，要求x必须在y之...

A. The Child and Homework 题目描述： Once upon a time a child got a test consisting of multiple-choice questions as homework. A multiple-choice question consists of four choices: A, B, C and D. Each choice has a description, and the child should find out the only one that is correct. Fortunately the chil...