暑假牛客多校第四场 2023-7-28
未补完
L. We are the Lights
算法:反向构造
做法:
我们用c_on, r_on, c_off, r_off
分别表示倒着推的行灯打开的集合、列灯打开的集合、列灯关闭的集合、行灯关闭的集合。倒着推时,我们先考虑on
的情况。为了偷懒,我们就只考虑行的情况,因为列的情况实际上是一样的。
打开灯时,我们先查找r_on
集合里是否之后要打开此行的灯,要打开就跳过,否则再找找r_off
的集合中是否这行将被关闭,将被关闭也跳过。两种情况都不符合的话,我们就将这行加入r_on
,并且加上这一行的最终打开的灯的数量,即ans += m - c_off.size() - c_on.size()
。(注意:
每一行要么出现在c_off
,要么出现在c_on
,因为如果这一行在从后往前推的过程中已经出现在了c_off
里,那么现在你要打开这一行的灯是无意义的,因为未来你将关闭这行灯。如果这一行在从后往前推的过程中已经出现在了c_on
里,那么现在你要关闭这一行的灯是无意义的,因为未来你要打开这一行的灯。)(另外,c_on.size()
是为了防止重复加了某些灯。)
关闭灯时,我们先查找r_off
集合里是否之后要关闭此行的灯,要关闭就跳过,否则再找找r_on
的集合中是否这行将被打开,将被打开也跳过。两种情况都不符合的话,我们就将这行加入r_off
,我们不需要删除任何数,因为我们再加灯的数量的时候就已经考虑了灯被关闭的影响。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 1000100;
int n, m, q;
struct W
{
string x, st;
int u;
}w[N];
void solve()
{
LL ans = 0;
cin >> n >> m >> q;
set<int> c_on, r_on, c_off, r_off;
for (int i = 0; i < q; i++)
{
int u;
string x, st;
cin >> x >> u >> st;
w[i] = { x, st, u };
}
for (int i = q - 1; i >= 0; i--)
{
int u = w[i].u;
string x = w[i].x, st = w[i].st;
if (st == "off")
{
if (x == "row" && r_off.find(u) == r_off.end() && r_on.find(u) == r_on.end())r_off.insert(u);
else if (x == "column" && c_off.find(u) == c_off.end() && c_on.find(u) == c_on.end())c_off.insert(u);
}
else if(st == "on")
{
if (x == "row")
{
if (r_off.find(u) != r_off.end())continue;
else if (r_on.find(u) != r_on.end())continue;
else
{
r_on.insert(u);
ans += m - c_off.size() - c_on.size();
}
}
else if(x == "column")
{
if (c_off.find(u) != c_off.end())continue;
else if (c_on.find(u) != c_on.end())continue;
else
{
c_on.insert(u);
ans += n - r_off.size() - r_on.size();
}
}
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}