@happyforever 2018-10-30T13:32:12.000000Z 字数 8437 阅读 502

10.25晚上解题报告

清北学堂 解题报告

图片.png

各题状况

期望得分： $100+100+10$
实际得分： $100+100+10$

T1

智尚锁
智商下线
降智打击
$O(1)$ 神题
特判想了 $1h+$
~~wby还写了个证明。。。~~

T2

单调性神题。
最开始Two Point的暴力写挂了，调了二十来分钟放弃掉重新写了一份近似 $O(n^3)$ 的暴力
正解敲了 $1h$ 左右

T3

不知道为啥大样例 $RE$ 。。。
很难受
只有白送的 $10$ 分

题目及考场代码

图片.png

/*
 * qndyd
 * https://blog.csdn.net/queuelovestack/article/details/52571408
 */
#include <cstdio>
int main()
{
    freopen("lock.in","r",stdin);
    freopen("lock.out","w",stdout);
    long long L,R;
    scanf("%lld%lld",&L,&R);
    if(!L)L++;
    if(!R)R++;
    if(R-L>=2)
        printf("%lld",(R-L)/2+1);
    else
        if(L==R)
        {
            if(L==1)
                puts("0");
            else
                if(L==2)
                        puts("1");
                else    puts("2");
        }
        else
        {
            if(L==1&&R==2)
                puts("1");
            else    puts("2");
        }
    fclose(stdin),fclose(stdout);
    return 0;
}

T2

图片.png

/*
 * https://blog.csdn.net/qq_37920580/article/details/78025341
 * 清北日常原题。。。
 *
 * 对每个点都求出以它为起点（或者是终点）的 长度不大于d的区间和
 * 考虑贪心,除非是无法使长度达到d,否则是一定要删掉长度为d的区间的
 * 那么我们的问题就在于：如何能够在一段区间内快速寻找到长度为d的和最大的子区间
 *
 * 首先预处理出前缀和sum
 * 那么对于每个点k为终点的长度不大于d的子区间
 * 在1<=k<=d时子区间和为sum[k]
 * 而当d+1<=k<=n时子区间和则为sum[k]-sum[k-d]
 * 于是对于一段区间[l,r]假设最大长度为d的子区间和为delta
 * 那么我们需要判断的即是sum[r]-sum[l-1]-delta是否<=p
 *
 * 单调递减队列,存入长度为d的区间的值
 * 对于每个点k为终点的讨论,都在队列中加入sum[k]-sum[k-d]使得讨论一定有解（标记位置为k-d+1)
 * 假设现在已经得到可以成立的区间[l,r]（[l-1,r],[l,r+1]都不能使条件成立）
 * 注意此时的右端点全部是r+1
 * 在讨论r+1为右端点时,左端点直接从l开始枚举
 * 而且对于单调队列中的元素,左端点也一定要>=r+1
 * 由于队列为单调递减,所以第一个元素一定是当前区间中,长度为d的子区间的和的最大值
 * 由此可以得到希望的结果
 *
 * 所以此时我们只需判断
        (sum[r+1]-sum[l-1]-队列第一个元素)是否<=p
 * 即可判定成立与否
 * 若成立,就可以直接更新结果,且以r+1为右端点的讨论终止
 * 若不成立,那么l+1,同时对当前单调队列的元素的左端点进行判定（左端点>=l+1)
 * 重复上述过程
 */
#include <cstdio>
inline long long read()
{
    long long n=0;int w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
inline int max(int x,int y)
{return x>y?x:y;}
const int N=1e6+1;
int n,d,ans;
long long sum[N],que[N],pos[N],p;
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read(),p=read(),d=read();
    ans=d;
    for(int i=1;i<=n;++i)
        sum[i]=sum[i-1]+read();
//  if(d>=n){printf("%d",n);goto E;}
    long long res;
    if(n<=100)
        for(int l=2,r=d+1;r<=n;++l,++r)
        {
            res=sum[r]-sum[l-1];
            for(int i=1;i<=l;++i)
                for(int j=r+1;j<=n;++j)
                    if(sum[j]-sum[i-1]-res<=p)
                        ans=max(ans,j-i+1);
        }
    else
    {
        int h=1,t=0,last_l=1;
        for(int i=d+1;i<=n;++i)
        {
            res=sum[i]-sum[i-d];
            while(h<=t && res>=que[t])--t;
            que[++t]=res;
            pos[t]=i-d+1;
            while(sum[i]-sum[last_l-1]>p+que[h])
                ++last_l;
            while(pos[h]<last_l)++h;
            ans=max(ans,i-last_l+1);
        }
    }
    printf("%d",ans);
E:  fclose(stdin),fclose(stdout);
    return 0;
}

T3

图片.png

/*
 */
#include <cstdio>
#include <algorithm>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
const int N=1e6+1;
int n,m,l,r,ans,tot,a[N];
bool vis[1001][1001];
void add(int u,int v)
{vis[u][v]=1;}
void change(int l,int r)
{
    for(int i=l;i<=r;++i)
        for(int j=i+1;j<=r;++j)
        {
            if(vis[i][j])
                vis[i][j]=false,vis[j][i]=true;
            else    vis[i][j]=true,vis[j][i]=false;
        }
}
void query()
{
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            for(int k=j+1;k<=n;++k)
                if((vis[i][j] && vis[j][k] && vis[k][i]) || (vis[j][i] && vis[k][j] && vis[i][k]))
                    ++ans;
}
int main()
{
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    n=read(),m=read();
    if(m==0)return printf("0"),0;
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            if(a[i]>a[j])
                add(i,j);
            else
                if(a[j]>a[i])
                    add(j,i);
        }
    for(int i=1;i<=m;++i)
    {
        l=read(),r=read();
        change(l,r);
    }
    query();
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

正解及代码

T1

第一次最多往第一个瓶子倒 $\frac{L+1}{2}$ ，第二次最多往第二个瓶子倒 $\frac{L+3}{2}$
第三次只能往第一个瓶子倒 $2$ 滴水，第四次最多往第二个瓶子倒 $2$ 滴水

最后答案如果 $R-L>=2$ 是 $\lfloor\frac{R-L}{2}\rfloor+1$
注意特判某些情况：
$R=L$ 时，若 $L=1$ 则输出 $0$ ，若 $L=2$ 那么输出 $1$ ，其他情况输出 $2$
剩下的就是 $R=L+1$ ， $R=2,L=1$ 的时候输出 $1$ ，其他情况输出 $2$

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    freopen("lock.in","r",stdin);
    freopen("lock.out","w",stdout);
    long long tmp,l,r,ans,sh;
    scanf("%lld%lld",&l,&r);
//  while(scanf("%lld%lld",&l,&r)!=EOF)
    {
        if(l==1&&r==1)
        {
            puts("0");
            return 0;
        }
        if(l<=2&&r<=2)
        {
            puts("1");
            return 0;
        }
        ans=2;
        sh=l+2;
        if(sh>=r-1)
        {
            puts("2");
            return 0;
        }
    //  printf("%d\n",(-1)/4);
        tmp=r-1-sh;
        tmp=tmp/2;
        if((r-1-sh)%2!=0)
            tmp++;
        ans=ans+tmp;
        printf("%lld\n",ans);
    }
    return 0;
}

T2

对每个点都求出以它为起点（或者是终点）的长度不大于d的区间和
考虑贪心,除非是无法使长度达到d,否则是一定要删掉长度为d的区间的
那么我们的问题就在于：如何能够在一段区间内快速寻找到长度为d的和最大的子区间

首先预处理出前缀和 $sum$
那么对于每个点 $k$ 为终点的长度不大于 $d$ 的子区间
在 $1\le k\le d$ 时子区间和为 $sum[k]$
而当 $d+1\le k\le n$ 时子区间和则为 $sum[k]-sum[k-d]$
于是对于一段区间 $[l,r]$ 假设最大长度为d的子区间和为 $delta$
那么我们需要判断的即是 $sum[r]-sum[l-1]-delta$ 是否 $\le p$ 所以问题变成维护一段区间内 $\lt p$ 的最大子段和
可以线段树，ST表 $O(n\log n)$
也可以单调队列

考虑Two Point法
有两个指针分别指向两个位置，那么这两个位置确定一个区间
图片.png
考虑如果 $[l,r]$ 合法，那么 $r$ 右移直到 $sum[r]-sum[l-1]\gt p$
如果 $[l,r]$ 不合法，那么 $l$ 左移直到 $sum[r]-sum[l-1]\le p$
可以发现 $l,r$ 一定是在不断右移的，不会存在 $[l,r]$ 不合法但是 $[l-1,r]$ 合法的情况
所以答案区间单调不降

单调递减队列,存入长度为 $d$ 的区间的值
对于每个点 $k$ 为终点的讨论,都在队列中加入 $sum[k]-sum[k-d]$ 使得讨论一定有解（标记位置为 $k-d+1$ ）
假设现在已经得到可以成立的区间 $[l,r]$ （ $[l-1,r],[l,r+1]$ 都不能使条件成立）
注意此时的右端点全部是 $r+1$
在讨论 $r+1$ 为右端点时,左端点直接从 $l$ 开始枚举
而且对于单调队列中的元素,左端点也一定要 $\ge r+1$
由于队列为单调递减,所以第一个元素一定是当前区间中,长度为 $d$ 的子区间的和的最大值
由此可以得到希望的结果

所以此时我们只需判断( $sum[r+1]-sum[l-1]-$ 队列第一个元素)是否 $\le p$
即可判定成立与否
* 若成立,就可以直接更新结果,且以 $r+1$ 为右端点的讨论终止
* 若不成立,那么 $l+1$ ,同时对当前单调队列的元素的左端点进行判定（左端点 $\ge l+1$ )
* 重复上述过程

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long sum[1010101],f[1010101],q[1010101],a[1010101];
inline int read()
{
    int ans=0,fu=1;
    char ch;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') fu=-fu;
    for(;ch<='9'&&ch>='0';ch=getchar()) ans=ans*10+ch-'0';
    return ans*fu;
}
inline long long readl()
{
    long long ans=0,fu=1;
    char ch;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') fu=-fu;
    for(;ch<='9'&&ch>='0';ch=getchar()) ans=ans*10+ch-'0';
    return ans*fu;
}
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    int n,d,i,l,ans=0,r,h,t;
    long long p;
    n=read(),p=readl(),d=read();
//  scanf("%d%lld%d",&n,&p,&d);
    for(i=1;i<=n;i++)
    {
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
    }
    for(i=1;i+d-1<=n;i++)
        f[i]=sum[i+d-1]-sum[i-1];//,printf("%d %d\n",i,f[i]);
    l=0,r=1,h=0,t=0;
    if(d==1)
        q[t++]=1;
    for(l=1;l<=n;l++)
    {
        if(h!=t&&q[h]<l)
            h++;
        while(r<=n&&(sum[r]-sum[l-1]-f[q[h]]<=p||r-l+1<=d))
        {
            r++;
            while(t-1>=h&&f[r-d+1]>f[q[t-1]])
                t--;
            if(r-d+1>0)
                q[t++]=r-d+1;
        }
//      printf("%d %d\n",l,r);
        ans=max(ans,r-l);
    }
    printf("%d\n",ans);
    return 0;
}

T3

实际是求图中最后的三元环个数
如果三个点不能构成三元环那么一定有一个人能打赢另外两个人
令 $d[i]$ 表示第 $i$ 个人能打赢 $d[i]$ 场
那么答案就是 ${n\choose 3}-\sum_{i=1}^n{d[i]\choose 2}$
问题转化为 $k$ 次操作后每个人能赢几场
但是依然不好做，依然需要 $N^2$ 枚举

注意到题目是先进行 $k$ 此翻转，最后每个人能赢几场
那么先进行哪次操作不会影响最终答案
考虑离线，记录所有的操作是什么能力值开始反转 $(L[i])$ 以及什么能力值结束反转 $(R[i])$
比如有一次操作 $L[i]=5,R[i]=9$ ，那么能力值为 $5$ 的时候出现反转，能力值为 $10$ 的反转结束
对于所有操作， $L[i]$ 位置记为 $1$ ， $R[i]+1$ 的位置记为 $-1$
能力值为 $1$ 的能赢几场就是先将 $l[i]=1$ 的进行反转，而后的操作相当于对一段区间 $\oplus 1$
这个是一个经典的线段树区间维护的问题，考虑第 $i$ 个叶子表示能力值为 $i$ 的是否进行了反转
最后求答案的时候相当于求有多少叶子的值为 $1$
而能力值为 $2$ 的时候，先将 $l[i]=2$ 的进行反转、将 $r[i]+1=2$ 的也要进行反转，最后求:"有多少位置 $\gt 2$ 的叶子值为 $1$ （原来能打过能力值为 $2$ 的但是经过反转打不过了） $+$ 有多少位置 $\lt 2$ 的叶子值为 $0$ （原来打不过能力值为 $2$ 的现在依然打不过"，引号内的内容就是 $d[2]$
那么推广：枚举所有能力值为 $k$ 的，将 $l[i]=k$ 进行反转，也将 $r[i]+1=k$ 的进行反转，求 $d[k]=$ 有多少位置 $\gt k$ 的叶子值为 $1+$ 有多少位置 $\lt k$ 的叶子值为 $0$

求出所有 $d[]$ ，最后 $ans={n\choose 3}-\sum_{i=1}^n{d[i]\choose 2}$

#include <vector>
#include <cstdio>
#include <algorithm>
const int N=100001;
int a[N],l[N],r[N];
std::vector<std::pair<int,int> >s[N<<2];
struct Node{
    int tag,w;
}tree[N<<3];
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
#define ls root<<1
#define rs root<<1|1
#define mp std::make_pair
void pushdown(int root,int left,int right)
{
    if(!tree[root].tag)return ;
    int mid=left+right>>1;
    tree[ls].tag^=1,tree[rs].tag^=1;
    tree[ls].w=mid-left+1-tree[rs].w;
//  printf("%d %d %d\n",left,right,tree[root*2].w);
    tree[rs].w=right-mid-tree[rs].w;
    tree[root].tag=0;
}
void update(int root,int left,int right,int x,int y)
{
//  printf("%d %d|%d %d\n",x,y,left,right);
    if(x<=left&&y>=right)
    {
//      printf("%d\n",tree[root].w);
        tree[root].w=right-left+1-tree[root].w;
        tree[root].tag^=1;
        return ;
    }
    pushdown(root,left,right);
    int mid=left+right>>1;
    if(mid>=x)update(ls,left,mid,x,y);
    if(mid< y)update(rs,mid+1,right,x,y);
    tree[root].w=tree[ls].w+tree[rs].w;
//  printf("%d %d %d\n",left,right,tree[root].w);
}
int query(int root,int left,int right,int x)
{
    if(left==right)
        return tree[root].w;
    pushdown(root,left,right);
    int mid=left+right>>1;
    if(mid>=x)
        return query(ls,left,mid,x);
    else    return query(rs,mid+1,right,x);
}
int main()
{
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    int tmp1,tmp2,c,m,ll,rr,tmp,n;
    long long ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    std::sort(a+1,a+n+1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&l[i],&r[i]);
        tmp1=std::lower_bound(a+1,a+n+1,l[i])-a;
        tmp2=std::upper_bound(a+1,a+n+1,r[i])-a;
        --tmp2;
        s[tmp1  ].push_back(mp(tmp1,tmp2));
        s[tmp2+1].push_back(mp(tmp1,tmp2));
    }
    update(1,1,n,1,n);
    ans=(long long)n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;++i)
    {
        c=s[i].size();
        if(i!=1)
            update(1,1,n,i-1,i-1);
        for(int j=0;j<c;++j)
        {
            ll=s[i][j].first;
            rr=s[i][j].second;
//          printf("%d %d %d|\n",i,ll,rr);
            if(ll<=rr)
            update(1,1,n,ll,rr);
//          printf("%d|\n",tree[1].w);
        }
        tmp=tree[1].w-query(1,1,n,i);
//      printf("%d %d %d\n",i,tmp,tree[1].w);
        ans=ans-((long long)tmp*(tmp-1)/2);
    }
    printf("%lld\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

10.25晚上解题报告

各题状况

T1

T2

T3

题目及考场代码

T2

T3

正解及代码

T1

T2

T3

内容目录

选择主题