Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Πίνακας περιεχομένων

[Πρότυπο] Μονοδιάστατο άθροισμα προθέματος

[Πρότυπο] Δισδιάστατο άθροισμα προθέματος

Βρείτε το κεντρικό ευρετήριο ενός πίνακα

Προϊόν συστοιχιών εκτός από τον εαυτό

άθροισμα επιφανειών μήτρας

---

[Πρότυπο] Μονοδιάστατο άθροισμα προθέματος

Εάν χρησιμοποιήσουμε ένα διάλυμα ωμής βίας,Ο πίνακας πρέπει να διασχίζεται κάθε φορά, συνολικά q φορές,Έτσιχρονική πολυπλοκότηταείναι πολύ υψηλό, αυτή τη στιγμή κατασκευάζουμε έναν πίνακα αθροίσματος προθέματος στοΤο άθροισμα κάθε διαστήματος εντός του διαστήματος 1-n αποθηκεύεται στο , χρειάζεστε τα πρώτα n στοιχεία και άμεση πρόσβαση στο πρόθεμα dp και στη θέση δείκτη του πίνακα. ο κώδικας εμφανίζεται ως εξής:

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	// 读入数据
	int n, q; cin >> n >> q;
	// n + 1 添加了虚拟节点0
	vector<int> arr(n + 1); // 默认全部为0
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
 
	// 预处理出一个前缀和数组
	vector<long long> dp(n + 1); // 防止溢出
	for (int i = 1; i <= n; i++)
		dp[i] = dp[i - 1] + arr[i];
 
	// 使用前缀和数组
	int l = 0, r = 0;
	while (q--)
	{
		cin >> l >> r;
		cout << dp[r] - dp[l - 1] << endl;
	}
	return 0;
}

---

[Πρότυπο] Δισδιάστατο άθροισμα προθέματος

προεπεξεργασίαένας πίνακας αθροίσματος προθέματος που θαΤο άθροισμα όλων των στοιχείων από τις θέσεις (1, 1) έως (i, j).υπάρχει σε αυτόν τον πίνακα dp, μέσωΜέθοδος υπολογισμού επιφάνειας, για να βρείτε την τελική απάντηση, ο κωδικός είναι ο εξής:

int main()
{
	// 读入数据
	int n, m, q; cin >> n >> m >> q;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> arr[i][j];
 
	// 预处理一个前缀和数组
	vector<vector<long long>> dp(n + 1, vector<long long>(m + 1)); // 防止溢出
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
 
	// 使用前缀和数组
	while (q--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
	}
	return 0;
}

---

Βρείτε το κεντρικό ευρετήριο ενός πίνακα

Σημειώστε τις ακραίες θήκες εδώΔεν χρειάζεται να ανοίξετε το πρόθεμα και τον πίνακα διαστήματος n+1, επειδή υπάρχει ένα στοιχείο στον αρχικό πίνακα που θα πρέπει να χρησιμοποιηθεί ως κεντρικός δείκτης αυτής της ερώτησης Ο κώδικας είναι ο εξής:

class Solution {
public:
	int pivotIndex(vector<int>& nums) {
		int n = nums.size();
		vector<int> f(n), g(n);
		// 预处理前缀和数组  从左向右
		for (int i = 1; i < n; i++)
			f[i] = f[i - 1] + nums[i - 1];
		// 预处理后缀和数组  从右向左
		for (int i = n - 2; i >= 0; i--)
			g[i] = g[i + 1] + nums[i + 1];
		for (int i = 0; i < n; i++)
		{
			if (g[i] == f[i])
				return i;
		}
		return -1;
	}
};

---

Προϊόν συστοιχιών εκτός από τον εαυτό

Το νόημα είναι παρόμοιο με την προηγούμενη ερώτηση, αλλά πρέπει να σημειωθεί ότι οι οριακές περιπτώσεις f(0) και g(n-1) θα πρέπει να αρχικοποιηθούν σε 1 αντί για 0. Ο κώδικας είναι ο εξής:

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
		vector<int> f(n), g(n), ret(n);
		// 处理边界情况
		f[0] = 1; g[n - 1] = 1;
		// 预处理前缀积数组  从左向右
		for (int i = 1; i < n; i++)
			f[i] = f[i - 1] * nums[i - 1];
		// 预处理后缀积数组  从右向左
		for (int i = n - 2; i >= 0; i--)
			g[i] = g[i + 1] * nums[i + 1];
		for (int i = 0; i < n; i++)
			ret[i] = f[i] * g[i];
		return ret;
	}
};

---

άθροισμα επιφανειών μήτρας

Σημείωση: Το δισδιάστατο πρόθεμα και ο πίνακας πρέπει να έχουν μία ακόμη σειρά και μία στήλη, διαφορετικά θα υπάρχει πρόσβαση εκτός ορίων. ans[ 0 ][ 0 ] αντιστοιχεί σε dp [ 1 ][ 1] αυτή τη θέση. ο κώδικας εμφανίζεται ως εξής:

class Solution {
public:
	vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
		int m = mat.size(), n = mat[0].size();  // m 为行 n 为列
		// 预处理一个二维前缀和数组 dp
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
		// 存放答案的二维数组 ans
		vector<vector<int>> ans(m, vector<int>(n));
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
				int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
				ans[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
			}
		}
		return ans;
	}
};