- 博客(117)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 区域赛前整理
文章目录数学相关期望：倍数快速乘图论DFS判环BFS搜路径数学相关期望：我们有一个长为L的pokey(是杏子，幻视ing)，现有一个程序，如果L>d，则在L上等可能的选择任意一点，吃掉左边，得到新的L，然后重复此程序，求程序执行次数的期望。即长为L的木棍，当L>d时，每次等可能的去掉X（0<X<=L），求操作次数的期望。设f(x)为长度为x的pokey的操作次数的...
2019-10-15 19:43:25
195
原创 EasyPoi word导出 简易使用指南
1、安装依赖 <!-- 集成 easypoi --> <dependency> <groupId>cn.afterturn</groupId> <artifactId>easypoi-base</artifactId> <version>3.3.0</version> </dependency>
2021-04-30 10:10:27
9611
6
原创 前向星和链式前向星
概念：前向星：前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置。链式前向星：链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。next表示当前结点的下一个节点。用vector表示二维数组。模板：//前向星int idx,e[mx],h[mx],ne[mx];void add(int a,int b){ e[idx]=b;ne
2020-11-13 15:29:27
258
原创 AcWing 1169. 糖果 （差分约束）
题干：幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果.但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。输入格式输入的第一行是两个整数...
2020-03-24 15:43:39
224
原创 2019上海网络赛(J) 计蒜客 - 41420 Stone game(DP)
题干：CSL loves stone games. He has n stones; each has a weight aia_iai . CSL wants to get some stones. The rule is that the pile he gets should have a higher or equal total weight than the rest; howev...
2020-03-20 09:46:49
210
原创 POJ - 1201 AcWing 362. Intervals（差分约束）（贪心+线段树）
题干：You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.Write a program that:reads the number of intervals, their end points and integers c1, …, cn from the standard input,c...
2020-03-16 22:27:37
163
原创 【CodeForces】675C - Money Transfers（前缀和）
题干：There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than 1. Also, bank 1 and bank n are neigh...
2020-02-24 15:42:49
180
原创 AcWing 1165. 单词环(01分数规划)
题干：我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：ababcbckjaca...
2019-12-07 16:04:03
132
原创 AcWing 361. 观光奶牛(01分数规划)(判正环)
题干：给定一张L个点、P条边的有向图，每个点都有一个权值f[i]，每条边都有一个权值t[i]。求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。注意：数据保证至少存在一个环。输入格式第一行包含两个整数L和P。接下来L行每行一个整数，表示f[i]。再接下来P行，每行三个整数a，b，t[i]，表示点a和b之间存在一条边，边的权值为t[i]。输出格...
2019-12-06 21:49:59
154
原创 BZOJ1977 AcWing 1148. 秘密的牛奶运输(次小生成树)
题干：农夫约翰要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。运输的总距离越小，运输的成本也就越低。低成本的运输是农夫约翰所希望的。不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。注意：：如果两个方案至少有一条边不同，则我们认为是不同方案；费用...
2019-11-27 10:49:53
199
原创 背包问题合集
文章目录AcWing 423. 采药题干思路AcWing 1024. 装箱问题题干思路AcWing 1022. 宠物小精灵之收服题干思路AcWing 423. 采药题干辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一...
2019-11-24 19:15:05
375
原创 AcWing 1145. 北极通讯网络 （最小生成树）
题干：北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y 表示。为了加强联系，决定在村庄之间建立通讯网络，使每两座村庄之间都可以直接或间接通讯。通讯工具可以是无线电收发机，也可以是卫星设备。无线电收发机有多种不同型号，不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d，就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。现在要先选择某一种...
2019-11-23 11:31:51
256
原创 AcWing 1146. 新的开始(最小生成树)
题干：发展采矿业当然首先得有矿井，小 F 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记了考虑矿井供电问题。为了保证电力的供应，小 FF 想到了两种办法：(1)在矿井 i 上建立一个发电站，费用为 vi（发电站的输出功率可以供给任意多个矿井）。(2)将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网，费用为 pi,jp_{i,j}pi,j。小 F ...
2019-11-23 10:55:06
289
原创 AcWing 1144. 连接格点（最小生成树）
题干：有一个 m 行 n 列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。输入格式第一行输入两个正整数 m 和 n。以下若干行每行四个正整数 x1,y1,x2,y2，表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。输入保证|x1−x2|+|y1−y...
2019-11-15 20:05:39
258
原创 POJ3662 AcWing 340. 通信线路(双端队列BFS)
题干：在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站Ai和Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费Li。电话公司正在举行优惠活动。农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩...
2019-11-07 09:31:21
256
原创 AcWing 175. 电路维修(双端队列BFS)
题干：达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。电路板的整体结构是一个R行C列的网格（R,C≤500），如下图所示。每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可...
2019-11-06 18:58:23
214
原创 AcWing 1135. 新年好 (dfs+spfa)
题干：重庆城里有 n 个车站，m 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。...
2019-11-04 20:40:36
238
原创 数字三角形模型DP
目录模板：例题：ACwing 898ACwing 1015模板：形如12 33 4 54 5 6 7从[1][1]出发，到[n][m]为止，只能向下或向右，求路径上的最大/最小/最大和/最小和。按照动态规划的思路，确定状态表示，考虑状态计算例题：ACwing 898题干：给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结...
2019-10-28 15:31:23
581
原创 动态规划合集
目录模板：例题：最长上升子序列最长公共子序列最长公共上升子序列最长上升子序列和模板：DP有个毛线的模板参考自yxc大佬。主要问题是要确定状态转移方程。根据闫式DP分析法，我们先确定状态表示：①所属的集合②属性然后考虑状态计算：确定例题：最长上升子序列给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。样例输入：73 1 2 1 8 5 6样例输出：4#in...
2019-10-24 19:09:06
426
原创 AcWing 271. POJ-2279 杨老师的照相排列（线性DP）
题干：有 N 个学生合影，站成左端对齐的 k 排，每排分别有 N1,N2,…,Nk 个人。 (N1≥N2≥…≥Nk)第1排站在最后边，第 kk 排站在最前边。学生的身高互不相同，把他们从高到底依次标记为 1,2,…,N。在合影时要求每一排从左到右身高递减，每一列从后到前身高也递减。问一共有多少种安排合影位置的方案？下面的一排三角矩阵给出了当 N=6,k=3,N1=3,N2=2,N3=1...
2019-10-17 09:10:04
225
原创 AcWing 346. 走廊泼水节(最小生成树)
题干：给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。输入格式第一行包含整数t，表示共有t组测试数据。对于每组测试数据，第一行包含整数N。接下来N-1行，每行三个整数X,Y,Z，表示X节点与Y节点之间存在一条边，长度为Z。输出格式每组数据输出一个整数，表示权值总和最小值。每个结果占一行。数据范围...
2019-10-12 21:05:46
127
原创 HDU - 5984 Pocky（数学推导）
题干：Let’s talking about something of eating a pocky. Here is a Decorer Pocky, with colorful decorative stripes in the coating, of length L.While the length of remaining pocky is longer than d, we per...
2019-10-11 20:35:40
327
原创 2019牛客国庆集训派对day7 B- 有向无环图（BFS）
题干：链接：https://ac.nowcoder.com/acm/contest/1112/B来源：牛客网Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。为了方便，点用 1,2,…,n 编号。设 count(x,y)count(x,y)\mathrm{count}(x, y)count(x,y)count(x,y)count...
2019-10-11 19:08:38
189
原创 2019牛客国庆集训派对day7 A 2016（数学）
题干：链接：https://ac.nowcoder.com/acm/contest/1112/A来源：牛客网给出正整数 n 和 m，统计满足以下条件的正整数对 (a, b) 的数量：1 <= a <= n, 1 <= b <= m;a × b 是 2016 的倍数。输入包含不超过 30 组数据。每组数据包含两个整数 n, m (1 <= n, m &...
2019-10-09 20:03:47
128
原创 2019CCPC秦皇岛 F-Forest Program（DFS）（快速幂）
题干：The kingdom of Z is fighting against desertification these years since there are plenty of deserts in its wide and huge territory. The deserts are too arid to have rainfall or human habitation, an...
2019-10-09 16:52:09
346
原创 2019CCPC秦皇岛 I-Invoker(简单dp)
题干：In dota2, there is a hero named Invoker. He has 3 basic skills in the game, which are Quas, Wex and Exort. Once he launches a basic skill, he will gain the corresponding element, where Quas gives ...
2019-09-29 21:30:29
1156
2
原创 2018-2019ACM焦作区域赛F - Honeycomb Gym -102028F(BFS)
题干：time limit per test：4.0 smemory limit per test：1024 MBcells built by honey bees, which can be described as a regular tiling of the Euclidean plane, in which three hexagons meet at each internal ...
2019-09-27 19:13:28
192
原创 POJ1734 AcWing 344. 观光之旅(任意两点间最短路)
题干：思路：#include <cstdio>#include <vector>#include <cmath>#include <algorithm>#include <iostream>#include <cstring>using namespace std;int d[310][310],x[310]...
2019-09-24 09:07:45
157
原创 POJ1094 AcWing 343. 排序(传递闭包)
题干：给定 n 个变量，m 个不等式。不等式之间具有传递性，即若 A>B 且 B>C ，则 A>C。判断这 m 个不等式是否有矛盾。若存在矛盾，则求出 t 的最小值，满足仅用前 t 个不等式就能确定不等式之间存在矛盾。若无矛盾，则判断这 m 个不等式是否能确定每一对变量之间的关系。若能，则求出 t 的最小值，满足仅用前 t 个不等式就能确定每一对变量之间的大小关系。...
2019-09-20 20:37:31
250
原创 2019ICPC银川区域赛H BZOJ2200 AcWing 342. 道路与航线(连通块+dij+拓扑排序)(SLF优化的SPFA模板)
题干：思路：#include <bits/stdc++.h>using namespace std;struct stu{ int next; int cost;};vector<stu> tu[100100];int dis[25010],vis[25010];void add(int a,int b,int c){ stu t;...
2019-09-19 19:40:59
279
2
原创 NOIP2009 AcWing 341. 最优贸易（最短路）
题干：C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来...
2019-09-18 19:23:55
126
原创 POJ3662 AcWing 340. 通信线路(多层最短路)
题干：在郊区有 N 座通信基站，P 条双向电缆，第 i 条电缆连接基站Ai和Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费Li。电话公司正在举行优惠活动。农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的...
2019-09-18 11:04:54
266
原创 2019上海网络赛B. Light bulbs（差分）
题干：There are N light bulbs indexed from 0 to N−1. Initially, all of them are off.A FLIP operation switches the state of a contiguous subset of bulbs. FLIP(L, R)means to flip all bulbs x such that L&...
2019-09-16 19:35:42
402
原创 AcWing 142. 前缀统计（trie-字典树）
题干：给定N个字符串S1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。输入字符串的总长度不超过10610^6106，仅包含小写字母。输入格式第一行输入两个整数N，M。接下来N行每行输入一个字符串SiSi。接下来M行每行一个字符串T用以询问。输出格式对于每个询问，输出一个整数表示答案。每个答案占一行。输入样例：3 2ab...
2019-09-10 20:01:01
379
原创 AcWing 152. 城市游戏（滑动窗口）
题干：有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。但是rainbow和freda的OI水平都...
2019-09-09 08:40:28
143
原创 AcWing 131. 直方图中最大的矩形(单调栈)
题干：直方图是由在公共基线处对齐的一系列矩形组成的多边形。矩形具有相等的宽度，但可以具有不同的高度。例如，图例左侧显示了由高度为2,1,4,5,1,3,3的矩形组成的直方图，矩形的宽度都为1：通常，直方图用于表示离散分布，例如，文本中字符的频率。现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。图例右图显示了所描绘直方图的最大对齐矩形输入格式输入包含几个测试用例。每个测试...
2019-09-09 08:30:00
246
原创 AcWing 154. 滑动窗口(单调栈)
题干：给定一个大小为n≤10610^6106的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。您只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。以下是一个例子：该数组为[1 3 -1 -3 5 3 6 7]，k为3。您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。输入包含两行。第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。第二...
2019-08-29 20:51:11
295
原创 AcWing 150. 括号画家（栈）
题干：这一天，刚刚起床的达达画了一排括号序列，其中包含小括号( )、中括号[ ]和大括号{ }，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：(1) 空的括号序列是美观的；(2) 若括号序列A是美观的，则括号序列 (A)、[A]、{A} 也是美观的；(3) 若括号序列A、B都是美观的，则括号序列AB也是美观的。例如 [ (){}] ( )是美观...
2019-08-28 20:31:29
305
1
针对数据库的增删改查，两个实验.zip
2019-11-20
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人