2021"MINIEYE杯"中超(4)
1002 Kanade Loves Maze Designing
本题点数n最多为2000，因此允许O(n²)的做法，我们用dfs来计算任意两点间的点的种类数即可得出答案。因本题数据量较小，所以无需快速幂优化，直接循环n次预处理出K ^ (j - 1)即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9, K = 19560929;
int t;
int n;
int cnt[N];
int am[N][N];
int c[N];
int ans;
int md1[N], md2[N];
vector<int> v[N];
void cal1(int i, int &k)//计算答案
{
for (int j = 1; j <= n; j ++ ) k = (1ll * k + 1ll * am[i][j] * md1[j - 1]) % MOD1;
}
void cal2(int i, int &k)//计算答案
{
for (int j = 1; j <= n; j ++ ) k = (1ll * k + 1ll * am[i][j] * md2[j - 1]) % MOD2;
}
void init()//预处理数组
{
md1[0] = md2[0] = 1;
for (int i = 1; i < N; i ++ )
{
md1[i] = 1ll * md1[i - 1] * K % MOD1;
md2[i] = 1ll * md2[i - 1] * K % MOD2;
}
}
//+-1法求[i, j]间点的种类数
void add(int k)//加操作
{
if (!cnt[k]) ans ++ ;
cnt[k] ++ ;
return;
}
void del(int k)//遍历过后的删除操作
{
if (cnt[k] == 1) ans -- ;
cnt[k] -- ;
return;
}
void dfs(int now, int to, int fr)//删除操作,now表示从now点开始搜,to表示当前点,fr表示来向防止重复搜
{
add(c[to]);//加上此点的值
am[now][to] = ans;//记录now到此点的结果
for (auto t : v[to])
if (t != fr)//防止重复搜索
dfs(now, t, to);
del(c[to]);
return;
}
void solve()
{
cin >> n;
for (int i = 2, x; i <= n; i ++ )
{
cin >> x;
v[i].push_back(x), v[x].push_back(i);
}
for (int i = 1; i <= n; i ++ ) cin >> c[i];
for (int i = 1; i <= n; i ++ )
{
dfs(i, i, -1);//当前搜i点,因为i点是起点,所以来向标记为-1
int ans1 = 0, ans2 = 0;
cal1(i, ans1), cal2(i, ans2);
cout << ans1 << ' ' << ans2 << endl;
}
//for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) cout << am[i][j] << (j == n ? '
' : ' ');
for (int i = 1; i <= n; i ++ ) v[i].clear();
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
init();//初始化
cin >> t;
while (t -- ) solve();
return 0;
}
1007 Increasing Subsequence
首先思考朴素一点的做法，采用一般处理线性dp的思路。f[i]表示以a[i]结尾的极大子序列，接着考虑贡献，对于j (j < i)，只有[j, i]中间没有a[j] ~ a[i]的元素，那么f[j] 才对 f[i]有贡献。f[i]对答案有贡献当且仅当[i ~ n]中没有比a[i]大的元素，所以朴素一点的线性dp解法就有了。O(n²)的复杂度，考虑到n是1e5的级别，会t。
接着思考优化，处理区间[l, r]时，以m为终点将其分开，然后两边维护两个单调栈，左边单调栈元素值从小到大，下标从大到小，右边单调栈元素值从小到大，下标从小到大。接着考虑贡献，对于f[i] (i > mid)，我们找到左边第一个比f[i]小的值a[j]，因为右边也维护了一个单调栈，所以栈顶元素即满足要求，如果栈空那么就返回0。然后去找左边单调栈中第一个比a[j]大的值和最后一个比a[i]小的值，那么这个范围内都是对f[i]有贡献的。直接将这些dp值加上即可。为了方便计算，我们可以用一个vector储存左边区间的dp值前缀和，并且在维护单调栈的同时也维护这个前缀和dp的vector。
code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int P = 998244353;
int add(int a, int b) {a += b; return a < P ? a : a - P;}
int sub(int a, int b) {a -= b; return a < 0 ? a + P : a;}
const int N = 100001;
int a[N], dp[N];
void solve(int l, int r)
{
if (l + 1 == r) return;
int mid = (l + r) >> 1;
solve(l, mid);//处理左边
vector<int> pos(r - l);
iota(pos.begin(), pos.end(), l);//递增赋值下标
sort(pos.begin(), pos.end(), [&](int i, int j) { return a[i] < a[j]; });//按照值递增排序排序
vector<int> ls, rs;
vector<int> sum(1, 0);//初始化加入一个0,方便前缀和
for (int i : pos)//pos是有序的,所以每个a[i]一定是比当前在栈中的值都要大
{
if (i < mid)
{
while (!ls.empty() && ls.back() < i)//在我左边而且值还比我小,一定没有贡献,删掉就行
sum.pop_back(), ls.pop_back();
ls.push_back(i);//将i加入左边序列的单调栈
sum.push_back(add(sum.back(), dp[i]));//更新左边dp前缀和
}
else
{
while (!rs.empty() && rs.back() > i)//在我右边还比我小,一定没有贡献,同样删掉
rs.pop_back();
if (ls.empty()) continue;//如果左边是空的,没有可以继承过来的状态
//id1是找到大于a[i]的第一个元素,由于dp前缀和中有一个0,所以偏移一下会到小于a[i]的最后一个元素
int id1 = partition_point(ls.begin(), ls.end(), [&](int x) { return a[x] < a[i]; }) - ls.begin();
//id2是找到大于a[rs.back()]的第一个元素
int id2 = rs.empty() ? 0 : partition_point(ls.begin(), ls.end(), [&](int x) { return a[x] < a[rs.back()]; }) - ls.begin();
//更新处于右边的dp数组
dp[i] = add(dp[i], sub(sum[id1], sum[id2]));
rs.push_back(i);
}
}
solve(mid, r);//递归处理右边
}
int main(void)
{
int T; scanf("%d", &T);
while (T--)
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1, v = INT_MAX; i <= n; ++i)//处理dp数组
{
if (v > a[i])//左边最小的比当前的大,说明以a[i]结尾的有贡献
dp[i] = 1;
else //反之一定会成为其他序列的子序列,没有贡献
dp[i] = 0;
v = min(v, a[i]);
}
solve(1, n + 1);//左闭右开
int ans = 0;
for (int i = n, v = 0; i >= 1; --i)
{
if (v < a[i])
ans = add(ans, dp[i]);
v = max(v, a[i]);
}
printf("%d
", ans);
}
return 0;
}
1008 Lawn of the Dead
对于每个点，只有其左边或者上面可以到达，它才可以到达。对于每个地雷，那么它一定挡住了从左边到达的这条路，这时候我们只能考虑从上方到达，因此对于每个地雷[i, j]，我们考虑[i - 1, j + 1]这个点向右连续不可到达的区域，那么第i行的这些列的可达情况肯定和其是一致的。因此我们可以通过这种操作算出不可到达的数量，最后用总点数量减去不可到达的数量再减去地雷数得到的就是答案。涉及到区间查询和区间修改的操作，因此可以用线段树维护状态，另外，因为考虑第i行的时候，我们只需要考虑第i - 1行的状态，类比滚动数组的思想，我们只需要建两棵线段树即可完成上述操作。
code
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, k;
int t;
vector<int> mine[N];//存每行地雷下标
struct node
{
int p, l, r, val, lmx;//lmx为区间左端点开始连续不可到达的长度
int lazy;//懒标记
}tr[2][N * 4];//两棵树
void build(int x, int u, int l, int r)
{
tr[x][u].l = l, tr[x][u].r = r, tr[x][u].lazy = -1;//初始化懒标记
if (l == r)
{
tr[x][u].val = tr[x][u].lmx = 0;
tr[x][u].lazy = -1;
return;
}
int mid = l + r >> 1;
build(x, u << 1, l, mid), build(x, u << 1 | 1, mid + 1, r);
//pushup操作
tr[x][u].val = tr[x][u << 1].val + tr[x][u << 1 | 1].val;
tr[x][u].lmx = 0;
}
void pushdown(int x, int u)
{
if (tr[x][u].lazy != -1)//打标记了
{
//处理左子树
tr[x][u << 1].val = (tr[x][u << 1].r - tr[x][u << 1].l + 1) * tr[x][u].lazy;
tr[x][u << 1].lmx = (tr[x][u << 1].r - tr[x][u << 1].l + 1) * tr[x][u].lazy;
//处理右子树
tr[x][u << 1 | 1].val = (tr[x][u << 1 | 1].r - tr[x][u << 1 | 1].l + 1) * tr[x][u].lazy;
tr[x][u << 1 | 1].lmx = (tr[x][u << 1 | 1].r - tr[x][u << 1 | 1].l + 1) * tr[x][u].lazy;
//传递懒标记
tr[x][u << 1].lazy = tr[x][u].lazy;
tr[x][u << 1 | 1].lazy = tr[x][u].lazy;
//清除父节点懒标记
tr[x][u].lazy = -1;
}
}
void modify(int x, int u, int l, int r, int v)
{
if (tr[x][u].l >= l && tr[x][u].r <= r)
{
tr[x][u].val = (tr[x][u].r - tr[x][u].l + 1) * v;
tr[x][u].lmx = (tr[x][u].r - tr[x][u].l + 1) * v;
tr[x][u].lazy = v;
return;
}
pushdown(x, u);
int mid = tr[x][u].l + tr[x][u].r >> 1;
if (l <= mid) modify(x, u << 1, l, r, v);
if (r > mid) modify(x, u << 1 | 1, l, r, v);
//pushup操作
tr[x][u].val = tr[x][u << 1].val + tr[x][u << 1 | 1].val;//维护val即区间不可到达的数量
if (tr[x][u << 1].val == tr[x][u << 1].r - tr[x][u << 1].l + 1)//左子树区间全部不可到达
tr[x][u].lmx = tr[x][u << 1].val + tr[x][u << 1 | 1].lmx;//那么等于左区间尺寸加右区间不可达
else tr[x][u].lmx = tr[x][u << 1].lmx;//否则就直接等于左区间不可达
return;
}
int query(int x, int u, int l, int r)
{
if (tr[x][u].l == l && tr[x][u].r == r) return tr[x][u].lmx;//此区间完全包含查询区间
pushdown(x, u);
int mid = tr[x][u].l + tr[x][u].r >> 1;
if (r <= mid) return query(x, u << 1, l, r);
if (l > mid) return query(x, u << 1 | 1, l, r);
int temp = query(x, u << 1, l, mid);//查询左子树,左边全部到不了再查右子树
if (temp == mid - l + 1) return temp + query(x, u << 1 | 1, mid + 1, r);
else return temp;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> t;
while (t -- )
{
cin >> n >> m >> k;
build(0, 1, 1, m), build(1, 1, 1, m);//建立两棵线段树
for (int i = 0; i <= n + 10; i ++ ) mine[i].clear();//清空vector
int x, y;
for (int i = 1; i <= k; i ++ )
{
cin >> x >> y;
mine[x].push_back(y);
}
long long ans = 0;//储存不可到达的非地雷区域数目
modify(0, 1, 1, m, 1);//处理第0行,懒标记为1表示不可到达
for (int i = 1; i <= n; i ++ )//一行一行处理
{
sort(mine[i].begin(), mine[i].end());//将地雷按照纵坐标升序排列
mine[i].push_back(m + 1);//保证最后一个区间一定有右端点,加一个哨兵
int last = 0;//此行上一个雷的位置
modify((i & 1), 1, 1, m, 0);//清空线段树
for (int j = 0; j < mine[i].size(); j ++ )//遍历所有雷
{
int poi = mine[i][j];//雷的位置
if (i == 1 && !last) {last = poi; continue;}//处理第一行
int l = last + 1, r = poi - 1, len;//处理区间[l + 1, r - 1]
if (l <= r)
{
len = query((i & 1) ^ 1, 1, l, r);//查询上一行
ans += 1ll * len;
}
else len = 0;//否则此区间不存在不可到达的点
if (!(l - 1 == 0 && l - 1 + len == 0)) modify((i & 1), 1, l - 1, l - 1 + len, 1);//标记左侧的地雷
last = poi;//更新上一个地雷的位置
}
}
cout << 1ll * n * m - ans - 1ll * k << endl;
}
return 0;
}