資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究使用指定約束查詢矩陣最後一個數值的 C++ 程式
假設我們有一個包含 N 個元素的數字列表 A。元素為 1、2 或 3，考慮一個數字 X[1][j] = A[j]，其中 j 在 1 到 N 的範圍內。並且 X[i][j] = |X[i-1][j] - X[i-1][j+1]|，其中 i 在 2 到 N 的範圍內，j 在 1 到 N+1-i 的範圍內。我們必須找到 X[i][j] 的值。
因此，如果輸入為 A = [1,2,3,1]，則輸出將為 1，因為
X[1][1] to X[1][4] are 1, 2, 3, 1 X[2][1], X[2][2], X[2][3] are |1-2| = 1, |2 - 3| = 1 and |3 - 1| = 2 X[3][1], X[3][2] are ∣ 1 − 1∣ = 0, ∣ 1 − 2∣ = 1. X[4][1] = |0 - 1| = 1 So the answer is 1
為了解決此問題，我們將遵循以下步驟 −
Define a function calc(), this will take N, M,
cnt := 0
for initialize k := N, when k is non-zero, update k >>= 1, do:
cnt := floor of (cnt + k)/2
for initialize k := M, when k is non-zero, update k >>= 1, do:
cnt := floor of (cnt - k)/2
for initialize k := N - M, when k is non-zero, update k >>= 1, do:
cnt := floor of (cnt - k)/2
return invert of cnt
From the main method, do the following
n := size of A
Define an array arr of size (n + 1)
for initialize i := 1, when i < n, update (increase i by 1), do:
arr[i - 1] = |A[i] - A[i - 1]|
(decrease n by 1)
hh := 1, pd := 0, ck := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
if arr[i] is non-zero, then:
if arr[i] is same as 1, then:
hh := 0
pd := pd XOR calc(n - 1, i)
Otherwise
ck := ck XOR calc(n - 1, i)
ck := ck AND hh
if pd XOR ck is non-zero, then:
return "1" + hh
return "0"示例
讓我們瞭解如下實現以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
int calc(int N, int M) {
int cnt = 0;
for (int k = N; k; k >>= 1)
cnt += k >> 1;
for (int k = M; k; k >>= 1)
cnt -= k >> 1;
for (int k = N - M; k; k >>= 1)
cnt -= k >> 1;
return !cnt;
}
string solve(vector<int> A) {
int n = A.size();
vector<int> arr(n + 1);
for (int i = 1; i < n; i++) {
arr[i - 1] = abs(A[i] - A[i - 1]);
}
--n;
bool hh = 1, pd = 0, ck = 0;
for (int i = 0; i < n; i++)
if (arr[i]) {
if (arr[i] == 1)
hh = 0, pd ^= calc(n - 1, i);
else
ck ^= calc(n - 1, i);
}
ck &= hh;
if (pd ^ ck)
return "1" + hh;
return "0";
}
int main(){
vector<int> A = { 1, 2, 3, 1 };
cout << solve(A) << endl;
}輸入
{ 1, 2, 3, 1 }輸出
1
更新於：2022-2-25
120 次瀏覽
廣告