Gym 100548G / UVALive 7041 – The Problem to Slow Down You [回文自动机]


Link http://codeforces.com/gym/100548/attachments Mean 给你两个字符串s1和s2,求有多少个四元组(a, b, x, y)使得s1[a:b]==s2[x:y]且s1[a:b]为回文串。两串长度最长均为2e5. Analysis 比赛时用后缀数组+Manacher+RMQ+主席树瞎凑…最后还是没搞出来… 这...

Gym 100548G / UVALive 7041 – The Problem to Slow Down You [回文自动机]

Link http://codeforces.com/gym/100548/attachments Mean 给你两个字符串s1和s2,求有多少个四元组(a, b, x, y)使得s1[a:b]==s2[x:y]且s1[a:b]为回文串。两...
阅读全文 0

HDU 5880 – Family View [AC自动机]


Link http://acm.hdu.edu.cn/showproblem.php?pid=5880 Problem Steam is a digital distribution platform developed by Valve Corporation offering digital rights management (DRM), multiplayer gaming and social networking services. A family view can help...

HDU 5880 – Family View [AC自动机]

Link http://acm.hdu.edu.cn/showproblem.php?pid=5880 Problem Steam is a digital distribution platform developed by Valve Corporation offering digita...
阅读全文 0

URAL 2060 – Subpalindrome pairs [Manacher+树状数组]


Link http://acm.timus.ru/problem.aspx?space=1&num=2060 Problem Your task is to calculate number of triplets (i, j, k) such that i ≤ j < k and s[i..j] is a palindrome and s[j+1 .. k] is a palindrome. Mean 给一个最长为300000的字符串s,问有多...

URAL 2060 – Subpalindrome pairs [Manacher+树状数组]

Link http://acm.timus.ru/problem.aspx?space=1&num=2060 Problem Your task is to calculate number of triplets (i, j, k) such that i ≤ j < k an...
阅读全文 0

URAL 1713 – Key Substrings [后缀数组+RMQ]


Link http://acm.timus.ru/problem.aspx?space=1&num=1713 Problem Although the program committee works as one team, heated debates arise frequently enough. For example, there is no agreement upon which client of the version control system is mor...

URAL 1713 – Key Substrings [后缀数组+RMQ]

Link http://acm.timus.ru/problem.aspx?space=1&num=1713 Problem Although the program committee works as one team, heated debates arise frequent...
阅读全文 0

CodeForces 589K – Task processing [暴力/数学/优先队列]


Link http://codeforces.com/problemset/problem/589/K Problem Vasya wants to create a computing system to process arbitrary tasks. As a part of the system he needs an algorithm which will choose an order of task execution. He came up with the follow...

CodeForces 589K – Task processing [暴力/数学/优先队列]

Link http://codeforces.com/problemset/problem/589/K Problem Vasya wants to create a computing system to process arbitrary tasks. As a part of the s...
阅读全文 0

HDU 5818 – Joint Stacks [左偏树/优先队列]


Link http://acm.hdu.edu.cn/showproblem.php?pid=5818 Problem A stack is a data structure in which all insertions and deletions of entries are made at one end, called the “top” of the stack. The last entry which is inserted is the first ...

HDU 5818 – Joint Stacks [左偏树/优先队列]

Link http://acm.hdu.edu.cn/showproblem.php?pid=5818 Problem A stack is a data structure in which all insertions and deletions of entries are made a...
阅读全文 0

HDU 3234 – Exclusive-OR [带权并查集+XOR性质]


Link http://acm.hdu.edu.cn/showproblem.php?pid=3234 Problem You are not given n non-negative integers X0, X1, …, Xn-1 less than 2 20 , but they do exist, and their values never change. I’ll gradually provide you some facts about them, ...

HDU 3234 – Exclusive-OR [带权并查集+XOR性质]

Link http://acm.hdu.edu.cn/showproblem.php?pid=3234 Problem You are not given n non-negative integers X0, X1, …, Xn-1 less than 2 20 , but th...
阅读全文 0

HDU 4333 – Revolving Digits [扩展KMP]


Link 传送门 Problem One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he can put all the digits to the front, so he will ...

HDU 4333 – Revolving Digits [扩展KMP]

Link 传送门 Problem One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several las...
阅读全文 0

HDU 4760 – Good Firewall [Trie]


Link 传送门 Problem Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called Good Firewall (a.k.a., GFW). Network flows enter in the GFW will be forwarded or dropped according to...

HDU 4760 – Good Firewall [Trie]

Link 传送门 Problem Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called G...
阅读全文 0

CodeForces 622C – Not Equal on a Segment [巧打表]


Link 传送门 Problem You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi. For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi. The first line contains two integers n, m (1 ...

CodeForces 622C – Not Equal on a Segment [巧打表]

Link 传送门 Problem You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi. For the i-th query...
阅读全文 0