PKUSC 模拟赛 day2 下午总结

终于考完了，下午身体状况很不好，看来要锻炼身体了，不然以后ACM没准比赛到一半我就挂掉了

下午差点AK，有一道很简单的题我看错题面了所以没有A掉

第一题显然是非常丝薄的题目

我们很容易通过DP来O(n^2)的求出深度至多为k的方案

然后我们很容易通过DP来O(n^2)的求出深度至多为k-1的方案

转移的时候分当前放左括号或者右括号讨论就可以了

两个作差就是答案了，单次询问时间复杂度O(n^2)

如果给dp加一维O(n^3)预处理，O(1)回答

当然要写高精度

成功抢到下午的first blood，请叫我手速狗，汪

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

const int mod=10000;
int n,k,kase;
struct big_num{
    int a[22],len;
    void add(const big_num &A){
        len=max(A.len,len)+1;
        for(int i=1;i<=len;++i)a[i]=a[i]+A.a[i];
        for(int i=1;i<=len;++i){
            a[i+1]+=a[i]/mod;
            a[i]%=mod;
        }
        while(len>0&&a[len]==0)len--;
    }
    void minus(const big_num &A){
        for(int i=1;i<=len;++i){
            if(a[i]<A.a[i])a[i+1]--,a[i]=a[i]+mod-A.a[i];
            else a[i]=a[i]-A.a[i];
        }
        while(len>0&&a[len]==0)len--;
    }
    void print(){
        printf("Case %d: ",kase);
        printf("%d",a[len]);
        for(int i=len-1;i>=1;--i)printf("%04d",a[i]);
        printf("\n\n");
    }
    void clear(){len=1;memset(a,0,sizeof(a));}
}f[102][52],ans;

int main(){
    while(scanf("%d%d",&n,&k)==2){
        if(!n&&!k)break;
        f[0][0].len=1;f[0][0].a[1]=1;
        n<<=1;kase++;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=k;++j){
                f[i][j].clear();
                if(j>0)f[i][j].add(f[i-1][j-1]);
                if(j<k)f[i][j].add(f[i-1][j+1]);
            }
        }
        ans=f[n][0];
        for(int i=1;i<=n;++i){
            for(int j=0;j<=k-1;++j){
                f[i][j].clear();
                if(j>0)f[i][j].add(f[i-1][j-1]);
                if(j<k-1)f[i][j].add(f[i-1][j+1]);
            }
        }
        ans.minus(f[n][0]);
        ans.print();
    }return 0;
}

第二题保证每个点恰好属于一个环，求最长环

我能想到的有两种做法：

1、这题目显然是点双的裸题QAQ

2、用并查集建树，之后枚举非树边计算环的大小更新答案

由于上午点双的阴影还在，所以果断写了第二种做法

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

const int maxn=5010;
int T,n,m;
int f[maxn];
int h[maxn],cnt=0;
bool check[maxn];
struct edge{
    int to,next;
}G[3000010];
struct Edge{
    int u,v;
}c[3000010];
int fa[maxn],dep[maxn];
int anc[maxn][20];

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 add(int x,int y){
    ++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
int ufs(int x){
    return f[x]==x?x:f[x]=ufs(f[x]);
}
void DFS(int u,int f){
    fa[u]=f;
    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);
    }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 fa[p];
}

int main(){
    read(T);
    while(T--){
        read(n);read(m);
        memset(h,0,sizeof(h));cnt=0;
        for(int i=1;i<=n;++i)f[i]=i,dep[i]=0;
        for(int i=1;i<=m;++i)check[i]=false;
        for(int i=1;i<=m;++i){
            read(c[i].u);read(c[i].v);
            int d1=ufs(c[i].u),d2=ufs(c[i].v);
            if(d1!=d2){
                f[d1]=d2;
                add(c[i].u,c[i].v);
                add(c[i].v,c[i].u);
                check[i]=true;
            }
        }
        for(int i=1;i<=n;++i)if(ufs(i)==i)DFS(i,-1);
        pre_LCA();
        int ans=0;
        for(int i=1;i<=m;++i){
            if(!check[i]){
                int lca=LCA(c[i].u,c[i].v);
                ans=max(ans,dep[c[i].u]+dep[c[i].v]-2*dep[lca]+1);
            }
        }printf("%d\n",ans);
    }return 0;
}

第三题是原题QAQ

我背后缀数组模板的时候背的题目

曾经跟lyc说过这道题目可以用SAM做，然后是论文题

然而SAM的极限时间复杂度是O(n*sqrt(n))，感觉多笔测资有些虚

考试后发现他们都写得SAM QAQ 貌似可以卡住的样子 QAQ

后缀数组码码码，明显后缀数组很不熟练，写了30min才写完

比其他模板写的慢多了QAQ 然后除了被系统卡了rank的关键字之外1A

真是舒爽

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int n,L,R,kase;
int s[maxn],now;
int cnt=-1;
int pos[maxn];
int wa[maxn],wb[maxn],w[maxn],wv[maxn];
int sa[maxn],height[maxn],rk[maxn];
int vis[1010],tim;
void get(int id){
    char ch=getchar();
    while(ch<'!')ch=getchar();
    while(ch>='a'&&ch<='z'){s[++cnt]=(int)(ch)+200;pos[cnt]=id;ch=getchar();}
    s[++cnt]=++now;
}
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void get_da(int n,int m){
    int *x=wa,*y=wb,*t;
    for(int i=0;i<m;++i)w[i]=0;
    for(int i=0;i<n;++i)w[x[i]=s[i]]++;
    for(int i=1;i<m;++i)w[i]+=w[i-1];
    for(int i=n-1;i>=0;--i)sa[--w[x[i]]]=i;
    for(int p=1,j=1;p<n;j<<=1,m=p){
        p=-1;
        for(int i=n-j;i<n;++i)y[++p]=i;
        for(int i=0;i<n;++i)if(sa[i]>=j)y[++p]=sa[i]-j;
        for(int i=0;i<n;++i)wv[i]=x[y[i]];
        for(int i=0;i<m;++i)w[i]=0;
        for(int i=0;i<n;++i)w[wv[i]]++;
        for(int i=1;i<m;++i)w[i]+=w[i-1];
        for(int i=n-1;i>=0;--i)sa[--w[wv[i]]]=y[i];
        t=x;x=y;y=t;x[sa[0]]=0;p=1;
        for(int i=1;i<n;++i)x[sa[i]]=cmp(t,sa[i],sa[i-1],j)?p-1:p++;
    }
    for(int i=0;i<n;++i)rk[sa[i]]=i;
    int k=0;
    for(int i=0;i<n;++i){
        if(rk[i]==0){height[rk[i]]=0;continue;}
        if(k)--k;
        int j=sa[rk[i]-1];
        while(s[j+k]==s[i+k])k++;
        height[rk[i]]=k;
    }return;
}
bool check(int blo){
    int tot=0;
    for(int i=n;i<=cnt;++i){
        if(height[i]<blo){
            tim++;tot=1;
            vis[pos[sa[i]]]=tim;
        }
        else{
            if(vis[pos[sa[i]]]!=tim)vis[pos[sa[i]]]=tim,tot++;
            if(tot>n/2)return true;
        }
    }return false;
}
void print(){
    if(L==0){printf("?\n");return;}
    int tot=0;
    for(int i=n;i<=cnt;++i){
        if(height[i]<L){
            tim++;
            if(tot>n/2){
                for(int j=sa[i-1];j<=sa[i-1]+L-1;++j)putchar(s[j]-200);
                printf("\n");
            }tot=1;vis[pos[sa[i]]]=tim;
        }else{
            if(vis[pos[sa[i]]]!=tim)vis[pos[sa[i]]]=tim,tot++;
        }
    }
    if(tot>n/2){
        for(int j=sa[cnt];j<=sa[cnt]+L-1;++j)putchar(s[j]-200);
        printf("\n");
    }return;
}
int main(){
    while(scanf("%d",&n)==1){
        if(n==0)break;
        if(kase)printf("\n");
        kase++;cnt=-1;now=0;
        for(int i=1;i<=n;++i)get(i);
        get_da(cnt+1,1000);
        memset(vis,0,sizeof(vis));tim=1;
        L=0,R=cnt;
        while(L<R){
            int mid=L+(R-L+1)/2;
            if(check(mid))L=mid;
            else R=mid-1;
        }
        print();
    }return 0;
}

第四题好难读的题面，然后读懂了就很容易发现是个斗地主的弱化版

随便写写就好啦

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

int T,kase;
char s[22][22];
char t[22][22];
int vis[4][12];
int tmp[1010];

bool DFS(int num){
    if(num==12){
        for(int i=1;i<=3;++i){
            for(int j=1;j<=9;++j){
                if(vis[i][j]==2)return true;
            }
        }return false;
    }
    for(int i=1;i<=3;++i){
        for(int j=1;j<=9;++j){
            if(vis[i][j]){
                if(vis[i][j]>=3){
                    vis[i][j]-=3;
                    if(DFS(num+3))return true;
                    vis[i][j]+=3;
                }
                if(vis[i][j+1]&&vis[i][j+2]){
                    vis[i][j]--;
                    vis[i][j+1]--;
                    vis[i][j+2]--;
                    if(DFS(num+3))return true;
                    vis[i][j]++;
                    vis[i][j+1]++;
                    vis[i][j+2]++;
                }
            }
        }
    }return false;
}

bool check(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=14;++i)vis[tmp[s[i][2]]][s[i][1]-'0']++;
    for(int i=1;i<=3;++i){
        for(int j=1;j<=9;++j){
            if(vis[i][j]>4)return false;
        }
    }
    if(DFS(0))return true;
    return false;
}

int main(){
    scanf("%d",&T);
    tmp['s']=1;tmp['b']=2;tmp['c']=3;
    while(T--){
        kase++;int cnt=0;
        for(int i=1;i<=13;++i)scanf("%s",s[i]+1);
        printf("Case %d:",kase);
        for(int i=1;i<=3;++i){
            if(i==1)s[14][2]='s';
            else if(i==2)s[14][2]='b';
            else s[14][2]='c';
            for(int j=1;j<=9;++j){
                s[14][1]=j+'0';
                if(check()){
                    printf(" ");cnt++;
                    putchar(s[14][1]);
                    putchar(s[14][2]);
                }
            }
        }
        if(!cnt)printf(" None");
        printf("\n");
    }return 0;
}

第五题考试的时候一直看错题，然后就没有A掉

后来听lyc说了题意之后发现是个背包的丝薄题

看对题之后随便写写就A啦

正确性的证明是因为答案是个二次函数QAQ

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

typedef long long LL;
const int maxn=110;
const LL oo=1LL<<60;
int n,L;
LL sa,sc;
int c[maxn],a[maxn];
LL f[maxn][maxn][502];

int main(){
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),sa+=a[i];
    for(int i=1;i<=n;++i)scanf("%d",&c[i]),sc+=c[i];
    for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)for(int k=0;k<=sa;++k)f[i][j][k]=oo;
    f[0][0][0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n;++j){
            for(int k=0;k<=sa;++k){
                f[i][j][k]=f[i-1][j][k];
                if(k>=a[i]&&j>=1)f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k-a[i]]+c[i]);
            }
        }
    }
    double ans=1e13;
    for(int i=1;i<=n;++i){
        if(i==L||n-i==L){
            for(int k=1;k<=sa-1;++k){
                if(f[n][i][k]!=oo){
                    double now=(double)(f[n][i][k])/(double(k))*(double)(sc-f[n][i][k])/(double)(sa-k);
                    ans=min(ans,now);
                }
            }
        }
    }printf("%.3lf\n",ans);
    return 0;
}

第六题正解是维护凸包，每次二分斜率求最优值做DP就可以了

然后考试的时候没有太多时间，很容易发现答案是fi+ci*abs(xi-xj)的形式

两边项次数都是一次

下面不加证明的给出以下结论：

1、当两边项都是二次的时候，使用KD_Tree并定期重构保证不退化时间复杂度较优

2、当两边项一个一次一个二次的时候，使用平衡树以二次项为键值维护并做KD_Tree的查询较优

3、当两边项均为一次时，使用线段树同时维护两个信息并做KD_Tree的查询较优

然后本题显然两个一次直接线段树+KD_Tree就可以啦

其实这个题目是式子是省选模拟某套题目的第一题的式子？

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

typedef long long LL;
const int maxn=100010;
const int oo=0x7fffffff;
int n;
int x[maxn],c[maxn],t[maxn];
int l[maxn<<2],r[maxn<<2];
LL mxd[maxn<<2],mxc[maxn<<2];
LL dp[maxn],now,k;

void UPD(int o,int L,int R,int p,LL d,LL c,int x){
    if(L==R){mxd[o]=d;mxc[o]=c;l[o]=x;r[o]=x;return;}
    int mid=(L+R)>>1;
    if(p<=mid)UPD(o<<1,L,mid,p,d,c,x);
    else UPD(o<<1|1,mid+1,R,p,d,c,x);
    mxd[o]=max(mxd[o<<1],mxd[o<<1|1]);
    mxc[o]=max(mxc[o<<1],mxc[o<<1|1]);
    l[o]=min(l[o<<1],l[o<<1|1]);
    r[o]=max(r[o<<1],r[o<<1|1]);
}
void ask(int o,int L,int R,int x,int y){
    if(L>=x&&R<=y){
        if(L==R)now=max(now,mxd[o]+mxc[o]*abs(l[o]-k));
        else{
            LL d1=mxd[o<<1]+mxc[o<<1]*max(abs(l[o<<1]-k),abs(r[o<<1]-k));
            LL d2=mxd[o<<1|1]+mxc[o<<1|1]*max(abs(r[o<<1|1]-k),abs(l[o<<1|1]-k));
            int mid=(L+R)>>1;
            if(d1>d2){
                if(d1>now)ask(o<<1,L,mid,x,y);
                if(d2>now)ask(o<<1|1,mid+1,R,x,y);
            }else{
                if(d2>now)ask(o<<1|1,mid+1,R,x,y);
                if(d1>now)ask(o<<1,L,mid,x,y);
            }
        }return;
    }
    int mid=(L+R)>>1;
    if(y<=mid)ask(o<<1,L,mid,x,y);
    else if(x>mid)ask(o<<1|1,mid+1,R,x,y);
    else ask(o<<1,L,mid,x,y),ask(o<<1|1,mid+1,R,x,y);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d%d",&x[i],&c[i],&t[i]);
    for(int i=1;i<=(n<<2);++i)l[i]=oo,r[i]=-oo;
    UPD(1,1,n,1,0,c[1],x[1]);
    for(int i=2;i<=n;++i){
        now=0;k=x[i];
        ask(1,1,n,1,i-1);
        dp[i]=now+t[i]；
        UPD(1,1,n,i,dp[i],c[i],x[i]);
    }printf("%lld\n",dp[n]);
    return 0;
}

今天下午发挥的较为不错

直接说缺点吧：

1、第三题的后缀数组模板不熟练，拖了一些时间

2、身体素质不太好，在四点半以后就开始狂吐不止，没有什么精力去仔细看第五题，导致第五题并没有A掉