7.13 ACM 部分简要题解

Provicy · 2020-07-14 08:58:08 · 个人记录

A ：MUG

简要题意：

有一个音游，给出你每个键的掉落顺序和价值，你可以用左手或右手去点击键位并获得价值，并给出四个规则：1、左手不能连用；2、左手交叉到右手右边的价值会乘上 p1\%；3、右手交叉到左手左边的价值会乘上 p2\%；4、右手连用的价值会乘上 p3\%。你还可以放弃一些键不去点击。问最大价值是多少。

简要题解：

根据题意，左手和右手分别所处位置对答案无影响，只有它们的相对位置对答案有影响，所以我们不会连续放弃超过一个键。

显然可以用 dp 去解决这个问题。记 f_{i} 表示第 i 个键我们用左手点击的价值，g_{i} 表示第 i 个键我们用右手点击的价值，那么转移方程就很容易得出了（注意不要忘了某些情况），最终答案就是 max\{f_{n},g_{n}\}。

简要代码：

int n,s[N],t[N],p1,p2,p3,f[N],g[N];
signed main()
{
    n=read();
    for(ri int i=1;i<=n;i++) s[i]=read()/100;
    for(ri int i=1;i<=n;i++) t[i]=read();
    p1=read(), p2=read(), p3=read();
    f[1]=g[1]=s[1]*100;
    for(ri int i=2;i<=n;i++)
    {
        f[i]=max(f[i-1],s[i]*100+max(f[i-2],g[i-2]));//左手上一次不取或者这次不取
        g[i]=max(g[i-1]+s[i]*p3,s[i]*100+max(f[i-2],g[i-2]));//右手连按或上次不拿，这次可以完整的拿
        if(t[i-1]<t[i]) g[i]=max(f[i-1]+s[i]*100,g[i]), f[i]=max(f[i],g[i-1]+s[i]*p1);//这次按的键位在上次的右边，左手需要交叉按
        else if(t[i-1]>t[i]) f[i]=max(g[i-1]+s[i]*100,f[i]), g[i]=max(g[i],f[i-1]+s[i]*p2);//这次按的键位在上次的左边，右手需要交叉按
        else f[i]=max(g[i-1]+s[i]*100,f[i]), g[i]=max(g[i],f[i-1]+s[i]*100);//两个键位同个位置，不用交叉按
    }
    printf("%lld\n",max(f[n],g[n]));
    return 0;
}

B：Count Angles

简要题意：

问 n 条直线最多能组成多少同旁内角。

简要题解：

1、三条直线最多组成 6 对同旁内角，使得 n 条直线中每三条直线都能组成 6 对同旁内角，答案即为 6C_{n}^{3}。

2、笔算一下，直接 OEIS

简要代码

无

E：Grammy's Restaurant

简要题意：

给出 m 个区间和 n 组询问，每组询问给出 k 个点 a_{i}，求在区间 [l_{j},r_{j}] 中的所有点排序后，r_{j}-l_{j}+\sum i\times a_{i} 的最大值，此处 a_{i} 表示在该区间中的点已被从小到大排序。（本题中 n 与 m 同阶）

题解：

首先有个重要的结论：如果一个区间被另一个区间所包含，那么这个区间一定不会被选到。于是我们可以把所有被其他区间完全包含的区间去掉，并且把剩下的区间按左端点排序，这样就可以得到左右端点都严格递增的区间集合。

考虑把对于每组数据读入的 k 个点从小到大排序，这样就得到了一个数值序列。考虑选取一些连续的数，有多少区间能够覆盖全部这些数。我们可以记对于每个数值，最左边覆盖它的区间为 ql_{i}，最右边覆盖它的区间为 qr_{i}，则有区间能够覆盖一段连续的数值序列 [L,R] 的条件就是 ql_{R}\geq qr_{L}。现在考虑求出 ql_{i} 和 qr_{i}。

由于一开始的结论，所以我们可以对于每个 a_{i}，二分出不在 a_{i} 右侧的最大的 L_{j} 和 不在 a_{i} 左侧的最小的 R_{j}。当然，如果找不到这个 L 或 R，或者是找到了却没覆盖到这个点，那么可以记这个位置 ql_{i}=ql_{r}=-1。

暴力去枚举数值序列的每个 [L,R] 显然会超时，考虑优化。发现当我们固定左端点 L 时，如果 [L,R] 可以被区间所包含，则 [L,R-1] 也可以被区间所包含。所以我们可以对于每个 L 去二分 R 并找到最大值。查询若干个连续区间集合的 R_{j}-L_{j} 的最大值可以用线段树或 ST 表。这样的做法是 O(nlog^{2}n) 的，如果优化其中一些地方也可以做到 O(nlogn)。

这题可以固定左端点二分右端点，于是我们再考虑可不可以用双指针去解决它。考虑把右指针 R 一直向右移，直到不满足 ql_{R}>=qr_{L} 或出现 ql_{R}==-1 或 R 大于 m（此时 m 为已经预处理过后剩下的区间总数）为止，然后可以求出 [L,R-1] 这段数值序列的价值。然后再把左端点向右移，直到重新满足 ql_{R}>=qr_{L} 为止。然后去掉了一堆小错误之后 “愉快” WA on test 43。

经过了漫长的寻找 hack 数据之后，终于由 kqh 贡献了一组 hack 数据如下：

1 2
1 100 3 10000
4 1 4 5 10001

1 3
1 100 3 10000 9999 10002
4 1 4 5 10001

将上做法带入这组数据就会发现出了大问题。原因是当我们到 10001 这个数发现不满足与左端点被某一区间所覆盖时，我们就会把左端点一直右移到与这个右端点满足条件为止。这样就会忽略掉在 L 右移过程中 [L,R-1] 可能作为一种更优答案的情况。（该数据的图片可以在 kqh 的 题解 中观察）于是我们可以在左端点右移的过程中一直计算 [L,R-1] 这段数值序列的最大答案即可。

代码：

#include <bits/stdc++.h>
#define ri register
#define int long long
using namespace std; const int N=400010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch-'0'), ch=getchar(); return s*w;
}
int n,m,book[N],a[N],qz[N];
struct Edge{ int L,R,fg; }e[N];
inline bool cp(Edge x,Edge y) { return x.L==y.L?x.R>y.R:x.L<y.L; }
int sum[N<<2];
#define lc (x<<1)
#define rc (x<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int x) { sum[x]=max(sum[lc],sum[rc]); }
void Build(int x,int l,int r)
{
    if(l==r) { sum[x]=e[l].R-e[l].L; return; }
    Build(lc,l,mid), Build(rc,mid+1,r);
    Push_Up(x);
}
int Ask(int u,int v,int l,int r,int x)
{
    int res=0;
    if(l>=u&&r<=v) return sum[x];
    if(u<=mid) res=max(res,Ask(u,v,l,mid,lc));
    if(v>mid) res=max(res,Ask(u,v,mid+1,r,rc));
    return res;
}
struct Point { int ll,rr; }q[N];
signed main()
{
    n=read(), m=read();
    for(ri int i=1;i<=m;i++) e[i].L=read(), e[i].R=read();
    sort(e+1,e+1+m,cp); int mR=0;
    for(ri int i=1;i<=m;i++)
    {
        if(e[i].R<=mR) e[i].fg=1;
        else mR=max(mR,e[i].R);
    } int cntt=0;
    for(ri int i=1;i<=m;i++) if(!e[i].fg) e[++cntt]=e[i]; m=cntt;
    int fir=0;
    for(ri int i=1;i<=m;i++) fir=max(fir,e[i].R-e[i].L);
    Build(1,1,m);
    for(ri int T=1;T<=n;T++)
    {
        int ki=read(); int ans=fir;
        for(ri int i=1;i<=ki;i++) a[i]=read();
        sort(a+1,a+1+ki); qz[0]=0;
        for(ri int i=1;i<=ki;i++) qz[i]=qz[i-1]+a[i];
        for(ri int i=1;i<=ki;i++)
        {
            int l=1, r=m, res=-1;
            while(l<=r)
            {
                if(e[mid].L<=a[i]) res=mid, l=mid+1;
                else r=mid-1;
            }
            if(res==-1 || e[res].R<a[i]) q[i].ll=q[i].rr=-1;
            else q[i].ll=res;
            l=1, r=m, res=-1;
            while(l<=r)
            {
                if(e[mid].R>=a[i]) res=mid, r=mid-1;
                else l=mid+1;
            }
            if(res==-1 || e[res].L>a[i]) q[i].ll=q[i].rr=-1;
            else q[i].rr=res;   
        }
        int ql,qr; ql=qr=1; int now=0;
        for(ri int i=1;i<=ki;i++) swap(q[i].ll,q[i].rr);
        while(ql<=ki && qr<=ki)
        {
            if(q[qr].ll==-1 || q[qr].rr==-1) { ql=qr=qr+1; now=0; continue; }
            while(qr<=ki && q[ql].rr>=q[qr].ll&& q[qr].ll != -1) now+=(qr-ql+1)*a[qr], qr++;
            ans=max(ans,Ask(q[qr-1].ll,q[ql].rr,1,m,1)+now);
            if(q[qr].ll == -1 || q[qr].rr==-1 )
            {
                qr--;
                while(ql<=qr) ans=max(ans,Ask(q[qr].ll,q[ql].rr,1,m,1)+now), now-=qz[qr]-qz[ql-1], ql++;
                qr++; ql=qr=qr+1;
            }
            else
            {
                while(ql<=ki && q[ql].rr<q[qr].ll) now-=qz[qr-1]-qz[ql-1], ql++, ans=max(ans,now+Ask(q[qr-1].ll,q[ql].rr,1,m,1));
            }
        }
        for(ri int i=1;i<=ki;i++) q[i].ll=q[i].rr=qz[i]=0;
        printf("%lld\n",ans);
    }
    return 0;
}

F： Balloons Tower Defence

简要题意：

一个平面上有 n 个点，你可以在平面上划一条直线，问能否至少经过 n*(p\%) 个点（即向上取整）。(20\leq p \leq 100)

简要题解：

考虑随机化。可以随机 rand 一个点，计算这个点与其他所有点的斜率并记录斜率相同的数最多有多少。由于 p\geq20，于是期望每次 rand 都有 20\% 的概率能得到正确答案，于是正确率就比较高了。

还有一种做法就是每次 rand 两个点，算在这两点直线上的点有多少。

简要代码：

#include <bits/stdc++.h>
#define ri register
#define inf 0x7fffffff
#define E (1)
#define mk make_pair
#define int long long
using namespace std; const int N=1000010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;
}
double n,p,res,g; unordered_map<double,int> Q;
struct Edge{double x,y; }e[N];
signed main()
{
    scanf("%lf%lf",&n,&p);
    g=ceil(1.0*n/100*p);
    for(ri int i=1;i<=n;i++) scanf("%lf%lf",&e[i].x,&e[i].y);
    srand(time(NULL));
    int now=rand()*rand()%((int)n)+1; res=0;
    for(ri int i=1;i<=n;i++)
    {
        double qwq=(e[i].y-e[now].y)/(e[i].x-e[now].x);
        Q[qwq]++; int ty=Q[qwq];
        res=res<ty?ty:res;
    }
    if(res+1>=g) { puts("possible"); return 0; }
    clock_t tb=clock(),lm=clock();
    while(((double)tb)/CLOCKS_PER_SEC < 0.95-((double)lm)/CLOCKS_PER_SEC)
    {
        now=rand()*rand()%((int)n)+1; Q.clear(); res=0;
        for(ri int i=1;i<=n;i++)
        {
            double qwq=(e[i].y-e[now].y)/(e[i].x-e[now].x);
            Q[qwq]++; int ty=Q[qwq];
            res=res<ty?ty:res;
        }
        if(res+1>=g) { puts("possible"); return 0; }
        tb=clock();
    }
    puts("impossible");
    return 0;
}