Accommodation

Created by LXC on Mon Feb 12 00:53:53 2024

https://codeforces.com/problemset/problem/1804/D

ranting: 2000

tag: brute force, dp, greedy, implementation

problem

一栋公寓有 $n$ 层，每层有 $m$ 个窗户，其中 $m$ 是 4 的倍数。

每层楼恰好有 $\dfrac{m}{2}$ 户是一居室，只有一个窗户；恰好有 $\dfrac{m}{4}$ 户是两居室，有相邻的两个窗户。你不知道每层楼哪些窗户是一居室、哪些连续窗户是两居室，且不同楼层的一居室和两居室的分布可能不同。

每个窗户有开灯和关灯两种状态。如果一居室的窗户开灯，或者两居室至少一个窗户开灯，则里面有人；否则没有人。请你计算整栋公寓至少和至多分别有多少户有人。

solution

设总亮着灯灯的数目为A

单人房中有T0个没有亮灯的，T1个亮一个灯的。

双人房中有D0个没有亮灯的，D1个亮一个灯的，D2个亮两个灯的。

U为居住用户数

有关系等式，U=T1+D1+D2，A=T1+D1+2*D2。所以U=A-D2

只需最大化D2得到最小居住数，最小化D2得到最大居住数。

如何最大化TD，只需找出所有连续的亮着的窗口段。不妨设这些段为$l_1,l_2,\cdots,l_s$。则最大化的$D2 = min(\frac{m}{4}, \sum \limits_{i=1}^{s} \lfloor \frac{l_i}{2}\rfloor)$

如何最小化D2，只需找到不存在连续两个亮着的窗口段。不妨设这些段为$l_1’,l_2’,\cdots,l_s’$。则最小化的$D2=max(0,\frac{m}{4}-\sum\limits_{i=1}^{s}\lfloor\frac{l_i’}{2}\rfloor)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
	int n, m;
    cin >> n >> m;
    int mx = 0, mn = 0;
    auto get_min = [](string& s) {
        int sz = s.size();
        int cnt = 0, c1 = 0;
        for (int i=0, j; i<sz; i = j) {
            if (s[i] == '0') {
                j = i+1;
            }
            else {
                j = i;
            	while (j<sz && s[j] == s[i]) j++;
				cnt += (j-i)/2;
            	c1 += j-i;
            }
        }
        return c1-min(cnt, sz/4);
    };
    auto get_max = [](string& s) {
        
		int sz = s.size();
        int cnt = 0, cur = 1, c1 = count(s.begin(), s.end(), '1');
        for (int i=1; i<sz; i++) {
            if (s[i-1] == s[i] && s[i] == '1') {
                cnt += cur/2;
                cur = 1;
            } else {
                cur++;
            }
        }
    	cnt += cur/2;
        return c1 - max(sz/4-cnt, 0);
    };
    string g;
    for (int _x = 0; _x < n; _x++) {
        cin >> g;
		mx += get_max(g);
        mn += get_min(g);		
    }
    cout << mn << " " << mx << endl;


}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}