睡前床边看LIVE时间限制1 秒空间限制512 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述作为 PISK 的一大特色玩家们可以化身豆腐人聚集在一个虚拟世界观看游戏角色的 3D 演出。而在演出开始之前有一群染过色的豆腐人围成了一圈你打算从中了解一些信息。一共有n nn个豆腐人每个豆腐人都染上了一个颜色。它们能看见其它n − 1 n - 1n−1个豆腐人的颜色但是无法知道自己是什么颜色。现在你对每个豆腐人都问了相同的问题“在你看见的n − 1 n - 1n−1个豆腐人中最多有多少个豆腐人它们的颜色是一样的”每个豆腐人都向你回答了一个整数。请问你是否能根据以上的信息判断出一定有豆腐人说谎了补充说明在本题中“一定有豆腐人说谎了”等价于不存在任何一种染色方案使得每个豆腐人的回答与实际相符。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 4 ) T\ (1 \le T \le 10^4)T(1≤T≤104)代表数据组数。每组测试数据描述如下第一行输入一个正整数n ( 2 ≤ n ≤ 2 × 10 5 ) n\ (2 \le n \le 2 \times 10^5)n(2≤n≤2×105)第二行输入n nn个正整数a 1 , a 2 , … , a n ( 1 ≤ a i n ) a_1, a_2, \dots, a_n\ (1 \le a_i n)a1,a2,…,an(1≤ain)代表每个豆腐人的回答。对于同一个测试点保证所有n nn之和不超过2 × 10 5 2 \times 10^52×105。输出描述对于每组数据如果你能判断出一定有豆腐人说谎了输出Lie否则输出Other。示例示例 1输入6 2 1 1 4 1 1 2 2 6 2 4 1 3 4 3 5 2 2 2 2 2 5 3 3 3 3 3 5 4 4 4 4 4输出Other Other Lie Other Lie Other说明为了方便解释我们假设每个豆腐人的颜色都可以被大写英文字母表示且相同的字母表示的是相同的颜色。第一组数据n 2 n2n2回答为1 1在两个豆腐人的情况中无论它们的颜色是否一样回答只会是1 1。因此不存在说谎输出Other。第二组数据n 4 n4n4回答为1 1 2 2假设四个人的颜色是A, A, B, C那么前两个人都会看到三种颜色的豆腐人各一个回答1 11后两个人会看到两个颜色A的豆腐人回答2 22。因此这种情况有可能发生输出Other。第三组数据n 6 n6n6回答为2 4 1 3 4 3不存在合法的染色方案一定有豆腐人说谎输出Lie。第四组数据n 5 n5n5回答为2 2 2 2 2一种符合所有豆腐人回答的颜色情况可能是A, A, B, B, C因此输出Other。第五组数据n 5 n5n5回答为3 3 3 3 3不存在合法的染色方案一定有豆腐人说谎输出Lie。第六组数据n 5 n5n5回答为4 4 4 4 4存在合法的染色方案输出Other。数据范围与提示1 ≤ T ≤ 10 4 1 \le T \le 10^41≤T≤1042 ≤ n ≤ 2 × 10 5 2 \le n \le 2 \times 10^52≤n≤2×1051 ≤ a i n 1 \le a_i n1≤ain所有测试数据的n nn之和不超过2 × 10 5 2 \times 10^52×105本题的核心是判断给定的回答数组是否存在一种染色方案与之对应属于组合存在性判定问题。解题思路本题是组合存在性判定问题给定每个豆腐人看到的其他n − 1 n-1n−1人中最大同色人数判断是否存在一种染色方案使得这些回答全部与实际相符。通过分析颜色组大小与回答的关系可以推导出合法的回答分布必须满足的几个必要条件只需统计最小值、最大值及最小值的出现次数即可O ( n ) O(n)O(n)判定。1. 问题等价转化设n nn个豆腐人的颜色分布中最大颜色组的大小为M MM即出现最多的颜色的个数。对于任意一个豆腐人如果他属于某个颜色组该组大小为b j b_jbj则他看不到自己该组在他眼中只剩b j − 1 b_j-1bj−1人而其他组人数不变。他看到的“最多同色人数”为max ( b j − 1 , 其他组最大人数 ) \max(b_j-1,\ \text{其他组最大人数})max(bj−1,其他组最大人数)。根据M MM和最大组的唯一性回答的分布只有以下三种可能所有豆腐人颜色相同只有一种颜色M n MnMn。每个人看到其他n − 1 n-1n−1个人全是同色回答均为n − 1 n-1n−1。此时最小回答m n mnmn 最大回答m x mxmxn − 1 n-1n−1。最大组不唯一至少两组并列最大设M MM为最大组大小且M n MnMn存在至少两个大小为M MM的组。那么属于任一最大组的人排除自己后自己组剩M − 1 M-1M−1人但能看到另一个最大组有M MM人所以回答为M MM。不属于最大组的人能看到最大组有M MM人回答也是M MM。因此所有人回答相同即m n m x M mn mx MmnmxM且必须满足n ≥ 2 M n \ge 2Mn≥2M因为至少有两个大小为M MM的组。最大组唯一且不是全部同色最大组大小为M MM且M n M nMn其他组大小均小于M MM。那么属于最大组的人排除自己后自己组剩M − 1 M-1M−1其他组最大不超过M − 1 M-1M−1因为第二大组≤ M − 1 \le M-1≤M−1所以回答为M − 1 M-1M−1。不属于最大组的人能看到最大组有M MM人回答为M MM。因此回答只有两种值M − 1 M-1M−1和M MM并且回答为M − 1 M-1M−1的人数恰好等于最大组大小M MM。即m n M − 1 mn M-1mnM−1m x M mx MmxM且m n mnmn的出现次数c m M m x cm M mxcmMmx。2. 判定条件根据上述分析给定回答数组只需统计m n mnmn最小回答值m x mxmx最大回答值c m cmcm最小回答值出现的次数。然后检查以下条件是否成立若m x − m n 1 mx - mn 1mx−mn1显然不合法因为合法时回答值最多只有M − 1 M-1M−1和M MM两种相差≤ 1 \le 1≤1。若m x m n mx mnmxmn若m x n − 1 mx n-1mxn−1对应全部同色合法否则必须满足m x × 2 ≤ n mx \times 2 \le nmx×2≤n即至少存在两组大小为m x mxmx的组合法否则不合法。若m x m n 1 mx mn 1mxmn1必须满足c m m x cm mxcmmx最大组唯一且最大组大小等于回答M − 1 M-1M−1的人数合法否则不合法。3. 复杂度分析时间复杂度每组数据只需一次线性扫描统计m n , m x , c m mn, mx, cmmn,mx,cmO ( n ) O(n)O(n)所有数据n nn之和≤ 2 × 10 5 \le 2\times 10^5≤2×105总时间O ( ∑ n ) O(\sum n)O(∑n)。空间复杂度仅需常数级变量O ( 1 ) O(1)O(1)。总结通过分析颜色组大小与回答的关系将问题简化为三种互斥情形。合法回答序列的形态只有两种全相同或差1 11且对最值出现次数有精确要求。因此只需扫描一遍即可判定是否存在对应染色方案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll mn,mx,cm;boolchk(){if(mx-mn1)returnfalse;if(mxmn)returnmxn-1||mx*2n;returncmmx;}voidsol(){cinn;mnn;mx0;cm0;for(ll i0;in;i){ll a;cina;mxmax(mx,a);if(amn){mna;cm1;}elseif(amn)cm;}cout(chk()?Other\n:Lie\n);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cinT;while(T--)sol();return0;}
