一些杂题【2022-07-16 更新】

Presentation_Emitter · 2022-01-13 16:17:53 · 个人记录

大致按照难度排序。

“自评难度”与当时状态存在一定关联，仅供参考。

ARC103A /\/\/\/

来源：AtCoder
难度：826,绿
自评难度：5,灰

放这题只是为了凑齐 ARC103 的 4 题。

Code:

ll n,v[100005],cnt[100005],a1,as1,a2,as2,t1,ts1,t2,ts2;
int main()
{
    n=rd();for(int i=1;i<=n;++i)v[i]=rd();
    clr(cnt,100001);
    for(int i=1;i<=n;i+=2)++cnt[v[i]];
    for(int i=1;i<=100000;++i)
    {
        if(cnt[i]>cnt[a1])as1=a1,a1=i;
        else if(cnt[i]>cnt[as1])as1=i;
    }
    t1=cnt[a1];ts1=cnt[as1];
    clr(cnt,100001);
    for(int i=2;i<=n;i+=2)++cnt[v[i]];
    for(int i=1;i<=100000;++i)
    {
        if(cnt[i]>cnt[a2])as2=a2,a2=i;
        else if(cnt[i]>cnt[as2])as2=i;
    }
    t2=cnt[a2];ts2=cnt[as2];
    if(a1^a2)prt(n-t1-t2);
    else prt(umin(n-t1-ts2,n-ts1-t2));
    ret 0;
}

IMO2019T5

来源：IMO
难度：无
自评难度：1.00

这种题对 OIer 来说还是水了点（

虽说 Atziluth 特别菜，给的证明不一定严谨什么的（

(a) 证明：

不妨设当前硬币正面朝上的位置集合为 S。此时 S 中必然存在至少一枚硬币为从左往右第 |S| 个硬币或其右侧的硬币。

接下来在从左往右第 |S| 个硬币上放置一个标记。不难发现下一次操作必然在标记对应的硬币上执行。

• 若标记对应的硬币正面朝上，则将其翻面后标记左移；
• 若标记对应的硬币反面朝上，则将其翻面后标记右移。

容易发现经过若干次操作后，标记会回到原位，同时原序列中正面朝上的数量会减少 1，即对于所有非空的 S 都能在若干次操作后到达一个 S' 满足 |S'|=|S|-1 。即所有 S 都能在若干次操作后到达 \varnothing。\Box

(b)

记标记从一个位置向右移直到将一个正面翻为翻面并最后回到出发点为一轮过程。设当前存在 k 枚硬币为正面，第 k 枚硬币右侧（包括第 k 枚本身）的第一枚正面朝上的硬币位置为 p，则这一轮过程的操作次数为 2p-2k+1。将其拆为 2p-1 与 -(2k-2) 并分别求期望：

代入得：

ARC139B Make N

来源：AtCoder
难度：1719,蓝
自评难度：400,棕

根号分治入门题，对性价比高的物品的体积分治即可。

蓝和蓝不能一概而论，我曾经在极端愤怒的情况下……被 Ring MST 吊着打。

Code:

ll T,n,a,b,x,y,z;cst ll lim=31000;
int main()
{
    T=rd();
    while(T --> 0)
    {
        n=rd();a=rd();b=rd();x=rd();y=rd();z=rd();ll ans=n*x;
        tomin(y,a*x);tomin(z,b*x);
        if(z*a>y*b)swap(a,b),swap(y,z);
        //cerr<<1<<' '<<x<<' '<<a<<' '<<y<<' '<<b<<' '<<z<<endl;
        if(b>=lim)for(ll i=0;i<=n;i+=b)tomin(ans,i/b*z+(n-i)/a*y+(n-i)%a*x);
        else for(ll i=0;i<=umin(a*b-a,n);i+=a)tomin(ans,i/a*y+(n-i)/b*z+(n-i)%b*x);
        prt(ans);
    }
    ret 0;
}

AGC030C Coloring Torus

来源：AtCoder
难度：3207,Cu
自评难度：1200,青