Codeforces Round #381 (Div. 1) A. Alyona and mex

太过爱你忘了你带给我的痛 2022-07-14 02:24 177阅读 0赞

这道题我觉得题意看懂了,大问题也就没有了。
一个比较简单的思维题。

mex是不在子串中的最小非负数,那么对于一个子串而言,最大的mex就是子串的长度+1。

因为子串的长度不一,那么mex就有一个范围,题意就是让你使得mex的最小值最大化,也就是保证最小长度的子串(假设长度为len)能够取到[0, len-1]的数。

那么,看到0~len-1就要想到 取模 。需要保证无论我的最短子串取在何处都可以取到0~len-1,则必然满足条件。

  1. n, m = map(int, raw_input().split())
  2. ans = 100000000;
  3. for i in range(m):
  4. a,b = map(int, raw_input().split())
  5. ans = min(ans, b-a+1)
  6. print ans
  7. print(' '.join(str(i%ans) for i in range(n)))

发表评论

表情:
评论列表 (有 0 条评论,177人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Codeforces Round #564 (Div. 1)

    A 太难了,一半时间刚这题还没做出来,简直自闭了。实际上分两种情况,一种很简单直接放,另一种就是要0,0,…,0,1,2,…,n,然后直接贪心,显然我是把情况判断错误一直没调