可以做哪些网站有哪些内容,hao123网址大全浏览器设为主页,化妆品网站推广策划书,钢材技术支持东莞网站建设题目描述与示例 题目描述 小红有一个长度为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 x evenx x 数组的奇偶性反过来 isAllEven not isAllEven isAllOdd not isAllOddoddx x evenx x 数组的奇偶性不变数组中只有偶数 isAllEven True不做任何处理t2 数组所有偶数加x数组中有奇数有偶数 isAllEven False and isAllOdd Falseevenx x 所有的偶数变为奇数 isAllOdd Trueevenx x 数组的奇偶性不变数组中只有偶数 isAllEven Trueoddx x evenx x 数组的奇偶性反过来 isAllEven not isAllEven isAllOdd not isAllOddoddx x evenx x 数组的奇偶性不变数组中只有奇数 isAllOdd True不做任何处理
代码 Python n, m map(int, input().split()) a list(map(int, input().split()))
oddx 0 evenx 0 isAllOdd False isAllEven False
for _ in range(m): t, x map(int, input().split()) # x为奇数的情况 if x % 2 1: # 若此时数组中同时存在偶数和奇数 if isAllEven False and isAllOdd False: # 若是操作1数组中所有奇数加上x if t 1: oddx x # 数组中所有的元素都变成偶数 isAllEven True # 若是操作2数组中所有偶数加上x elif 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 #include
using namespace std;
int main() { int n, m; cin n m; vector 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了解更多
