- 博客(93)
- 收藏
- 关注
RSS订阅原创 深度优先搜索（DFS）
深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止（属于盲目搜索）。“一路走到头，不撞墙...
2019-04-19 21:19:22
271
原创 ACM-ICPC Jiaozuo Onsite 2018 Honeycomb【bfs】
题意：其实就是迷宫直接跑就行了，原本还想把迷宫转换一下想麻烦了。。#include<bits/stdc++.h>using namespace std;const int INF =100000000;char mp[10000][10000];int d[10][2]={4,0,-4,0,-2,-6,-2,6,2,-6,2,6};int n,m;typedef pa...
2018-12-11 20:45:40
310
原创 CodeForces - 215E 【数位dp】
Ť题意：判断一个区间中有多少个数是二进制时是循环的，比如101010，以10为循环。思路：以位数来处理，i是处理到当前长度i，j是循环体的长度，当i<len【二进制的长度】时只要i%j==0则长度为j时的全部数都可以，当i==len时要特殊处理到最大的循环，还有去重，因为循环体j的长度为4时已经包含了长度1【1111】，2【1010】【1111】 #include<stdio...
2018-12-07 23:16:28
230
原创 P1118 数字三角形【杨辉三角+全排列】
#include<bits/stdc++.h>using namespace std;int a[20][20];int b[20];int c[20][20];int cmp(int a,int b){ return a>b;}int main(){ int n=1,sum; cin>>n>>sum; for...
2018-11-24 19:53:36
278
原创 hdu 2089 不要62【数位dp】
题意：给定一个范围n~m，求出数中不存在4和连续62的数的个数。数位dp经典入门题。#include<bits/stdc++.h>using namespace std;#define ll long longint digit[20];ll dp[20][2];ll dfs(int len,bool if6,bool limit){ if(len==0) re...
2018-11-17 19:22:49
170
原创 P1045 麦森数【数学】
题意：2^p-1的位数和后500位的每个数。位数直接公式p*log10（2）+1.后500位可以每次乘2^20能节约很多时间#include<bits/stdc++.h>using namespace std;long long a[555],b[600],c[55];int main(){ int p; cin>>p; int...
2018-11-15 13:56:20
492
原创 ZOJ - 3469 Food Delivery (区间dp)
题意：一条在x轴的路，一个饭店（起始点）和n个顾客，每个人都有一个抱怨值随时间累加，求最小的抱怨值。巨难啊。。。不会啊。。。区间dp【i】【j】【0/1】0代表在左边停下，1在右边停下，dp【i】【j】【0】可以从dp【i+1】【j】【0/1】转移到dp【i】【j】【1】可以从dp【i】【j-1】【0/1】转移到，#include<stdio.h>#include&...
2018-11-05 22:02:53
105
原创 HDU 4283 You Are the One【区间dp】
题意：n个人排成一排，每个人轮流上场，第i个人上场有（i-1）*a【i】的愤怒值，有一个小黑屋，你可以把人塞进去，先进的后出来，求最小的愤怒值。dp不亏是dp真难(可能是我太菜了。。。感觉写了不少了但还是很难自己写出来，菜哭题解;区间dp，断点k代表的是第i个人第几次出场。dp【i】【j】=min（dp【i】【j】，dp【i+1】【i+k-1】+（k-1）*a【i】+dp【i+k】【j...
2018-10-29 21:33:59
98
原创 POJ - 2195 Going Home 【最小费用流】
题意：n*m的地图有人和房子，要让每个人进入一个房子（每个房子只能进入一个人，人可以走任何地方（可以经过房子也可以多人在一个位置，每个人走一步花费1美元，求最小的花费。思路：最小费用流模板，建好图。。抄模板就行了，这个图比较好建。原点0~（1~k）房子~（k+1~k+kk）人~（k+kk+1）结点#include<stdio.h>#include<string...
2018-10-17 13:15:24
164
原创 poj 3281 Dining 【网络流+拆点】
题意：农夫能做F种食物D种饮料，n头牛每头牛只吃特定食物和饮料，求最大的农夫能满足的牛的个数（食物和饮料都要满足第一道网络流的题，主要是建图，建好图就是敲模板了。。。这道题拆点，0是源点，1~f【食物】，【f+1~n+f】 左牛【n+f+1~2*n+f】 右牛【 2*n+f+1~2*n+f+d】饮料 【2*n+f+d+1】结点原点-->食物-->左牛-->右牛--&g...
2018-10-16 21:12:55
130
原创 LightOJ1079---Just another Robbery（01背包）
题意：抢银行，一共有n个银行，每个银行可以抢v【i】的钱，被抓的概率是m【i】。问在低于P概率的情况下，最多能抢多少钱。思路；01背包dp【i】存的是抢到【i】钱不被被抓的概率。1-dp【i】就是被抓的概率。#include<stdio.h>#include<string.h>#include<algorithm>#include<iost...
2018-10-16 16:22:30
100
原创 LIghtOJ1038---Race to 1 Again【期望dp】
题意：一个整数n每次除以他的因子求除以到1时的期望次数。t=10000，100000>=n>=1肯定要打表的。dp【50】=（dp【1】+dp【2】+dp【5】+dp【10】+dp【25】+dp【50】）/6+1。1是贡献的次数1。按这个方程打表即可。#include<stdio.h>#include<string.h>#include&l...
2018-10-15 11:26:12
151
1
原创 LightOJ 1030 - Discovering Gold （期望dp）
题意：1*n的迷宫，刚开始在1的位置，你有一个骰（这个字居然念tou。。。涨知识了）子，你每次前进骰子的数。每个位置还有金子的个数求到n时的金子的期望，走到迷宫外时重新骰。dp【n】=a【i】，dp【i】=dp【i+1】/6+dp【i+2】/6+dp【i+3】/6+dp【i+4】/6+dp【i+5】/6+dp【i+6】/6+a【i】。不足6的，到n-i停止。#include<...
2018-10-14 22:23:05
125
原创 Lightoj 1027 Dangerous Maze （期望）
题意：你在一个迷宫里，一共有n个门，走进每个门的概率是相同的，如果这个门是个正数（w）代表你将花费w的时间出去如果是一个负数（-t）代表你将花费w的时间回到原点，回到原点后你选择每个门的概率还是相同的。（求期望） 思路：根据期望的公式假设期望为a，第三个样例a=1/3*（3）+1/3*（6+a）+1/3*（9+a）。因为回到原点后期望还是a没有变。因为答案是分数的形式，要约分。#...
2018-10-14 11:15:33
103
原创 hdu2476 String painter （区间dp）
题意：给个a，b两个字符串，刷a，一次可以将一个区间刷成一个字母，求最小的操作次数将a串变为b串。深深的感受到被dp支配的恐惧，，，这道题真不好想。。。看题解看了好久才看明白（菜哭
2018-10-12 23:38:09
125
原创 POJ1651:Multiplication Puzzle （区间dp）
题意：一串数列，除了开头和结尾，每次取一个数，然后+上a【i-1】*a【i】*a【i+1】的价值，然后让求出最小的价值。区间dp的经典题，这个k的值代表的是最后取的数，然后将区间划分为3部分dp【i】【k】+dp【k】【j】+a【i】*a【k】*a【j】。#include<stdio.h>#include<iostream>#include<string...
2018-10-10 21:58:00
188
原创 POJ 2955 Brackets (区间DP)
题意：求最长的括号匹配子序列。区间dp基础题，将k设为在i~j与i匹配的结点，则dp【i】【j】=dp【i+1】【k-1】+dp【k+1】【j】+1；i与k匹配是+1，再加上中间的区间和右边的区间。这道题很好的让我理解了一下区间dp的运作。果然多刷题才是王道（以前一直理解不清///#include<stdio.h>#include<string.h>#...
2018-10-10 16:39:31
125
原创 Cake （凸包+区间dp）
题意：一个多边形先是确定是否是凸多边形，可以用凸包模板来判断。然后是求最小的切割价值。最小切割价值用区间dp来求解dp【i】【j】=min(dp【i】【j】,dp【i】【k】+dp【k】【j】#include<bits/stdc++.h>using namespace std;int dp[306][306];double add(double a,double b)...
2018-10-09 16:58:58
186
原创 New Game! （最短路）
https://www.nowcoder.com/acm/contest/201/L题意：给两条平行的直线，还有n个圆，在直线和圆上走不耗时间，求最短的时间从一条直线到另一条。思路：这道题就是让求最短距离，但真没想到真是用最短路写的。。。代码中0，1位置存的是两条直线节点，#include<bits/stdc++.h>using namespace std;#de...
2018-10-02 20:56:49
183
原创 P1880 [NOI1995]石子合并（区间dp）
https://www.luogu.org/problemnew/show/P1880题意：一串环形的数，每相邻的两个数可以合并，加上价值，价值是两个数的和，求最大和最小价值。思路：区间dp板子，有一点要注意因为是环形的数，首位和末尾也是可以合并的，因此可以将原数组，再往后加一遍。就变成链型的了。#include<bits/stdc++.h>using namesp...
2018-10-02 16:03:27
149
原创 P1280 尼克的任务(dp)
https://www.luogu.org/problemnew/show/P1280题意：给了k个时间段不能重叠，求能得到的最大的空余时间。状态转移方程： 这个时间段没工作 dp[i]=dp[i+1]+1 有工作 dp[i]=max(dp[i],dp[i+p[w].y])#include<bits/stdc++.h>usin...
2018-09-29 21:56:16
179
原创 模板
素数打表int a[10006],num=0;bool visit[10006];void table(){ memset(visit,true,sizeof(visit)); for(int i=2;i<=10000;i++) { if(visit[i]) a[++num]=i; for(int j=1;j<=n...
2018-09-28 20:59:31
92
原创 P1091 合唱队形（dp）
https://www.luogu.org/problemnew/show/P1091题意就是求最长的先上升后下降的子序列（可以不上升也可以不下降）。这道题给我个深刻的教训，好好看题！！好好看题！！原本理解错了，以为要对称的上升和下降，WA出一片天。 #include<bits/stdc++.h> using namespace std; int a[106],b[1...
2018-09-28 11:43:23
137
原创 P1020 导弹拦截（dp）
https://www.luogu.org/problemnew/show/P1020题意：就是求最长上升子序列#include<bits/stdc++.h>using namespace std;#define ll long longint b[100060],a[100060],dp[100060],d[100060];int main(){ int i=0...
2018-09-26 07:38:48
70
原创 P1064 金明的预算方案 （dp）
https://www.luogu.org/problemnew/show/P1064题意：和开心的金明不一样的是有附属关系，#include<bits/stdc++.h>using namespace std; int dp[33000],w[100],w1[100],w2[100]; int e[100],e1[100],e2[100];int main(){...
2018-09-22 11:21:36
135
原创 P1060 开心的金明 （dp）
题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NNN元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的NNN元。于是，他把每件物品规定了一个重要度，分为555等：用整数1−51-51−5表示，第555等最重要。他还从因特网上查到了...
2018-09-19 22:55:21
179
原创 P1074 靶形数独 （o2优化95分）
题目描述小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 999 格宽×999 格高的大九宫格中有99 9 个 333 格宽×333 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫...
2018-09-09 22:16:56
448
原创 B-烟花 （求期望）
https://www.nowcoder.com/acm/contest/180/B期望什么的根本不会啊，先记录下来。。。#include<bits/stdc++.h>using namespace std;double a[100010],sum,w[100010][220];int main(){ int n,k; scanf("%d%d",&n,&a...
2018-09-08 00:02:39
125
原创 hdu1850 Being a Good Boy in Spring Festival （sg函数）
Problem Description一年在外 父母时刻牵挂春节回家 你能做几天好孩子吗寒假里尝试做做下面的事情吧陪妈妈逛一次菜场悄悄给爸爸买个小礼物主动地 强烈地 要求洗一次碗某一天早起 给爸妈用心地做回早餐如果愿意 你还可以和爸妈说咱们玩个小游戏吧 ACM课上学的呢～下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以...
2018-09-07 11:11:37
107
原创 hdu1848 Fibonacci again and again（sg打表）
Fibonacci again and againTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11711 Accepted Submission(s): 5054Problem Description任何一个大学生对...
2018-09-03 22:28:08
92
原创 sg函数模板
1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);2.可选步数为任意步，SG(x) = x;3.可选步数为一系列不连续的数，用GetSG()计算打表//f[]：可以取走的石子个数//sg[]:0~n的SG函数值//hash[]:mex{}int f[N],sg[N],hash[N]; void getSG(int n){ ...
2018-09-03 18:38:35
159
原创 easy CodeForces - 438D (线段树区间取余)
给一个序列支持3种操作1 u v 对于所有i u<=i<=v，输出a[i]的和2 u v t 对于所有i u<=i<=v a[i]=a[i]%t3 u v 表示a[u]=v（将v赋值给a[u]）n,q<=1e5 a[i],t,v<=1e9Input5 51 2 3 4 52 3 5 43 3 51 2 52 1 3 31 1 3...
2018-08-24 15:49:37
267
原创 A - 单点更新板子题 * （线段树）
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。Input本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5...
2018-08-22 15:06:22
157
原创 区间更新区间求和板子 *(线段树lazy)
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the ...
2018-08-22 14:59:52
255
原创 The Elevator（扩展欧几里德好题)
全是电梯。Philo正处于高度为0的一个平台上，在他面前的一个平面，全是上上下下的电梯。Philo想要离开这里，请你帮帮他。电梯世界规则：这里的电梯所能到达的层数皆为整数层，当Philo进入电梯，他只能选择上升a层或者下降b层（电梯只有这两种选择且a,b不同时为0）。对于任意整数层都有无限的电梯可乘坐（前提是Philo能够到达这一层）。Philo在第0层，现在请你帮助Phil...
2018-08-19 09:46:44
158
原创 Number Sequence (KMP模板)
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K ...
2018-08-18 10:44:16
117
原创 Oulipo 哈希
求模式串在待匹配串的出现次数。Input第一行是一个数字T，表明测试数据组数。之后每组数据都有两行：第一行为模式串，长度不大于10000；第二行为待匹配串，长度不大于1000000。所有字符串只由大写字母组成。Output每组数据输出一行结果。Sample Input4ABCDABCDABAABABABACDCDCDCCDCKMPNAIVES...
2018-08-17 20:30:04
406
原创 Crazy Search 哈希
给定一个字符串，其中含有不同的字母数量为m，现在求这个字符串中有多少个长度为n且长的互不相同的字符子串举个例子, n=3, m=4 ，字符串 "daababac". 长度为3的不同的子串分别是: "daa"; "aab"; "aba"; "bab"; "bac". 因此, 答案是5.Input第一行是两个整数n,m,，一个空格隔开。 接下来一行是我们要解决的字符串.（ 你可以认为
2018-08-17 20:27:37
133
原创 辞树的最大数(搜索)
Description 给出两个整数a和b，对于数字a可以无限次更换两个数位上的数字以构造不超过b的最大数。Input 输入：第一行输入一个整数 T（0<T<11），代表有T组数据。每行输入两个整数 a，b (0<a，b < 1e18）Output 输出：打印最大可能的数字，该数字是a的数字排列并且不大于b。每组数据输出后换行...
2018-08-16 14:34:05
95
原创 HDU3635 Dragon Balls (带权并查集)
Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together. His country has N cities...
2018-08-15 16:03:30
112
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人