题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
    #define IOSIZE (1<<20)
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template	<typename T>inline T    read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*1+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return true;}inline void print(bool b){putchar(b+48);}template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}jyt;template<typename T>Fast_IO&operator>>(Fast_IO&jyt,T&b){return read(b),jyt;}template<typename T>Fast_IO&operator<<(Fast_IO&jyt,T b){return print(b),jyt;}
    struct IO{static const int S=1<<21;char buf[S],obuf[S],*p1,*p2;int st[105],Top;~IO(){clear();}inline void clear(){fwrite(obuf,1,Top,stdout);Top=0;}inline void pc(const char c){Top==S&&(clear(),0);obuf[Top++]=c;}inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}IO&operator>>(char&x){while(x=gc(),x==' '||x=='\n');return*this;}template<typename T>IO&operator>>(T&x){x=0;bool f=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f^=1;ch=gc();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc();f?x=-x:0;return*this;}IO&operator<<(const char c){pc(c);return*this;}template<typename T>IO&operator<<(T x){if(x<0)pc('-'),x=-x;do{st[++st[0]]=x%10,x/=10;}while(x);while(st[0]){pc('0'+st[st[0]--]);}return*this;}}ld;
} using namespace fast_IO;
#define ll long long
#define ull unsigned long long
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define rep(i, l, r) for (int i = l; i < r ; ++i)
#define per(i, l, r) for (int i = l; i > r ; --i)
#define pf(x) (1ll * (x) * (x))
#define bitcount(x) __builtin_popcountll(x)
#define albit(x) ((1 << (x)) - 1)
#define mkbit(x) (1 << (x - 1))
#define gtbit(x, id) (((x) >> (id - 1)) & 1)
// #define ld cin
// #define jyt cout
// #define int long long
const int N = 50;
const int inf = 1e9 + 7;
const ll linf = 1e18 + 7;
const int P = 998244353;
namespace MG42 {
    int T, n, m, a[N], lxl[N], Ans = 0;
    struct Node {int l, r;} c[N];
    ull Up, Do;
    inline void dfs(int i, int Res) {
        if (Res >= Ans) return;
        if (i > m) return Ans = Res, void();
        int upc = bitcount(Up & ((1ull << c[i].r) - 1ull)), doc = bitcount(Do & ((1ull << c[i].r) - 1ull)), bec = i - upc - doc - 1; upc -= bitcount(Up & ((1ull << c[i].l) - 1ull)), doc -= bitcount(Do & ((1ull << c[i].l) - 1ull));
        Up |= (1ull << c[i].r), dfs(i + 1, Res + min(upc, doc + bec)), Up ^= (1ull << c[i].r); 
        Do |= (1ull << c[i].r), dfs(i + 1, Res + min(doc, upc + bec)), Do ^= (1ull << c[i].r);
    }
    signed main() {
        ld >> T;
        while (T--) {
            ld >> n, m = 0, Ans = inf;
            REP(i, 1, n) {
                ld >> a[i];
                if (!lxl[a[i]]) lxl[a[i]] = i;
                else c[++m] = (Node) {lxl[a[i]], i};
            }
            sort(c + 1, c + m + 1, [](Node a, Node b) {return a.l == b.l ? a.r < b.r : a.l < b.l;});
            dfs(1, 0), jyt << Ans << '\n';
            REP(i, 1, n) lxl[i] = 0;
        }
        return 0; 
    }
}
signed main() {
//	freopen("std.in", "r", stdin);
//	freopen("user.out", "w", stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
    MG42::main();
    return 0;
}