3
已解决
新手光能
1.冲刺A班暑期内容
1.文件操作如果考，那就是所有题都考
2.分段收费如果考，顶多1题
3.小数处理通常和分段收费一起考
4.字符串模拟稍微简单一些，主要跟题目有关
字符串模拟跟普通模拟差不多，只不过是字符串
5.枚举法，可能不会单独考，骗分可用
6.桶，基本都会考，是重点
7. map，也许会考，通常会跟桶一起用
8.日期问题，应该不考
9.周期问题，可能会跟模拟一起用
10.平面几何一般不考
11.数论是一种数学概念，所以可能会考
12.筛法通常是优化
13.贪心基本应该都会考，贪心策略
14.模拟，可以说基本上全部都考
15.栈，可能会考
16.滑动窗口主要是优化，考试时可以用上
2.搜索
dfs的概念：
dfs是不撞南墙不回头
只有搜到底，才回溯继续朝下一个反向搜
通常会需要一个dir方向数组
四个方向的dir:
int dir[5][2]={{0},{-1,0},{1,0},{0,-1},{0,1}};
八个方向的dir:
int dir[9][2]={{0},{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
dfs(迷宫问题)的代码:
int dir[5][2]={{0},{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){
if(x==n&&y==m){
return ;
}
for(int i=1;i<=4;i++){
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&!vis[dx][dy]){
vis[dx][dy]=true;
dfs(dx,dy);
vis[dx][dy]=false;
}
}
}
dfs(全排列)代码:
bool vis[15];
int path[15];
void dfs(int pos){//pos代表当前填的是第几个格子
if(pos==n+1){
for(int i=1;i<=n;i++){
cout<<path[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){//遍历要填的数字i
if(!vis[i]){//i这个数没有填
vis[i]=true;
path[pos]=i;//填数 第pos个格子填i
dfs(pos+1);
vis[i]=false;
}
}
}
dfs(组合的输出):
int path[15];
int n,r;//r:为每几个一个排列
void dfs(int pos){
if(pos==r+1){
for(int i=1;i<=r;i++){
cout<<path[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=path[pos-1]+1;i<=n;i++){
psth[pos]=i;
dfs(pos+1);
}
}
dfs(素数环):
int n,cnt;
bool vis[25];
int path[25];
bool Judge(int x){
if(x<2) return false;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
void dfs(int pos){
if(pos==n+1){
if(Judge(path[n]+path[1])){
cnt++;
for(int i=1;i<=n;i++){
cout<<path[i]<<" ";
}
cout<<endl;
}
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]&&Judge(path[pos-1]+i)||pos==1){
vis[i]=true;
path[pos]=i;
dfs(pos+1);
vis[i]=false;
}
}
return ;
}
dfs(八皇后) :
int cnt;
int path[15];
bool vis[15];
bool b[15];
bool c[17];
void dfs(int pos){
if(pos>8){
cnt++;
if(cnt<=5){
for(int i=1;i<=8;i++){
cout<<path[i]<<" ";
}
cout<<endl;
}
return ;
}
for(int i=1;i<=8;i++){
if(!vis[i]&&!b[pos-i+7]&&!c[pos+i]){
path[pos]=i;
vis[i]=true;
b[pos-i+7]=true;
c[pos+i]=true;
dfs(pos+1);
vis[i]=false;
b[pos-i+7]=false;
c[pos+i]=false;
}
}
return ;
}
3.动态规划
动态规划主要有以下几步：
1.状态是什么
2.状态转移方程
3.目标
4.边界
由于动规有点难，所以考试通常会用白板或者画图来做图进行解答
DP最大连续子数组和：
1.状态为：
f[i] 前i个元素 必含第i个元素的最大连续子数组和
f[i-1] 前i-1个元素 必含第i-1个元素的最大连续子数组和
2.代码实现：
while(t--){//此处为多组数据
ans=-0x3f3f3f3f;//多组数据处理
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){//整个for为状态转移方程
if(f[i-1]<=0)
f[i]=a[i];
else
f[i]=f[i-1]+a[i];
ans=max(ans,f[i]);
}
cout<<ans<<endl;
}
DP最长不下降子序列：
1.状态为：
f[i] 前i个元素必含第i个元素的最长不下降子序列长度
2.代码实现：
for(int i=1;i<=n;i++){
f[i]=1;//边界
for(int j=1;j<i;j++){//内层循环为状态转移方程
if(a[i]>=a[j]){
f[i]=max(f[i],f[j]+1);
}
}
ans=max(ans,f[i]);//ans为目标
}
DP最长公共子序列(注:公共子序列通常可能跟字符串连用):
1.状态为：
f[i][j] A中前i个元素和B中前j个元素的最长公共子序列长度（不必含）
2.代码实现：
getline(cin,a); //输入两个字符串
getline(cin,b);
n=a.size(),m=b.size();
a=" "+a,b=" "+b;//对字符串进行预处理,下标从1开始
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){//内层循环为状态转移方程
if(a[i]==b[j]){
f[i][j]=f[i-1][j-1]+1;
}else{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
}
cout<<f[n][m]; //目标
其他DP：
主要是我们上面讲的这4点
再重复一遍
1.状态是什么
2.状态转移方程
3.目标
4.边界
01背包：
这个背包是用DP写的
普通的01背包空间复杂度有点高
所以我们要加上降维
不然可能MLE
1.状态为:
f[i][j] 前i个物品选择一些放入容量为j的背包中获得最大价值
2.代码实现:
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];//vi为价值，wi为时间
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){//内层为状态转移方程
if(j>=v[i]){
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}else{
f[i][j]=f[i-1][j];
}
}
}
cout<<f[n][m]; //目标
滑动窗口:
滑动窗口主要是用于优化
通常是通过一个while循环
滑动窗口准确来讲不能算DP
代码如下(此处以布展(diff)这道题为例):
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);//排序
int l=1,r=n-k;//此处为固定窗口大小
while(r<=n){
ans=min(ans,a[r]-a[l]);//求窗口内的最小值，其实是通用的，得知道本题窗口维护的是什么
l++;
r++;
}
cout<<ans;
4.放平心态
火箭班升创新班没有讲创新班那么难
放平心态，考出好成绩
如果有人跟我一样火箭班升创新班，那么让我们一起放平心态，考出好成绩！
焦胤轩在2024-08-24 16:32:20追加了内容
这个也可以算是给新学的同学们的一个代码注释，毕竟我可能随时都要走，这个帖子可能是我的最后一个帖子
0
已采纳
新手光能
哦，我的同学，我们秋季还要上课哈
0
中级光能
DA LAO ZAI JIAN
0
初级光能
再见
0
高级守护
感谢！
0
新手光能
加油，我的同学，你一定成功渡过这一劫！！如果考不上，唉……
人生自古谁无死？留取丹心照酷町……
0
初级光能
加油加油加油
你一定可以的
