首页 > 代码库 > BZOJ1106 [POI2007]立方体大作战tet

BZOJ1106 [POI2007]立方体大作战tet

2024-07-30 12:38:59   219人阅读

考试前刷刷水感觉还是不错的。

 对于某两个相同的数，若中间未被匹配的数（即只出现一次的数）的数量为x，则至少要交换x次。

于是用树状数组维护1 - n中的未被匹配的数的个数即可。

（为什么蒟蒻觉得有O(n)的做法。。。不科学。。。）

 

 1 /************************************************************** 2     Problem: 1106 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:164 ms 7     Memory:1976 kb 8 ****************************************************************/ 9  10 #include <cstdio>11  12 using namespace std;13 const int N = 100005;14 int n, ans;15 int a[N], BIT[N], l[N];16  17 inline int read(){18     int x = 0, sgn = 1;19     char ch = getchar();20     while (ch < ‘0‘ || ch > ‘9‘){21         if (ch == ‘-‘) sgn = -1;22         ch = getchar();23     }24     while (ch >= ‘0‘ && ch <= ‘9‘){25         x = x * 10 + ch - ‘0‘;26         ch = getchar();27     }28     return sgn * x;29 }30  31 inline int lowbit(int x){32     return x & -x;33 }34  35 inline int query(int x){36     int res = 0;37     for (; x; x -= lowbit(x))38         res += BIT[x];39     return res;40 }41  42 inline void add(int x, const int del){43     for (; x <= n; x += lowbit(x))44         BIT[x] += del;45 }46  47 int main(){48     n = read(), n <<= 1;49     int i;50     for (i = 1; i <= n; ++i)51         a[i] = read();52     for (i = 1; i <= n; ++i)53         if (!l[a[i]]) add(i, 1), l[a[i]] = i;54         else{55             ans += query(i) - query(l[a[i]]);56             add(l[a[i]], -1);57         }58     printf("%d\n", ans);59     return 0;60 }
View Code

 

BZOJ1106 [POI2007]立方体大作战tet


联系
我们