簽到題，數據量很小，也沒有仔細想直接兩個哈希集合，去重并判斷每個元素是否在另一個集合出現過，沒有出現過就添加到結果數組中。

class Solution {
public:vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> s1, s2;for (auto x : nums1) s1.insert(x);for (auto x : nums2) s2.insert(x);vector<vector<int>> ret(2);for (auto x : s1) {if (s2.count(x) == 0) ret[0].push_back(x);}for (auto x : s2) {if (s1.count(x) == 0) ret[1].push_back(x);}return ret;}
};

題目的意思就是偶數位置的元素要和下一個位置的元素不相等。因為只向后看， 所以當時想到了一個構造答案的方法：首先統計每個數字連續出現的次數x。對于偶數位置，ans+=x-1，對于奇數位置，ans+=x-2。最后如果要填充奇數位置，則++ans，因為最后一個位置必須要保證數組的長度為偶數。

class Solution {
public:int minDeletion(vector<int>& nums) {vector<pair<int, int>> cnt;int n = nums.size();for (int i = 0; i < n; ) {int j = i + 1;while (j < n && nums[j] == nums[i]) ++j;cnt.emplace_back(nums[i], j - i);i = j;}n = cnt.size();int ans = 0, x;bool is_even = true;for (int i = 0; i < n; ++i) {x = cnt[i].second;if (is_even) {ans += x - 1;is_even = false;} else {if (x == 1) {is_even = true;} else {ans += x - 2;}}}if (!is_even) ++ans;return ans;}
};

這樣做的正確性在于，對于偶數位置，他如果連續出現了多次，最多只能保留1個。對于奇數位置，如果連續出現了多次，最多只能保留2個。這里我們每次都選擇的是盡可能保留以滿足題目中的最短長度。最后我們處理了一下讓整個數組的長度為偶數：如果下一次要填充的是奇數位置的數字，那么說明前面的位置是偶數位置，需要將其刪除。

接下來我們簡單討論一下為什么盡可能保留數字是最優的。假如某個位置我們可以保留某個數字但是我們將其刪光了，后面的數字會移動到前面，同樣需要刪除，并不能讓解更好。詳細的證明需要分類討論之類的，這里我們就不求甚解了。

是一個對我來講有點思維量的模擬，我們需要能夠構造任意長度，第任意大小的回文串。為了能夠構造第x大的回文串，我們需要使用類似進制轉換的思想。
對于相同長度的回文串，其值和相對大小是由前面一半的數字支配的，后面一半的數字都不用進行考慮。
第一個數字只能是1-9，后面的數字每一位都可以是0-9。對于一個回文串長度為intLength，他的所有可能結果是$maxn=9?10^{\frac{intLength?1}{2}}$。如果x大于maxn，則直接返回-1。
接下來我們來從前往后確定每一位數字的大小。第一位數字確定后，后面的數字有maxn/=9種可能。即第1——maxn個回文串的第一位是1，第maxn+1——2maxn個回文串的第一位是2。為了確定第一位的數字，我們可能想要讓x/maxn來確定。但是整除需要我們特別處理一下。
因為算數運算默認是從0開始的，0——maxn-1 /x都是0。為了尋求這種統一，我們不妨給x減一，從而可以直接套用算術運算。
對于后面的位數也是同樣的道理。總結一下就是為了能夠讓x對固定步長（上面的maxn）進行分組，我們讓x-1，從而將原本1——maxn變成了0——manx-1，變成了在數值意義上的同一組。
后面取余仍然會從0開始，所以我們只用減一一次。

class Solution {using ll = long long;ll n_, maxn_, len_;ll work(ll x) {--x;vector<int> arr;ll n = n_;arr.push_back(x / n + 1);x %= n;ll len = len_;len -= 2;while (len > 0) {n /= 10;arr.push_back(x / n);x %= n;len -= 2;}ll ret = 0;for (auto x : arr) ret = ret * 10 + x;if (len_ & 1) arr.pop_back();int nn = arr.size();for (int i = nn - 1; i >= 0; --i) ret = ret * 10 + arr[i];return ret;}public:vector<long long> kthPalindrome(vector<int>& queries, int intLength) {len_ = intLength;int n = (intLength - 1) >> 1;n_ = 1;for (int i = 0; i < n; ++i) {n_ *= 10;}maxn_ = n_ * 9;vector<ll> ret;for (auto x : queries) {if (x > maxn_) ret.push_back(-1);else {ret.push_back(work(x));}}return ret;}};

仔細研究了一下大牛的解法，發現我這里處理復雜的原因是沒有想到每位填充的也是十進制數字，那么x-1+maxn就是前一半數字。x-1是第一位從0開始的第x個數字，加上maxn就是第一位從1開始的。

我們很容易就可以計算出從一個棧中取m個硬幣的面值和，那么問題就是我們可以從n個棧中取硬幣，每個棧可以取0個或多個，最終取k個的最大和。想了一下也沒有什么狀態轉移的，就直接記憶化搜索了。

class Solution {int n_;vector<vector<int>> sum;vector<int> cnt;vector<vector<int>> memo;int dfs(int x, int k) {if (x == n_) {return sum[x][k];} else {if (memo[x][k] != -1) return memo[x][k];int kk = std::min(k, (int)sum[x].size() - 1);for (int i = std::max(0, k - cnt[x]); i <= kk; ++i) {memo[x][k] = max(memo[x][k], sum[x][i] + dfs(x + 1, k - i));}}return memo[x][k] == -1 ? INT_MIN : memo[x][k];}
public:int maxValueOfCoins(vector<vector<int>>& piles, int k) {int n = piles.size();memo.resize(n, vector<int>(k + 1, -1));n_ = n - 1;sum.resize(n);cnt.resize(n);for (int i = 0; i < n; ++i) {auto &arr = piles[i];auto &s = sum[i];s.push_back(0);for (auto x : arr) {s.push_back(s.back() + x);}}int t = 0;for (int i = n - 1; i >= 0; --i) {cnt[i] = t;t += piles[i].size();}return dfs(0, k);}
};

當時最后幾分鐘寫完后一直運行錯誤，我心態有點崩，覺得果然又要到此為止了嗎。但是還是耐下性子去看代碼到底哪里有問題。當時報的是堆上的錯誤，我就覺得是不是哪里數組越界了。認真一看，sum、cnt不可能越界，那是不是備忘錄memo越界了呢？仔細一想，memo的第二個維度是可以取到k的，而我第二個維度的大小只有k，于是將第二個維度的大小改成k+1就過了。
以前寫記憶化搜索都是自己特化一個對pair的哈希然后用unordered_map做，這次因為時間不夠用的二維數組，而之前都沒有寫過用二維數組進行備忘錄，所以就沒注意過這個問題。

雖然時間緊迫，但是我對自己這個記憶化搜索還是挺滿意的，有備忘錄，有必要的剪枝，代碼也很緊湊。
首先初始化了一下memo和sum數組，sum[x][k]表示的是第x個棧取k個硬幣的面值和，memo[x][k]表示的是對于從x到n-1的棧，總共取k個硬幣的最大面值和，最終的答案就是memo[0][k]，初始化為-1表示沒有進行更新，如果memo[x][k]不可能存在，則賦值為無窮小。因為我們求的是最大值，所以不會用到這個狀態。

cnt數組是為了剪枝維護的狀態，cnt[x]表示從x+1到n-1總共有多少個硬幣，std::max(0,k-cnt[x])就表示第x個棧至少要取多少枚硬幣才能夠保證從x到n-1能夠取到k個硬幣，std::min(k, (int)sum[x].size()-1)表示第x個棧至多能夠取到多少個硬幣。

總共最多有O(x)*O(k)=2e6個狀態，每個狀態至多求解一次，每個狀態的求解至多是O(k)，因此最壞的時間復雜度是2e9。本來心里有些打鼓，但是提交后發現通過了，非常開心。

仔細閱讀了一下大牛的解法，發現是一個01背包問題。感覺自己對背包問題的理解還是不夠深刻，應該專門再整理一下背包問題的思路。