※ 引述《fatcat8127 (胖胖猫)》之铭言： : 如题，题目在中女中的OJ上(http://tcgs.tc.edu.tw:1218/ShowProblem?problemid=z033) : 目前没人通过且NPSC补完计画上的程式码也是会TLE，当年的纪录也没有队伍AC。 : 题目的数字个数最多会有 1e6 个，虽然时限是 6s : 但枚举任意组的开头和结尾形成的子区间判断会吃TLE。 : 附个暴力法实作的 Code : https://www.codepile.net/pile/oVxp1RVO : 想问一下这题有O(N^2)的暴力法外的其他作法吗? 先讲一下如果数字范围<64的话要怎麽做: 假设数字只有K种 那我就能用 K bits 表示"目前各种数字总数之奇偶性" 比方说看完1 1 3 2 3, 共有三种数字, 那他们的数量(2,1,2)奇偶性就是 0 1 0 假设 state[i] 为加入第i个数字时的奇偶性, 共有三种数字 那 state[0] = 000 而区间 [i,j] 是一个符合题目要求的区间 等於是 state[i-1] 跟 state[j] 每个bit要完全一样 以区间尾巴j的角度来看 要数有几个满足的区间头, 就等於是数跟state[j]同样的家伙出现了几次 因为数字最多只有64种, 所以奇偶状态可以用long long表达, 要做到上面的事情, 只要用一个 map<long long, int> 做为各奇偶状态的counter就好 总而言之, 每加入一个Ai -> 更新奇偶状态 -> 将答案加上"以目前位置为尾巴的区间数量" -> counter++ 但到目前为止都不是困难的事 此题的数字种类为1e6种, 根本不可能去存各奇偶状态的counter, 於是仔细想想, 奇偶状态虽然总可能性有 2^(1e6) 种, 跑完阵列却也只会出现 1e6种而已, 所以拿个够大的数字%掉, 不要运气太差的话就会过了= = https://paste.ofcode.org/vnnTrh5q4sW2BfZRv2mWTU --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.231.71.98 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1555915738.A.900.html ※ 编辑: GYLin (61.231.71.98), 04/22/2019 14:49:56 ※ 编辑: GYLin (61.231.71.98), 04/22/2019 14:51:17 ※ 编辑: GYLin (61.231.71.98), 04/22/2019 14:51:59