本文共 3087 字，大约阅读时间需要 10 分钟。
这就是个简单线段树+延迟标记。因为对bool使用了~而不是！，wa了一下午找不到原因。
1 /* 3275 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set 26 #define stpii set > 27 #define mpii map 28 #define vi vector 29 #define pii pair 30 #define vpii vector > 31 #define rep(i, a, n) for (int i=a;i =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 typedef struct { 44 bool f; 45 int ln, tot; 46 } node_t; 47 48 const int maxn = 1e5+5; 49 char s[maxn]; 50 node_t nd[maxn<<2]; 51 int L, R; 52 53 inline void PushUp(int rt) { 54 nd[rt].ln = nd[rt<<1].ln + nd[rt<<1|1].ln; 55 } 56 57 inline void PushDown(int rt) { 58 if (nd[rt].f) { 59 int lb = rt<<1; 60 int rb = lb|1; 61 nd[lb].f = !nd[lb].f; 62 nd[lb].ln = nd[lb].tot - nd[lb].ln; 63 nd[rb].f = !nd[rb].f; 64 nd[rb].ln = nd[rb].tot - nd[rb].ln; 65 nd[rt].f = false; 66 } 67 } 68 69 void Build(int l, int r, int rt) { 70 nd[rt].f = false; 71 nd[rt].tot = r - l + 1; 72 if (l == r) { 73 nd[rt].ln = (s[l] == '1'); 74 return ; 75 } 76 77 int mid = (l + r) >> 1; 78 Build(lson); 79 Build(rson); 80 81 PushUp(rt); 82 } 83 84 int Query(int l, int r, int rt) { 85 if (l == r) 86 return l; 87 88 PushDown(rt); 89 int mid = (l + r) >> 1; 90 int ret; 91 92 if (nd[rt<<1].ln == nd[rt<<1].tot) 93 ret = Query(rson); 94 else 95 ret = Query(lson); 96 PushUp(rt); 97 98 return ret; 99 }100 101 void Update(int l, int r, int rt) {102 if (L<=l && R>=r) {103 nd[rt].f = !nd[rt].f;104 nd[rt].ln = nd[rt].tot - nd[rt].ln;105 return ;106 }107 108 PushDown(rt);109 int mid = (l + r) >> 1;110 111 if (R <= mid) {112 Update(lson);113 } else if (L > mid) {114 Update(rson);115 } else {116 Update(lson);117 Update(rson);118 }119 120 PushUp(rt);121 }122 123 int main() {124 ios::sync_with_stdio(false);125 #ifndef ONLINE_JUDGE126 freopen("data.in", "r", stdin);127 freopen("data.out", "w", stdout);128 #endif129 130 int n, l;131 int ans, k;132 133 while (scanf("%d %d",&n,&l)!=EOF && (n||l)) {134 scanf("%s", s+1);135 Build(1, n, 1);136 if (nd[1].tot == nd[1].ln) {137 puts("0");138 continue;139 }140 if (l == 0) {141 puts("-1");142 continue;143 }144 145 ans = 0;146 while (1) {147 ++ans;148 k = Query(1, n, 1);149 L = k;150 R = L + l - 1;151 #ifndef ONLINE_JUDGE152 // printf("k = %d\n", k);153 #endif154 if (R > n) {155 ans = -1;156 break;157 }158 Update(1, n, 1);159 if (nd[1].tot == nd[1].ln)160 break;161 }162 printf("%d\n", ans);163 }164 165 #ifndef ONLINE_JUDGE166 printf("time = %d.\n", (int)clock());167 #endif168 169 return 0;170 }
转载于:https://www.cnblogs.com/bombe1013/p/5080577.html