这个式子看起来很复杂不知道如何解,但其实也很简单,我们还有一个条件没有用上。就是f必然是一个递增函数,这个其实不需要严格证明,我们直观上就可以感受出来。既然f是递增函数,那么上面式子当中很多元素的大小关系就都明显了。

这样递推式就出来了,我们接下来要做的就是根据这个递推式写出它的通项。

我们把上面的式子全部累加在一起,右边带有f的项会被全部消掉,最终得到:。这个表达式有了,那么代码自然手到擒来。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
using namespace std;
const int N=1000050;
const long long Mod=1000000007;

int t, x;

int main() {
    scanf("%d", &t);
    rep(z, 0, t) {
        scanf("%d", &x);
        printf("%d\n", int(log(x)/log(2)) + 1);
    }
    return 0;
}

感想

这道题从难度上来讲其实不大,但是真正在笔试的过程当中遇到,估计很多同学可能做不出来。倒不是因为算法有多难,而是会一开始的时候就走了歪路,比如去思考怎么样选择k,比如去想递推的解法等等。这种对问题的敏感和思路是需要练习的,并不是看几篇文章或者是听听大牛讲课就可以获得的。

一般公司的笔试题不会很难,往往都是这种需要缜密思考的思维题,这种题多做多练很容易就摸到套路了。如果对这些问题感兴趣可以看看codeforces专题,里面有很多有趣的思维题。

今天的文章就到这里,衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话,请来一个三连支持吧~(点赞、关注、转发

原文链接,求个关注

{{uploading-image-72342.png(uploading...)}}

12-08 21:49
查看更多