The Parity(ceoi99) algorithm, devised by Xiao Tian, involves establishing an array called sum, where sum[i] represents whether the sum from 1 to i is odd (true) or even (false), with sum[0] initialized as false. This allows any given question (a,b) to be expressed using the expression sum[b] xor sum[a-1].
Initially, the values of sum[1..n] are unknown and assumed to be false, meaning that any sum[a] and sum[b] are independent. For each question (a,b,c), we can determine the relationship between sum[b] and sum[a-1] by using the equation sum[b] xor sum[a-1]=c. This step can be performed using a disjoint-set data structure. If sum[a-1] and sum[b] do not belong to the same set for a given question, they are merged into the same set. If sum[a-1] xor sum[b] does not equal c, a contradiction is detected, and the total sentence count is output before exiting.
For a consistent sum array without contradictions, each set is divided into two parts, with one part designated as true and the other as false. This allows for the determination of the sum array. Using the equation sum[i] xor sum[i-1], we can calculate the value of the ith digit. Since there are no questions asked between different sets, this sequence of numbers represents a valid solution, proving the correctness of the algorithm. It is often used in various algorithms.
我的内容管理
展开
