0w1

IOICJ

IOICJ 35 Stamp Problem ( Z-value, Union Find )

Problem Description: You are given a string S. You want to find minimum length of string A, such that you could print S with A stamped on a paper arbitrary times. When making a new stamp, it is allowed to cover part of the string on the pa…

IOICJ 57 LCM Problem ( Math, Search )

Problem Description: Given N, you want to know max{ LCM(x,y,z), 1≤x,y,z≤N }.Constraints: 1≤T≤1000 1≤n≤1e6Sample Input: 3 7 9 100Sample Output: 210 504 960300Solution: It is obvious that we would like some of the largest x, y, z, such that …

IOICJ 36 Interval Sum EX ( Math, Segment Tree )

Problem Description: You are given an array A wit length N. You need to support these operations, noted with [ p, e, c ]: if p = 0: __square root and discard non-integer value of range [ e, c ] if p = 1: __change value at e to c if p = 2: …

IOICJ 108 Where is He! ( Tree, Timestamp )

Problem Description: You are given a tree with N nodes. There are Q queries, with u, v, w, where you want to know the node x such that x is a node in the simple path between u and v, where it is also the nearest to w.Constraints: 1≤T≤50 2≤…

IOICJ 109 Big Tower ( DP, Deque )

Problem Description: There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to trav…

IOICJ 102 No Title ( FFT )

Problem Description: Given N integers A[ 0, N ), you want to know how many ordered tuples ( i, j, k ) satisfy: 1 ≤ i, j, k ≤ N and A[ i ] + A[ j ] = A[ k ] Constraints: 1≤T≤10 3≤n≤1e5 −50000≤a1,a2,…,an≤50000Sample Input: 3 3 1 2 3 4 2 2 2 …

IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description: Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.Constraints: 1≤T≤300 3≤n≤1e5 1≤xi,yi≤n A valid tree …

IOICJ 82 Minions ( DP )

Problem Description: Currently you have n minions in a row on the war field, where each minion at the i'th position shows an attack value of a[ i ]. You have another m aces yet to be summoned. You can set aces at both ends or between any t…

IOICJ 77 Lowest Common Ancestor ( DFS )

Problem Description: Node 1 denotes the root of the tree. You are given the parent nodes of 2 ~ N. Count for all v the number of ordered pairs such that their LCA is v. Constraints: 1≤T≤100 2≤n≤100000 1≤pi vvi G; vl ans; vi size; void dfs(…

IOICJ 88 Necklace 2 ( Hash )

Problem Description: lo has a string Slo, and li has a string Sli. You want to find the maximum length of common palindrome substring of both strings.Constraints: 1≤T≤30 1≤|Slo|,|Sli|≤100000Sample Input: 2 abaxyza xyzaaba abaxyzwvcddcpirik…

IOICJ 89 Tool Man ( DP )

Problem Description: You are given an array A consisting of N elements. You know that they are K different people's orders, where some consecutive elements are what they have ordered. You also know that every order was ordered by some one,…

IOICJ 31 Repeated String ( KMP )

Problem Description: Given string S, find A with minimum length, such that S is equivalent to A being concatenated several times.Constraints: 1≤T≤100 1≤|S|≤1e5 TL: 1000 msSample Input: 3 ababab aaabaaab aaabaaaSample Output: 2 4 7Solution:…