也会有发光的一天吖

用户名：wzi

访问量：8657

签　名：

我怎么能这么笨啊，脑袋长的干嘛的？

等　　级
排　　名	113
经　　验	7940
参赛次数	0
文章发表	37
年　　龄	88
在职情况	学生
学　　校	蓝翔技校
专　　业

　　自我简介：

1.素质教育漏网之鱼 2.晚睡协会常任理事3.情侣辩论赛冠军 4. 国家级抬杠运动员6.中国驰名窝里横 7.家里蹲大学博士

TA的其他文章

该题注意事项
浏览：104

应该是对于初学者来说最好理解的
浏览：132

Java语言编写的
浏览：118

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

3170: 蓝桥杯2023年第十四届省赛真题-反异或 01 串

　　作者: 也会有发光的一天吖　　　　发表时间：2023-05-22 09:48:22 浏览：292　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-反异或 01 串

![](/image_editor_upload/20230522/20230522094637_96278.png)

[# 题解在CSDN上，欢迎大家前往查看。](https://blog.csdn.net/weixin_43554580/article/details/130699777?spm=1001.2014.3001.5501 "# 题解在CSDN上，欢迎大家前往查看。")

`package 蓝桥__真题__专题;

import java.util.Scanner;
import java.util.Vector;

public class _2023试题试题J__反异或01串_02 {
	public static void main(String[] args) {
		// # 马拉车算法
		// # 字符串扩展，每个字母间插入'0'，解决奇偶长度回文问题
		// s = '0' + '0'.join(list(s)) + '0'

Scanner scanner = new Scanner(System.in);

Vector<Character> s = new Vector<>();
		char w;

while (scanner.hasNext()) {
			w = scanner.next().charAt(0);
			s.add('0');
			s.add(w);
		}
		s.add('0');
		int l = 0,r = 0;
		int n = s.size();

// # 每个字母的臂长
		Vector<Integer> m = new Vector<>(n,0);
		// # 初始化，第0个字母臂长肯定是0，即自己
		// # m[0] = 0
		// '''
		// ddabacabac
		//      l ir
		//   2345678
		// m[li] = 1
		// '''

// 前缀和优化
		Vector<Integer> pre = new Vector<>(n+1,0);
		if (s.get(0) == '1') {
			pre.set(1, 1);
		}

int li;
		for (int i = 1;i < n;i++) {
			if (s.get(i) == '1') {
				pre.set(i + 1, pre.get(i) + 1);
			}
			else {
				pre.set(i + 1, pre.get(i));
			}
			// # 在臂长范围中
			if (i < r) {
				// # 镜像i位置
				li = l - (i - l);
				// # 根据回文对称性，获取已知最短臂长
				m.set(i, Math.min(r - i, m.get(li)));
			}
			// # 暴力扩展
			while (i+ m.get(i) +1 < n && i- m.get(i) -1 >= 0 && s.get(i + m.get(i) + 1).equals(s.get(i - m.get(i) - 1))) {
				m.set(i, 1);
			}

// # lr-box更新
			if (i + m.get(i) > r) {
				l = i;
				r = i + m.get(i);
			}
		}

int res = pre.get(n);
		for (int i=0;i<n;i++) {
			// # 奇数回文中点不能为 1
			if (s.get(i) == '1') {
				continue;
			}

l = i - m.get(i);
			r = i + m.get(i);
			//  [0,l) + [l,r] / 2 + [r+1,n]
			//  [l,r] 为回文子字符串，因此 1 个数减半
			res = Math.min(res, pre.get(l) + (pre.get(r + 1) - pre.get(l)) / 2 + pre.get(n) - pre.get(r + 1));
		}
		System.out.println(res);
	}
		// # 初始化，第0个字母臂长肯定是0，即自己
		// # m[0] = 0

}

https://blog.csdn.net/weixin_43554580/article/details/130699777?spm=1001.2014.3001.5501

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

3170: 蓝桥杯2023年第十四届省赛真题-反异或 01 串

评论区

精彩推荐

简洁的代码

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

P1000 （C语言代码）

愚蠢的摄影师（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

3170: 蓝桥杯2023年第十四届省赛真题-反异或 01 串

评论区

精彩推荐

简洁的代码

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

P1000 （C语言代码）

愚蠢的摄影师 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

　　评论区

愚蠢的摄影师（C++代码）