程序员经验分享-hwhale

考研机试题 -- 字符串、背包、枚举

2023-11-19

首字母大写（字符串）

https://www.noobdream.com/DreamJudge/Issue/page/1240/
如何读入一行字符串（getline），如何分开每个单词，如何转大写（toupper）

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	getline(cin, s);
	
	for(int i = 0; i < s.length(); i ++) {
		if(i == 0 || s[i - 1] == ' ')
			cout << (char)toupper(s[i]);
		else
			cout << s[i];	
	}
	return 0;
}

日志排序（字符串，双关键字排序）

https://www.noobdream.com/DreamJudge/Issue/page/1227/
双关键字排序，如何分割字符串（stringstream），如何从一个字符串中读数据（sscanf）

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 10010;
int n;

struct log {
	string s; //原始数据 
	string t1; //开始执行时间 
	double time; //消耗时间 
	
	bool operator < (const log &w) const {
		if(time != w.time) return time < w.time;
		else return t1 < w.t1;
	}
	
} logs[N];

int main() {
	string s;

	while(getline(cin, logs[n].s) && logs[n].s.length() != 0) {
		stringstream ssin(logs[n].s);
		string str1, str2, str3, str4;
		ssin >> str1 >> str2 >> str3 >> str4;
		logs[n].t1 = str2 + str3; //年月日和时分秒合并 
		sscanf(str4.c_str(), "%lf(s)", &logs[n].time); //提取浮点数	
		n ++;
	}
	
	sort(logs, logs + n);
	
	for(int i = 0; i < n; i ++)
		cout << logs[i].s << endl; 
	return 0;	
}

stringstream的用法：

#include<sstream>
string str[3];
string s = "aa bb cc";
stringstream ss(s);
ss >> str[0] >> str[1] >> str[2];

sscanf的用法：注意sscanf第一个参数是char数组

string s = "1234.5678abcd";
double a;
sscanf(s.c_str(), "%lf", &a);

字符串转换整数（字符串）

https://www.acwing.com/problem/content/3507/

#include <iostream>
#include <string>
#include <cstring>
#include <limits.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	bool flag = false;
	long long LL = 0; //记得初始化
	 
	for(int i = 0; i < s.length(); i ++) {
		if(isdigit(s[i])) {
			flag = true;
			LL = LL * 10 + (s[i] - '0'); //易错，s[i]要减去'0' 
			if(LL > INT_MAX) { //INT_MAX在cmlits头文件，int最大值2^31-1
				flag = false;
				break;
			}
			if(!isdigit(s[i + 1])) {
				break;
			}
		}
	}
	
	if(flag) cout << LL; 
	else cout << -1;
	
	return 0;
}

法二：不用flag，当for循环发现第一个数字时，用while循环找出完整的整数

#include <iostream>
#include <string>
#include <cstring>
#include <limits.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	 
	for(int i = 0; i < s.length(); i ++) {
		if(isdigit(s[i])) {
			long long LL = 0;
			while(i < s.length() && isdigit(s[i])) {
				LL = LL * 10 + (s[i] - '0');
				if(LL > INT_MAX) {
					cout << -1;
					return 0;
				}
				i ++;
			}
			cout << LL;
			return 0;
		}
	}
	cout << -1;
	
	return 0;
}

点菜问题（01背包）

https://www.noobdream.com/DreamJudge/Issue/page/1247/
f[i][j]表示从前 i 个物品中任选，总重量不超过 j 的集合，其属性为最大价值

#include <iostream>
using namespace std;

const int N = 1010;
int c, n, v[N], p[N], f[N][N];

int main() {
	cin >> c >> n;
	for(int i = 1; i <= n; i ++)
		cin >> p[i] >> v[i];
		
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= c; j ++) {
			f[i][j] = f[i - 1][j];
			if(j >= p[i]) 
				f[i][j] = max(f[i][j], f[i - 1][j - p[i]] + v[i]);
		}
	}
	
	cout << f[n][c];
	return 0;	
}

优化为一维数组：

#include <iostream>
using namespace std;

const int N = 110;
int c, n, v[N], p[N], f[N];

int main() {
	cin >> c >> n;
	for(int i = 1; i <= n; i ++)
		cin >> p[i] >> v[i];
		
	for(int i = 1; i <= n; i ++) {
		for(int j = c; j >= p[i]; j --) {
			f[j] = max(f[j], f[j - p[i]] + v[i]);
		}
	}
	
	cout << f[c];
	return 0;	
}

神奇的口袋（01背包，计数）

https://www.noobdream.com/DreamJudge/Issue/page/1242/
f[i][j]表示从前 i 个物品中任选，总重量恰好为 j 的集合，其属性为方案数
划分成两个子集合：选 i 和不选 i；f[i][j]等于两个子集合的方案数相加，即f[i][j] = f[i - 1][j] + f[i - 1][j - wi]

#include <iostream>
using namespace std;

const int N = 50;
int n, f[N][N], w[N];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> w[i];
		
	f[0][0] = 1; //f[0][0]需要初始化成1。因为什么i=0表示都不选，此时总重量恰好为1，这也是一种方案
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= 40; j ++) {
			f[i][j] = f[i - 1][j];
			if(j >= w[i])
				f[i][j] += f[i - 1][j - w[i]];
		}
	}
	
	cout << f[n][40];
	return 0;
}

整数拆分（完全背包，计数）

https://www.noobdream.com/DreamJudge/Issue/page/1158/
每个2^n当作物品，1、2、4、8、16…为每个物品的重量。每个数可以选无限次（完全背包）
f[i][j]表示前 i 个物品任选，总体积恰好为 j 的总方案数

注意：此题使用二维数组会爆内存，因此要优化为一维数组

//原始解法：使用二维数组
#include <iostream>
using namespace std;

const int N = 1e6 + 10, MOD = 1e9;

int n, f[10000][10000], w[N];

int main() {
	cin >> n;
	w[1] = 1;
	for(int i = 2; i <= n; i ++) { //将所有2次幂保存在w中
		w[i] = w[i - 1] * 2;
	}
			
	f[0][0] = 1;
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= n; j ++) {
			f[i][j] = f[i - 1][j];
			if(j >= w[i])
				f[i][j] = f[i][j] + f[i][j - w[i]];
		}
	}
	
	cout << f[n][n];
	return 0;
}

优化为一维数组：

#include <iostream>
using namespace std;

const int N = 1e6 + 10, MOD = 1e9;

int n, f[N];

int main() {
	cin >> n;

	f[0] = 1;
	for(int i = 1; i <= n; i *= 2) {
		for(int j = i; j <= n; j ++) {
			f[j] = (f[j] + f[j - i]) % MOD;
		}
	}
	
	cout << f[n];
	return 0;
}

CCF201512-2 消除类游戏（枚举）

https://blog.csdn.net/qq_51800570/article/details/122933824

#include <iostream>
#include <cstring>
using namespace std;

const int N = 40;
int n, m, a[N][N], b[N][N];

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			cin >> a[i][j];
			
	memset(b, 0, sizeof b);
	
	//按行枚举 
	for(int i = 0; i < n; i ++) {
		for(int j = 1; j < m - 1; j ++) {
			if(a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1]) {
				b[i][j - 1] = 1;
				b[i][j] = 1;
				b[i][j + 1] = 1;
			}
		}
	}		
	//按列枚举
	for(int j = 0; j < m; j ++) {
		for(int i = 1; i < n - 1; i ++) {
			if(a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j]) {
				b[i - 1][j] = 1;
				b[i][j] = 1;
				b[i + 1][j] = 1;
			}
		}
	}	
	
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			if(b[i][j] == 1) cout << 0 << " ";
			else cout << a[i][j] << " ";
		}	
		cout << endl;
	}
	
	return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

考研

算法

考研机试题 -- 字符串、背包、枚举 的相关文章

随机推荐

  • doris-查询原理

    目录 一 查询简介 二 查询流程 1 Query 接收 2 Query Parse 3 Query Analyze 4 Query Rewrite 5 Plan 5 1 Query 单机Plan 5 2 Query 分布式Plan 6 Qu

  • 【bug】antd全局的主题色样式被覆盖,被修改为`antd`默认的主题色

    背景 项目本身修改了主题色 配置如下 umi配置文件 export default theme primary color 2F54EB 全局主色 需要对图片上传组件做封装 并在项目中统一引用 如下 import TdsUpload fro

  • mapengpeng1999@163.com 操作系统4~处理机调度

    处理机调度 1 三级调度体系 1 处理机调度主要是对处理机运行时间进行分配 即 按照一定算法或策略 将处理机运行时间分配给各个并发进程 同时尽量提高处理机的使用效率 2 现代操作系统中 按调度所实现的功能分3种类型 高级调度 中级调度和低级

  • python3 爬取36氪新闻网页

    一个做了反爬的36氪 返回数据恶心 感觉是一堆垃圾 这里只是记录一下爬取过程 一 爬取环境 win10 python3 scrapy 二 爬取过程 1 入口 搜索 2 动态js数据加载 查看下一页操作 3 返回数据 4 请求链接 http

  • Jmeter 数据库压力测试

    一 jmeter本地数据库压力测试 1 将JMeterPlugins Extras jar和JMeterPlugins Standard jar放到apache jmeter 3 0 lib ext目录下 2 在本地打开ServerAgen

  • 操作系统学习（九）进程通信

    一 知识总览 二 定义 进程通信是指进程之间的信息交换 每个进程都拥有自己的内存空间 是相互独立的 这样在每个进程执行时 才不会被其他进程所干扰 三 进程通信的方式 1 共享存储 1 两个进程对共享区的访问必须是互斥的 即在同一时间内 只允

  • C语言实现kafka多线程,【转】c++（11）使用librdkafka库实现kafka的消费实例

    版权声明 本文为博主原创文章 遵循 CC 4 0 by sa 版权协议 转载请附上原文出处链接和本声明 本文链接 https blog csdn net lijinqi1987 article details 76691170 librdk

  • AspectJ使用

    一 AOP介绍 AOP Aspect Oriented Programming 面向切面编程 是一种新的方法论 编程范式 是对传统 OOP Object Oriented Programming 面向对象编程 的补充 旨在通过允许横切关注点

  • 2022 React 面试题（50道）

    什么是同源 如果两个页面 接口 的协议 域名 端口号都相同 我们认为他们具6511有相同的源 UmiJs和dva roadhog是什么关系 roadhog 是基于 webpack 的封装工具 目的是简化 webpack 的配置 umi 可以

  • 初学Linux基本的命令操作应当记牢

    Linux管理文件和目录的命令 命令 功能 命令 功能 pwd 显示当前目录 ls 查看目录下的内容 cd 改变所在目录 cat 显示文件的内容 grep 在文件中查找某字符 cp 复制文件 touch 创建文件 mv 移动文件 rm 删除

  • 7.Closing non transactional SqlSession 导致事务失败问题

    博主在研究Spring事务源码 编写测试代码时 出现了Closing non transactional SqlSession 导致事务失败的问题 于是写下这篇文章 记录一下这个问题 前提 已经通过配置方式 开启了 Spring 声明式事务

  • JS练习_九九乘法表

    效果图 分析 1 先使用基本的for循环嵌套 展示乘法表 2 完

  • Qt使用https

    Qt貌似默认是不支持SSl认证的 可以这样操作 将 libeay32 dll和ssleay32 dll这两个库文件拷贝到程序生成目录下 即生成exe的同级目录 或者拷贝到QtNetwork模块的库文件目录中 路径示例 E Qt Qt5 12

  • qt orm 基于Qt的ORM框架QyOrm，类似peewee，最简单的语法，最高效的使用

    QyOrm Gitee传送门 支持功能 AutoGenerate根据数据库表自动生成类的定义代码 外键 实例化 联合查询 特殊查询 Json的读取和保存 QT GUI常见input widget 的双向绑定 以下是使用的例子 手动 类的定义

  • 第一篇：PyGame小游戏——2D迷宫游戏（16W字详解）

    目录 在开头的开场白 在CSDN看到一篇 利用深度优先算法自动生成随机迷宫 的blog 突发灵感 就想做这个迷宫游戏 本文大部分讲的意思 而非代码 文章最后会展示最终代码和图片的 读者不用过多地注意那些 本文是作者第一次写blog 难免有些

  • 【Java编程】关于Java的几个基础问题

    关于Java的几个基础问题 String 和 StringBuffer 和 StringBuilder 的异同 相同点 三者在 Java 中都是用来处理字符串的 三个类都被 final 修饰 因此都是不可继承的 StringBuilder

  • 超级等级福利礼包

    文章目录 一 介绍 二 设计等级礼包的目的 1 提升游戏玩家活跃度 2 提升游戏用户吸引力 3 提高游戏用户留存率 4 实现间接收入 5 持续营收 三 玩家心理总结 四 总结该模式的赢利点 五 该模式的应用场景举例 一 介绍 超级等级福利礼

  • 二分查找(C语言版)

    刚刚学到到的知识 掌握的不怎么好 如有不足麻烦留言 第一步 先理清你要查找的数组 最好是有序排序的数组 本人还没学到数组的排序就只能用有序的数组来 int arr 10 1 2 3 4 5 6 7 8 9 10 第二步 计算出该数组的长度

  • MATLAB（1）MATLAB工作环境

    目录 工具栏 当前文件夹窗口 命令行窗口 工作区 文件编辑窗口 图形 Figure x 窗口 本文基于MATLAB R2020b MATLAB刚打开时 一般如下图所示 包括上方的工具栏 左侧的当前文件夹窗口 中间的命令行窗口以及最右侧的工作

  • 考研机试题 -- 字符串、背包、枚举

    目录 首字母大写 字符串 日志排序 字符串 双关键字排序 字符串转换整数 字符串 点菜问题 01背包 神奇的口袋 01背包 计数 整数拆分 完全背包 计数 CCF201512 2 消除类游戏 枚举 首字母大写 字符串 https www n

热门标签