2016 USP-ICMC

Problem - B - Martian Sunrise贪心

题目描述：

给你$m$行音调，每行音调有$7$个元素，给你一行目标音调$n$ , 每次可以从$m$行任选两行,作为你的元素集合去匹配目标音调，求最少多少次完成匹配。$（1 \le m \le 16，1 \le n \le 1e4）$

题目分析：

所有选择的方案总共$m*(m-1)/2$，乘上总元素大约$3000$，然后直接从第一个目标音调的元素枚举到$n$，同时枚举所有现存的包含当前元素的集合，同时去除不包含的，如何此时没有任何一个集合满足，则重新枚举所有集合并且答案数$++$。这里有个贪心正确性：取匹配目标元素最长的集合并不会让总集合数变多。时间复杂度大约$3e7$左右。

题目代码：

map<string, int> mp;
int cnt;
set<int> b[300];
bool st[300];
void solve()
{
    int m;
    cin >> m;
    vector<int> v[m];
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            string s;
            cin >> s;
            if (!mp[s])
            mp[s] = ++cnt;
            v[i].pb(mp[s]);
        }
    }
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
    {
        string s;
        cin >> s;
        x = mp[s];
    }
    
    int idx = 0;
    if (m == 1)
    {
        for (auto &x : v[0])
            b[idx].insert(x);
        idx++;
    }
    
    for (int i = 0; i < m; i++)
    {
        for (int j = i + 1; j < m; j++)
        {
            for (auto &x : v[i])
                b[idx].insert(x);
            for (auto &x : v[j])
                b[idx].insert(x);
            idx++;
        }
    }
    
    memset(st, 0, sizeof st);
    int num = idx, ans = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < idx; j++)
        {
            if (!st[j] && b[j].find(a[i]) == b[j].end())
                num--, st[j] = 1;
            if (!num)
            {
                i--;
                break;
            }
        }
        if (!num)
            num = idx, ans++, memset(st, 0, sizeof st);
    }
    
    cout << ans << "\n";
}

Problem - I. Lazy Painting/DFS/SET(stl)

题目描述：

实验室地板可以表示为一个 $N$ 行、$M$ 列的矩阵，总共有 $N \times M$ 块瓷砖。指令是以矩形区域为单位进行涂漆，每个矩形的高度为 $H$，宽度为 $W$，且这些矩形可以重叠。每次指令后，需要计算还有多少瓷砖未涂漆。

马加里达负责执行指令，她会检查矩形的左边界，如果左侧边框中的瓷砖都已经涂漆，她会跳过该矩形。如果有未涂漆的瓷砖，她会将从左侧边框可到达的所有未涂漆的瓷砖进行涂漆。如果只有矩形内的未涂漆瓷砖可以到达某个瓷砖，那么这个瓷砖也会被涂漆。

输入

第一行包含五个整数 $N$、$M$ $(1 ≤ N, M ≤ 10^5$ 和 $1 ≤ N * M ≤ 3 * 10^6)$、$H$、$W$ $(1 ≤ H ≤ N$， $1 ≤ W ≤ M)$ 和 $Q$ $(1 ≤ Q ≤ 10^5)$. 然后是 $Q$ 行. 第 $i$ 行包含两个整数 $r_i$ 和 $c_i$ $(1 ≤ r_i ≤ N - H + 1$， $1 ≤ c_i ≤ M - W + 1)$—要绘制的矩形区域的左上平铺. 研究实验室最左边最上面的瓦片是 $(1, 1)$.

输出

每次指令过后有多少未覆盖的瓷片.

题目分析：

因为是检查左边界，用$set$记录每列还有哪些没有被覆盖。当执行命令的时候二分查找还存在的，加到队列中进行$DFS/BFS$覆盖即可，同时维护答案–。因为整个询问 $q$ 次的时候，矩阵只会被访问一次 ，每次访问的时候set删除 $\log n$，所以总复杂度约为 $O((Q+N \times M) \log n)$.

题目代码：

int n, m, h, w, Q, ans, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
set<int> s[N];
queue<PII> q;
bitset<M> st;
void bfs(int u, int v)
	{
		int nn = u + h - 1, mm = v + w - 1;
		set<int>::iterator it = s[v].lower_bound(u);
		// cout<<u<<" "<<*it<<" "<<nn<<" "<<mm<<"\n";
		while (*it <= nn)
		{
			q.push({*it, v});
			// cout<<*it<<"\n";
			st[(*it - 1) * m + v] = 1;
			it++, ans--;
		}
		// cout<<nn<<"#"<<mm<<"#"<<q.size()<<"\n";
		while (q.size())
		{
			auto [xx, yy] = q.front();
			q.pop();
			s[yy].erase(xx);
			for (int i = 0; i < 4; i++)
			{
				int t = xx + dx[i];
				int z = yy + dy[i];
				if (t >= u && t <= nn && z >= v && z <= mm && st[(t - 1) * m + z] == 0)
				{
					st[(t - 1) * m + z] = 1;
					q.push({t, z});
					ans--;
				}
			}
		}
}
void solve()
{
	cin >> n >> m >> h >> w >> Q;
	ans = n * m;
	for (int i = 1; i <= n+1; i++)
	{
		for (int j = 1; j <= m; j++)
			s[j].insert(i);
	}
	
	while (Q--)
	{
		int x, y;
		cin >> x >> y;
		bfs(x, y);
		cout << ans << "\n";
	}
}