ZJ第九套总结

Author Avatar
Llf0703 10月 29, 2018
  • 在其它设备中阅读本文章

购物(shopping)

洛谷题目：P1658 购物

贪心水题。如果我们已经可以凑出 $ [1,n] $ 之间所有面值，那么携带 $ \forall x\in [1,n+1] $ 面值的硬币，我们一定可以凑出 $ [1,n+x] $ 之间所有面值。

要让硬币个数尽可能少，就让携带的每个硬币面值尽可能大，所以我们就在面值 $ \in [1,n+1] $ 的硬币中取最大的即可。

很容易想到，如果最小面值都 $ >1 $ 就肯定无解，输出 $ -1 $.

int s[15],n,m,x;

int main()
{
    x=read(); n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    if (s[1]>1)
    {
        printf("-1");
        return 0;
    }
    int can=1,ans=1;
    while (can<x)
    {
        int i=n;
        while (s[i]>can+1 && i>=2) i--;
        can+=s[i];
        ans++;
    }
    printf("%d",ans);
    return 0;
}

养猪(pig)

Vijos题目：养猪

还有个洛谷的双倍经验：P1987 摇钱树，只是多组数据

贪心+dp。贪心策略是按P从大到小排序，然后01背包决定杀不杀即可。贪心证明如下：

假设最初的顺序是 及

对于第 $ x $ 和第 $x+1$ 头猪，杀了它们获得的利益和 $ W1 $ 是

如果我们交换第 $ x $ 和第 $ x+1 $ 头猪，利益和 $ W2 $ 就变成了

肯定是有更多利益我们才会交换，所以需要满足

交换后就是 $ P[x]>P[x+1] $ 了，所以按照p从大到小排序。

剩下的就是标准01背包，由于数据不大，用不用滚动数组都可以。方程式是：

int n,k,f[1005][1005],ans;
struct pig{
    int a,p;
} s[1005];

inline bool cmp(pig x,pig y)
{
    return x.p>y.p;
}

int main()
{
    n=read(); k=read();
    if (k>n) k=n;
    for (int i=1;i<=n;i++) s[i].a=read();
    for (int i=1;i<=n;i++) s[i].p=read();
    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n;i++)
        for (int j=k;j;j--)
            f[i][j]=max(f[i-1][j-1]+max(0,s[i].a-s[i].p*(j-1)),f[i-1][j]);
    for (int i=1;i<=k;i++) ans=max(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

数位平方和(count)

洛谷题目：P1660 数位平方和

按题意记忆化DFS即可，需要记忆的就是h的值。

需要注意一定会出现环，当某一个值被搜索到第二次的时候返回即可。

ll k,a,b;
ll hh[4000005],vis[4000005];

inline ll _min(ll x,ll y)
{
    if (x<=y) return x;
    return y;
}

inline ll s(ll x)
{
    ll ans=0;
    while (x)
    {
        ll now=x%10,sum=1;
        for (ll i=1;i<=k;i++) sum*=now;
        ans+=sum;
        x/=10;
    }
    return ans;
}

inline ll h(ll x)
{
    if (hh[x]!=-1) return hh[x];
    if (vis[x]==2) return x;
    ll sx=s(x);
    vis[x]++;
    ll ans=_min(x,_min(sx,h(sx)));
    vis[x]--;
    return hh[x]=ans;
}

int main()
{
    k=read(); a=read(); b=read();
    ll ans=0;
    for (int i=1;i<=4000000;i++) hh[i]=-1;
    for (int i=a;i<=b;i++) ans=(ans+h(i))%ha;
    printf("%lld",ans);
    return 0;
}

扩散(ppg)

洛谷题目：P1661 扩散

看起来四周扩散很复杂，但扩散的次数实质上就是两个点的曼哈顿距离 $ \div 2 $ (向上取整)。所以只需要将没两个点之间连一条权值为 $ (|x1-x2|+|y1-y2|+1)\div 2 $ 的边跑最小生成树即可，答案就是最小生成树中的最长边。

struct point{
    int x,y;
} pt[55];
struct Edge{
    int st,ed,w;
} edge[2505];
int n,m,a,b,c,fa[55],cnt,ans;

inline void add(int u,int v,int w)
{
    edge[++cnt].st=u;
    edge[cnt].ed=v;
    edge[cnt].w=w;
}

inline void init()
{
    for (int i=1;i<=n;i++)
        fa[i]=i;
}

int getfa(int x)
{
    if (x==fa[x]) return fa[x];
    fa[x]=getfa(fa[x]);
    return fa[x];
}

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fa[gfx]=gfy;
    return 1;
}

inline bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}

inline void kruskal()
{
    for (int i=1;i<=cnt && n;i++)
    {
        int x=edge[i].st,y=edge[i].ed;
        if (merge(x,y))
        {
            n--;
            ans=max(ans,edge[i].w);
        }
    }
}

int main()
{
    n=read();
    init();
    for (int i=1;i<=n;i++) pt[i].x=read(),pt[i].y=read();
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            add(i,j,(abs(pt[i].x-pt[j].x)+abs(pt[i].y-pt[j].y)+1)>>1);
    sort(edge+1,edge+cnt+1,cmp);
    kruskal();
    printf("%d",ans);
    return 0;
}

总结

今天考的非常爆炸，第一题把样例看错了，发现怎么就是多了1，想都没想就把答案-1了(-100s)；第二题按p排了序，方程式也是对的，就是最后没有取最大值(-100s)；第三题知道有环，也写了记搜，但是每个点搜到第一次就返回了，只A了一个点(-90s)；第四题真的没想出来，打了20分暴力(-80s)。然后就把一手320的好牌打成30分。。。

所以我觉得我还应注意以下两点：

  1. 不管题再简单也要把样例推几遍，更不能一晃而过
  2. 需要非常熟练掌握基础的dp模型

以上。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-zj9.html