TLS 9.2 A & B

客官°小女子只卖身不卖艺 2023-06-02 11:57 4阅读 0赞

# TLS 9.2A #

![DIW23YHsVC5WpQl\_Ri77gzIWtLbPIJO\_cTAbT-5bBjw.original.fullsize.png][DIW23YHsVC5WpQl_Ri77gzIWtLbPIJO_cTAbT-5bBjw.original.fullsize.png]

这其实是[\[HNOI2006\]鬼谷子的钱袋][HNOI2006]对叭...

然后你就考虑二进制是咋做到完美表示任意一个十进制数字的.

你看看它二进制下有多少位就行了.

# TLS 9.2B #

由于\\(T1\\)太水了,所以我决定把它和\\(T2\\)放一起.

![z5b-oTEnqCSbIL9EZ-HpzIsiHEfRkD0X-HkZcL\_qbh0.original.fullsize.png][z5b-oTEnqCSbIL9EZ-HpzIsiHEfRkD0X-HkZcL_qbh0.original.fullsize.png]

这题水的不行...我们当场想出了一堆做法,包括但不限于线段树,左端点排序暴力染色,并查集,差分.

我一开始写了线段树写\\(RE\\)了,然后我毅然决然地选择了差分.

先讲线段树:

你就每次区间修改,最后像建树一样再把叶子的值赋值回去,再扫一遍就行了.  
注意:线段树建树的复杂度是\\(O(n)\\)的.

然后是左端点排序暴力染色:

把所有询问读进来,按左端点排序,从左向右染色就行了,最后也要再扫一遍.

然后是并查集:

你令并查集数组\\(f\_i\\)表示\\(i\\)这个点向右第一个被染过色的节点的位置,然后路径压缩,每次跳并查集就行了,这是并查集的基操,应该大多数学过并查集的人都会.

最后是最简单的差分:

因为你只关心最后是\\(0\\)的区间,所以每次来一个操作你就直接差分\\(O(1)\\)修改最后前缀和求出修改完的数组,再扫一遍就行了.

只给差分的代码,因为我只留了差分的代码:

\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #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 #define mid ( ( l + r ) >> 1 ) #define ls ( rt << 1 ) #define rs ( rt << 1 | 1 ) using std::set ; 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 = 1e6 + 100 ; struct pairs { int x , y ; } ans[N] ; int n , m , v[N] , cnt ; inline bool cmp (pairs a , pairs b) { if ( a.x != b.x ) return a.x < b.x ; return a.y < b.y ; } signed main (int argc , char * argv[] ) { freopen ("interval.in" , "r" , stdin) ; freopen ("interval.out" , "w" , stdout) ; n = rint () ; m = rint () ; while ( m -- ) { int x = rint () , y = rint () ; ++ v[x] ; -- v[y+1] ; } rep ( i , 1 , n ) v[i] += v[i-1] ; rep ( i , 1 , n ) { if ( v[i] == 0 ) { ans[++cnt].x = i ; while ( v[i] == 0 && i <= n ) ++ i ; ans[cnt].y = i - 1 ; } } std::sort ( ans + 1 , ans + cnt + 1 , cmp ) ; rep ( i , 1 , cnt ) printf ("%lld %lld\n" , ans[i].x , ans[i].y ) ; return 0 ; }

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

[DIW23YHsVC5WpQl_Ri77gzIWtLbPIJO_cTAbT-5bBjw.original.fullsize.png]: /images/20230601/760977332dea4300ac1decdb8b5267f9.png
[HNOI2006]: https://www.luogu.org/problem/P2320
[z5b-oTEnqCSbIL9EZ-HpzIsiHEfRkD0X-HkZcL_qbh0.original.fullsize.png]: /images/20230601/7461375ac78e4c65b4cdd225166eed93.png