ZROI#960

Bertha 。 2023-06-02 11:56 7阅读 0赞

[ZROI\#960][ZROI_960]

先说\\(\\Theta(n^2)\\)暴力叭.  
显然的想法就是枚举答案中相邻两个\\(1\\)之间的\\(0\\)的个数.  
然后贪心匹配,注意判断最后一段是否满足限制.

#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 one first #define two second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; 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 = 1e5 + 100 ; char s[N] ; int n , ans , tmp[N] ; bool v[N] ; inline bool check () { return true ; } signed main (int argc , char * argv[]) { scanf ("%s" , s + 1 ) ; n = strlen ( s + 1 ) ; rep ( i , 1 , n ) v[i] = ( s[i] == '1' ) ; rep ( i , 0 , n ) { int time = 0 , res = 0 , cur = 0 ; bool f = false , d = 0 , able = false ; rep ( j , 1 , n ) { if ( ! d && ! v[j] ) { ++ cur ; if ( cur == i ) d = true , ++ time ; } if ( d && v[j] ) { cur = 0 ; d = false ; res += ( i + 1 ) ; able = true ; } } if ( able ) { if ( time < 2 ) continue ; if ( d ) { ans = max ( ans , res + i ) ; } else ans = max ( ans , res - 1 ) ; } } printf ("%lld\n" , ans ) ; return 0 ; }

然后我们发现这个算法的瓶颈在于去匹配一串\\(0\\),这里如果你对根号分治熟悉的话就可能会自然地想根号分治,这是完全可行的.  
但我们要说的不是这种做法,我们考虑,虽然原序列中\\(0\\)的个数不存在单调性,但是前缀\\(0\\)的个数确实具有单调性的.  
而且只需要关注以\\(1\\)为界的划分即可.于是我们就可以去二分/倍增地找一段\\(0\\).  
代码没写.

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

[ZROI_960]: http://www.zhengruioi.com/problem/960