区间dp 并不困难，这一类问题我的思通常是这样的：关注最终状态。我注意到了，最终只会剩一个元素。那么我们可以枚举这最后剩的一个元素。决定了最后剩的元素就帮助我们把整个区间化成了两个小区间了。类似分治了。 下面就是愉快的区间dp了 #include<cstdio> #include<algorithm> using namespace std; const int inf = 1e9; int dp[110][110],a[110],n; int main(){ scanf("%d",&n); for (int i=1;i<=n;++i)scanf("%d"...

区间dp 我想起了雨神说的一句话，dp问题没有什么难的，只要你能把他们之间的关系理清楚就好了 同样这一题算是超级麻烦了因为不可以两个括号染上相同的颜色这一个特殊条件，我们在进行区间dp的过程中，必须也同时记录两端的颜***r>把所需求解的信息都记录下来。 #include<cstdio> #include<cstring> #include<vector> using namespace std; typedef long long ll; const ll mod = 1e9+7; ll dp[710][710][3][3]; int pre[710...

区间dp 算是经典的区间dp问题 但是我上来写错了，，，唉 我的思路错了，还是要小心啊 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[110][110]; char s[110]; int n; bool check(char s1,char s2){ return (s1=='('&&s2==')')||(s1=='['&&s2==']'); } int main(){ while (scanf("%s",...

区间dp 没有好好地做过区间dp 今天算是正式地初体验没想出来，但是有点感觉先暂时不说dp地推导 我直接说怎么做地吧直接设dp[i][j]表示区间(i,j)的最小需要的衣服数量然后直接枚举长度，之后枚举断点，dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j])判断条件:c[i]==c[k]感觉好奇妙哇 形式如此的固定，正式比赛时我们是不是可以根据推导出的少量信息蒙呢？ 接下来说明转移公式真正的推导：我们要求dp[i][j]首先我们知道若i->j所有的c都不一样那么一定是j-i+1接下来我们想想，对于c[i]如果i+1->j都没有c[i]的话那么c...

搞笑的题 这题其实类似于上面的一个也和前缀有关的题就是不断地套next 但是刚开始我理解错题义了直接开始二分 更离谱的是我二分还写错了，没有写r=mid-1这一句 然后我ac了真的是离谱 #include<cstdio> #include<cstring> using namespace std; const int max_n = 1e6+100; int n; int net[max_n]; void getnext(char p[]){ net[0]=-1; for (int i=0,j=-1;i<n;){ if (j==-1||p[i]==p[j])net...

模板题，同样没有难度。顺便一提，因为Manacher的算法他会预处理插入分割符所以我们无论在统计长度还是其他什么信息时是相对比较麻烦的有时候甚至是要进行分类讨论。难点就在这里 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int max_n = 3e5+100; int n; void Manacher(char s[],int d[],char ts[]){ int m=n*2+1; fill(d,d+m+10,1); for (int...

没有难度的模板题 我们可以直接先上Manacher然后就能够找到最长的回文子串 然后我们对字串进行解码如何进行解码？巧妙地利用取模。试几次就出来了 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 2e5+100; void Manacher(char s[],int d[],char ts[]){ int n = strlen(s); fill(d,d+n*2+10,1); for (int i=0,j=0;i&lt...

仍然可以说是Manacher算法的模板题并不需要改动算法内部成分我们需要对每个索引处再记录他到左边满足严格单调不递减的最大长度然后遍历统计的时候，取小就可以了 另外这里我说一下，我觉得无论是kmp，扩展kmp，Manacher抑或是后缀数组 我们不要仅仅在特殊的一些运用上记住他们事实上这种算法，他帮助我们维护的是一些包含字符串信息的数组这些信息的存在使得我们可以解决一些复杂的问题 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int max_...

Manache模板题 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e6+100; void Manacher(char s[],int d[],char ts[]){ int n = strlen(s); fill(d,d+2*n+10,1); for (int i=0,j=0;i<n;++i){ ts[j++]='#';ts[j++]=s[i]; }n=n*2+1;ts[n]='\0';ts[n-1]='#...

hash、hashtable 这题是真好，问我一共wa+tle共20+才做出来 正经做法好像是扩展kmp+字典树但是，我想直接用hash做于是我使用了hash(我觉得hash是真的nb，太强了！适用范围太广了！必须要好好掌握的！) 首先输入就十分的困难我们知道所有的字符串的长度之和的上限但是因为字符串可能非常之多，所以我们难以求解分配给每一个字符串空间在这里我学到了一个处理方法。我们开一个上限空间的数组然后每个字符串都搞一个头指针这个指针指向上限数组中他们开始的位置。 真的非常的巧妙。very good 然后是下一个难关：我们该如何hash呢？我们想想哈，我们hash后肯定要统计个数。那么这个...

基本思想就是暴力枚举分割处没什么难的 关键是如何判断，分割后左边和右边是否是回文的 很简单的我们可以利用扩展kmp搞当然也可以利用hash搞 随便搞 我这里用了扩展kmp #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 5e5+100; void getnext(char p[],int net[]) { register int a = 0;register int b = 0; int pn = strlen(p...

扩展kmp，循环问题 考察你对循环的理解。稍微有点绕但是没事，凭感觉往前走就好了 直接上模板 #include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int max_n = 2e6+100; int net[max_n], extend[max_n]; void getnext(char p[]) { register int a = 0;register int b = 0; int pn = str...

最小表示法 传递性的巧妙应用 以前在牛客上做过类似的题目。当时留下了很深刻的印象 #include<iostream> #include<algorithm> #include<cstring> #include<set> using namespace std; typedef unsigned long long ull; const ull base = 131; const ull mod = 1e9+7; const int max_n = 11000; int getminstring(char s[]){ int n = strle...

最大最小表示法 直接上模板，然后求一个最小循环节就好了 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e6+100; int getminstring(char s[]){ int nn = strlen(s); int i=0,j=1,k=0; while (i<nn&&j<nn&&k<nn){ if (s[(i+k)%nn]==s[(j+k)%nn])++k;...