hdu 5835 题目链接 题意：n种礼物，每种a[i]个。现在有无穷个小朋友排成一排，分给每个人一个“普通”的礼物，一个“昂贵”的礼物（哪个普通哪个昂贵是自己定的，或者说，任意的） 要求是相邻的小朋友的普通的礼物不能是同一种。现在问最多能给多少小朋友分礼物。。。 思路：容易知道，因为昂贵的礼物是没有限制的。。所以没什么用。。考虑礼物总数sum..那么最多只可能分给sum/2个小朋友。。。然后再两个指针模拟一下。。记得特判n=1的情况。1A /* *********************************************** Author :111qqz Created Time :2016年08月14 …

hdu 5842题目链接 题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。 思路：上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下 /* *********************************************** Author :111qqz Created Time :2016年08月14日 星期日 12时13分22秒 File Name :code/ccpc2016/1011.cpp ************************************************ */ …

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 03时22分47秒 File Name :code/hdu/3374.cpp …

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 02时44分21秒 File Name :code/hdu/2609.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。 思路：先做个变换，按照题意，第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8; 然后求出最小表示开始的位置。。输出即可。 /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 02时17分45秒 File Name :code/poj/4162.cpp …

poj 1509 题目链接 题意&思路：同uva 1314 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 18时48分29秒 File Name :code/uva/1314.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

uva 1314 题目链接 题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 18时48分29秒 File Name :code/uva/1314.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

首先放一波资料：叶子豪_最小表示法 周源_《浅谈最小表示法在字符串循环同构问题中的应用》 参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。 一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。 令i=0,j=1 如果S[i] S[j] i=j, j=i+1 如果S[i] S[j+k] i=j,j=i+1** _ 否则j++ **返回i** 注意到，朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。 令i=0,j=1 如果S[i] S[j] i=j, …

hdu 4300题目链接 吐槽：题意难懂的一逼，关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。？本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。 题意：给一个26个字母一一对应的密码表。 然后给出一个字符串，先是密文再是明文，明文可能不全。问最小的可能的密文+明文串是什么。。 思路： 把字符串按照密码表转化得到一个新的字符串，然后跑kmp得到原字符串a的后缀等于转化后的字符串b的前缀的最长长度的字符串。（需要注意的是,kmp匹配的时候，由于密文长度一定是大于等于明文的，并且如果字符串a和字符串b相等，匹配全部是没有意义的，所以我们从中间位置开始匹配，更具体的说，是从第一个后面的字符串 …

hdu 3336 题目链接 题意：给一个字符串，问这个字符串的所有前缀的出现次数的和。 思路：这道题需要完全理解nxt函数是干嘛的。。nxt[i]表示的是字符串的0..i-1位中，前缀和后缀相等的串的最长长度为nxt[i] 这东西对于这道题有什么用呢？ 举个例子，对于字符串ababa： s a b a b a i 0 1 2 3 4 5 next[i] -1 0 0 1 2 3 ans初始为len(因为长度为len的字符串有len个前缀，每个前缀至少出现一次) next[3] = 1，ans + 1 = 6，next[1] = 0 next[4] = 2，ans + 1 = 7，next[2] = 0 next[5] = 3，ans …