1.28学习总结

2024-01-29 20:04
文章标签 学习 总结 1.28

本文主要是介绍1.28学习总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

队列：
1.求区间所有后缀最大值的位置（单调队列）
搜索：
1.天下第一（记忆化）
2.拯救oibh总部（DFS+连通性问题）
3.国王的魔镜（递归）
4.回家（BFS+三维的标记）
5.取数游戏(DFS)
6.数的划分（递归）

求区间所有后缀最大值的位置https://www.luogu.com.cn/problem/B3667

题目描述

给定一个长度为 �n 的数列 �a，对于其中每个长度为 �k 的子区间，请你求出这个这个子区间构成的数列的所有后缀最大值的位置个数。

一个下标 �i 是是数列 �b 的后缀最大值下标当且仅当：对于所有的 �<�≤∣�∣i<j≤∣b∣，都有 ��>��bi​>bj​，其中 ∣�∣∣b∣ 表示 �b 的元素个数。

输入格式

第一行是两个整数，依次表示操作次数 �n 和子区间长度 �k。
第二行有 �n 个整数，第 �i 个整数表示 ��ai​。

输出格式

共输出 �−�+1n−k+1 行每行一个整数，按左端点从小到大的顺序依次输出每个子区间构成的数列的后缀最大值位置个数。

输入输出样例

输入 #1复制

5 3
2 1 3 5 4

输出 #1复制

1
1
2

说明/提示

样例 1 解释

第一个子数列：2,1,32,1,3。其中 33 是后缀最大值。
第二个子数列：1,3,51,3,5，其中 55 是后缀最大值。
第三个子数列：3,5,43,5,4，其中 55 和 44 是后缀最大值。

数据规模与约定

对于全部的测试点，保证 1≤�≤�≤1061≤k≤n≤106，1≤��<2641≤xi​<264。

思路：本质上是找单调队列的队内元素个数

#include <bits/stdc++.h>
using namespace std;
unsigned long long  a[1000005];
int main()
{int n,k;cin>>n>>k;for (int i=1;i<=n;++i)cin>>a[i];deque<unsigned long long>q;for (int i=1;i<=n;++i){while (!q.empty() && a[q.back()]<a[i])q.pop_back();if (!q.empty()&& i-q.front()>=k)q.pop_front();q.push_back(i);if (i>=k)cout<<q.size()<<endl;}
}
天下第一https://www.luogu.com.cn/problem/P5635

题目背景

天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后，开始了自己休闲的生活，并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人，所以 zhouwc 虽然是一个蒟蒻，也有能和 cbw 玩游戏的机会。

题目描述

游戏是这样的：

给定两个数 �x，�y，与一个模数 �p。

cbw 拥有数 �x，zhouwc 拥有数 �y。

第一个回合：�←(�+�) mod �x←(x+y)modp。

第二个回合：�←(�+�) mod �y←(x+y)modp。

第三个回合：�←(�+�) mod �x←(x+y)modp。

第四个回合：�←(�+�) mod �y←(x+y)modp。

以此类推....

如果 �x 先到 00，则 cbw 胜利。如果 �y 先到 00，则 zhouwc 胜利。如果 �,�x,y 都不能到 00，则为平局。

cbw 为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。

输入格式

有多组数据。

第一行：�T 和 �p 表示一共有 �T 组数据且模数都为 �p。

以下 �T 行，每行两个数 �,�x,y。

输出格式

共 �T 行

11 表示 cbw 获胜，22 表示 zhouwc 获胜，error 表示平局。

输入输出样例

输入 #1复制

1 10
1 3

输出 #1复制

error

输入 #2复制

1 10
4 5

输出 #2复制

1

说明/提示

1≤�≤2001≤T≤200。

1≤�,�,�≤100001≤x,y,p≤10000。

思路：用记忆化搜索，不需要管它每一轮的变化，把x，y一直变。谁先到0谁就赢

#include <bits/stdc++.h>
using namespace std;
short vis[10010][10010];
int t,mod;
int f(int x ,int y)
{if (vis[x][y])return vis[x][y];if (vis[x][y]==-1)return -1;vis[x][y]=-1;if (!x)return 1;if (!y)return 2;int num=(x+y)%mod;vis[x][y]=f(num,(num+y)%mod);return vis[x][y];
}
int main()
{cin>>t>>mod;while (t--){int x,y;cin>>x>>y;int ans=f(x,y);if (ans==-1)cout<<"error"<<endl;else if (ans==1)cout<<ans<<endl;else if (ans==2)cout<<ans<<endl; }
}
拯救oibh总部https://www.luogu.com.cn/problem/P1506

题目背景

oibh 总部突然被水淹没了！现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 �,�x,y。

接下来 �x 行，每行 �y 个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

输入输出样例

输入 #1复制

4 5
00000
00*00
0*0*0
00*00

输出 #1复制

1

输入 #2复制

5 5
*****
*0*0*
**0**
*0*0*
*****

输出 #2复制

5

说明/提示

对于 100%100% 的数据，1≤�,�≤5001≤x,y≤500。

思路：考察搜索的连通性问题，以边界为起点，搜索一边，把0全部变成*，最后再找剩余0的个数

#include <bits/stdc++.h>
using namespace std;
char mp[550][550];
int vis[550][550];
int n,m;
void dfs(int x ,int y)
{if (mp[x][y]=='*')return;mp[x][y]='*'; vis[x][y]=1;int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};for (int i=0;i<4;++i){int tx=x+dir[i][0],ty=y+dir[i][1];if (tx<0|| ty<0|| tx>n || ty>m)continue;if (mp[tx][ty]=='0' &&vis[tx][ty]==0){dfs(tx,ty);}}vis[x][y]=0;
}
int main()
{cin>>n>>m;for (int i=0;i<n;++i)cin>>mp[i];for (int i = 0; i < n; ++i){dfs(i, 0);dfs(i, m - 1);}for (int j = 0; j < m; ++j){dfs(0, j);dfs(n - 1, j);}int cnt=0;for (int i=0;i<n;++i){for (int j=0;j<m;++j){if (mp[i][j]=='0')cnt++;}}cout<<cnt;
}
国王的魔镜https://www.luogu.com.cn/problem/P2799

题目描述

国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用AB来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为ABBA。如果再用一端接触的话，则会变成ABBAABBA（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

输入格式

只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

输出格式

只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。

输入输出样例

输入 #1复制

ABBAABBA

输出 #1复制

2

思路：递归

#include <bits/stdc++.h>
using namespace std;
int f(string &s,int length)
{if (length==1)return length;int idx=length/2-1;string qian=s.substr(0,idx+1);string hou=s.substr(idx+1);reverse(hou.begin(),hou.end());if (qian==hou){return f(qian,length/2);}else {return length;}
}
int main()
{string s;cin>>s;int length=s.length();length=f(s,length);cout<<length;
}

回家https://www.luogu.com.cn/problem/P2802

题目描述

小 H 在一个划分成了 �×�n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 66 点，每移动一格他要消耗 11 点血量。一旦小 H 的血量降到 00， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。

地图上有五种格子：

0：障碍物。

1：空地， 小 H 可以自由行走。

2：小 H 出发点， 也是一片空地。

3：小 H 的家。

4：有鼠标在上面的空地。

小 H 能否安全回家？如果能， 最短需要多长时间呢？

输入格式

第一行两个整数 �,�n,m， 表示地图的大小为 �×�n×m。

下面 �n 行， 每行 �m 个数字来描述地图。

输出格式

一行， 若小 H 不能回家， 输出 -1，否则输出他回家所需最短时间。

输入输出样例

输入 #1复制

3 3
2 1 1
1 1 0
1 1 3

输出 #1复制

4

说明/提示

对于所有数据，1≤�,�≤91≤n,m≤9。

思路：BFS，但是由于还多了一个血量，所以在建立标记数组的时候应该用三维的，因为可能到达同一个点，但是血量不同

#include <bits/stdc++.h>
using namespace std;
struct Node{int xueliang;int x;int y;int t;
};
int vis[10][10][7];
int mp[10][10];
int main()
{int n,m;cin>>n>>m;int start_x,start_y;for (int i=0;i<n;++i){for (int j=0;j<m;++j){cin>>mp[i][j];if (mp[i][j]==2){start_x=i,start_y=j;}}}queue<Node>q;int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};q.push(Node{6,start_x,start_y,0});vis[start_x][start_y][6]=1;while (!q.empty()){Node news=q.front();q.pop();for (int i=0;i<4;++i){int tx=news.x+dir[i][0],ty=news.y+dir[i][1];if (tx<0 || ty<0 || tx>n ||ty>m || vis[tx][ty][news.xueliang-1])continue;if (mp[tx][ty]==1 && news.xueliang>1 ){Node olds=Node{news.xueliang-1,tx,ty,news.t+1};q.push(olds);vis[tx][ty][news.xueliang-1]=1;}else if (mp[tx][ty]==3&& news.xueliang>1){cout<<news.t+1;return 0;}else if (mp[tx][ty]==3&& news.xueliang<=1){continue;}else if (mp[tx][ty]==4 && news.xueliang>1){Node olds=Node{6,tx,ty,news.t+1};vis[tx][ty][6]=1;q.push(olds);}else if (mp[tx][ty]==4 && news.xueliang<=1) {continue;}else if (news.xueliang==0){continue;}}}cout<<-1;return 0;	
}
取数游戏https://www.luogu.com.cn/problem/P1123

题目描述

一个 �×�N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 88 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式

第一行有一个正整数 �T，表示了有 �T 组数据。

对于每一组数据，第一行有两个正整数 �N 和 �M，表示了数字矩阵为 �N 行 �M 列。

接下来 �N 行，每行 �M 个非负整数，描述了这个数字矩阵。

输出格式

共 �T 行，每行一个非负整数，输出所求得的答案。

输入输出样例

输入 #1复制

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

输出 #1复制

271
172
99

说明/提示

样例解释

对于第一组数据，取数方式如下：

[67]7563102929[92]14[21]687156867[91]25[67]29[21]8​75296867​63[92]71[91]​10145625​

数据范围及约定

  • 对于20%20%的数据，1≤�,�≤31≤N,M≤3；
  • 对于40%40%的数据，1≤�,�≤41≤N,M≤4；
  • 对于60%60%的数据，1≤�,�≤51≤N,M≤5；
  • 对于100%100%的数据，1≤�,�≤61≤N,M≤6，1≤�≤201≤T≤20。

思路：DFS加剪枝

#include <bits/stdc++.h>
using namespace std;
int t,n,m;
int mp[8][8];
int dir[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
int vis[8][8];
int maxn=0;
void dfs(int x,int y,int sum)
{if (x==n+1){maxn=max(maxn,sum);return ;}if (y==m+1){dfs(x+1,1,sum);return;}dfs(x,y+1,sum);if (vis[x][y]==0){for (int i=0;i<8;++i){int tx=x+dir[i][0],ty=y+dir[i][1];vis[tx][ty]++;}dfs(x,y+1,sum+mp[x][y]);for (int i=0;i<8;++i){int tx=x+dir[i][0],ty=y+dir[i][1];vis[tx][ty]--;}}
}
int main()
{int t;scanf("%d",&t);while (t--){memset(mp,0,sizeof(mp));memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for (int i=1;i<=n;++i){for (int j=1;j<=m;++j){scanf("%d",&mp[i][j]);}}dfs(1,1,0);printf("%d\n",maxn);maxn=0;}
}
数的划分https://www.luogu.com.cn/problem/P1025

题目描述

将整数 �n 分成 �k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：�=7n=7，�=3k=3，下面三种分法被认为是相同的。

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

问有多少种不同的分法。

输入格式

�,�n,k （6<�≤2006<n≤200，2≤�≤62≤k≤6）

输出格式

11 个整数，即不同的分法。

输入输出样例

输入 #1复制

7 3

输出 #1复制

4

说明/提示

四种分法为：
1,1,51,1,5;
1,2,41,2,4;
1,3,31,3,3;
2,2,32,2,3.

思路：DFS，类似全排但是要剪枝

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int k,n,cnt;
void dfs(int minx,int sum,int len)
{if (len==k){if (sum==n){cnt++;}return ;}for (int i=minx;sum+i*(k-len)<=n;++i){dfs(i,sum+i,len+1);}
}
int main()
{cin>>n>>k;dfs(1,0,0);cout<<cnt;
}

这篇关于1.28学习总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/658029。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
51单片机学习记录———定时器

51单片机学习记录———定时器

文章目录 前言一、定时器介绍二、STC89C52定时器资源三、定时器框图四、定时器模式五、定时器相关寄存器六、定时器练习 前言 一个学习嵌入式的小白~ 有问题评论区或私信指出~ 提示：以下是本篇文章正文内容，下面案例可供参考 一、定时器介绍 定时器介绍：51单片机的定时器属于单片机的内部资源，其电路的连接和运转均在单片机内部完成。 定时器作用： 1.用于计数系统，可
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
[word] word设置上标快捷键 #学习方法#其他#媒体

[word] word设置上标快捷键 #学习方法#其他#媒体

word设置上标快捷键 办公中，少不了使用word，这个是大家必备的软件，今天给大家分享word设置上标快捷键，希望在办公中能帮到您！ 1、添加上标 在录入一些公式，或者是化学产品时，需要添加上标内容，按下快捷键Ctrl+shift++就能将需要的内容设置为上标符号。 word设置上标快捷键的方法就是以上内容了，需要的小伙伴都可以试一试呢！
阅读更多...
AssetBundle学习笔记

AssetBundle学习笔记

AssetBundle是unity自定义的资源格式，通过调用引擎的资源打包接口对资源进行打包成.assetbundle格式的资源包。本文介绍了AssetBundle的生成，使用，加载，卸载以及Unity资源更新的一个基本步骤。 目录 1.定义： 2.AssetBundle的生成： 1）设置AssetBundle包的属性——通过编辑器界面 补充：分组策略 2）调用引擎接口API
阅读更多...
Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
《offer来了》第二章学习笔记

《offer来了》第二章学习笔记

1.集合 Java四种集合：List、Queue、Set和Map 1.1.List：可重复 有序的Collection ArrayList： 基于数组实现，增删慢，查询快，线程不安全 Vector： 基于数组实现，增删慢，查询快，线程安全 LinkedList： 基于双向链实现，增删快，查询慢，线程不安全 1.2.Queue：队列 ArrayBlockingQueue：
阅读更多...
十五.各设计模式总结与对比

十五.各设计模式总结与对比

1.各设计模式总结与对比 1.1.课程目标 1、 简要分析GoF 23种设计模式和设计原则,做整体认知。 2、 剖析Spirng的编程思想，启发思维,为之后深入学习Spring做铺垫。 3、 了解各设计模式之间的关联，解决设计模式混淆的问题。 1.2.内容定位 1、 掌握设计模式的"道" ，而不只是"术" 2、 道可道非常道，滴水石穿非一日之功，做好长期修炼的准备。 3、 不要为了
阅读更多...
硬件基础知识——自学习梳理

硬件基础知识——自学习梳理

计算机存储分为闪存和永久性存储。 硬盘（永久存储）主要分为机械磁盘和固态硬盘。 机械磁盘主要靠磁颗粒的正负极方向来存储0或1，且机械磁盘没有使用寿命。 固态硬盘就有使用寿命了，大概支持30w次的读写操作。 闪存使用的是电容进行存储，断电数据就没了。 器件之间传输bit数据在总线上是一个一个传输的，因为通过电压传输（电流不稳定），但是电压属于电势能，所以可以叠加互相干扰，这也就是硬盘，U盘
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2