备案网站服务内容,网站死链接扫描,免费推广引流平台有哪些,网站销售怎么做的题目描述与示例
题目描述
小红有一个长度为n的数组a#xff0c;她将对数组进行m次操作#xff0c;每次操作有两种类型#xff1a;
将数组中所有值为奇数的元素加上x将数组中所有值为偶数的元素加上x
请你输出m次操作后的数组
输入描述
第一行两个整数n和m#xff0c;…题目描述与示例
题目描述
小红有一个长度为n的数组a她将对数组进行m次操作每次操作有两种类型
将数组中所有值为奇数的元素加上x将数组中所有值为偶数的元素加上x
请你输出m次操作后的数组
输入描述
第一行两个整数n和m表示数组长度和操作次数
第二行n个整数表示数组a的初始值。
接下来m行每行两个整数t和xt表示一次操作的类型和参数t为1表示第一种操作t为2表示第二种操作
1 n, m 10^5
1 ai, x 10^5
1 t 2输出描述
输出一行包含n个整数表示m次操作后的数组
示例
输入
5 3
1 2 3 4 5
1 2
2 2
1 3输出
6 4 8 6 10说明
第一次将所有奇数元素加 2数组变为[3,2,5,4,7]
第二次将所有偶数元素加 2数组变为[3,4,5,6,7]
第三次将所有奇数元素加 3数组变为[6,4,8,6,10]
时空限制
时间限制 C/C 1000MS其他语言 2000MS
内存****限制 C/C 256M其他语言 512M
解题思路
注意到一个非常重要的数学性质对于任意两个正整数相加
奇数 奇数 偶数
偶数 偶数 偶数
奇数 偶数 奇数
偶数 奇数 奇数假设一开始数组中既存在奇数也存在偶数。在遇到第一个为奇数的x时若
t 1则数组中所有的奇数都要加上x相加完毕后所有元素都变成偶数t 2则数组中所有的偶数都要加上x相加完毕后所有元素都变成奇数
我们分别用isAllOdd和isAllEven两个变量来表示数组的状态。当
isAllOdd和isAllEven均为False时说明此时数组中既存在奇数也存在偶数。isAllOdd True此时数组中的元素均为奇数isAllEven True此时数组中的元素均为偶数注意不可能出现isAllOdd和isAllEven均为True的情况。
设置两个变量oddx和evenx分别表示初始数组中的奇数和偶数在m次操作中的增量。那么在遍历过程中所有元素的变化可以依照下表进行
x是奇数x是偶数t1数组所有奇数加x数组中有奇数有偶数isAllEven False and isAllOdd Falseoddx x所有的奇数变为偶数isAllEven Trueoddx x数组的奇偶性不变数组中只有奇数isAllOdd Trueoddx xevenx x数组的奇偶性反过来isAllEven not isAllEvenisAllOdd not isAllOddoddx xevenx x数组的奇偶性不变数组中只有偶数isAllEven True不做任何处理t2数组所有偶数加x数组中有奇数有偶数isAllEven False and isAllOdd Falseevenx x所有的偶数变为奇数isAllOdd Trueevenx x数组的奇偶性不变数组中只有偶数isAllEven Trueoddx xevenx x数组的奇偶性反过来isAllEven not isAllEvenisAllOdd not isAllOddoddx xevenx x数组的奇偶性不变数组中只有奇数isAllOdd True不做任何处理
代码
Python
n, m map(int, input().split())
a list(map(int, input().split()))oddx 0
evenx 0
isAllOdd False
isAllEven Falsefor _ in range(m):t, x map(int, input().split())# x为奇数的情况if x % 2 1:# 若此时数组中同时存在偶数和奇数if isAllEven False and isAllOdd False:# 若是操作1数组中所有奇数加上xif t 1:oddx x# 数组中所有的元素都变成偶数isAllEven True# 若是操作2数组中所有偶数加上xelif t 2:evenx x# 数组中所有的元素都变成奇数isAllOdd True# 已经是全偶数或全奇数的情况变号elif (isAllEven and t 2) or (isAllOdd and t 1):oddx xevenx xisAllEven not isAllEvenisAllOdd not isAllOdd# x为偶数的情况else:# 若此时数组中同时存在偶数和奇数if isAllEven False and isAllOdd False:# 若是操作1数组中所有奇数加上xif t 1:oddx x# 若是操作2数组中所有偶数加上xelse:evenx x# 已经是全偶数或全奇数的情况不变号elif (isAllEven and t 2) or (isAllOdd and t 1):oddx xevenx x# 遍历原数组所有奇数加上oddx所有偶数加上evenx
ans [a[i] oddx if a[i] % 2 1 else a[i] evenx for i in range(n)]
print( .join(map(str, ans)))Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i] sc.nextInt();}int oddx 0;int evenx 0;boolean isAllOdd false;boolean isAllEven false;for (int i 0; i m; i) {int t sc.nextInt();int x sc.nextInt();if (x % 2 1) {if (!isAllEven !isAllOdd) {if (t 1) {oddx x;isAllEven true;} else if (t 2) {evenx x;isAllOdd true;}} else if ((isAllEven t 2) || (isAllOdd t 1)) {oddx x;evenx x;isAllEven !isAllEven;isAllOdd !isAllOdd;}} else {if (!isAllEven !isAllOdd) {if (t 1) {oddx x;} else {evenx x;}} else if ((isAllEven t 2) || (isAllOdd t 1)) {oddx x;evenx x;}}}int[] ans new int[n];for (int i 0; i n; i) {if (a[i] % 2 1) {ans[i] a[i] oddx;} else {ans[i] a[i] evenx;}}for (int i 0; i n; i) {if (i n - 1) {System.out.print(ans[i] );} else {System.out.println(ans[i]);}}}
}C
#include iostream
#include vectorusing namespace std;int main() {int n, m;cin n m;vectorint a(n);for (int i 0; i n; i) {cin a[i];}int oddx 0;int evenx 0;bool isAllOdd false;bool isAllEven false;for (int i 0; i m; i) {int t, x;cin t x;if (x % 2 1) {if (!isAllEven !isAllOdd) {if (t 1) {oddx x;isAllEven true;} else if (t 2) {evenx x;isAllOdd true;}} else if ((isAllEven t 2) || (isAllOdd t 1)) {oddx x;evenx x;isAllEven !isAllEven;isAllOdd !isAllOdd;}} else {if (!isAllEven !isAllOdd) {if (t 1) {oddx x;} else {evenx x;}} else if ((isAllEven t 2) || (isAllOdd t 1)) {oddx x;evenx x;}}}vectorint ans(n);for (int i 0; i n; i) {if (a[i] % 2 1) {ans[i] a[i] oddx;} else {ans[i] a[i] evenx;}}for (int i 0; i n; i) {if (i n - 1) {cout ans[i] ;} else {cout ans[i] endl;}}return 0;
}时空复杂度
时间复杂度O(mn)。一共有m次操作最后修改数组需要遍历n个元素。
空间复杂度O(1)。仅需若干常数变量
华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 OD算法冲刺训练课程表 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
