HUSTOJ第14场补题赛

HUSTOJ第14场补题赛

问题 A: A - B +/- A

题目描述
You are given positive integers A and B.If A is a divisor of B, print A+B; otherwise, print B−A.
Constraints
·All values in input are integers.
·1≤A≤B≤20

输入
Input is given from Standard Input in the following format:
A B
输出
If A is a divisor of B, print A+B; otherwise, print B−A.
样例输入
4 12
样例输出
16
提示
As 4 is a divisor of 12, 4+12=16 should be printed.

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a = 0; int b = 0;
	cin >> a >> b;
	if(b % a == 0)
		cout << a + b << endl;
	else
		cout << b - a << endl;
	
	
	return 0;
}

问题 B: Foods Loved by Everyone

时间限制: 1 Sec 内存限制: 128 MB

题目描述
Katsusando loves omelette rice.
Besides, he loves crème brûlée, tenderloin steak and so on, and believes that these foods are all loved by everyone.
To prove that hypothesis, he conducted a survey on M kinds of foods and asked N people whether they like these foods or not.
The i-th person answered that he/she only likes the Ai1-th, Ai2-th, …, AiKi-th food.
Find the number of the foods liked by all the N people.

Constraints
·All values in input are integers.
·1≤N,M≤30
·1≤Ki≤M
·1≤Aij≤M
·For each i (1≤i≤N), Ai1,Ai2,…,AiKi are distinct.
输入
Input is given from Standard Input in the following format:
N M
K1 A11 A12…A1K1
K2 A21 A22…A2K2
:
KN AN1 AN2…ANKN
输出
Print the number of the foods liked by all the N people.
样例输入
3 4
2 1 3
3 1 2 3
2 3 2
样例输出
1
提示
As only the third food is liked by all the three people, 1 should be printed.

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n = 0; int m = 0;
	cin >> n >> m;
	
	unordered_map<int, int> cnt;
	
	for(int i = 0; i < n; ++i)
	{
		int l = 0;
		cin >> l;
		for(int j = 0; j < l; ++j)
		{
			int temp = 0;
			cin >> temp;
			cnt[temp]++;
		}
	}
	
	int num = 0;
	
	for(auto it = cnt.begin(); it != cnt.end(); ++it)
	{
		if(it->second == n) num++;
	}
	
	cout << num << endl;
	return 0;
}

问题 C: Monsters Battle Royale

时间限制: 1 Sec 内存限制: 128 MB

题目描述
There are N monsters, numbered 1,2,…,N.
Initially, the health of Monster i is Ai.
Below, a monster with at least 1 health is called alive.
Until there is only one alive monster, the following is repeated:
A random alive monster attacks another random alive monster.
As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.
Find the minimum possible final health of the last monster alive.

Constraints
All values in input are integers.
2≤N≤105
1≤Ai≤109
输入
Input is given from Standard Input in the following format:

N
A1 A2 … AN

输出
Print the minimum possible final health of the last monster alive.
样例输入 Copy
4
2 10 8 40
样例输出 Copy
2
提示
When only the first monster keeps on attacking, the final health of the last monster will be 2, which is minimum.
思路:求最大公约数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int gcd(int a, int b)
{
    if(b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
	int n = 0;
	int res = 0;
	cin >> n;
	cin >> res;
	
	for(int i = 0; i < n - 1; ++i)
	{
		int temp;
		cin >> temp;
		res = gcd(res, temp);
	}
	
	cout << res << endl;;
		
	return 0;
}

问题 G: 牛牛的密码

时间限制: 1 Sec 内存限制: 128 MB

题目描述
牛牛在注册不同的网站时,总是会使用不同的密码来保证他的账号安全。
为了保证他的密码强度,牛牛使用他的“字符串筛选器”来测试密码的强度。
具体来说,他先将输入的字符串筛选分成四部分。
第一部分仅由小写英文字母组成
第二部分仅由大写英文字母组成
第三部分仅由 0 到 9 的数字组成
第四部分由其余特殊字符组成
这四部分要保留它们在原字符串中的相对顺序。
比如将"1q2w3E4R{6}“这个字符串进行筛选后
四部分分别为:“qw”、“ER”、“123456”、”{}"。
然后只要某一部分不为空,牛牛就认为他的密码等级高 1 级。
密码等级最低为 1 级,最高 4 级。
例如"asdA@123"的密码等级为 4,“20020101"的密码等级为 1。
请帮助牛牛判断他注册账号时的密码等级,以及该密码做字符串筛选后的结果。。
输入
仅一行一个字符串 s,表示牛牛的密码。
输出
首先输出一行"password level:X”,X 表示牛牛的密码等级,最低为 1 级,最高 4级。
接下来输出 4 行,表示四部分的筛选结果,输出时要注意保留它们在原字符串中的相对顺序,如果某一部分为空串,则改为在该行输出"(Null)"
样例输入 Copy
【样例1】
123456
【样例2】
Pass_Word
样例输出 Copy
【样例1】
password level:1
(Null)
(Null)
123456
(Null)
【样例2】
password level:3
assord
PW
(Null)
_
提示
对于20%的测试数据,保证仅有小写英文字母组成,且1≤|s|≤100
对于40%的测试数据,保证仅有大小写英文字母组成,且1≤|s|≤100
对于100%的测试数据,保证字符串是不含空格、回车、或者其他不可见字符的
非空字符串,且保证字符串长度1 ≤ |s| ≤ 104。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	cin >> s;
	
	int lev = 0;
	
	string low = "";
	string up = "";
	string num = "";
	string spe = "";
	
	for(int i = 0; i < s.size(); i++)
	{
		if('a' <= s[i] && s[i] <= 'z')
			low += s[i];
		else if('A' <= s[i] && s[i] <= 'Z')
			up += s[i];
		else if('0' <= s[i] && s[i] <= '9')
			num += s[i];
		else 
			spe += s[i];
	}
	
	if(low.size())lev++;
	if(up.size()) lev++;
	if(num.size())lev++;
	if(spe.size())lev++;

	printf("password level:%d\n", lev);
	
	if(low.size())
		cout << low << endl;
	else
		cout << "(Null)" << endl;
	
	if(up.size())
		cout << up << endl;
	else
		cout << "(Null)" << endl;
	
	if(num.size())
		cout << num << endl;
	else
		cout << "(Null)" << endl;
		
	if(spe.size())
		cout << spe << endl;
	else 
		cout << "(Null)" << endl;
	
	return 0;
}

问题 H: 牛牛的跳跳棋

时间限制: 1 Sec 内存限制: 128 MB

题目描述
牛牛最近在玩一种叫做跳跳棋的游戏,棋盘可以看成是一个一维的线性数组,编号从1到n+1。
一开始牛牛的棋子位于第1个格子,游戏的最终目的是将棋子移动到第n+1个格子。
棋盘1~n的每个格子都有一个“弹力系数”的权值pi。
当棋子位于第i个格子时,它的下一步可以移动到[i−pi,i+pi]范围内的任意一个格子。
举例来说,假设第3个格子的弹力系数为2,那么牛牛下一步可以移动到第1,2,3,4,5格中的任意一格。
现在给定1~n每格的弹力系数pi
牛牛发现,好像有时由于棋盘的pi设置不合理,导致游戏无法通关。
所以牛牛准备施展他神奇的魔法,他每次施展魔法都可以使得一个格子的弹力系数pi+1,他可以施展若干次魔法操作不同的格子,但是要求他不能够重复对一个格子施展魔法。
牛牛想要知道,为了使跳跳棋通关,他最少施展多少次魔法,并且他应该操作哪些格子。
请输出牛牛的最小操作次数,以及施展魔法的操作序列,操作序列的第i个数表示该次施展魔法的格子编号,由于答案不唯一,所以请你输出一个最小字典序的答案。
最小字典序指:在保证第1个数字尽可能小的前提下,保证第2个数字尽可能的小,然后在此前提下保证第3个数字尽可能的小…以此类推
输入
第一行输入一个正整数n表示跳跳棋的格子数目。
接下来输入一行n个非负整数pi表示跳跳棋前n个格子的弹力系数。
输出
首先输出一个非负整数ans,表示少施展魔法的次数。
如果ans不为0,则再输出一行ans个整数表示需要施展魔法的格子编号,请给出一个最小字典序的答案。
样例输入 Copy
【样例1】
12
5 4 3 3 2 1 0 0 0 1 0 0
【样例2】
8
0 1 0 1 0 1 0 1
【样例3】
5
0 0 0 0 0
【样例4】
5
1 1 1 1 1
样例输出 Copy
【样例1】
5
4 8 9 10 12
【样例2】
4
1 2 4 6
【样例3】
5
1 2 3 4 5
【样例4】
0
提示
【样例1说明】
除了"4 8 9 10 12"这个操作的答案序列以外,“5 8 9 10 12”,“6 8 9 10 12"也同样是
最小操作数下的答案。
但是"4 8 9 10 12"这个答案是字典序最小的,故输出"4 8 9 10 12”。

【样例3说明】
本样例可以说明,不存在无解的情况,因为你至少可以令所有pi全都+1。

对于 20% 的测试数据,保证 1 ≤ n ≤ 10
对于 40% 的测试数据,保证 ≤ pi ≤ 1
对于 100% 的测试数据,保证 1 ≤ n ≤ 105 , 0 ≤ pi ≤ 100
思路:贪心,找到每次能去的最远距离,不断更新判断,能去就更新,不能去就操作

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	vector<int> res;
	int dis = 1;//距离
	int mag = 1;//需要魔法操作的下标
	
	for(int i = 1; i <= n; ++i)//最小字典序
	{
		int temp = 0;
		cin >> temp;
		if(i > dis)
		{
			res.push_back(mag); 
		}
		if(i + temp > dis)
		{
			dis = i + temp;
			mag = i;
		}
	}
	
	if(dis < n + 1)//最后一位特判
		res.push_back(mag);
		
	cout << res.size() << endl;
	for(int i : res)
		cout << i << ' ';
	return 0;
}

问题 K: 帕琪的药园

时间限制: 1 Sec 内存限制: 128 MB

题目描述
从红魔馆的大门往里面看就可以看到一个大花园。园内不止种花,而且还种植了各种魔法药材供帕秋莉使用。芙兰对花园里的药材感到好奇,于是她就问红魔馆的门番兼园丁花园里有多少种不同的药材。但是红师傅在看门的时候不是在睡觉就是在睡觉!她只知道各种药材被分割开来,互不相邻。现在你从帕琪那里拿到了花园的地图,药材用小写字母表示,其他花草用’*'表示,空地用空格表示,你能替那个门番回答二小姐的问题吗?

顺便一提,同种药材也有优劣之分,帕琪可能会用不同的小写字母表示同一种药材,不同种类的药材一定是被其他花草或是空地分割开的。
输入
输入一个正整数n表示地图有n行
接着n行每行有一个字符串,包含小写字母,空格和’*'三种字符,意义如题面。
注意:每行都有可能以若干空格开头,且每行长度也不一定相同!
输出
一个正整数,表示药材的种类数。
样例输入 Copy
在这里插入图片描述
样例输出 Copy
3
提示
于10%的数据:n≤10,字符串长度≤10;
对于30%的数据: n≤100,字符串长度≤200;
对于100%的数据: n≤1000,字符串长度≤400;
思路:深搜,标签给的广搜应该也能做,但是我没做出来,看了下大佬的题解,用的深搜,check函数用于检查边界情况

#include<bits/stdc++.h>
using namespace std;

int dir_x[] = {0, 0, 1, -1};
int dir_y[] = {1, -1, 0, 0}; 

string grid[1005];
bool vis[1005][1005];
int n = 0;

bool check(int x, int y)
{
	if(('a' <= grid[x][y] && grid[x][y] <= 'z') && 0 <= y && y < grid[x].size() && 0 < x && x <= n)
		return true;
	else 
		return false;
}

void dfs(int x, int y)
{
	vis[x][y] = true;
	for(int i = 0; i < 4; ++i)
	{
		int next_x = x + dir_x[i];
		int next_y = y + dir_y[i];
		if(!vis[next_x][next_y] && check(next_x, next_y))
			dfs(next_x, next_y);
	}
}

int main()
{
	int cnt = 0;

	cin >> n;
	
	for(int i = 0; i <= n; ++i)
	{
		getline(cin, grid[i]);
	}
	
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j < grid[i].size(); ++j)
		{
			if(!vis[i][j] && ('a' <= grid[i][j] && grid[i][j] <= 'z'))
			{
				cnt++;
				dfs(i, j);
			}
		}
	}	
	
	cout << cnt << endl;
	
	return 0;
}

问题 L: 八目鳗

时间限制: 1 Sec 内存限制: 128 MB

题目描述
米斯蒂娅去捕捉八目鳗为开店作准备。现在,她在一个有八目鳗的池塘边。她知道池塘里的有n条八目鳗,把第i条八目鳗从池塘弄回小店需要ti∗2个单位的时间(毕竟需要往返)。

这些八目鳗会自己吃P点!随着时间的推移,米斯琪把它们弄回来所消耗的体力与时间成正比,即在第t个时刻开始运第i条八目鳗所消耗的体力为t∗ci,其中,ci是给定的常数。一开始所有的八目鳗都没有P点,也就是说运送第一条八目鳗所消耗的体力为0。

米斯琪想知道把所有八目鳗运回小店所消耗的体力最少是多少。
输入
第一行输入一个整数n,表示八目鳗的数量。
接下来n行,每行包含两个整数ti,ci。
输出
一个整数,表示最少消耗的体力。
样例输入 Copy
6
3 1
2 5
2 3
3 2
4 1
1 6
样例输出 Copy
86
提示
对于10%的数据,n≤10,t≤100,ci≤10;
对于60%的数据,n≤1000,t≤20000,ci≤100;
对于100%的数据,n≤100000,t≤2000000,ci≤100。
思路:贪心,cmp函数关系式需要推一下

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef struct fish
{
	ll t = 0;
	ll c = 0;
} fish;

fish fishes[100005];

bool cmp(fish a, fish b)
{
	return (a.t * b.c) <= (b.t * a.c);
}

int main()
{
	int n = 0;	
	cin >> n;
	
	for(int i = 0; i < n; ++i)
	{
		cin >> fishes[i].t >> fishes[i].c;
		fishes[i].t *= 2;
	}
	
	sort(fishes, fishes + n, cmp);
	
	ll res = 0;
	ll temp = 0;
	for(int i = 0; i < n; ++i)
	{
		res += temp * fishes[i].c;
		temp += fishes[i].t;
	}
	
	cout << res << endl;
	
	return 0;
} 

总结:比赛的时候刚好在外面准备比赛,不是很想做2333,ACM打完了回来接着补,还是发现了很多问题,最后还有五道题没去补,确实基础有些不稳,有机会的话争取以后补上(如果以后记得住233)

热门文章

暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

GMX 命令分类列表

建模和计算操作命令&#xff1a; 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体&#xff0c;就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛&#xff0c;这门课会介绍许多方法去利用离散点最大化地逼近这个函数&#xff0c;甚至它的导数、积分&#xff0c;甚至微分方程的解。…
暂无图片
编程学习 ·

在职阿里5年,一个28岁女软测工程师的心声

简单的先说一下&#xff0c;坐标杭州&#xff0c;14届本科毕业&#xff0c;算上年前在阿里巴巴的面试&#xff0c;一共有面试了有6家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09; ​ 编辑切换为居中…
暂无图片
编程学习 ·

字符串左旋c语言

目录 题目&#xff1a; 解题思路&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 总代码&#xff1a; 题目&#xff1a; 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·

设计模式--观察者模式笔记

模式的定义与特点 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·

睡觉突然身体动不了,什么是睡眠痽痪症

很多朋友可能有这样的体验&#xff0c;睡觉过程中突然意识清醒&#xff0c;身体却动弹不了。这时候感觉非常恐怖&#xff0c;希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况&#xff0c;一年有一百多次&#xff0c;那时候很害怕晚上到来&#xff0c;睡觉了就会出…
暂无图片
编程学习 ·

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别&#xff08;move-only type&#xff0c;只移型别还有std::mutex等&#xff09;。 结合一下工厂模式&#xff0c;看看其基本用法&#xff…
暂无图片
编程学习 ·

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在&#xff0c;但代码中需要用到它&#xff0c;通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能&#xff0c;通常需要完成两步操作&#xff1a;一.是在Web页面中添加上传输入项&#xff1b;二是在Servlet中读取上传文件的数据&#xff0c;并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度&#xff08;&#xff1f;&#xff09; 不管两个高积木之间的的积木是怎样乱七八糟的高度&#xff0c;最后能用来装水的…
暂无图片
编程学习 ·

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的&#xff0c;用的是MFC VS2019. 详见&#xff1a;http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936&#xff0c;然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·

贪心(一):区间问题、Huffman树

区间问题 例题一&#xff1a;区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N&#xff0c;表示区间数。 接下来 …
暂无图片
编程学习 ·

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家&#xff0c;在他的着作中曾经提到&#xff1a;「若有一只免子每个月生一只小免子&#xff0c;一个月后小免子也开始生产。起初只有一只免子&#xff0c;一个月后就有两只免子&#xff0c;二个月后有三只免子…
暂无图片
编程学习 ·

Android开发(2): Android 资源

个人笔记整理 Android 资源 Android中的资源&#xff0c;一般分为两类&#xff1a; 系统内置资源&#xff1a;Android SDK中所提供的已经定义好的资源&#xff0c;用户可以直接拿来使用。 用户自定义资源&#xff1a;用户自己定义或引入的&#xff0c;只适用于当前应用的资源…
暂无图片
编程学习 ·

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法&#xff08;Algorithm&#xff09;是一系列解决问题的清晰指令&#xff0c;也就是说&#xff0c;能够对一定规范的输入&#xff0c;在有限时间内获得所要求的输出。 如果一个算法有缺陷&#xff0c;或不适合于某个问题&#xff0c;执…
暂无图片
编程学习 ·

人工智能:知识图谱实战总结

人工智能python&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习人工智能&#xff1a;知识图谱实战前言一、实体建模工具Protegepython&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习 人工智能&#xff1a;知识图…
暂无图片
编程学习 ·

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…