Difference Array
算法本质
（数学）思维
题目大意
给定长度n的不减数组a[]，进行n-1轮以下操作：
- 将自身赋值为其差分数组（会使得其长度-1）
- 重新排序（维持不减）
输出最后a[]剩余的唯一数字。
n <= 1e5
a[] <= 5e5思路推演
对着规则稍加模拟，并没有发现什么核心规律。
但是元素值的范围给的很不错，于是开始向这个方向思考。
模拟过程中可以发现，通常情况来说，元素的值在操作时会降低的十分快，目前没有跑满的情况。
这大概率有所问题。
笔者思考到这后，没有想到之后的运用
这实际上其核心在于种类有限。
若当前有n个不同元素，希望下一轮的元素没有重复的，则当前元素的最大值应该是n^2级别。
所以在经过第一次处理后，不同元素的种类至多有sqrt(5e5)个。
如果我们可以对重复元素做出处理，加速计算过程，则可以直接暴力通过该题。
对重复元素加速处理的方式有很多，其中用map会好写一些（看代码）。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
void f(map<int, int> &mp1)
{
map<int, int> mp2;
for (auto it=mp1.begin(); it!=mp1.end(); it++)
{
int val=it->first, num=it->second;
if (num>1) // 避免出现数目为0的情况
mp2[0] += num-1; // 计算重复的元素（加速计算）
auto it2 = next(it);
if (it2!=mp1.end())
mp2[it2->first - val]++;
}
mp1 = mp2;
}
inline void solve()
{
cin>>n;
map<int, int> mp;
for (int i=1; i<=n; i++)
mp[in()]++;
n--;
while (n--)
f(mp);
cout<<mp.begin()->first<<endl;
return;
}DFS Trees
算法本质
思维
题目大意
给定无向、联通、无重边的图，其中边权按边给出的下标顺序增加。
Alice希望得到最小生成树的图，但她写了一个错误代码：
bool vis[maxn];
void dfs(int u):
v：根据u周边的边权按升序遍历
if (vis[v])
将u-v放入有效边集合
dfs(v)
最后得到的边集合就是Alice认为的最小生成树的图现在请告诉Alice使用这段错误代码从哪些点开始可以得到正确图，哪些点不可行。
思路推演
由于没有相等权值的边，所以最小生成树的图是唯一的。
可以知道图中存在一些违规边。
核心就在于违规边对整体产生影响：
- 对于任意一条违规边a--b
可以先将所有点视作白色，a--b在最小树上的路径点被染成黑色，黑色点可以不路过a/b点可以抵达的点被染成灰色。 - 在所有违规边中，都为白色的点，就是最后的可行点
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
省略了dsu和LCA板子
vector<pair<int,int>> die; // 记录被删除的边
int val[maxn];
vector <int> g[maxn]; // 注意这里替换g[]
void f(int u, int fr=0)
{
val[u] += val[fr];
for (int v:g[u])
{
if (v==fr) continue;
f(v, u);
}
}
inline void solve()
{
cin>>n>>m;
DSU dsu(n);
for (int i=1; i<=m; i++)
{
int u=in(), v=in();
if (dsu.same(u, v)) // 这里实际上是一个Kruskal，但是由于其边的权值给的十分规律，所以可以直接处理
die.push_back({u, v});
else
g[u].push_back(v), g[v].push_back(u), dsu.merge(u, v);
}
dfs(1); // LCA处理
init_up();
for (auto [u, v] : die)
{
if (u==v) continue;
if (deep[u] < deep[v]) swap(u, v);
int zu = find_zu(u, v);
if (zu!=v)
{
val[1]++;
val[u]--;
val[v]--;
}
else
{
int cha = deep[u] - deep[v];
int sonv = u;
swim(sonv, cha-1);
val[sonv]++;
val[u]--;
}
}
f(1);
for (int i=1; i<=n; i++)
cout<<(val[i]==0 ? 1 : 0);
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)