Codeforces Round #479


Codeforces 977 C Less or Equal

题意

找到一个数 \(x\) 满足数列中恰好有 \(k\) 个数小于等于 \(x\) 。

分析

显然,只需要排序以后判断第 \(k\) 个数与第 \(k+1\) 个数是否相等即可。

  • 如果相等,显然不存在这样的 \(x\);
  • 如果不想等,显然输出 \(x\) 就是满足要求的答案。

需要注意特别处理 \(k=0\) 和 \(k=n\) 的情况(无法比较第 \(k\) 个数与第 \(k+1\) 个数)。

特别地,当 \(k=0\) 的时候

  • 如果最小的数是 \(1\) ,由于要求 \(x\) 必须在 \([1,10^9]\) 范围内,则不存在这样的 \(x\) ,输出 \(-1\) ;
  • 否则输出最小的数 \(-1\) 即可。 

Codeforces 977 D Divide by three, multiply by two

题意

一个数 \(x\) 有两种变化方式:

  • 如果 \(x\) 是 \(3\) 的倍数,变成 \(x/3\) ;
  • 变成 \(2x\) 

给出一个数列,将这个数列重组,满足上述的变化方式。

分析

将每个数看作一个点,满足变化方式的点之间连有向边。

以每一个点作为根跑一遍 dfs ,求出任意一条长度为 \(n\) 的链就是答案。

Codeforces 977 E Cyclic Components

题意

询问图中有多少联通块是一个简单环。

分析

对于一个联通块,如果他是一个简单环,当且仅当每一个点的度数都为 \(2\) 。

于是我们用 dfs 将每一个联通块标记出来,计算每一个联通块的最小度数和最大度数。

如果一个联通块满足最小度数 \(=\) 最大度数 \(=2\) ,那么这个联通块就是一个简单环,统计这样的数量即可。

Codeforces 977 F Consecutive Subsequence

题意

求数列中最长的连续子序列。

分析

显然,对于一个数 \(x\) 之前如果存在若干个 \(x-1\) ,我们一定会从最靠后的 \(x-1\) 转移过来,因为相对来说,越靠后,最长的连续子序列可能越长。

于是我们只需要知道,每一个数最后出现的位置进行转移。

因为数范围是 \([1,10^9]\) ,我们用 map 辅助转移即可。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 129,017

Categories

Archive

Comments