进了交大的 ACM 班，被分到了程设的 A 班。第一次作业被助教美名其曰全是“基础算法”，用来复健。于是写博客记录一下。

1664 卖果汁

题意：有 K(1≤K≤10)K(1\le K\le 10) 台榨汁机和 N(1≤N≤100)N(1\le N\le 100) 个客人，每位客人会点某种果汁(果汁种类 1≤xi≤201\le x _{i}\le 20)。如果有空的榨汁机或者有某台榨过这种果汁的榨汁机就可以直接用这台，否则就要重新找一台洗干净再榨。问知道每个客人的点单情况下最少洗几次榨汁机？

解析：经典贪心。对于每个客人，先找有没有榨过这种果汁的榨汁机，没有就找空的榨汁机。如果都没有，则需要考虑选一台洗掉。首先选择之后没有这种果汁的订单的榨汁机洗掉，如果没有的话就考虑下一次出现这种果汁订单最晚的那台洗。正确性也比较好证明，假设我们 KK 台榨汁机分别榨的果汁种类为 a1,a2⋯aKa _{1},a _{2}\cdots a _{K}，且下一次出现这种果汁订单的时间满足 a1≤a2≤⋯≤aKa _{1}\le a _{2}\le \cdots \le a _{K}，即 aKa _{K} 是下次出现最晚的那一台，那么我们需要选择这台洗掉。如果我们选择时间更早的榨汁机洗掉，比如 aK−1a _{K-1}，那么我们下次遇见 aK−1a _{K-1} 时就会洗一次，再到下次遇见 aKa _{K} 时可能又会多洗一次(因为这期间可能有其他的订单把 aKa _{K} 也洗掉了)；反之，如果我们先洗 aKa _{K}，那么我们直到下次遇见 aKa _{K} 时才需要洗一次。总而言之，先洗最晚的，那么下次时间排在前面的不用洗的订单就会更多，洗的次数就更少。

貌似还有一个状压 DP 的做法，设 fi,jf_{i,j} 代表处理了前 ii 个订单，目前榨汁机使用状态为 jj 时的最小洗涤次数。因为最多只有 2020 种果汁，状压成一个 2020 位的数，先把含有 KK 个 11 的数预处理出来，即 KK 台机器全被使用了的情况。接着先扫描订单直到把 KK 台占满，这就是初始化的状态，赋值为 00，即一次都还没洗，其他情况赋为极大值。接着扫描剩下的订单，对于每一个预处理好的状态，看看它有没有用榨汁机榨过这种果汁，如果有直接继承，否则就扫描它使用的榨汁机中找一个替换。即对于状态 SS，订单 aia _{i}，若 SS 的第 aia _{i} 位为 11，则 fi,S=min⁡(fi,S,fi−1,S)f _{i,S}=\min(f _{i,S},f _{i-1,S})，否则扫描 SS 的第 j(0≤j<20)j(0\le j< 20) 位，fi,S∪ai/j=min⁡(fi,S∪ai/j,fi−1,S+1)f _{i,S\cup a _{i}/j}=\min(f _{i,S\cup a _{i}/j},f _{i-1,S}+1)。可以用滚动数组把第一维优化掉，但时间复杂度要比贪心高很多。

代码：

//
// Created by 屋顶上的小丑 on 2022/9/22.
//
#include<cstdio>
using namespace std;
const int maxn=100,maxk=10;
int k,n,x[maxn+5],ans;
int v[maxk+5];
int main()
{
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)
    {
        bool flag=0;
        for(int j=1;j<=k;j++)
            if(v[j]==x[i])
            {
                flag=1;
                break;
            }
        if(!flag)
        {
            for(int j=1;j<=k;j++)
                if(!v[j])
                {
                    v[j]=x[i];
                    flag=1;
                    break;
                }
        }
        if(flag)
            continue;
        ans++;
        for(int j=1;j<=k;j++)
        {
            flag=1;
            for(int l=i+1;l<=n;l++)
                if(v[j]==x[l])
                {
                    flag=0;
                    break;
                }
            if(flag)
            {
                v[j]=x[i];
                break;
            }
        }
        if(flag)
            continue;
        int pos,tim=0;
        for(int j=1;j<=k;j++)
            for(int l=i+1;l<=n;l++)
                if(v[j]==x[l])
                {
                    if(tim<l)
                    {
                        tim=l;
                        pos=j;
                    }
                    break;
                }
        v[pos]=x[i];
    }
    printf("%d",ans);
    return 0;
}

1665 选员工

题意：nn 个人中选 mm 个人当员工，其中 kk 对人实力相当(中间可能有重复，即一个人可能出现在多对中)(1≤n,m,k≤2×1041\le n,m,k\le 2\times 10 ^{4})，问应该选多少人当员工，使得对于每一个实力，同一实力层级的人要么全部被选上要么全部不选，选出的人数和 mm 尽量接近。

解析：显然想到用并查集维护每一个实力层级，得出每个实力层级的人数，然后就转化成了一个 01 背包问题，相当于从一堆数中选出一些数，使他们的和与 mm 最接近，直接用 bitset 加速即可。或者把他看成多重背包解决，复杂度也能接受。

代码：

//
// Created by 屋顶上的小丑 on 2022/9/22.
//
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
const int maxn=2e4;
int n,m,k,ans;
int fa[maxn+5],siz[maxn+5];
int v[maxn+5],cnt;
bitset<maxn+5> f[2];
int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=getfa(x);
        y=getfa(y);
        if(x!=y)
        {
            fa[x]=y;
            siz[y]+=siz[x];
        }
    }
    for(int i=1;i<=n;i++)
        if(fa[i]==i)
            v[++cnt]=siz[i];
    int now=0;
    f[now][0]=f[now^1][0]=1;
    for(int i=1;i<=cnt;i++)
    {
        f[now]=f[now^1]|(f[now^1]<<v[i]);
        now^=1;
    }
    for(int i=1;i<=n;i++)
        if(f[now^1][i]&&abs(ans-m)>abs(i-m))
            ans=i;
    printf("%d",ans);
    return 0;
}

1669. 货运站点

题意：nn 个村庄，知道相邻村庄之间的距离 di(0<di≤100)d _{i}(0<d _{i}\le 100)，在 nn 个村庄中选 m(0<m≤n<500)m(0<m\le n<500) 个站点，使所有村庄到距离最近的站点的距离和最小，求出这个距离和。

解析：一道很经典的 DP。我们用 fi,jf _{i,j} 表示在前 ii 个村庄建立 jj 个货运站点的最小距离和，答案就是 fn,mf _{n,m}，初始化 f0,i=0f _{0,i}=0，其余赋成极大值。再用 sumi,jsum _{i,j} 代表从 ii 到 jj 这些村庄之间建立一个站点后这些村庄到这个站点的最小距离和，初始化也是 sumi,i=0sum _{i,i}=0，其余赋成极大值。根据贪心思想可以得出站点一定得建在最中间(即中位数的地方)，那么状态转移方程就是 fi,j=min⁡(fi,j,fk,j−1+sumk+1,i)f _{i,j}=\min(f _{i,j},f _{k,j-1}+sum _{k+1,i})。现在我们考虑如何求出 sumsum，容易得到，从 sumi,j−1sum _{i,j-1} 到 sumi,jsum _{i,j}，建立站点的位置并没有发生变化(假如原来有奇数个村庄，边上加入一个村庄后，站点位置还是在中间两个之一；假如原来有偶数个村庄，由于对称性可以知道站点建在中间两个任意一个都可以，我们不妨设它建在右边那个，那么右边加入新村庄后，站点仍然在正中间没有变)。因此我们只用考虑新加入村庄的距离，显然为 ⌊i+j2⌋\left\lfloor\dfrac{i+j}{2}\right\rfloor 到 jj 的距离，处理下 did _{i} 的前缀和就很好求出。即 sumi,j=min⁡(sumi,j,sumi,j−1+dis(⌊i+j2⌋,j))sum _{i,j}=\min(sum _{i,j},sum _{i,j-1}+dis(\left\lfloor\dfrac{i+j}{2}\right\rfloor,j))。

代码：

//
// Created by 屋顶上的小丑 on 2022/9/25.
//
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500;
int n,m,d[maxn+5],dis[maxn+5];
int sum[maxn+5][maxn+5];
int f[maxn+5][maxn+5];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&d[i]);
        dis[i]=dis[i-1]+d[i];
    }
    memset(sum,0x3f,sizeof(sum));
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        sum[i][i]=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            sum[i][j]=min(sum[i][j],sum[i][j-1]+dis[j]-dis[(i+j)/2]);
    for(int i=0;i<=m;i++)
        f[0][i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<i;k++)
                f[i][j]=min(f[i][j],f[k][j-1]+sum[k+1][i]);
    printf("%d",f[n][m]);
    return 0;
}

1685. 序列

题意：给一个长度为 nn 的数组，回答 Q(1≤n,Q≤5×105)Q(1\le n,Q\le 5\times 10 ^{5}) 次询问，每次输出区间 [l,r][l,r] 中恰好出现两次自然数的数量，满足数组元素小于 10910 ^{9}。

解析：这个题目看起来就很莫队，但是 5×1055\times 10 ^{5} 显然会卡，跑不过。不过还是能拿一半的分。正解选择用树状数组维护，先离散化一下，然后把询问存下来离线操作，从右往左像滑动窗口一样扫描每个询问，直接树状数组求和就是答案。重点在于如何修改。我们用 nexinex _{i} 表示数组 aa 中下一个与 aia _{i} 相同的数的下标，显然对于 ai,anexia _{i},a _{nex _{i}} 便是两个相同的自然数，那么对于 [nexi,nexnexi−1][nex _{i},nex _{nex _{i}}-1] 这个区间内，我们都要把贡献 +1+1， 区间操作在树状数组中可以通过差分转换成单点操作，求和时再前缀和加回去即是答案。不过注意在把 [nexi,nexnexi−1][nex _{i},nex _{nex _{i}}-1] 加上 11 后，要把 [nexnexi,nexnexnexi−1][nex _{nex _{i}},nex _{nex _{nex _{i}}}-1] 要减去 11。原因是在我们扫描到 ai,anexia _{i},a _{nex _{i}} 前，我们会先扫描到 anexi,anexnexia _{nex _{i}},a _{nex _{nex _{i}}}。在这里我们为了算贡献已经把 [nexnexi,nexnexnexi−1][nex _{nex _{i}},nex _{nex _{nex _{i}}}-1] 加了 11，所以在之后我们要减回去，保证统计的一直是出现两次的自然数的数量，否则就会把出现三次甚至多次的自然数也算上。

代码：

(莫队 50 pts)

//
// Created by 屋顶上的小丑 on 2022/9/22.
//
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=5e5;
int n,m,Q;
int a[maxn+5],b[maxn+5],c[maxn+5];
int num[maxn+5],ans[maxn+5],len;
int bl[maxn+5],tot;
struct ques
{
    int l;
    int r;
    int id;
}q[maxn+5];
inline bool cmp(ques x,ques y)
{
    if(bl[x.l]==bl[y.l])
    {
        if(bl[x.l]&1)
            return x.r<y.r;
        return x.r>y.r;
    }
    return x.l<y.l;
}
void add(int x)
{
    if(num[c[x]]==1)
        tot++;
    if(num[c[x]]==2)
        tot--;
    num[c[x]]++;
}
void del(int x)
{
    if(num[c[x]]==3)
        tot++;
    if(num[c[x]]==2)
        tot--;
    num[c[x]]--;
}
int main()
{
    scanf("%d%d",&n,&Q);
    len=n/sqrt(Q*2/3.0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
        bl[i]=(i-1)/len+1;
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        c[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+Q+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=Q;i++)
    {
        while(L<q[i].l)
            del(L++);
        while(L>q[i].l)
            add(--L);
        while(R>q[i].r)
            del(R--);
        while(R<q[i].r)
            add(++R);
        ans[q[i].id]=tot;
    }
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

(树状数组 100 pts)

//
// Created by 屋顶上的小丑 on 2022/9/22.
//
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e5;
int n,m,Q,nex[maxn+5],pos[maxn+5];
int a[maxn+5],b[maxn+5],c[maxn+5];
int tr[maxn+5],ans[maxn+5];
struct ques
{
    int l,r;
    int id;
}q[maxn+5];
inline bool cmp(ques x,ques y)
{
    return x.l>y.l;
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int val)
{
    if(!x)
        return ;
    for(int i=x;i<=n+1;i+=lowbit(i))
        tr[i]+=val;
}
inline int query(int x)
{
    int sum=0;
    for(int i=x;i;i^=lowbit(i))
        sum+=tr[i];
    return sum;
}
int main()
{
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        c[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=n;i>=1;i--)
    {
        nex[i]=pos[c[i]];
        pos[c[i]]=i;
    }
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+Q+1,cmp);
    int now=n;
    for(int i=1;i<=Q;i++)
    {
        int L=q[i].l,R=q[i].r;
        while(now>=L)
        {
            int nex1=nex[now],nex2=nex[nex1],nex3=nex[nex2];
            add(nex1,1);
            add(nex2,-2);
            add(nex3,1);
            now--;
        }
        ans[q[i].id]=query(R);
    }
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

1686. Magic Lamp（1）

咕咕咕