开心一点,快乐一点。
「启」

这是 ZR 国庆集训赠送的一场测试。貌似是从题库里面找的四道题组起来的,总体难度并不算难,做题的时候用数位板随便写写画画感觉很爽(

但是这篇是我在做完了题 \(10\) 天之后写的,所以只能说很简略的思路了(

下面的 Code 缺省源均为  「V5」.

「A」有趣的数

场上忘了防溢出w

「A」题目简述

求满足在 \(B_1\) 进制下位数为 \(D_1\),在 \(B_2\) 进制下位数为 \(D_2\) 的正整数的个数,规定大于 \(10^{18}\) 的数都是不合法的。

数据范围:\(2 \le B_1,B_2 \le 100,1 \le D1,D2 \le 20.\)

「A」思路简述

既然是考虑位数,那么显然是可以得到一个数的范围的。

那么最终的区间为 \([\max(b1^{d1-1},b2^{d2-1}),\min(b1^{d1}-1,b2^{d2}-1)]\),答案即为这个区间的长度。

但是要注意溢出,所以在写幂的加个判断。

「A」Code

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

template<typename J>
I J Hmin(const J &x,const J &y) {Heriko x<y?x:y;}

const LL LMT(1e18);

I LL FstPow(LL x,LL y)
{
    LL res(1);

    while(y)
    {
        if(y&1) res*=x;

        if(res>LMT or res<=0) Heriko LMT+1;

        y>>=1;

        if(y) x*=x;

        if(x>LMT or x<=0) Heriko LMT+1;
    }

    Heriko res;
}

LL d1,d2,b1,b2; 

S main()
{
    fr(b1),fr(d1),fr(b2),fr(d2);
    LL l1(FstPow(b1,d1-1)),r1(FstPow(b1,d1)-1),l2(FstPow(b2,d2-1)),r2(FstPow(b2,d2)-1);
    LL l(Hmax(l1,l2)),r(Hmin(r1,r2));
    fw(Hmax(r-l+1,0ll),1);

    Heriko Deltana;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
「B」木棒

场上暴力枚举(

「B」题目简述

\(T\) 次询问,每次询问给出 \(12\) 个正整数 \(l_i\),求问这些正整数最多可以组成多少个三角形(规定每个木棒只能用一次)。

数据范围:\(1 \le T \le 6000,1 \le l_i \le 10^9.\)

「B」思路简述

首先,暴力做法是显然的,爆搜就行。

当然我现在还不知道为什么我的爆搜代码是 \(55\) pts,错的点还都是 \(WA.\)

不过满分做法也是爆搜,只不过使用了状压略做优化。

「B」Code

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

CI MXX((1<<12)-1),NXX((1<<12)+1);

short f[NXX],now(1),T,vis[NXX];

int a[12];

I short DeltanaFerrariSF1000(int st)
{
    if(vis[st]==now or !st) Heriko f[st];

    short temp;f[st]=0,vis[st]=now;

    for(short i(0);i<12;++i)
        if((st>>i)&1) {temp=i;break;}

    f[st]=DeltanaFerrariSF1000(st^(1<<temp));

    for(short i(temp+1);i<12;++i)
        if((st>>i)&1)
            for(short j(i+1);j<12;++j)
                if((st>>j)&1 and a[temp]+a[i]>a[j])
                    f[st]=Hmax(f[st],(short)(1+DeltanaFerrariSF1000(st^(1<<temp)^(1<<i)^(1<<j))));
    
    Heriko f[st];
}

S main()
{
    Files();
    fr(T);

    for(;now<=T;++now)
    {
        for(int i(0);i<3;++i) fr(a[i]);
        for(int i(3);i<6;++i) fr(a[i]);
        for(int i(6);i<9;++i) fr(a[i]);
        for(int i(9);i<12;++i) fr(a[i]);

        sort(a,a+12);fw(DeltanaFerrariSF1000(MXX),1);
    }

    Heriko Deltana;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.

今天测试这个题的 Code 的时候,还被 OJ 干了。

我本来这个题是显示通过的,但是我交了一发之后(图一),给我显示不过了(图二)……

我寻思着就算我这次交的是最优解(图三和图四)也不至于把我踢出去正解列表啊(?)

而且我本来是第三优解来着,现在也没了(?)

我直接大异或,算是给正赛 + RP 了。

「C」装饰

我有病考场没开 long long \(100 \to 70.\)

「C」题目简述

给出一颗有 \(n\) 个节点的有根树,要求每个节点 \(x\) 以及它子树上的总装饰品数量至少为 \(C_x\),在每个结点上安装一个装饰品的时间为 \(T_x\),现在求满足所有结点的数量要求的最短时间。

「C」思路简述

我的思路很简单,因为本题之和父子关系有关,所以考虑用 DFS 解决问题。

考虑分成两个 DFS 去解决问题,第一个用来处理一些需要的数组,第二个计算答案。

我们贪心的去考虑如何满足每个结点的要求:

首先显然对于叶子结点,每个结点都要安装自己所需的最少的装饰物。那么再考虑非叶子结点,有两种情况:

  1. 其子树里的点已经满足了要求,不用管。

  2. 其子树里的点没有满足要求,那么乆从其子树中找到最小的 \(T\) 的结点把不够的补上即可,这个贪心显然是正确的。

「C」Code

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

template<typename J>
I J Hmin(const J &x,const J &y) {Heriko x<y?x:y;}

CI MXX(1e5+1);

int n;

LL c[MXX],t[MXX];

struct Node
{
    int nex,to;
}

r[MXX<<1];int cnt,head[MXX];

I void Add(int x,int y)
{
    r[++cnt]=(Node){head[x],y};head[x]=cnt;
    r[++cnt]=(Node){head[y],x};head[y]=cnt;
}

LL ans,mival[MXX],sum[MXX],ned[MXX];

void DFS1(int x,int fa)
{
    mival[x]=t[x],ned[x]=c[x];

    for(int i(head[x]);i;i=r[i].nex)
    {
        int y(r[i].to);

        if(y==fa) continue;

        DFS1(y,x);
        mival[x]=Hmin(mival[x],mival[y]);
        ned[x]=Hmax(ned[x],ned[y]);
    }
}

void DFS2(int x,int fa)
{
    for(int i(head[x]);i;i=r[i].nex)
    {
        int y(r[i].to);

        if(y==fa) continue;

        DFS2(y,x);
        sum[x]+=sum[y];
    }

    if(sum[x]<ned[x]) ans+=(mival[x]*(ned[x]-sum[x])),sum[x]=ned[x];
}

S main()
{
    Files();
    fr(n);
    int fa;fr(fa),fr(c[1]),fr(t[1]);

    for(int i(2);i<=n;++i) fr(fa),fr(c[i]),fr(t[i]),Add(i,fa);

    DFS1(1,0);DFS2(1,0);fw(ans,1);

    Heriko Deltana;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
「D」翻转硬币

场上没想出来啥

「D」题目简述

有一个长度为 \(n\)\(01\) 串 和一个整数 \(m\),求最小需要几次下列操作可以使得 \(01\) 串的前 \(n-m\) 位和后 \(n-m\) 位相同。

操作有两种:

翻转定义为 \(1\) 变为 \(0\)\(0\) 变为 \(1.\)

  • 将一个 \(1\) 翻转为 \(0\),或将一个 \(0\) 翻转为 \(1;\)

  • 将前 \(k \times m\) 位翻转。

数据范围:\(1 \le n,m\)

「D」思路简述

因为过去有一点久了我也不太记得了,所以可能有点短(

考虑分块 + DP,对于 \(m>\sqrt n\) 时暴力去做,否则去 DP.

「D」Code

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

template<typename J>
I J Hmin(const J &x,const J &y) {Heriko x<y?x:y;}

CI MXX(301);

int f[MXX][2],belong[MXX],sub[MXX][2],bn,a[MXX];

int n,m;

char s[MXX];

I void Div()
{
    for(int i(1);i<=n;++i) belong[i]=(i-1)/m+1;

    bn=belong[n];

    for(int i(1);i<=bn;++i) sub[i][0]=(i-1)*m+1,sub[i][1]=m*i;

    sub[bn][1]=Hmin(sub[bn][1],n);
}

#define lowbit(x) ((x)&(-x))

I int Cntone(int x) {int res(0);while(x) x-=lowbit(x),++res;Heriko res;}

I int F1()
{
    int res(0x3f3f3f3f);

    for(int st(0);st<(1<<bn);++st)
    {
        int cnt(0);

        for(int i(1);i<=n-m;++i) cnt+=(a[i]^(st>>(belong[i]-1)))^(a[i+m]^(st>>(belong[i+m]-1)));

        res=Hmin(res,cnt+Cntone(st));
    }

    Heriko res;
}

I int F2()
{
    int res(0x3f3f3f3f);

    for(int st(0);st<(1<<m);++st)
    {
        for(int i(1);i<=bn;++i)
        {
            int cnt[2]={0,0};

            for(int j(sub[i][0]);j<=sub[i][1];++j) ++cnt[a[j]^(st>>(j-sub[i][0])&1)];

            f[i][0]=Hmin(f[i-1][0]+cnt[1],f[i-1][1]+cnt[1]+1);
            f[i][1]=Hmin(f[i-1][1]+cnt[0],f[i-1][0]+cnt[0]+1);
        }
        
        res=Hmin(res,Hmin(f[bn][0],f[bn][1]+1));
    }

    Heriko res;
}

S main()
{
    Files();
    scanf("%s",s);fr(m);n=strlen(s);Div();

    for(int i(1);i<=n;++i) a[i]=s[i-1]-'0';

    m>sqrt(n)?fw(F1(),1):fw(F2(),1);
    
    Heriko Deltana;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
「末」

实际上最后几天想让自己保持一个好的心态,快乐点好。

Do you like WHAT YOU SEE ?