D.More Wrong
算法本质
思维
题目大意
存在一个固定的未知长度n排序p[]，现在有5n*n硬币，可以进行操作：
- 选择
l r，花费(r-l)^2硬币，获得p[l~r]的逆序对
通过交互，最后输出p[]最大值的下标。
思路推演
这类交互题的核心在于，如何用相对固定、巧妙的方式，去获得信息。
现在需要求得最大值的下标，一种常见的贪心做法是，将数组二分划治，来减少花费，接下来需要验证思路是否可行。
对于2个相邻的值而言，仅需判断他们之间的逆序对即可判断谁大谁小。
但若对于2个不相邻的元素，如何判断。
如果思考无果，可以从硬币数重新思考，若要判断两者的大小，至少需要两者距离平方的硬币。
考虑最大情况，近似2的等比公式求和，答案需要2n^2^的硬币，所以这里大致允许2次逆序对，再额外来点常数。
稍加模拟即可判断出，使用[l, r-1]和[l, r]的询问，可以求得p[l~r-1]中大于p[r]的个数，即可判断p[l]和p[r]孰大。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int ask(int l, int r)
{
if (l==r) return 0;
cout<<"? "<<l<<" "<<r<<endl;
return in();
}
int dfs(int l, int r)
{
if (l==r) return l;
int mid = (l+r)/2;
int p1=dfs(l, mid), p2=dfs(mid+1, r);
int x1 = ask(p1, p2);
int x2 = ask(p1, p2-1);
return x1-x2>0 ? p1 : p2;
}
inline void solve()
{
cin>>n;
int p = dfs(1, n);
cout<<"! "<<p<<endl;
return;
}E1.PermuTree (easy version)
算法本质
思维
题目大意
给定一棵树，每个点的权值由玩家决定，需要满足：
- 点权的集合是一个排列
对于一对点，若其满足：
- 其两点的lca点值，处于两点值中间（不准相等）
则贡献+1。
输出最大化的贡献值。
思路推演
显然我们应该以每个顶点为lca进行思考，这时面对的一个问题就是：能否控制顶点下的所有其他点，任意调配其值大于或小于顶点，且不干扰之前点为lca点的判断。
简单模拟和推理后发现可行，则整个题就变成了贪心地对待每个lca点，其可以转移题意为：
- 所有除了根节点的节点都涂上黑色或者白色，任意一对点不在同一子树，则可以视为贡献+1，计算最大贡献值。
但是现在面临若干个子树（可以视作n/2个），每个子树有若干种选择（可以视作n/2种），而合起来则有许多种情况，显然无法计算，还需要一些贪心的思路优化复杂度。
一个朴素的想法是，是否一个子树中全黑或者全白为最优解。
证：
设某条子树有n个点，其中x个点涂白，n-x点涂黑。
设其他子树有a个白点、b个黑点。
则当前子树的贡献化简后是（这里未除常数2）：a*n + (b-a)*x x范围[0, n]
其中n固定，a b会随着外界的情况变化，但是可见x=0或者x=n是最优解之一。现在得证其为全黑或全白，看似有2^n^次方种选择，但是实际上其特征可以合并，可以视作背包问题，由于其棋子数目的限制，可以在O(n)的时间复杂度下求得整体可以取多少黑子和白子，而目前黑子和白子不可能同属于一个子树，就可以整体相乘了——背包求得后，遍历算出最大贡献即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int fu[maxn], cnt[maxn]; // 记录父节点
vector<int> g[maxn];
int ans;
void dfs(int u=1)
{
cnt[u] = 1; // 包括当前节点的节点数
vector<int> son; // 记录各个儿子节点的数目
for (int v:g[u])
{
dfs(v);
cnt[u] += cnt[v];
son.push_back(cnt[v]);
}
vector<int> dp(cnt[u]); // 建立背包dp
dp[0] = 1; // 全涂
for (int x:son)
{
for (int i=cnt[u]-1; i>=x; i--)
dp[i] |= dp[i-x];
}
int num=0;
for (int i=0; i<=cnt[u]-1; i++)
{
if (dp[i] && i*(cnt[u]-1-i) > num*(cnt[u]-1-num))
num = i;
}
ans += num * (cnt[u]-1-num);
}
inline void solve()
{
cin>>n;
ans=0;
for (int i=2; i<=n; i++)
{
cin>>fu[i];
g[fu[i]].push_back(i);
}
dfs();
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)