当前位置: 首页 > news >正文

个人骗分导论

1.贪心

这个不讲了,根据题目来贪心就行了。

比如说取模后求 max,从大往小枚举。

2.暴力

这种就很多方法了,举几个例子:

  • 枚举(子集,染色等等)
  • DFS/BFS
  • 迭代加深搜索IDA*
  • 折半搜索
  • 双向宽搜

然后我们暴力时还可以剪枝,比较常见的有最优性剪枝,可行性剪枝,估价函数剪枝等等。

3.打表

一般来讲分为朴素打表和分段打表。

分段打表一般用于比较容易递推(可递推且依赖状态较少)的情况。

根据打表尝试推规律,这个就有点难了,凭感觉。

不过可以列一个类似于 f(i)=A*f(i-1)+B*f(i-2)+C*f(i-3)之类的例子来列一下,看看能不能整出来。

还可以看看有没有积性函数的性质。

4.随机化/模拟退火

这个东西就比较强了,一般有这种性质的写了基本上有大分。

随机化,不言而喻,有些题目每次找到答案的概率较大(比如1/2或1/3),用随机化跑跑总没错。

然后,讲一下很 NB 的模拟退火:

模拟退火算法较适用于在较大或复杂的解空间中寻找近似全局最优解的优化问题,特别是当问题存在多个局部最优解,且传统贪心算法容易陷入局部最优时。

基本上板子不用改,背下来就好:

void mnth(){// 初始温度T0  终止温度Te  衰减系数Tx for(double t=1e4;t>1e-4;t*=0.99){int a=rand()%m+1,b=rand()%m+1;int now=calc();swap(e[a],e[b]);if(n+(e[n].x==10)==m){//满足约束条件int nxt=calc();//当前情况下的价值int delta=nxt-now;if(delta > 0){} else {if(exp(delta/t) < (double)rand()/RAND_MAX){swap(e[a],e[b]);}}}else swap(e[a],e[b]);}
}

max 改成 min只需要把:

int delta=nxt-now;if(delta > 0){} else {if(exp(delta/t) < (double)rand()/RAND_MAX){swap(e[a],e[b]);}
}

改成:

int delta=nxt-now;if(delta < 0){} else {if(exp(-delta/t) < (double)rand()/RAND_MAX){swap(e[a],e[b]);}
}
http://www.hskmm.com/?act=detail&tid=36112

相关文章:

  • Java三大特性
  • 高级程序设计第二次作业
  • 10月21日日记
  • home-assistant.-Adding integrations
  • Windows系统内存占用过高,且任务管理器找不到对应进程
  • NOIP 二十五
  • 理想婚姻
  • equal和hashcode
  • Ancestral Problem 题解
  • AWS IAM角色最佳实践:构建云安全的核心防线
  • 正睿 2025 NOIP 20连测 Day6
  • Hetao P5593 删 题解 [ 蓝 ] [ 线性 DP ] [ DFS 序 ] [ 虚树 ]
  • o(N^2)找出所有回文子串
  • 第二次高级程序作业
  • 大学生需要认真听课的肌肉记忆(注意力训练)
  • 初始人工智能和机器学习
  • 10/21
  • 蛋白表达技术概述
  • 二叉树的中序遍历- 递归原理 - MKT
  • 友链测试
  • 二叉树的中序遍历- 二叉树基本-递归 - MKT
  • 做了一个概率小游戏,没想到服务器被打爆被攻击了!原因竟然是他?真没想到...
  • 接下来的目标
  • 阿里云对象存储OSS之Java - Soul
  • 敬启,致那时的我
  • 后量子密码学技术与标准化进程解析
  • 10月21日
  • 清楚标签默认样式,内容溢出盒子时的处理
  • 用 大模型 和 Gradio 构建一个 AI 反向词典
  • MySQL 事务