柒葉灬 的博客

柒葉灬 的博客

做题技巧(个人笔记2)

posted on 2018-08-25 21:05:02 | under 计数 |
  • 比赛的时候看到了计数的题目,需要注意什么???


  • 举个栗子例子,比如说输出方案的个数,如果有多个询问就看最大方案总和,如果最后这答案ans>1e8,那么说明肯定不是酱紫的
  int ans=0;
  for(int i=1;i<=n;i++)
    if(check(i))ans++;
  cout<<ans<<endl;

所以应该怎么解才应该是对的呢?


  • 1.如果题目在树上进行,一般是进行 dsu启发式合并 进行统计。

  • 2.其次,再观察 离线做 能不能更加方便,如果是离线的话,则直接离线即可。

  • 3.那么,如果离线还不行该怎么办?无论在树上还是线性结构上, 倍增(+贪心) 是个不错的选择。

END