原来以前主页打不开是cf使用了谷歌字体库的原因,用360镜像字体库替换之后总算能正常访问了。以后有空会补题+做一些比赛。希望有生之年能打到2200rating
两道简单的想法题
1.2^n个人进行淘汰赛,每相邻的两个人比一场,胜利的进入下一轮。给出两个人的编号,假设他们实力足够强,求他们在第几轮相遇
思路:记总人数为N,若ab分别位于两个半区(a小于等于N/2和b大于N/2,则他们在第n轮相遇,否则相遇轮数至多为n-1,将人数缩减到一半(若a大于N/2 则将ab都减去N/2)重复上述判断直到ab落在两个半区
2.给出n个整数,极差不超过2,求一个新的数列,满足极差不超过2,平均值与原数列相同,新数列的数与原数列尽可能不同(不同数的个数尽可能多)
思路:任何数列可以转换成(-1,0,1)的数列,两个数列满足和值相同。
若原数列只有-1 0或者0 1,则新数列必须和原数列相同
考虑有三种数的情况,记原数列和值为S,假设S大于0,则新数列中至少有S个1,记剩下的数个数为K=n-S,则其中最多有K/2个1,最少有0个1,只需比较这两种极限情况下与原数列不同元素个数即可