NEERC2014

2024-03-20 22:43:16

题目描述：给出一个\(n \times m\)的国际象棋棋盘，每次选定一个矩形，使得矩形中的每个格子的颜色翻转，求出最少次数的方案使得最终棋盘只有一种颜色。

solution
先翻转所有偶数行，再翻转所有偶数列。

时间复杂度：\(O(n)\)

题目描述：有\(n\)中香料，每种香料有两个值\(a_i,b_i\)，表示每用\(1\)克第\(i\)种香料，总的\(a\)增加\(a_i\)，总的\(b\)增加\(b_i\)，求出一种方案，使得总的\(a\)超过\(A\)，总的\(b\)小于\(B\)，且总的\(a\)最大。可以是小数。

solution
按\(a_i/b_i\)从大到小排序，依次选取。

时间复杂度：\(O(nlogn)\)

题目描述：难以描述。

solution
暴力\(bitset\)即可。

时间复杂度：\(O(10^9/64)\)

题目描述：给出一个\(n\)的排列，在一条数轴上将相邻的数字连边，然后\(0\)与第一个数字连边，现在移动一些点，使得边不相交（可以包含），问最多多少个点不同。

solution
题目可以转化为求最长的振荡幅度越来越小的振荡子序列，可以分别求出以某个数字结尾的最长上升子序列和最长下降子序列，枚举分解线\(i\)，以\(i\)结尾最长上升子序列+以\(i+1\)为结尾最长下降子序列的和更新答案。

时间复杂度：\(O(nlogn)\)

题目描述：有一个\(n\)排列，给出这个排列删掉空格之后的字符串，还原这个排列。

solution
字符串的长度决定\(n\)，然后搜索即可。

时间复杂度：\(O(能过)\)

题目描述：有\(n\)辆车在数轴上行驶，每辆车在\([a_i, b_i]\)间往返行驶，速度相同，有若干个询问，每次询问一个区间在\(t_i\)时刻有多少辆车。

solution
暴力枚举。

时间复杂度：\(O(nm)\)

码农公寓