HBC231131牛妹和01串,排序,贪心Circle of Life题解

凉芷 算法基础篇 75 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
Specifically, a crash will happen in two situations: The right splited Twinkle in vertex iii and the left splited Twinkle in vertex i+2i+2i+2 will crash in vertex i+1i+1i+1. The right splited Twinkle in vertex iii and the left splited Twinkle in vertex i+1i+1i+1 will crash in the iii-th edge. Lucky hopes there's always some Twinkle living on the chain. In addition, in order to be more convenient for Lucky to check the validity, there should be duplicated configurations within 2n2n2n seconds. Specifically, a configuration can be denoted by a binary string SSS of length nnn, where Si=1S_i = 1Si=1 iff vertex iii lives a Twinkle, and CiC_iCi denotes the configuration after iii seconds. Your task is to find an initial configuration C0C_0C0 so that for each i,Ci≠0000i,, C_i neq 00cdots00i,Ci=0000 and that there exist two integers i,j(0≤i

Your friend Lucky is a little elf. Recently, Lucky discovered a magical creature, she named them ``Twinkle''. Lucky has a magical chain of nnn vertices and n−1n-1n−1 edges, where the vertices are connected by the edges one by one. We assume that the vertices are numbered 111 to nnn from left to right, and the iii-th edge connects vertex iii and vertex i+1i+1i+1. She found that Twinkles could live in the magical chain. Lucky can put some Twinkles on some vertices simultaneously with her magic, but there should be at most one Twinkle in one vertex since the near Twinkles will perish together. Then, every second, each Twinkle will split into two Twinkles simultaneously and they will dash in the opposite directions to the two adjacent vertices. Formally, a Twinkle in vertex uuu splits into two Twinkles, the left splited Twinkle and the right splited Twinkle. The left splited Twinkle will dash toward the left and reach the vertex u−1u-1u−1. The right splited Twinkle will dash toward the right and reach the vertex u+1u+1u+1. But unluckily, if one side has no vertex, the Twinkle will dash out of the chain and die out(for the left splited Twinkle in vertex 111 and the right splited Twinkle in vertex nnn). Much more unfortunately, if two Twinkles dash to have a head-on collision (i.e. meet in the same vertex or edge), they will perish together with a tearing crash! Specifically, a crash will happen in two situations:  The right splited Twinkle in vertex iii and the left splited Twinkle in vertex i+2i+2i+2 will crash in vertex i+1i+1i+1(assuming that vertex i+1i+1i+1 lives no Twinkle).  The right splited Twinkle in vertex iii and the left splited Twinkle in vertex i+1i+1i+1 will crash in the iii-th edge. Lucky hopes there's always some Twinkle living on the chain. In addition, in order to be more convenient for Lucky to check the validity, there should be duplicated configurations within 2n2n2n seconds. Specifically, a configuration can be denoted by a binary string SSS of length nnn, where Si=1S_i = 1Si​=1 iff vertex iii lives a Twinkle, and CiC_iCi​ denotes the configuration after iii seconds. Your task is to find an initial configuration C0C_0C0​ so that for each i (0≤i≤2n),Ci≠00⋯00i,(0le i le 2n), C_i neq 00cdots00i(0≤i≤2n),Ci​​=00⋯00 and that there exist two integers i,j (0≤i

HBC231131牛妹和01串,排序,贪心Circle of Life题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
成为编程大师,不再是梦想!全网最全C++题库,助您开启编程新篇章。

标签: HBC231131牛妹和01串 排序 贪心Circle of Life题解