成都定制网站建设地址,怎样不让网站自动跳转wap,黑龙江省公共资源交易中心,关键词排名优化网站建设公司哪家好兔子与兔子
很久很久以前#xff0c;森林里住着一群兔子。 有一天#xff0c;兔子们想要研究自己的 DNA 序列。 我们首先选取一个好长好长的 DNA 序列#xff08;小兔子是外星生物#xff0c;DNA 序列可能包含 26 个小写英文字母#xff09;。 然后我们每次选择两个区间森林里住着一群兔子。 有一天兔子们想要研究自己的 DNA 序列。 我们首先选取一个好长好长的 DNA 序列小兔子是外星生物DNA 序列可能包含 26 个小写英文字母。 然后我们每次选择两个区间询问如果用两个区间里的 DNA 序列分别生产出来两只兔子这两个兔子是否一模一样。 注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
输入格式 第一行输入一个 DNA 字符串 S。 第二行一个数字 m表示 m 次询问。 接下来 m 行每行四个数字 l1,r1,l2,r2分别表示此次询问的两个区间注意字符串的位置从1开始编号。
输出格式 对于每次询问输出一行表示结果。 如果两只兔子完全相同输出 Yes否则输出 No注意大小写。
数据范围 1≤length(S),m≤1000000 输入样例 aabbaabb 3 1 3 5 7 1 3 6 8 1 2 1 2 输出样例 Yes No Yes 我们都知道Hash的思想就是把字符转化为便于比较的数字 在Hash中取底的话有两个经验值 131 1331这两个的重复率更低。 还有一个值得注意的就是我们可以用unsigned long long 来取模这样可以避免许多操作。 这就是一道hash板子题不多说了直接上代码。
#includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
typedef unsigned long long ULL;
const int N 1e6 10;
const ULL base 131;ULL h[N], p[N];//h放的是hash值p中是base的i次方在得到某一串的字符的hash值中有用。
char s[N];
ULL get(int l, int r) {return h[r] - h[l - 1] * p[r - l 1];
}
int main() {p[0] 1;scanf(%s, s 1);int n strlen(s 1);for(int i 1; i n; i) {h[i] h[i - 1] * base s[i] - a 1;p[i] p[i - 1] * base;}int t;scanf(%d, t);while(t--) {int l1, r1, l2, r2;scanf(%d %d %d %d, l1, r1, l2, r2);ULL a get(l1, r1);ULL b get(l2, r2);printf(%s\n, a b ? Yes : No);}return 0;
}雪花雪花雪花
有N片雪花每片雪花由六个角组成每个角都有长度。 第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。 因为雪花的形状是封闭的环形所以从任何一个角开始顺时针或逆时针往后记录长度得到的六元组都代表形状相同的雪花。 例如ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6ai,1就是形状相同的雪花。 ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1也是形状相同的雪花。 我们称两片雪花形状相同当且仅当它们各自从某一角开始顺时针或逆时针记录长度能得到两个相同的六元组。 求这N片雪花中是否存在两片形状相同的雪花。
输入格式 第一行输入一个整数N代表雪花的数量。 接下来N行每行描述一片雪花。 每行包含6个整数分别代表雪花的六个角的长度这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到。 同行数值之间用空格隔开。
输出格式 如果不存在两片形状相同的雪花则输出 No two snowflakes are alike. 如果存在两片形状相同的雪花则输出 Twin snowflakes found.
数据范围 1≤n≤100000, 0≤ai,j10000000 输入样例 2 1 2 3 4 5 6 4 3 2 1 6 5 输出样例 Twin snowflakes found.
这道hash与上面又有点不一样但是意思还是很好理解的直接上代码。
#includeiostream
#includecstdio
#includealgorithm
#includemap
using namespace std;
typedef unsigned long long ULL;
mapULL, int m;
int a[10];
ULL get_hash()
{ULL sum 0, mul 1;for (int i 1; i 6; i) {sum sum a[i];mul mul * a[i];}return sum mul;
}
int main() {int n;scanf(%d, n);for(int i 0; i n; i) {for(int j 1; j 6; j)scanf(%d, a[j]);ULL k get_hash();if(m.count(k)) {puts(Twin snowflakes found.);return 0;}m[k];}puts(No two snowflakes are alike.);return 0;
}回文子串的最大长度
如果一个字符串正着读和倒着读是一样的则称它是回文的。 给定一个长度为N的字符串S求他的最长回文子串的长度是多少。
输入格式 输入将包含最多30个测试用例每个测试用例占一行以最多1000000个小写字符的形式给出。 输入以一个以字符串“END”不包括引号开头的行表示输入终止。
输出格式 对于输入中的每个测试用例输出测试用例编号和最大回文子串的长度参考样例格式。 每个输出占一行。
输入样例 abcbabcbabcba abacacbaaaab END 输出样例 Case 1: 13 Case 2: 6
这道题目还是有点意思的用了二分还有hash来找最回文串。 为了避免回文串是偶数的讨论在每个字符间都插入了一个非字母符号来减小代码讨论量所以我们只有二分回文长度的一半就行然后通过hash值比对确定回文串的长度。
#includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
typedef unsigned long long ULL;
const int N 2e6 10, base 131;
char s[N];
ULL hl[N], hr[N], p[N];
ULL hash1(int l, int r) {return hl[r] - hl[l - 1] * p[r - l 1];
}
ULL hash2(int l, int r) {return hr[r] - hr[l - 1] * p[r - l 1];
}
int main() {int t 1;while(scanf(%s, s 1) strcmp(s 1, END)) {int n strlen(s 1);for(int i 2 * n; i 1; i - 2) {s[i] s[i / 2];s[i - 1] z 1;}p[0] 1;n * 2;for(int i 1, j n; i n; i, j--) {hl[i] hl[i - 1] * base s[i] - a 1;hr[i] hr[i - 1] * base s[j] - a 1;p[i] p[i - 1] * base;}int ans 0;for(int i 1; i n; i) {int l 0, r min(i - 1, n - i);while(l r) {int mid (l r 1) 1;if(hash1(i - mid, i - 1) ! hash2(n - (i mid) 1, n - (i 1) 1)) r mid - 1;else l mid;}if(s[i l] z) ans max(ans, l 1);//这一步要注意我们插入的字符可能在最左右端这个时候我们要特殊考虑。else ans max(ans, l);}printf(Case %d: %d\n, t, ans);}return 0;
}
