A小紅的雙排列

?沒什么好說的 直接 1 1 2?2 3 3 4 4……

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n;for (int i = 1; i <= n; i++) {cout << i << " " << i<< " ";}cout << endl;return 0;
}

B小紅的雙排列拆分

?就要注意是子序列，順序不能倒，然后就是標記已經打印的數，并且記住他的位置（或使他們變為-1）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
int n;
using namespace std;
int a[200];
int b[100];
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定int s;cin >> n;for (int i = 1; i <= n*2; i++) {cin >> a[i];}for (int i = 1; i <= n*2; i++) {if (b[a[i]] == 0) {cout << a[i] << " ";b[a[i]]++;a[i] = -1;}}cout << endl;for (int i = 1; i <= n*2; i++) {if (a[i] != -1) {cout << a[i] << " ";}}cout << endl;return 0;
}

C小紅的雙排列刪除

?我一開始寫煩了，就不講之前的方法了，將一個簡單的。

就是看從第一個開始能不能找到連續的使其消除 例 1 ……1 2……2 3……3

之前代碼：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int t, n;
int a[400005];
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> t;while (t--) {cin >> n;for (int i = 0; i < n*2; i++) {cin >> a[i];}stack<int> q;vector<bool> f(n+1);for (int i = 1; i < n; i++) {f[i] = false;}for (int i = 0; i < n * 2; i++) {if (q.empty()) {q.push(a[i]);f[a[i]] = true;}else {if(f[a[i]]==false){f[a[i]] = true;q.push(a[i]);}else{while(!q.empty()&&q.top()!=a[i]) {f[q.top()] = false;q.pop();}if(!q.empty()){f[q.top()] = false;q.pop();}}}}if (q.empty()) {cout << "Yes" << endl;}else {cout << "No" << endl;}}return 0;
}

之后簡單代碼：?

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int t, n;
int a[400005];
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> t;while (t--) {cin >> n;for (int i = 0; i < n * 2; i++) {cin >> a[i];}int j = 0;for (int i = 1; i < n * 2; i++) {if (a[j] == a[i]) {j = i + 1;i++;}}if (j>=n*2) {cout << "Yes" << endl;}else {cout << "No" << endl;}}return 0;
}

?D小紅的雙排列權值

?

不難發現： 1 2 1 2/ 2 1 1 2 / 1 2 2 1/2 1 2 1 怎么交換權值都不會遍

只有：1 1 2 2? ? ? 1 2怎樣交換權值都是變多 (a[2]-a[1])*2

所以找到距離最遠的兩個就解決了

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
int a[400005];
int b[200005];
bool c[200005];
ll sum = 0;
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n;for (int i = 1; i <= n*2; i++) {cin >> a[i];}int q = 0;for (int i = 1; i <= n*2; i++) {if (b[a[i]] == 0) {b[a[i]] = i;}else {sum += i - b[a[i]] - 1;if (q == 0) {q = i;}}}int qq = 0;for (int i = n * 2; i >=1; i--) {if(c[a[i]]==false){c[a[i]] = true;}else {qq = i;break;}}if (q < qq) {cout << (qq - q) * 2 + sum << endl;}else {cout << sum << endl;}return 0;
}

E小紅的雙排列刪除得分

動態規劃題：? ? ? ? ? ? dp[i] = max(dp[i], dp[c[a[i]]] + b[i] - b[c[a[i]] - 1]); （有點小難）

?

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
ll dp[200005];
int h = 0;
ll a[400005], b[400005], c[200005];
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n;a[0] = 0;for (int i = 1; i <= 2*n; i++) {cin >> a[i];b[i] = b[i - 1] + a[i];}for (int i = 1; i <=2* n; i++) {dp[i] = dp[i - 1];if (c[a[i]]) {dp[i] = max(dp[i], dp[c[a[i]]] + b[i] - b[c[a[i]] - 1]);}c[a[i]] = i;}cout << dp[n * 2] << endl;return 0;
}

F小紅的雙排列期望（easy）

這題好像是dp題，但我沒有用dp來寫

我是直接算，唯一要知道的就是除法的逆序元

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll mod = 1e9 + 7;
int n;
ll chu(ll w, int k) {ll sum0 = 1;while (k>0) {if (k % 2 != 0) {sum0 = (sum0 * w) % mod;}w = (w * w) % mod;k /= 2;}return sum0;
}
ll b[102];
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n;vector<int>a(n*2);for (int i = 0; i < n*2; i++) {cin >> a[i];}sort(a.begin(), a.end());b[1] = 1;for (int i = 2; i <=100; i++) {b[i] = chu(i, mod - 2);}ll sum = 0;for (int i = 0; i < n * 2; i++) {sum = (sum + (i + 2) / 2 * 100 * b[a[i]] % mod) % mod;}cout << sum << endl;return 0;
}

?G?小紅的雙排列期望（hard）

dp題，但我有點小菜，目前還=沒有學過這種dp，會的大佬可以留言告訴我?