NEERC2014

NEERC2014

A - Alter Board

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

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

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

B - Burrito King

题目描述:有\(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)\)

C - Cactus Generator

D - Damage Assessment

E - Epic Win!

F - Filter

题目描述:难以描述。

solution
暴力\(bitset\)即可。

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

G - Gomoku

H - Hidden Maze

I - Improvements

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

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

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

J - Jokewithpermutation

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

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

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

K - Knockout Racing

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

solution
暴力枚举。

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

上一篇:Python 绘制图表之我见 ---一个java程序员的看法


下一篇:做为一个Python程序员的基本素养