2019.08.25校内模拟赛Page

矫情吗；* 2023-06-02 11:58 14阅读 0赞

![page.png][]  
这个题目其实我一眼就看出来是原题了,原题是\\(SPOJ688\\)也就是\\(POI2005\\)的题.  
原题\\(link\\)在这里:[原题][Link 1]  
正如许多人想的一样,这题正解就是个贪心.  
如果说出现缺页(需要拿新玩具),而我们还有空间可以放,那么就直接拿出来,\\(++ans\\).  
如果没有空间了,我们就把空间里出现次数最早的一次最晚的那个页面(玩具)拿出来,把新的放进去.  
贪心思路十分简单,主要的难度在于实现.实现上,目前已知的除了暴力有两种做法.  
第一种是权值线段树的做法[想出此种做法的大佬][Link 2],第二种是\\(STL\\)的\\(set\\)做法[想出此种做法的大佬][Link 3].  
我自己是写了一个\\(O(n^2)\\)的贪心,但是由于这题的数据有梯度,所以我过了\\(75pts\\).为什么不写正解呢?因为我是懒癌重度患者...(反正只差\\(25pts\\))  
我写的做法是每次加入一个新数需要更新内存的时候就暴力去找空间里出现次数最早的一次最晚的那一个,然后开桶记录内存里有啥.  
暴力做法如下:  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <map> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; int n , k , v[N] , tot , ans ; bool mk[N] , cnt[N] ; signed main() { freopen ("page.in" , "r" , stdin) ; freopen ("page.out" , "w" , stdout) ; n = rint () ; k = rint () ; rep ( i , 1 , n ) v[i] = rint () ; rep ( i , 1 , n ) { if ( cnt[v[i]] ) continue ; else if ( tot < k ) ++ ans , ++ tot , cnt[v[i]] = true ; else { MEM ( mk , false ) ; int pos ; rep ( j , i + 1 , n ) { if ( mk[v[j]] || ! cnt[v[j]] ) continue ; pos = j ; mk[v[j]] = true ; } rep ( k , 1 , i ) if ( cnt[v[k]] && ! mk[v[k]] ) pos = k ; ++ ans ; cnt[v[pos]] = false ; cnt[v[i]] = true ; } } printf ("%lld\n" , ans ) ; return 0 ; }

而权值线段树的做法由于太过繁琐,我决定不去码它.而是去码\\(set\\)的做法:  
\\(Code:\\)

咕咕咕咕咕~

转载于:https://www.cnblogs.com/Equinox-Flower/p/11408760.html

[page.png]: https://i.loli.net/2019/08/25/rFxPecZXlC2GfwS.png
[Link 1]: https://www.spoj.com/problems/SAM/
[Link 2]: https://www.cnblogs.com/last-diary/
[Link 3]: https://www.cnblogs.com/wyxdrqc/