G2020寒假训练赛2

信息学——模拟赛

---

T1. TIME IS MOONEY

考虑$DP$

设：$f[i][x]$表示第$i$天到达城市$x$的最大收益

则容易得出：

$$f[i][x]=\max_{\text{y为x的前继}}(f[i-1][y]+w[x])$$

由于$y$为$x$的前继，所以考虑建反向边。

答案为：

$$Answer=\max(f[i][1]-c*i*i)$$

那么最后只需确定$i$的范围即可。

令$C$取最小值$1$,点权$w_i$均为最大值$1000$

则此时$i$取最大值$1000$。

所以可得$i<=1000$

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m,c;
int w[1005];
struct node{
    int v,nex;
}edge[4005];
int head[1005],len,f[1005][1005],ans;
inline void make_map(int u,int v)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    head[u]=len;
}
int main(){
    n=read(),m=read(),c=read();
    for (register int i=1;i<=n;++i)
        w[i]=read();
    for (register int i=1;i<=m;++i) 
        {
        int u=read(),v=read();
        make_map(v,u);
        }
    memset(f,-0x7f,sizeof(f)); 
    f[0][1]=0;
    for (register int i=1;i<=1000;++i)
        {
        for (register int x=1;x<=n;++x)
            for (register int j=head[x];j;j=edge[j].nex)
                {
                int y=edge[j].v;
                if (f[i-1][y]>=0)
                   f[i][x]=max(f[i][x],f[i-1][y]+w[x]);
                }
        ans=max(ans,f[i][1]-c*i*i);
        }
    printf("%d",ans);
    return 0;
}

T2. FARMER JOHN SOLVES 3SUM

因为$n$只有$5000$，而询问$q$很大有$10^5$。

可以考虑离线算法。

设$f[i][j]$表示$i$到$j$的范围内，有多少个$k\in(i,j)$使得$a[i]+a[j]+a[k]=0$。

我们枚举$i$,$j$。

由于$(i,j)$与$(i,j+1)$之间只多了一个数。

所以考虑对于每个$i$开个桶，每次将当前的$j$丢到桶里去。

那么我们就可以用$O(n^2)$的时间预处出所有$f[i][j]$。

我们对$f[i][j]$做二维前缀和，记作$sum[i][j]$。

那么询问相当于就是要求以$(l,l)$为左下角，以$(r,r)$为右上角的矩阵和。

那么直接容斥一下就好了。

还有一个地方需要注意，由于$a[i]$可能有负数，所有需要先加一个$INF$，才能开桶，处理一下就好。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const int INF=1e6;
int n,q;
int a[5005],cnt[2000005];
long long f[5005][5005];
int main(){
    n=read(),q=read();
    for (register int i=1;i<=n;++i)
        a[i]=read(),a[i]+=INF;
    for (register int i=1;i<=n;++i)
        {
        for (register int j=i+1;j<=n;++j)
            {
            if (j>i+1&&a[i]+a[j]<=3*INF&&a[i]+a[j]>=INF)
               f[i][j]=cnt[3*INF-a[i]-a[j]];
            cnt[a[j]]++;
            }
        for (register int j=i+1;j<=n;++j)
            cnt[a[j]]--;
        }
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    while (q--)
          {
          int l=read(),r=read();
          printf("%lld\n",f[r][r]-f[l-1][r]-f[r][l-1]+f[l-1][l-1]);
          }
    return 0;
}

T3. SPRINGBOARDS

考虑$dp$。

为了方便，我们先加上两个跳板。

第$0$个跳板$(0,0)->(0,0)$

第$m+1$个跳板$(n,n)->(n,n)$

设：$f[i]$为走到第$i$个跳板，所花费的最小代价。

则：

$$f[i]=\min_{cj<=a_i,d_j<=b_i}(f[j]+a_i+b_i-c_j-d_j)$$

这样的话时间复杂度是$O(m^2)$的。

考虑拿树状数组维护$f[j]-c_j-d_j$。

则时间复杂度降到$O(mlogm)$，可过。

注意数据较大，需要对$a[i].y$进行离散化。

//The code is from dxbdly
#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int x,y,b,id;
}a[200005];
int ls[200005],tot,len,c[200005],f[200005];
inline bool operator <(node x,node y)
{
    return x.x!=y.x?x.x<y.x:x.y<y.y;
}
inline int lowbit(int x)
{
    return x & (-x);
}
inline void update(int x,int num)
{
    while (x<=tot)
          c[x]=min(c[x],num),x+=lowbit(x);
}
inline int query(int x)
{
    int minn=INF;
    while (x)
          minn=min(minn,c[x]),x-=lowbit(x);
    return minn;
}
int main(){
    n=read(),m=read();
    ls[++tot]=0,ls[++tot]=n,a[++len]=(node){0,0,0,0},a[++len]=(node){n,n,1,m+1};
    for (register int i=1;i<=m;++i)
        {
        int x1=read(),y1=read(),x2=read(),y2=read();
        ls[++tot]=y1,ls[++tot]=y2;
        a[++len]=(node){x1,y1,1,i},a[++len]=(node){x2,y2,0,i};
        }
    sort(ls+1,ls+tot+1);
    int cnt=unique(ls+1,ls+tot+1)-ls-1;
    for (register int i=1;i<=len;++i)
        a[i].y=lower_bound(ls+1,ls+cnt+1,a[i].y)-ls;
    sort(a+1,a+len+1);
    for (register int i=1;i<=tot;++i)
        c[i]=INF;
    for (register int i=1;i<=len;++i)
        {
        if (a[i].b)
           f[a[i].id]=query(a[i].y)+a[i].x+ls[a[i].y];
        else
           update(a[i].y,f[a[i].id]-a[i].x-ls[a[i].y]);
        }
    printf("%d",f[m+1]);
    return 0;
}