PKUSC 模拟赛 day1 上午总结

思考了一下第二题，觉得有无数种乱搞做法

类似什么bitset压位，MCS染色之类奇怪的做法

然而都是玄学正确性或者玄学复杂度

先放题解把

第一题显然具有单调性，二分就可以啦

O(nlogn)，貌似输出要求去尾QAQ

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define eps 1e-3
using namespace std;

typedef long long LL;
const int maxn=100010;
int n,k;
double a[maxn];
double mx,mn;

LL check(double k){
    LL sum=0;
    for(int i=1;i<=n;++i){
        sum+=(LL)(a[i]/k);
    }return sum;
}

int main(){
    scanf("%d%d",&n,&k);
    mn=1e12;mx=-1e12;
    for(int i=1;i<=n;++i){
        scanf("%lf",&a[i]);
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    double L=mx/k,R=mx;
    while(R-L>eps){
        double mid=(L+R)/2.0;
        if(check(mid)<k)R=mid;
        else L=mid;
    }printf("%.2lf\n",fabs(L-4*eps));
    return 0;
}

第二题略过，又臭又长的题面，比赛的时候看都没有看

第三题显然我们枚举可选区间的右端点，寻找满足条件的最远的左端点

ans=sigma(Ri-Li+1)

然后判断是否合法就是查询区间最大值和区间最小值，直接线段树或者ST表可以做到O(logn)的查询

如果我们二分这个左端点，显然时间复杂度O(nlog^2n)，这是会T的

我们很容易发现随着右端点的递增，左端点也是递增的，维护一个单调指针即可

时间复杂度O(nlogn)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

typedef long long LL;
const int maxn=100010;
int T,n,k;
int a[maxn];
int mx[maxn<<2];
int mn[maxn<<2];
LL ans;
void read(int &num){
    num=0;char ch=getchar();
    while(ch<'!')ch=getchar();
    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void build(int o,int L,int R){
    if(L==R){mn[o]=mx[o]=a[L];return;}
    int mid=(L+R)>>1;
    build(o<<1,L,mid);
    build(o<<1|1,mid+1,R);
    mx[o]=max(mx[o<<1|1],mx[o<<1]);
    mn[o]=min(mn[o<<1|1],mn[o<<1]);
}
int ask_max(int o,int L,int R,int x,int y){
    if(L>=x&&R<=y)return mx[o];
    int mid=(L+R)>>1;
    if(y<=mid)return ask_max(o<<1,L,mid,x,y);
    else if(x>mid)return ask_max(o<<1|1,mid+1,R,x,y);
    else return max(ask_max(o<<1,L,mid,x,y),ask_max(o<<1|1,mid+1,R,x,y));
}
int ask_min(int o,int L,int R,int x,int y){
    if(L>=x&&R<=y)return mn[o];
    int mid=(L+R)>>1;
    if(y<=mid)return ask_min(o<<1,L,mid,x,y);
    else if(x>mid)return ask_min(o<<1|1,mid+1,R,x,y);
    else return min(ask_min(o<<1,L,mid,x,y),ask_min(o<<1|1,mid+1,R,x,y));
}

int main(){
    read(T);
    while(T--){
        read(n);read(k);
        for(int i=1;i<=n;++i)read(a[i]);
        build(1,1,n);int pos=1;
        ans=0;
        for(int i=1;i<=n;++i){
            while(pos<=i&&ask_max(1,1,n,pos,i)-ask_min(1,1,n,pos,i)>=k)pos++;
            ans=ans+i-pos+1;
        }printf("%lld\n",ans);
    }return 0;
}

第四题弱化一下问题，如果不是链是边显然我们一遍树形DP就可以搞定了

扩展一下树形DP的做法之后我们发现当我们选择一条链之后这棵树被分解成若干子树，每个子树都是独立的

还是可以做树形DP的，关键是快速计算每种方案的价值

我们定义s2表示每个点儿子的DP值的和，s1表示自己的DP值的和

那么选择一条链的价值就是这条链上s2的和减去s1的和+这条链的收益，这是容易用树链剖分或者LCT维护的

DP的时候转移两种情况，当前点被链覆盖和不被链覆盖，随意搞一搞就可以啦

考试的时候比较傻，能用树状数组不用写线段树，能用树剖求LCA还要写倍增，最后码了20多分钟才码完，整整4K+ QAQ

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int maxn=100010;
int T,n,m,u,v,now;
int h[maxn],cnt=0;
struct edge{
    int to,next;
}G[maxn<<1];
struct Line{
    int u,v,val,lca;
}c[maxn];
int ed[maxn],tot;
int fa[maxn],dep[maxn],w[maxn],son[maxn];
int pos[maxn],fp[maxn],top[maxn],sum;
int anc[maxn][20];
int s1[maxn<<2];
int s2[maxn<<2];
int dp[maxn];

bool cmp(const Line &A,const Line &B){
    return ed[A.lca]<ed[B.lca];
}
void add(int x,int y){
    ++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
void read(int &num){
    num=0;char ch=getchar();
    while(ch<'!')ch=getchar();
    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void DFS(int u,int f){
    fa[u]=f;w[u]=1;
    for(int i=h[u];i;i=G[i].next){
        int v=G[i].to;
        if(v==f)continue;
        dep[v]=dep[u]+1;
        DFS(v,u);w[u]+=w[v];
        if(w[son[u]]<w[v])son[u]=v;
    }ed[u]=++tot;return;
}
void Get_pos(int u,int f){
    top[u]=f;pos[u]=++sum;fp[sum]=u;
    if(!son[u])return;
    Get_pos(son[u],f);
    for(int i=h[u];i;i=G[i].next){
        int v=G[i].to;
        if(v==fa[u]||v==son[u])continue;
        Get_pos(v,v);
    }return;
}
void pre_LCA(){
    for(int i=1;i<=n;++i){
        anc[i][0]=fa[i];
        for(int j=1;(1<<j)<=n;++j)anc[i][j]=-1;
    }
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i<=n;++i){
            if(anc[i][j-1]!=-1){
                int a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
            }
        }
    }return;
}
int LCA(int p,int q){
    if(dep[p]<dep[q])swap(p,q);
    int log;
    for(log=0;(1<<log)<=dep[p];++log);--log;
    for(int i=log;i>=0;--i){
        if(dep[p]-(1<<i)>=dep[q])p=anc[p][i];
    }
    if(p==q)return p;
    for(int i=log;i>=0;--i){
        if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
            p=anc[p][i];q=anc[q][i];
        }
    }return anc[p][0];
}
void UPD_s1(int o){s1[o]=s1[o<<1|1]+s1[o<<1];}
void UPD_s2(int o){s2[o]=s2[o<<1|1]+s2[o<<1];}
void build(int o,int L,int R){
    if(L==R){s1[o]=s2[o]=0;return;}
    int mid=(L+R)>>1;
    build(o<<1,L,mid);
    build(o<<1|1,mid+1,R);
    UPD_s1(o);UPD_s2(o);
}
void modify_s1(int o,int L,int R,int p,int v){
    if(L==R){s1[o]+=v;return;}
    int mid=(L+R)>>1;
    if(p<=mid)modify_s1(o<<1,L,mid,p,v);
    else modify_s1(o<<1|1,mid+1,R,p,v);
    UPD_s1(o);
}
void modify_s2(int o,int L,int R,int p,int v){
    if(L==R){s2[o]+=v;return;}
    int mid=(L+R)>>1;
    if(p<=mid)modify_s2(o<<1,L,mid,p,v);
    else modify_s2(o<<1|1,mid+1,R,p,v);
    UPD_s2(o);
}
int ask(int o,int L,int R,int x,int y){
    if(L>=x&&R<=y)return s2[o]-s1[o];
    int mid=(L+R)>>1;
    if(y<=mid)return ask(o<<1,L,mid,x,y);
    else if(x>mid)return ask(o<<1|1,mid+1,R,x,y);
    else return ask(o<<1,L,mid,x,y)+ask(o<<1|1,mid+1,R,x,y);
}
int ask_s2(int o,int L,int R,int p){
    if(L==R)return s2[o];
    int mid=(L+R)>>1;
    if(p<=mid)return ask_s2(o<<1,L,mid,p);
    else return ask_s2(o<<1|1,mid+1,R,p);
}
int ASK(int u,int v){
    int sum=0;
    while(top[u]!=top[v]){
        sum+=ask(1,1,n,pos[top[u]],pos[u]);
        u=fa[top[u]];
    }sum+=ask(1,1,n,pos[v],pos[u]);
    return sum;
}
void Get_DP(int u,int f){
    for(int i=h[u];i;i=G[i].next){
        int v=G[i].to;
        if(v==f)continue;
        Get_DP(v,u);
        dp[u]+=dp[v];
    }
    while(now<=m&&c[now].lca==u){
        int ans=c[now].val+ASK(c[now].u,c[now].lca)+ASK(c[now].v,c[now].lca);
        ans=ans-ask_s2(1,1,n,pos[c[now].lca]);
        dp[u]=max(dp[u],ans);now++;
    }
    modify_s1(1,1,n,pos[u],dp[u]);
    if(fa[u]!=-1)modify_s2(1,1,n,pos[fa[u]],dp[u]);
}
int main(){
    read(T);
    while(T--){
        read(n);read(m);
        for(int i=1;i<=n;++i)h[i]=0;
        cnt=0;
        for(int i=1;i<=n;++i)son[i]=0;
        for(int i=1;i<n;++i){
            read(u);read(v);
            add(u,v);add(v,u);
        }tot=0;DFS(1,-1);
        sum=0;Get_pos(1,-1);
        pre_LCA();
        for(int i=1;i<=m;++i){
            read(c[i].u);read(c[i].v);read(c[i].val);
            c[i].lca=LCA(c[i].u,c[i].v);
        }
        sort(c+1,c+m+1,cmp);now=1;
        build(1,1,n);
        for(int i=1;i<=n;++i)dp[i]=0;
        Get_DP(1,-1);
        printf("%d\n",dp[1]);
    }return 0;
}

第五题显然L/(R-L+1)<=2015不是白给的

仔细分析发现这个区间在线段树上的深度不会很大，暴力搜索还原所有可能的区间就可以啦

貌似裸搜就能过啦

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

typedef long long LL;
const LL oo=1LL<<62;
LL ans;
LL a,b;
void DFS(LL L,LL R,LL len,int dep){
    if(L==0)ans=min(ans,R);
    if(L<0)return;
    if(R>ans)return;
    if(dep==12)return;
    DFS(L,R+len,len<<1,dep+1);
    DFS(L-len,R,len<<1,dep+1);
    DFS(L-len-1,R,len<<1|1,dep+1);
    DFS(L,R+len-1,(len<<1)-1,dep+1);
}

int main(){
    while(scanf("%d%d",&a,&b)==2){
        LL len=(b-a+1);
        ans=oo;
        DFS(a,b,len,0);
        if(ans==oo)printf("-1\n");
        else printf("%lld\n",ans);
    }return 0;
}

第六题一眼题，HEOI2016的题目+一个输出字典序最小的方案

然而看到题目的时候离比赛结束只有25分钟了，疯狂码码码

交上去之后不停得RE，然后开始写对拍，写暴力

我居然在25分钟之内写完了正解，数据生成器和暴力！

人的潜能真是无穷的啊，最后发现自己忘记离散化了QAQ

最后还剩3分钟的时候交上去A掉了

我们考虑DP，把可转移的条件写出来发现是三维偏序，直接上CDQ就可以啦

之后要求字典序最小我们不妨采用从后往前DP的形式就很容易确定啦

然后树状数组多维护一个pos之后就可以了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100010;
int n,cnt;
int pre[maxn];
int dp[maxn];
int tmp[maxn];
struct Num{
    int a,b,id;
}c[maxn];
int tim=0;
struct BIT{
    int t,v,p;
}t[maxn];

bool cmpa(const Num &A,const Num &B){
    return A.a<B.a;
}
bool cmpb(const Num &A,const Num &B){
    if(A.b==B.b)return A.id>B.id;
    return A.b>B.b;
}
bool cmpid(const Num &A,const Num &B){
    return A.id<B.id;
}
void read(int &num){
    num=0;char ch=getchar();
    while(ch<'!')ch=getchar();
    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
int lowbit(int x){return x&(-x);}
void UPD(int x,int pos,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        if(t[i].t!=tim)t[i].t=tim,t[i].v=0,t[i].p=0;
        if(v>t[i].v||(v==t[i].v&&pos<t[i].p)){
            t[i].v=v;t[i].p=pos;
        }
    }return;
}
pair<int,int> ask(int x){
    int sum=0,p=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        if(t[i].t==tim){
            if(t[i].v>sum||(t[i].v==sum&&t[i].p<p)){
                sum=t[i].v;
                p=t[i].p;
            }
        }
    }return make_pair(sum,p);
}
void Solve(int L,int R){
    if(L>=R)return;
    int mid=(L+R)>>1;
    Solve(mid+1,R);
    sort(c+L,c+R+1,cmpb);
    tim++;
    for(int i=L;i<=R;++i){
        if(c[i].id>mid)UPD(c[i].a,c[i].id,dp[c[i].id]);
        else{
            pair<int,int>now=ask(c[i].a);
            if(now.first+1>dp[c[i].id]||(now.first+1==dp[c[i].id]&&now.second<pre[c[i].id])){
                dp[c[i].id]=now.first+1;
                pre[c[i].id]=now.second;
            }
        }
    }
    sort(c+L,c+R+1,cmpid);
    Solve(L,mid);
}
void print(int k){
    if(!k)return;
    printf("%d",k);
    if(!pre[k])printf("\n");
    else{
        printf(" ");
        print(pre[k]);
    }return;
}

int main(){
    while(scanf("%d",&n)==1){
        tim++;
        for(int i=1;i<=n;++i)read(c[i].a),c[i].id=i;
        for(int i=1;i<=n;++i)read(c[i].b);
        sort(c+1,c+n+1,cmpa);cnt=0;
        for(int i=1;i<=n;++i)tmp[i]=c[i].a;
        for(int i=1;i<=n;++i){
            if(tmp[i]!=tmp[i-1])c[i].a=++cnt;
            else c[i].a=cnt;
        }
        sort(c+1,c+n+1,cmpid);
        for(int i=1;i<=n;++i)dp[i]=1,pre[i]=0;
        Solve(1,n);
        int ans=0,k=0;
        for(int i=1;i<=n;++i){
            ans=max(ans,dp[i]);
        }printf("%d\n",ans);
        for(int i=1;i<=n;++i){
            if(ans==dp[i]){k=i;break;}
        }
        print(k);
    }return 0;
}

感觉今天上午属于超常发挥，而且在cojs上出题的功效也发挥出来了，上午的五道题我有三道题都写完了一套(正解，暴力，数据生成器）

出题对码力的提升是不可小觑的

考试时较好的地方：

1、直接跳过了第二题(事实证明结束的时候也没有人A掉第二题）

2、第四题没有畏惧代码量，直接强行4K+在半个小时之内就搞定了

3、第五题的乱搞方法非常值得以后比赛借鉴（注意到了题目信息）

考试时不太好的地方：

1、第一题没有仔细读题，导致并不知道要求去尾输出

2、第四题的思维没有优化，导致代码量过大

3、第六题写的时候心中有些紧张了，导致忘记了离散化，差点就没有A掉