一剑，一念。
You Are So Beautiful
算法本质
思维
题目大意
定义数组a[]中美丽子数组：
a[]有且仅有一个子序列与其相等
给定长度n的数组a[]，计数其美丽子数组。
思路推演
模拟：
3 2 1 2 3 1比如其中3 2 1是一种显然不美丽的情况，因为1之后存在1。
考虑是否所有数字都要满足身后没有重复的数字。
进一步思考，发现对于3 2 1来说，需要保证1是最后一次出现、3是第一次出现。
遍历拿下。
Dances (Hard Version)
算法本质
思维
题目大意
给定长度n的数组a[] b[]，会进行m轮游戏，输出每轮游戏得到值的和。
其中仅a[1]在第i轮游戏的值为i，其他信息每轮游戏不会改变。
每轮游戏规则：
玩家希望顺序执行以下操作，使得最后对于任意i来说都满足a[i]<b[i]：
- 玩家删除
k个a[]的元素和k个b[]的元素 - 玩家改变
a[]或者b[]元素顺序
每轮游戏得到的值是最小化的k。
n m <= 2e5
k <= n
元素值 <= 1e9思路推演
首先思考每轮游戏如何处理。（即easy版本）
显然在排序后，每个删除都会是删除a[]最大值、b[]最小值（最优删除）。
那什么时候才算合法，举例：
a[]: 1 2 3 4 5 6 7
b[]: 1 1 2 2 3 3 4按照最优删除处理，至少也得删除两次，使得b[1]>a[1]，如此一来，其实我们可以用连线来表示两者的关系。
对于a[i]来说，其连线对象是b[]中大于a[i]且没有被占用的最小值。
k显然是没有相连的元素个数。
接着思考多轮游戏会如何变化。
如果我们仅改变一个值，实际上对游戏的影响并不大。
首先时候a[2~n]和b[]制作连线图，然后观察b[]未被连线的最大元素，若a[1]的值小于这个最大元素，则可以视作两者相连，反之则可以记作没有相连的元素。
这里是一个贪心思路，可能需要仔细思考一下
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>m;
vector<int> a, b;
a.push_back(2e9); // 这里可以给一个无限大或者不给
for (int i=2; i<=n; i++)
a.push_back(in());
for (int i=1; i<=n; i++)
b.push_back(in());
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// 排序后将其放入双端队列中，需要其取前、取后的功能
for (int x:a)
dqa.push_back(x);
for (int x:b)
dqb.push_back(x);
vector<int> sheng; // 记录b[]中没有被占线的元素
int res=0; // 记录删除元素个数
while (1)
{
int x=dqa.front();
while (dqa.size() && dqb.front()<=dqa.front()) // 如果不合法，则需要删除元素，使用最优删除操作
{
sheng.push_back(dqb.front());
dqa.pop_back(), dqb.pop_front(), res++;
}
if (dqa.size()==0) // 说明已经合法了
break;
dqa.pop_front();
dqb.pop_front();
}
int top = sheng.back(); // 找到b[]中没有占线元素的最大值
int ans=0;
int p=min(top-1, m);
ans += p * (res-1); // a[1] = 1~p，其k值是res-1
ans += (m-p) * res; // a[1] = p+1~m，其k值是res
cout<<ans<<endl;
return;
}Time Travel
算法本质
思维、模拟
题目大意（抽象）
存在n个点m条无向边，但是m条边分布在t张图中。
在这场旅行中一共有k天，玩家希望从点1走至点n，当玩家处于第i天时，仅能使用第a[i]张图的边进行移动。
为了方便理解，我们可以视作玩家仅能在白天行动，在第0天的傍晚玩家处于点1处、接着休息了一晚上，第1天清晨仍然处于点1且准备行动。
玩家每天行动至多一条边（可以不动）。
输出抵达点n的天数（通常来说是傍晚抵达的），或者告知k天内无法抵达。
n m k <= 2e5思路推演
刚开始看，觉得像传说中的分层图，但是转念一想，cf不会这样出的
最短路思想，用dj即可解决。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<pair<int,int>> g[maxn]; // {w, v}
inline void solve()
{
int t;
cin>>n>>t;
for (int i=1; i<=t; i++)
{
cin>>m;
while (m--)
{
int u, v;
cin>>u>>v;
g[u].push_back({i, v}); // i表示第i张图的边
g[v].push_back({i, u});
}
}
cin>>k;
vector<vector<int>> cod(t+5); // cod[x] = {a, b, c}表示第x张图会在第a、b、c天出现
for (int i=1; i<=k; i++)
cod[in()].push_back(i);
vector<int> dis(n+5, 1e18), vis(n+5); // 最短路结构
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> q;
q.push({0, 1}); // 第0天傍晚抵达点1
dis[1] = 0;
while (q.size())
{
auto [t, u] = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [w, v]:g[u])
{
auto it = lower_bound(cod[w].begin(), cod[w].end(), t+1); // 第二天清晨，需要w>=t+1
if (it==cod[w].end()) continue;
int nt = *it; // 在nt的傍晚抵达点v
if (nt < dis[v])
{
dis[v] = nt;
q.push({dis[v], v});
}
}
}
int ans = (dis[n]<=k ? dis[n] : -1);
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)