प्रौद्योगिकी साझेदारी

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

सामग्रीसूची

[सारूप्यम्] एक-आयामी उपसर्ग योग

[सारूप्यम्] द्वि-आयामी उपसर्ग योग

सरणीयाः केन्द्रसूचकाङ्कं ज्ञातव्यम्

आत्मनः अतिरिक्तानां सरणीनां उत्पादः

आकृति क्षेत्र योग

---

[सारूप्यम्] एक-आयामी उपसर्ग योग

यदि वयं क्रूरबलसमाधानस्य उपयोगं कुर्मः तर्हिसरणीं प्रत्येकं समये, कुलम् q वारं, अवश्यं भ्रमितव्यम्,अतःकालजटिलताअतीव उच्चम् अस्ति, अस्मिन् समये वयं to इति उपसर्गं sum array निर्मामः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;
}

---

[सारूप्यम्] द्वि-आयामी उपसर्ग योग

पूर्वसंसाधनम्उपसर्गः योगमात्रिका यत् करिष्यति(१, १) तः (i, j) स्थानपर्यन्तं सर्वेषां तत्त्वानां योगःअस्मिन् dp सरणीयां विद्यते, throughक्षेत्रगणना विधि, अन्तिमम् उत्तरं अन्वेष्टुं कोडः निम्नलिखितरूपेण अस्ति ।

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) इत्येतयोः आरम्भः 0 इत्यस्य स्थाने 1 इति करणीयम् ।सङ्केतः निम्नलिखितरूपेण अस्ति ।

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;
	}
};

---

आकृति क्षेत्र योग

नोटः- द्वि-आयामी उपसर्गस्य सरणीयाश्च एकः अधिकः पङ्क्तिः एकः स्तम्भः च भवितुमर्हति, अन्यथा सीमातः बहिः अभिगमः भविष्यति तदतिरिक्तं, स्थानानां मेलनं कर्तुं dp सरणीयाः ans सरणीयाः च मध्ये उपलिप्याः समायोजनं करणीयम् 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;
	}
};