题意： 告诉你两个字符串，问你从第一个字符串刷到第二个字符串最少需要几步？每次刷操作：可以把任意一个区间刷成同一个字母。 思路： 和LightOJ1422神似。点击打开链接 这个只是多了一步。真的感觉区间dp很神奇。 从一个字符串到另一个字符串不太好操作。 我们先考虑由空字符串刷到第二个字符串的最少操作。 先令dp[i][j]表示ij区间 空字符串刷到目标串的最少操作。 那么j个点，可以单独刷 dp[i][j]=dp[i][j-1]+1; 也可以由前面和它一样的同时刷。 dp[i][j]=min{dp[i][k]+dp[k+1][j-1]}str2[k]str2...

A HDU5695拓扑排序 m个有序关系，显然是拓扑排序。 要想分数最大，先安排大数即可。 用优先队列比较好实现。 注意分数会爆int include<cstdio> include<cstring> include<algorithm> include<iostream> include<queue> //defineintlonglong usingnamespacestd; typedeflonglongLL; intT; constintmaxn=100000+10; vector<int&g...

题意： 告诉你n天需要穿衣服的类型，你可以套着穿衣服，但是如果拖下来，这件就不能用了，求最少衣服件数。 思路： 区间dp 令dp[i][j]表示ij区间的最少衣服件数。 首先第j件衣服可以穿一个新的。 即dp[i][j]=dp[i][j-1]+1; 其次第j件衣服也可以穿前面的。 即dp[i][j]=min{dp[i][k]+dp[k+1][j-1],,a[k]a[j]}  include<cstdio> include<cstring> include<algorithm> usingnamespacestd; cons...

题意： 给你n个数（1，2，3，，，n），刚开始都是连续的，有三种操作： 1.将某个数x切割开（变的不连续） 2.恢复上一个切割的数（变的连续） 3.查询x位置数，最长连续的长度。 思路： 线段树： 需要维护l表示这个区间从左端点开始最大连续长度 r表示这个区间从右端点开始的最大连续长度 m表示这个区间的最大连续长度。 整体是单点更新，单点查询。 就是pushup比较麻烦点。 先更新父区间的l，r在根据儿子区间 来更新m。 查询稍微有些类似主席树的查询 有几个坑： 修复时，可能会修复一个未切割的结点（这时候应该不操作！！！） include<cstdio>...

题意： 给你一个图，q个查询，每个查询输出两点之间的路径中最大值的最小值。 思路： 要想路径最大值最小，边肯定在最小生成树上。 先把图建成最小生成树。 那么问题就是 输出树上两点之间的边权最大值。 赤裸裸的树剖。 可惜比赛时脑残没有想到最小生成树。 include<cstdio> include<cstring> include<algorithm> include<vector> usingnamespacestd; constintmaxn=50000+7; constintmaxt=100000+7; constinti...

思路： 也是个ac自动机裸题 给每个节点维护编号和数量就好。  因为一个节点可能会重复匹配一个病毒多次， 所以不能清空维护的数量。 include<cstdio> include<cstring> include<algorithm> include<vector> include<queue> usingnamespacestd; constintmaxn=50000+10; intans[maxn]; structTrie{ intL,root; intnext[maxn][128]; intfail[...

大体题意： 有向图中是否是任意两个点都是联通的！ 思路： 有向图的强联通分量表述的就是是否任意两个点是联通的！ 那么直接判断强联通分量是不是1个即可！ Tarjan算法！不用记录具体的强联通分量，直接结果即可！ 可以用vector建图！ include<cstdio> include<cstring> include<algorithm> include<vector> usingnamespacestd; constintmaxn=10000+10; vector<int>g[maxn]; boolinStack[maxn];...

大体题意： 括号匹配问题，要求添加尽可能少的括号使得括号匹配 ，其中空括号是匹配的，括号有[]和()两种！ 思路： dp思想： 令dp[i][j]表示字符串i位置到j位置 最少添加的括号数量！ 两种方法递推和记忆化搜索思路是一样的，说下整体思路： 如果i和j这两个位置能匹配的话，那么转移就是ans=min{dp[i+1][j-1]} 然后在类似于最优三角剖分的方法，在中间找一个位置！ 使得ans=min{dp[i][k]+dp[k+1][j]} 无论匹配不匹配都要进行第二个转移，否则[][]这种情况就转移到了][这种情况！！ 这样最终会得到 dp每个子字符串所要...

大体题意： 告诉你一个自定义的F函数求解方法，给你q个自变量（区间），求解答案！ 思路： 分析自定义的函数可以知道，我们可以变换一下这个函数，变换之后也就是F（l，r）=a[l]%a[l+1]%.....%a[r]; 如果这样纯粹的求解的话，肯定会超时的，不说有多少个操作，就是这个取模就慢的不行！ 我们知道，一个数对比他大的数取模的话，那么这个数取模后是不变的，我们可以利用这一个性质进行优化！ 我们定义nest[i]表示在i位置以后第一个不比a[i]大的数，这样我们不断的跳位置即可！因为之间的没必要进行枚举，因为取模了值也不变！这样就可以通过了！ 坑： 注意，输入的n个数会有0存在，因此不...

大体题意： 给你n个玩具，把n个玩具放到三个箱子里面，每个玩具有个标号每天玩一个玩具，每次玩时，你都要把那一箱玩具搬出来，求出玩完所有的玩具至少搬多少重量的玩具！ 思路： 题意转换一下就是求，如何把n个数分配成三组， 使得每一组的质量和乘以数量 的总和最小！ 没有找到确切的规律！ 那就枚举把！ 既然把玩具分成三组，肯定是质量相近的越好， 所以要先排个序！ 分成三组需要两个分界线！ 先枚举第一个分界线！ 想想会发现 第二个分界线左右是个凹凸性的函数，存在一个极值！ 在第一个分界线后三分第二个分界线，找到一个值最小的位置！ 注意，这样在算某个箱子时，利用前...

大体题意： 给你一个nn的棋盘，有一定量的黑棋（相当于障碍）！，让你放尽可能多的白棋（皇后），使得任意两个白棋不能相互攻击！ 思路： 想暴力的，结果也没搞出来！ 发现有6ms过得，原来不是暴力！ 请教了学长！ 可以这样考虑： 对于每一个可以放白棋的地方，把他不能攻击到的地方相连，这样最终会得到一个无向图，两个点能连通代表了两个棋子不能相互吃掉！ 最后求一个解使得任意两个棋子都不能相互吃掉！那不就是任意两个点都相互连通吗！ 这不就是一个完全图吗！ 所以这个问题转换成了求一个最大的完全图的数量！ 最大团模板 include<cstdio> include<cstring&gt...

大体题意： 两个人，一个人认为一个数如果是素数的话，那么是符合要求的，另外一个人认为这个数的因子个数是素数的话，那么才是符合要求的！ 给你一个区间[L，R]，求出该区间内同时符合两个人要求或者同时不符合两人要求数的个数! 思路： 很有意思的一道题目！ 我们可以用间接法来求，总数肯定是R-L+1可以求出符合一个但不符合另一个人数的个数！ 我们很容易想到 如果这个数是素数的话，那么他肯定是符合要求的！ 接下来，问题就转换成了 求L到R区间内有多少个数是合数并且这个数的因子个数是素数！ 求这个问题，我们就要考虑这个数的素因子了！ 假设这个数是p1^ap2^bp3c...... ...

大体题意： 如图： 告诉你长和宽的比为a：b求出 长度和宽度的实际值！ 思路： 令长为ax，宽为bx！ 那么 》 由于勾股定理： 带入得： 答案就是ax：bx了！ 代码： include<cstdio> include<cstring> include<algorithm> include<cmath> include<cstdlib> usingnamespacestd; intmain(){ doublea,b; intkase=0; while(scanf("%lf:%lf",&a,&...

FavoriteDonut TimeLimit:1500/1000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):2746    AcceptedSubmission(s):667 ProblemDescription nparts.Everyparthasitsownsugarinessthatcanbeexpressedbyaletterfromatoz(fromlowtohigh),andari...

大体题意： 有n个结点，初始时每个结点的父节点都不存在。你的任务是执行一次I操作和E操作，格式如下： Iu，v把结点u的父节点设置为v，距离为|u-v|%1000 保证u没有父节点。 Eu，询问u到根节点的距离！ 思路： 并查集： 用d[u]表示u结点到根节点的距离。 每次E操作都初始化父节点和 距离！ 每次I操作都要查一下父节点，find，在find过程中更新d数组！ 大体过程就是在递归返回的过程中更新d  d[x]+=d[pa[x]] ！仔细想想这样正好全部加回去！！ include<cstdio> include<...

RoundandRoundWeGo TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):907    AcceptedSubmission(s):464 ProblemDescription Acyclicnumberisanintegerndigitsinlengthwhich,whenmultipliedbyanyintegerfrom1ton,yieldsa{!0}...

大体题意： 给你n，m，k 从而会算出一个n个元素的集合，求出一个子集合的长度，其中子集合存在X满足X<=k; 思路： 建立一个vis数组，表示每个数出现的次数，然后一个一个数的遍历，只有满足当前数符合访问次数为1并且大小小于等于k，则cnt 然后建立一个pos表示左端的最优解的位置 寻找方法很简单 当pos位置的数vis大于1或者大小大于k都不是最优的都应该pos 最后当cntk时更新答案即可！ include<cstdio> include<cstring> include<algorithm> usingnamespac...

大体题意： 告诉你有n个学生，有n/2个牛肉堡，和n/2个鸡肉堡，求最后两个孩子吃相同汉堡的概率！ 思路： 请教的队友 先算不同的概率！ 从剩下的n-2个人中，选择(n-2)/2个人吃鸡肉，剩下(n-2)/2吃牛肉堡！ 这样概率就是C（n-2，（n-2）/2）（1/2）^(n-2） 算算递推式就可算出ans[n] =ans[n-2](n-3)1.0/(n-2); include<cstdio> include<cstring> include<algorithm> usingnamespacestd; constintmaxn=100000+...

soeasy TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):195    AcceptedSubmission(s):157 ProblemDescription n integers,assume  f(S) astheresultofexecutingxoroperationamongalltheelementsofset S.e...

题意很简单： 问一个马从起点走到终点最短步数。 思路： 简单的bfs，输入得到起点终点，直接用队列走就可以了！ include<cstdio> include<queue> usingnamespacestd; intsx,sy,gx,gy; constintINF=1e8; intidx[10][10]; constintdx[]={-1,-2,-2,-1,1,2,2,1}; constintdy[]={-2,-1,1,2,2,1,-1,-2}; typedefpair<int,int>P; intmain() { chars1[5],s2[5]; w...