- 博客(204)
- 收藏
- 关注
RSS订阅原创 数据库复习
数据库码（Key）超码（super key）：是一个或多个属性的集合，这些属性的组合可以使我们在一个关系中唯一的标识一个元祖。候选码（ candidate key)：超码中可能包含了无关紧要的属性，我们通常只对这样的一些超码感兴趣，它们的任意子集都不能成为超码。这样最小超码称为候选码（candidate key) 。主码（primary key）： 被数据库设计者所选中用来标识一个关系的候...
2019-01-15 12:05:01
982
原创 CF 57 (Div. 2) D. Easy Problem (Dynamic Programming)
D. Easy Problem题目链接：题意给你一个长度为N的串，如果里面出现了"hard"这个子序列，那么这个串就是hard串，你可以删除一些字符，来使他不是一个hard串，每个字符会有一个权值A[i]，每次删除字符，都会消耗权值，要求最小的删除方案是什么？思路官方题解Denote string t as hard.We will solve this problem with...
2019-01-04 10:04:47
259
原创 CF #527 (Div. 3) F. Tree with Maximum Cost
F. Tree with Maximum Cost题目链接： Tree with Maximum Cost题意给你一棵N个点的树，每个点有一个权值A[i]，现在定义一个MAX值为选定一个点v∑i=1ndist(i,v)∗A[i]\sum ^n_{i = 1} dist(i,v)*A[i]i=1∑ndist(i,v)∗A[i]问这个值最大为多少？数据范围： N<...
2019-01-03 13:44:11
241
原创 Gym - 101908L - Subway Lines (二分+Dinic)
Subway Lines题目链接： Subway Lines Gym - 101908L题意给你R个炼油厂，P个加油站，现在，每个炼油厂有着各自的储油量，每个加油站都有着需要的油量。现在给出一些匹配方路线，每条路线无油量运输限制，但跑一边路程会需要花费一定量的时间，问能否满足所有的加油站油量需要，如果可以满足，最少用多少时间？数据范围： R,P<103R,P<1...
2018-10-29 14:44:37
337
原创 Gym - 101667H - Rock Paper Scissors （FFT）
Rock Paper Scissors题目链接： Rock Paper Scissors Gym - 101667H 题意给你两个串，长度分别为n,m。每个串由三个字符组成’R’,‘P’,‘S’，分别代表着石头剪刀布，第一个串代表是机器出的，第二个串代表是你出的，现在，你已知了机器出的顺序，可以跳过任意个，但是一旦开始就必须进行到比赛结束，所以，问最多赢几盘？数据范围： 1<...
2018-10-27 21:30:15
658
原创 ICPC网络赛 - F. Fantastic Graph （上下界网路流）
F. Fantastic Graph题目链接： 计蒜客 - 题库链接题意给你一个二分图，N左边的点，M右边的点的，K总共的边数，L，R要求能否删除一些边使得图中所有点的度都在区间[L,R][L,R][L,R]中思路构造一个网络流，这是关于网路流的上下界问题。增加四个点，分别是点超级源点s，超级汇点t,还有两个属于上下界问题的xx,yy节点。题目这样就转化为了一...
2018-09-10 15:59:04
341
原创 ICPC网络赛 Ryuji doesn't want to study （线段树/树状数组）
Ryuji doesn’t want to study题目链接： 计蒜客 - 题库链接 题意给你N个数，M个询问，有两种操作将一个数修改为另一个值求区间和 a[l]∗L+a[l+1]∗(L−1)+...+a[r−1]∗2+a[r]a[l]∗L+a[l+1]∗(L−1)+...+a[r−1]∗2+a[r]a[l] * L + a[l+1]*(L-1) + ...+a[r-1]*2...
2018-09-10 15:45:23
244
原创 ICPC网络赛 AC Challenge （状压）
AC Challenge题目链接： AC Challenge题意给出N个任务，每个任务花费一个单位时间，现在求每个任务完成时，会获得a[i]∗t+b[i]a[i]∗t+b[i]a[i] * t + b[i] 的价值，但是每个任务都有必须要在之前完成的任务，就是前置任务。数据范围：N<20,−109<a[i],b[i]<109N<20,−109<a[i]...
2018-09-03 20:46:57
301
原创 ICPC网络赛 - Magical Girl Haze （DP+最短路）
Magical Girl Haze题目链接： Magical Girl Haze题意给你一个图，N个节点，M条边，现在给你最多K次机会将一条边的权值变为0，求从1到N的最短路。N<105,M<2∗105,K<=10N<105,M<2∗105,K<=10 N < 10^5 ,M < 2*10^5,K dis[v][k]=dis[u][k]+cost...
2018-09-01 21:52:51
221
原创 ICPC网络赛 - Lpl and Energy-saving Lamps （线段树）
AC Challenge题目链接： AC Challenge 题意你有N个房间（N&amp;lt;1e5）,每天买M个灯泡（M&amp;lt;100），每个房间都有需要装的灯泡数，每天装灯泡时，必须从第一个房间到最后一个房间，如果可以装，即手中的灯泡数大于房间需要的灯泡数，就装。总共有Q个询问（Q&amp;lt;1e5）,每次询问的天数，小于等于1e4,每次询问输出当前天时，所点亮的房间数和现在手中的灯泡数...
2018-09-01 21:31:52
360
原创 ZOJ-1610 Count the Colors （线段树区间修改）
Count the Colors题目链接： F - Count the Colors ZOJ - 1610 题意给你一个区间，n个操作，每次将左右端点分别为l和r的区间染成自己的对应的颜色，最后求每块颜色的分别。思路就是普通的线段树区间修改，只需最后在进行一部Down操作即可，中间需要注意的就是做标记时，不能以add为0，要将其改为>-1因为这个数据为0也是合法的...
2018-08-24 20:42:08
177
原创 HDU-6435 Problem J. CSGO （最大曼哈顿距离）
Problem J. CSGO题目链接： Problem J. CSGO题意有n个主武器，m个副武器，（n &amp;lt; 1e5,m &amp;lt; 1e5）每个武器有个主属性S和一个 K（K &amp;lt; 5）个副属性，现在要求以下值最大 S1+S2+∑Ki=1|Xni−Xmi|S1+S2+∑i=1K|Xni−Xmi| S_1 + S_2 + \sum_{i=1}^K|Xni - Xmi| ...
2018-08-22 21:32:11
441
转载 tex数学公式和字符表示方法
tex数学公式和字符表示方法上下标（1）上标符号为“^”、下标符号为“_” , 例如 : 2^r , a_5（2）可同时输入上下标（注意要先下标再上标） 例如 : C_n^m分式(1)简单的可以用单斜杠 / 表示分数线， 例如 : 2/3，a/b，a/{b+c}，a^2/(b_2+c)^2(2)使用 \frac{}{} 第一个{}内放分子，第二个...
2018-08-22 20:10:10
5013
原创 Poj-2528 Mayor's posters （离散+线段树）
Mayor’s posters题目链接： Mayor’s posters POJ - 2528题意给你n（1 &lt; n &lt; 10000）个海报，每个海报有l和r（1&lt;=l&lt;=r&lt;=1e7），代表自己覆盖的区间，后面的会覆盖前面的，求总共会当最后一个覆盖结束后有多少海报可以看见。思路本题的难点在于修改的l，r区间非常的大，如果直接开数组，暴力跑线段...
2018-08-21 13:52:03
145
原创 HDU-6415 Rikka with Nash Equilibrium （DP/找规律）
Rikka with Nash Equilibrium题意定义一个大数为一个矩阵中所在行，所在列的最大值。给出一个N，M，MOD，问可以构造多少矩阵来使得一个矩阵最多只有一个大数思路我们先从最大的数开始考虑，这个数可以放在任意位置，第二大的数则只能放在最大数所在的行或者列，第三大的数则可以有更多的选择，这样我们可以列出一个DP方程。 dp[i+1][j][k+1]+=dp...
2018-08-20 22:02:09
193
原创 HDU-6230 - Palindrome （Manacher + 主席树/树状数组）
Palindrome题目链接：Palindrome HDU - 6230 题意给你一个字符串，问你里面会有几个符合一个半回文串的定义，一个半回文串的定义是类似与这种abcbabc ；思路题意可以转化为:有多少对i,j(i代码一#include &lt;bits/stdc++.h&gt;using namespace std;#define rep(i,...
2018-08-17 22:01:57
252
原创 HDU-3416 Marriage Match IV （最短路+最大流）
Marriage Match IV题目链接：Marriage Match IV HDU - 3416题意给你一个图，问有多少条不同的最短路，有重边并且可当作分开的两边，其多条最短路之间不能有任何相同的边思路开始时，看到了每条边只能经过一次，我想到了费用流，可惜这里的数据不小，N为1000，M为1e5，按照费用流平均复杂度，F * E * log（v） 毫无疑问会T，那么...
2018-08-17 13:13:42
313
原创 VOJ - OSU! （概率DP）
OSU!题目链接： OSU! HYSBZ - 4318题意osu 是一款群众喜闻乐见的休闲软件。 我们可以把osu的规则简化与改编成以下的样子: 一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3^ 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释） 现...
2018-08-16 21:25:51
283
原创 HDU-6386 Age of Moyu （想法+迪杰斯特拉）
Age of Moyu题目链接： Age of Moyu题意给你N个顶点，M条边，每条边都属于一个海贼，在从一个海贼的边到另一个海贼的边时需要交1点路费，如果还是同一个海贼，则不用交。思路现在问题的核心在于，我们原先是直接贪心的找一条最短边，加入进来，但是现在如果直接确定最短路，非常难，因为不知道前一个航道的情况，那么我们就可以用一个set来到达当前点最短路时，可能...
2018-08-13 21:52:35
289
原创 HDU-4417 - Super Mario （主席树）
Super Mario题目链接： Super Mario HDU - 4417题意给n个数的数组，m次询问，每次询问区间【L，R】中小于等于k的数有几个 思路就是裸的主席树吧，因为要求小于等于k的值，所以，我们先将其离散化，然后从第一个数据开始建不同版本的主席树，每个线段树了里面所储存的就是总共的子树数目，然后我们就可以通过比较 r 版本和 l-1版本中ID小于等于k的...
2018-08-07 21:05:58
221
原创 HDU-4348 - To the moon （主席树+区间修改）
To the moon题目链接： To the moon HDU - 4348 题意给你长度为n的数组，共有四个操作：•1.对区间【L，R】增加d，并时间增加1 •2.询问当前时间的区间【L，R】的和•3.询问时间为T时的区间【L，R】的和•4.返回到时间为T的时候思路既然有着时间点的要求也就是历史版本的要求，那么主席树肯定是没跑的了，奈何我没有合适...
2018-08-07 20:44:18
273
转载 2018HDUContest
命题人在赛前预估的难度等级是：非常简单：B, E简单：C, G, H中等：A, F, I, K困难：D, J, L而正确通过每道题目的队伍数量如下： 题目 A B C D E F G H I J K L 通过数量 7 457 2 10 906 3 193 44 2 3 ...
2018-08-06 18:02:25
204
原创 POJ-2362 - Square （DFS + 剪枝）
Square题目链接：A - Square POJ - 2362 题意给你n个小木棍，要求全部用上，能否组成一个正方形。思路我原先的方法，非常非常暴力，就开个dfs，来记录每个状态的值，反正每个木棍都是要组成一个边的，于是我就枚举它放边的过程，复杂度为4^20次方吧，果然会炸。有些基本的优化就不谈了，比如最长的边大于平均边，边总和不是4的倍数。。。现在考虑枚举...
2018-08-04 21:42:56
201
原创 HDU - 2234 - 无题 （DFS + 剪枝）
无题题目链接： 无题I题意在一个4*4的矩阵中分别有4个1，4个2，4个3和4个4分别表示4种不同的东西，每一步小A可以把同一行的4个数往左移或者往右移一步或者把同一列的4个数字往上移或者往下移一步(1,2,3,4往左移后是2,3,4,1)，小A现在想知道进过最少的几步移动可以将矩阵的每行上的4个数字都一样或者每列上的4个数字都一样。 思路直接暴力DFS即可。但是适当的...
2018-08-03 21:28:34
163
原创 VOj - Kingdom of Obsession （数学优化+二分图匹配）
Kingdom of Obsession题目链接： Kingdom of Obsession HDU - 2853题意给你一个起点s,和n要求从s+1到s+n的自然数按照一定次序排序，满足自己的值一定能整除自己的排序号思路题3目中的s和n都很大，所以暴力运算并不可取，那么我们就需要自己优化。题目显然一个素数在1以外找不到自己的座位，那么就可以从素数入手，数学原理可得...
2018-08-02 21:37:18
176
原创 HDU - 6341 Let Sudoku Rotate （DFS+剪枝）
Let Sudoku Rotate题目链接： Problem J. Let Sudoku Rotate题意给你一个16 * 16的矩阵，里面出现的数为十六进制的1到F，为数独分布，有人将其任意个4 * 4的单独小块逆旋转任意多次，现在，需要我们将其顺时针还原，问最少还原几次。思路直接dfs+可行性剪枝即可，因为在数独中，剪枝效率高。代码#includ...
2018-08-02 20:44:35
189
原创 VOJ - Avoiding the Apocalypse （最大流—时间拆点）
Avoiding the Apocalypse题目链接： Avoiding the Apocalypse Gym - 101512A 题意有n个点，开始i点上有g个人，每条路是a通向b，花费t秒，每秒可以通过t人，有m个终点，问在s秒内最多多少人到达终点思路因为单向边的有向性，与时间的有向性相呼应，所以我们可以将其拆点，将时间转换成空间，这题的时间和点数都挺少的，所以，...
2018-08-02 09:25:48
325
原创 VOJ - Going Home （最小费用流）
Going Home题目链接：Going Home POJ - 2195题意给你你一个n*m的图，里面’.’代表路，’H’房子，’m’人，人数和房子数是相等的所以现在需要所有的人到到达自己的房子里面，问最小需要多少时间，所有人都可以到达房子思路这道题本来是带权二分匹配的裸题，可惜我没有好的模板，于是用费用流硬刚，这也非常完美，就是只需用一个超级起点来连接所有的人，cap...
2018-07-31 15:23:44
249
原创 POJ 2771 - Guardian of Decency （二分图）
Guardian of Decency题目链接： Guardian of Decency POJ - 2771题意有一个古板的老师，要带学生去郊游，为了防止学生谈恋爱，所有带的学生互相之间必须满足如下条件Their height differs by more than 40 cm. They are of the same sex. Their preferred musi...
2018-07-30 11:46:53
178
原创 VOJ - Anniversary party （树形DP）
Anniversary party题目链接：H - 树形DP例题 HDU - 1520题意在一个有根树上每个节点有一个权值，每相邻的父亲和孩子只能选择一个，问怎么选择总权值之和最大。思路树形dp的常规入门题：设dp[i][0]表示:当前这个点不选，dp[i][1]表示当前这个点选择的最优解。转移方程：dp[cur][0]+=max(dp[son][1],dp[son...
2018-07-29 23:27:55
122
原创 VOJ - Did he drop any good loot? （三维DP）
Did he drop any good loot?题目链接：A - Did he drop any good loot? Gym - 100694A题意n种物品，每种物品有价值p[i]、重量w[i]和加成d[i]，d[i]表示如果带上i物品则可以额外多带d[i]单位重量，最多能带m单位重量的物品，所带物品最多有两个物品可以加成，问最多可以带多少价值的物品 思路如果没有...
2018-07-26 21:05:34
146
原创 VOJ - Victor's Research （想法）
Victor’s Research题目链接： C - Victor’s Research Gym - 100247C题意求一个数组中有多少非空区间满足和为s思路和上一题一样的套路，记，那么题目就变成了求多少对满足，用map计数即可。注意sum[0]=1，答案会爆int。代码#include &lt;bits/stdc++.h&gt;using name...
2018-07-23 20:57:54
243
原创 VOJ - Victor's Research （贪心+堆）
Victor’s Research题目链接： C - Victor’s Research Gym - 100247C题意有n个导弹要进攻你，你的能源每个单位会涨一，现在你需要拦截第i个导弹需要ai的能源，可以使用拦截导弹消灭一个导弹，问你最少拦截几次。思路把前面的导弹的攻击力存储下来，如果抵挡不住接下来的攻击，就取出一个攻击力最高的导弹消灭掉。 代码...
2018-07-23 20:31:56
164
原创 VOJ - For the Honest Election (递归/筛法)
For the Honest Election题目链接：L - For the Honest Election Gym - 100247L题意有n个人要投票选市长，P想当市长，所以他要找一些支持者给他投票，他可以把一群人分成若干人数相等的小组，对每个小组还可以执行类似的操作，投票规则是每个组分成的小组中有过半组投支持P这个组才支持P，问P通过适当的分组后让自己被选上市长需要的最少支...
2018-07-23 19:15:36
1277
原创 VOJ - Ildar Yalalov （初级博弈论）
Ildar Yalalov题目链接： I - Ildar Yalalov Gym - 101808I题意给你N堆石头,每堆Ai个数，(1 ≤ N ≤ 100) (1 ≤ A**i ≤ 106) ，让两个人，进行如下操作 1) Remove one stone from any pile. 2) Remove one stone from every pile if e...
2018-07-16 18:26:34
454
原创 TSOJ - 子序列 (DP 字符串)
子序列 (DP 字符串)题目链接： 子序列题目信息描述给定一个字符串，求出该字符串有多少不同的子序列。子序列：字符串中按顺序抽出一些字符得到的串。比如字符串abcd里，ab、ac、ad、abc、acd都是子序列。输入输入一个字符串。输出输出不同的子序列的个数除以23333得到的余数。样例1输入ababc样例1输出2...
2018-06-05 16:58:52
614
原创 数字盒子
数字盒子题目链接：算法训练营 - 第一周 （简单数据结构）数字盒子问题描述你有一个盒子，你可以往里面放数，也可以从里面取出数。初始时，盒子是空的，你会依次做 Q 个操作，操作分为两类：插入操作：询问盒子中是否存在数 x，如果不存在则把数 x 丢到盒子里。删除操作：询问盒子中是否存在数 x，如果存在则取出 x。对于每个操作，你需要输出是否成功插入或删除。输入...
2018-05-24 15:26:39
1440
原创 ZOJ - 2851 Code Formatter
ZOJ - 2851 Code Formatter题目链接： C - Code Formatter ZOJ - 2851 题意给你一篇文章，让你进行两个操作 1，将其中的 ‘\t’ 全都改成四个空格 2，将其每行最后的多余空格删除掉文章将以”##”结尾，输出’\t’的个数和删掉空格的个数。思路题目的意思非常简单，但是我开始时没有做，因为我觉得这个需要用到一些编...
2018-05-07 16:41:36
163
原创 [kuangbin带你飞]专题四 最短路练习 - Frogger
Frogger题目链接： B - Frogger POJ - 2253 ## 题意话说，这道题意真难理解，我看了好久，又看了题解才懂了题意。题目的意思是有N块石头并给出他们的坐标，青蛙要从第一块到第二块，设Max1为青蛙从起点到终点路径中跳的最远的距离，现在要求所有可能的路径中Max1最小的值思路看到了最大套最小，我们应该很轻易的想到用二分可以过，但是这样花费的时间会很多，...
2018-05-04 16:15:39
134
原创 2018年湘潭大学程序设计竞赛 - D. Fibonacci进制(找规律)
D. Fibonacci进制(找规律)题目链接： Fibonacci进制题意Fibonacci数是非常有名的一个数列,它的公式为 f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2。 我们可以把任意一个数x表示成若干不相同的Fibonacci数的和， 比如说14 = 13+1 = 8+5+1 = 8+3+2+1。如果把Fibonacci数列作为数的位权，即f(i)...
2018-04-27 17:33:20
611
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人