แบบสอบถามเกี่ยวกับจำนวนของเมทริกซ์ย่อยไบนารีของขนาดที่กำหนดใน C++

ในปัญหานี้ เราได้รับไบนารีเมทริกซ์ bin[][] ขนาด nXm งานของเราคือแก้แบบสอบถาม q ทั้งหมด สำหรับข้อความค้นหา (x, y) เราจำเป็นต้องค้นหาจำนวนเมทริกซ์ย่อยขนาด xx*x เพื่อให้องค์ประกอบทั้งหมดของอาร์เรย์ y (เลขฐานสอง)

คำอธิบายปัญหา

ในที่นี้ เราต้องนับจำนวนทั้งหมดของเมทริกซ์ย่อยของขนาดที่กำหนดที่ประกอบด้วยหนึ่งในสองบิตเท่านั้น นั่นคือเมทริกซ์ย่อยจะเป็นองค์ประกอบทั้งหมด 0/1

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n =3 , m =4bin[][] ={{ 1, 1, 0, 1}{ 1, 1, 1, 0}{ 0, 1, 1, 1}}q =1q1 =(2 , 1)

ผลลัพธ์

2

คำอธิบาย

เมทริกซ์ย่อยทั้งหมดของขนาด 2 ที่มีองค์ประกอบ 1 ทั้งหมดคือ −

วิธีแก้ปัญหานี้คือการใช้การเขียนโปรแกรมแบบไดนามิก เข้าใกล้. ในการแก้ปัญหา เราจะรักษา 2D เมทริกซ์ DP[][] เพื่อเก็บเมทริกซ์ย่อยที่ใหญ่ที่สุดของบิตเดียวกัน เช่น DP[i][j] จะเก็บค่าของเมทริกซ์ย่อยที่มีดัชนีสิ้นสุด (i, j) และองค์ประกอบทั้งหมดเหมือนกัน

เพื่อความเข้าใจของคุณ ถ้า DP[4][5] =2 องค์ประกอบที่ bin[3][4], bin[3][5],bin[4][4] และ bin[4][5] เหมือนกัน .

ดังนั้น สำหรับการหา DP[i][j] เรามีสองกรณี −

กรณีที่ 1 − if i =0 orj =0 :DP[i][j] =1 เนื่องจากสามารถเป็นเมทริกซ์ย่อยได้เพียงรายการเดียวเท่านั้น

กรณีที่ 2 − มิฉะนั้น bin[i-(k-1)][j] =bin[i][j - (k-1)] …:ในกรณีนี้ DP[i][j] =min(DP[i][ j-1] , DP[i -1][j], DP[i-1][j-1] ) + 1 สิ่งนี้จะนำไปสู่เมทริกซ์ย่อยอย่างที่เราต้องการ ลองมาสรุปกัน กรณีที่มี k =2 เช่น ถ้าเราพิจารณาเมทริกซ์ย่อยที่มีขนาด 2X2 จากนั้นเราต้องตรวจสอบว่า bin[i][j] =bin[i] [j - 1] =bin[i- 1][j] =bin[i -1 ][j -1 ] หรือไม่ ถ้าเป็นไปได้ จากนั้น เราจะพบ DP[i][j] for k =2 .

หากไม่ตรงตามเงื่อนไขกรณีที่ 2 เราจะตั้งค่า DP[i][j] =1 ซึ่งสามารถถือเป็นค่าเริ่มต้นได้

ค่าของ DP[i][j] นี้สามารถเป็นได้ทั้ง set bit หรือ unset bit เราจะตรวจสอบค่าของ bin[i][j] เพื่อดูว่าค่าใดเป็นค่าที่ตั้งไว้หรือค่าที่ไม่ได้ตั้งค่าที่ค่า k เป็นของ ในการหาความถี่ เราจะสร้างอาร์เรย์สองชุด นั่นคือ zeroFrequrency เพื่อเก็บความถี่ของเมทริกซ์ย่อยที่สร้างขึ้นสำหรับ 0 และหนึ่งความถี่เพื่อเก็บความถี่ของเมทริกซ์ย่อยที่สร้างขึ้นสำหรับ 1

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include ใช้เนมสเปซ std;#define N 3#define M 4int min(int a, int b, int c) { if (a <=b &&a <=c) คืนค่า a; อื่นถ้า (b <=a &&b <=c) ส่งคืน b; อื่นส่งคืน c;}int SolveQuery(int n, int m, int bin[N][M], int x, int y){ int DP[n][m], สูงสุด =1; สำหรับ (int i =0; i =0; i--) { zeroFrequency[i] +=zeroFrequency[i + 1]; oneFrequency[i] +=oneFrequency[i + 1]; } ถ้า (y ==0) คืนค่า zeroFrequency[x]; อื่นส่งคืน oneFrequency[x];}int main(){ int n =3, m =4; int mat[N][M] ={{ 1, 1, 0, 1}, { 1, 1, 1, 0}, { 0, 1, 1, 1}}; int Q =2; แบบสอบถาม int[Q][2] ={{ 2, 1}, { 1, 0}}; for(int i =0; i  
ผลลัพธ์
 
สำหรับ Query 1:จำนวนของเมทริกซ์ย่อยไบนารีของขนาดที่กำหนดคือ 2For Query 2:จำนวนของเมทริกซ์ย่อยไบนารีของขนาดที่กำหนดคือ 3