专栏文章

题解：P12543 [APIO2025] 转杆

JJunounly
P12543题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8vvk6
此快照首次捕获于
2025/12/03 08:04
3 个月前
此快照最后确认于
2025/12/03 08:04
3 个月前
查看原文
不同于 std 的做法。
首先可以盯出一个结论：
  • ⌊n2⌋\big \lfloor \cfrac{n}{2} \big \rfloor 根线水平放置，⌈n2⌉\big \lceil \cfrac{n}{2} \big \rceil 根线竖直放置，一定是一种最优形态。
证明简单，调整法即可。
钦定 vi=0v_i=0 为 x\text{x} 轴，vi=25000v_i=25000 为 y\text{y} 轴，考虑如何做出最终形态。
我们将所有线分为以下几种：
  • 红线：平行于 x\text{x} 轴的线
  • 黑线：平行于 y\text{y} 轴的线
  • 蓝线：斜率为正数的线
  • 绿线：斜率为负数的线
记红线、黑线、蓝线、绿线的数量分别为 rd,bl,bu,grrd,bl,bu,gr。
请注意，一开始需要钦定没有红线和黑线，对于 viv_i 为 00 或 2500025000 的线，将它们钦定为蓝线或绿线。
称将一条蓝线或绿线转为黑线或红线的操作为校正。
在一开始没有红线和黑线的情况下，我们可以交替进行校正操作。
具体地，当 bl≤rdbl \le rd 时，可以将一条蓝线或绿线转为黑线；当 bl≥rdbl \ge rd 时，可以将一条蓝线或绿线转为红线，取等时的选择后面会用到。
在保证夹角和不降的情况下，最后一定有 ⌊n2⌋\big \lfloor \cfrac{n}{2} \big \rfloor 根红线和 ⌈n2⌉\big \lceil \cfrac{n}{2} \big \rceil 根黑线。
考虑怎么保证夹角和不降。
红线校正与黑线校正同理，这里只讨论黑线校正。
不失一般性地，我们钦定 bu≥grbu \ge gr，否则可以将整个图镜面翻转。
将斜率最大的蓝线转 θ\theta 的角度校正为黑线。
最劣情况下，这样做对总夹角和的贡献为 θ(bu−1+rd−bl−gr)\theta(bu-1+rd-bl-gr)。
这样做是对的当且仅当 bu−1+rd−bl−gr≥0bu-1+rd-bl-gr \ge 0，所以可以拿到 1111 分。
由于此时为黑线校正，bl≤rdbl \le rd，又有 bu≥grbu \ge gr。
不难得出仅在 bu=gr,bl=rdbu=gr,bl=rd 时有可能出现错误。
考虑这个局面怎么做。
不难发现这个局面有非常好的性质：
  • 对于一条线，将其旋转任意角度，红线和黑线对其夹角和的总贡献是不变的。
原因是红线黑线数量相同，且一条线与红线黑线的夹角和总为 90∘90^{\circ}。
因此只需考虑蓝绿线之间的夹角和变化。
可以同时转所有的蓝线和绿线，并进行一次校正，但这样花费太高了，只能拿到 7474 分。
刚才的做法启发我们转同样数量的蓝线和绿线。
具体地，我们可以同时转动斜率最大的蓝线和绿线各一根，角度为 θ\theta。
最劣情况下，对夹角和的贡献为 θ(bu−1−gr+1)+θ(gr−1−bu+1)=0\theta(bu-1-gr+1)+\theta(gr-1-bu+1)=0。
但上述式子有前提条件，即绿线不能变为蓝线，蓝线不能变为绿线。
这是好处理的，令斜率最大的蓝线与 y\text{y} 轴夹角为 θ1\theta_1，斜率最大的绿线与 x\text{x} 轴夹角为 θ2\theta_2，取 θ=min⁡{θ1,θ2}\theta=\min \{ \theta_1 , \theta_2 \} 即可。
由于此时黑线和红线数量相等，所以红线校正和黑线校正都是可行的。
每次花 11 或 22 的代价校正一条线，操作数不超过 2n2n。
根据上述分析模拟即可。
Code:
C
#include<bits/stdc++.h>
using namespace std;
void energy(int n,vector<int> v);
void rotate(vector<int> t,int x);
multiset<pair<int,int> > g,b;
void rotate_(int pos,int x)
{
    vector<int> t;
    t.emplace_back(pos);
    rotate(t,(x+50000)%50000);
}
void energy(int n,vector<int> v)
{
    int rd=0,bl=0,bu=0,gr=0;
    for(int i=0;i<n;i++)
    {
        int x=v[i];
        if(x<25000) bu++,b.emplace(x,i);
        else gr++,g.emplace(x,i);
    }
    for(;bu|gr;)
        if(bl<=rd)
        {
            if(bu==gr&&bl==rd)
            {
                vector<int> t;
                int x=(--b.end())->first,y=(--b.end())->second;
                int x_=(--g.end())->first,y_=(--g.end())->second;
                if(50000-x_<25000-x)
                {
                    int del=50000-x_;
                    t.emplace_back(y);t.emplace_back(y_);
                    rd++;
                    rotate(t,del);
                    g.erase(--g.end());gr--;
                    b.erase(--b.end());
                    v[y]=(v[y]+del)%50000;
                    if(v[y]==25000) bl++,bu--;
                    else b.emplace(v[y],y);
                }
                else
                {
                    int del=25000-x;
                    t.emplace_back(y);t.emplace_back(y_);
                    bl++;
                    rotate(t,del);
                    b.erase(--b.end());bu--;
                    g.erase(--g.end());
                    v[y_]=(v[y_]+del)%50000;
                    if(v[y_]==0) rd++,gr--;
                    else g.emplace(v[y_],y_);
                }
            }
            else if(bu>=gr)
            {
                int x=(--b.end())->first,y=(--b.end())->second;
                b.erase(--b.end());
                bu--;bl++;
                rotate_(y,25000-x);
            }
            else
            {
                int x=(g.begin())->first,y=(g.begin())->second;
                g.erase(g.begin());
                gr--;bl++;
                rotate_(y,25000-x);
            }
        }
        else
        {
            if(bu>=gr)
            {
                int x=(b.begin())->first,y=(b.begin())->second;
                b.erase(b.begin());
                bu--;rd++;
                rotate_(y,-x);
            }
            else
            {
                int x=(--g.end())->first,y=(--g.end())->second;
                g.erase(--g.end());
                gr--;rd++;
                rotate_(y,50000-x);
            }
        }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...