第二个点WA求助,其他AC
  • 板块P3392 涂国旗
  • 楼主BlueSky
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/11 09:54
  • 上次更新2024/1/11 17:46:05
查看原帖
第二个点WA求助,其他AC
1027669
BlueSky楼主2024/1/11 09:54

没找出哪里出bug了/求助大佬们;

#include<bits/stdc++.h>
using namespace std;
#pragma warning(disable: 4996)
int N, M;

// w = 1  B =2  R = 3  第[0][0]所在十字行与列为空
// ar记录这一行的已有格子分别是什么
int ar[52][4];
int ans;

int RED[51], WHITE[51];

// 为blue建立树桩数组方便任意区间加和
int BLUE_TREE[53], RED_TREE[53];
int lowbit(int x)
{
	return x & (-x);//从右边到左边第一个1一共有多少个0;
}

// 实际上不需要做红色的线段数组,b=2可以不用管
int sum(int a, int b=2) {
	int su = 0;
	for (int i = a; i > 0; i -= lowbit(i)) {
		if(b==2)
			su += BLUE_TREE[i];
		//else
		//	su += RED_TREE[i];
	}
	return su;
}
// 实际上不需要做红色的线段数组,p=2可以不用管
void tree_array(int p = 2) {
	for (int i = 1; i <= N; i++) {
		for (int j = i - lowbit(i) + 1; j <= i; j++) {
			if (p==2)
				BLUE_TREE[i] += (ar[j][1]+ar[j][3]);
			//else
			//	RED_TREE[i] += ar[N-j][3];
			//// 红色倒过来计算总和
		}
	}
}


int main() {
	scanf(" %d %d", &N, &M);
	char temp;
	for (int i = 1; i <= N;i++) {
		for (int j = 0; j < M; j++) {
			scanf(" %c", &temp);
			if (temp == 'W') {
				ar[i][1]++;
			}
			else if (temp == 'B') {
				ar[i][2]++;
			}
			else {
				ar[i][3]++;
			}
		}
	}

	//要填白色格子 行数的树桩数组
	tree_array();
	//tree_array(3);

	// 处理 截止第i行,要填多少格白色
	WHITE[1] = ar[1][2]+ar[1][3];
	for (int i = 2; i <= N - 1; i++) {
		WHITE[i] = WHITE[i - 1] + ar[i][2]+ar[i][3];
	}

	// 倒过来处理 第N行到第i行,要填多少格红色
	RED[N] = ar[N][1]+ar[N][2];
	for (int i = N-1; i >= 2; i--) {
		RED[i] = RED[i + 1] + ar[i][1]+ar[i][2];
	}

	ans = WHITE[1] + sum(N - 1, 2) - sum(1, 2) + RED[N];
	for (int i = 2; i <= N-2; i++) {
		for (int j = i ; j <= N-1; j++) {
			ans = min( ans,WHITE[i-1] + sum(j,2)-sum(i-1,2)+RED[j+1]);
		}
	}
	//RED[N] = ar[N][3];
	//for (int i = N-1; i >= 2; i--) {
	//	RED[i] = RED[i + 1] + ar[i][3];
	//}
	//int temp;
	//for (int i = 2; i <= N - 1; i++) {
	//	temp = ar[i - 1][1] + sum(i) - sum(i - 1) + ar[i + 1][3];
	//}
	//ans = ar[N][3] + ar[1][3];
	cout << ans;
}
2024/1/11 09:54
加载中...