数独数组【牛客tracker 每日一题】

数独数组时间限制1秒 空间限制1024M知识点模拟网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的由n nn个整数组成的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1​,a2​,…,an​}我们称其为数独数组当且仅当其每一个长度为 99 的连续子数组都包含1 ∼ 9 1 ∼ 91∼9这9 99个数字。现在对于给定的数组是否存在一种方案使得其经过重新排序后成为数独数组如果是直接输出Y E S YESYES否则输出N O NONO。注意您不必给出具体的排序方案。输入描述第一行输入一个整数n ( 9 ≦ n ≦ 10 5 ) n(9≦n≦10^5)n(9≦n≦105)代表数组中的元素数量。第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≦ a i ≦ 9 ) a_1,a_2,…,a_n(1≦a_i≦9)a1​,a2​,…,an​(1≦ai​≦9)代表数组元素。输出描述如果数组在重新排序后可以成为数独数组输出Y E S YESYES否则输出N O NONO。示例1输入9 1 2 3 4 5 6 7 9 8输出YES说明在这个样例中不需要经过重新排序数组已经是一个数独数组。示例2输入9 1 2 3 4 5 6 7 8 1输出NO解题思路本题核心是数字频率统计数学条件校验判断数组重排后能否成为数独数组。数独数组要求每9个连续元素必须包含1~9各一个因此总元素数n拆分后商k n//9余数r n%9。数字1~9的出现次数只能是k或k1且恰好有r个数字出现k1次剩余数字出现k次。遍历数组统计1~9的频次校验所有频次符合要求且高频次数字数量等于余数满足则输出YES否则NO。算法时间复杂度O ( n ) O(n)O(n)高效适配n ≤ 10 5 n≤10^5n≤105的数据规模。总结核心逻辑数独数组的必要条件是1 ∼ 9 1 ∼ 91∼9的频次仅为商/商 1 11且高频数字数量等于总长度的余数。关键操作统计数字频次校验频次合法性与数量匹配规则。效率保障线性遍历统计频率常数级条件判断无冗余计算。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N7e310;constll p1e97;constll INF1e18;constll M2e310;intmain(){ll n;cinn;ll x1n/9,x2n/91;vectorlla(10,0);for(ll i1;in;i){ll b;cinb;a[b];}ll y10,y20;for(ll i1;i9;i){if(a[i]x1)y1;elseif(a[i]x2)y2;else{coutNOendl;return0;}}if(y2(n%9))coutYESendl;elsecoutNOendl;return0;}