UOJ Logo zdw1999的博客

博客

“卓见杯”第五届CCPC中国大学生程序设计竞赛河南省赛题解

2019-04-15 14:47:46 By zdw1999

A: 最大下降矩阵

设f[i]表示选择了第i行时能保留的最大行数

那么显然 f[i]=max(1,f[j]+1) , { $ j < i,第j行中每一列的数均大于第i行 $ }

直接按上式dp即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int ha=1e9+7;
const int N=1e6+5;

ll A[505][505],f[505];
ll n,m;

bool isbig(int i1,int i2){
    for(int i=1;i<=m;++i)
        if(A[i1][i]<=A[i2][i])return 0;
    return 1;
}

int main(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;

    for(int i=1;i<=m;++i)A[0][i]=-(1LL<<60);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            cin>>A[i][j];
        }
    ll ans=1;
    f[1]=1;
    for(int i=2;i<=n;++i){
        f[i]=1;
        for(int j=1;j<i;++j)
            if(isbig(j,i))f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
        //cout<<f[i]<<endl;
    }
    cout<<n-ans;

    return 0;

}

C: 大小接近的点对

我们从根开始做dfs, 并用一个树状数组$B$记录目前扫描过的所有点的权值的个数

每次走到一个点$i$, 我们先记录下$B.query(V_i-K,V_i+K)$的值

然后扫描这个点的所有子树, 扫描完毕后, 再次记录$B.query(V_i-K,V_i+K)$的值并减去之前的值

最后的值就是当前点的子树对当前点的贡献, 直接将其记录即可

最后将每个点的贡献全部加起来就是答案

特别地, 数值的范围是$10^9$, 所以我们需要先用一个map记录所有会用到的数并将其按顺序离散化处理

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int ha=1e9+7;
const int N=3e5+5;

ll B[N*2];
void U(int i,ll x){++i;while(i<N*2)B[i]+=x,i+=i&-i;}
ll Q(int i){++i;ll r=0;while(i)r+=B[i],i-=i&-i;return r;}

ll A[N],L[N],R[N],fa[N],ans[N],n,K,a,l,r;
vector<int>G[N];
vector<int>WW;
map<int,int>Z;

void readll(ll &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

ll dfs(int u){
    ll res=0;
    res-=Q(R[u])-Q(L[u]); //old sum
    U(A[u],1);
    for(auto &v:G[u]){
        dfs(v);
        res+=ans[v];
    }
    res+=Q(R[u])-Q(L[u]); //now sum
    return ans[u]=res;
}

int main(){

    readll(n);
    readll(K);

    for(int i=1;i<=n;++i){
        readll(A[i]);
        L[i]=A[i]-K;
        R[i]=A[i]+K;
        Z[L[i]]=Z[A[i]]=Z[R[i]]=1;
    }
    int cnt=0;
    for(auto &i:Z)i.second=++cnt;
    for(int i=1;i<=n;++i){
        L[i]=Z[L[i]];
        A[i]=Z[A[i]];
        R[i]=Z[R[i]];
    }
    for(int i=2;i<=n;++i){
        readll(fa[i]);
        G[fa[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=n;++i)
        printf("%lld\n",ans[i]);
    return 0;

}

D: 文本修正

没啥好说的, 直接读取每个独立的字符串并特判其是否等于"henan", 是就替换即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int ha=1e9+7;
const int N=1e6+5;

ll A[505][505];
ll n,m;
vector<int>V;
char s[1000];

int main(){
    char c;
    while(1){
        while((c=getchar())==' ')putchar(' ');
        if(~c&&c!='\r'&&c!='\n'){
            s[0]=c;
            scanf("%s",s+1);
            if(string("henan")==s)printf("Henan");
            else printf(s);
        }else break;
    }
    return 0;

}

E: 咕咕的的复复读读机机

直接找出出现次数最多的那个数即可

#include<bits/stdc++.h>
using namespace std;


int A[1025];

int main()
{
    int n,x;
    cin>>n;
    while(n--){
        cin>>x;
        A[x]++;
    }
    x=0;
    for(int i=1;i<=100;++i)
        if(A[x]<A[i])x=i;

    printf("%d\n",x);
}

F: 咕咕的计数题 II

首先分析性质, 假设$a=7$, 那么$7/1=7, 14/2=7, 15/2=7.5, 21/3=7, 22/3=7.33, 23/3=7.66 $ ...

也就是说这是一个等差数列, 直到 $49/7=7$ 为止, 也就是$a^2$, 不难发现大于 $ a^2 $的数一定有解

所以我们把大于的部分特判掉直接计入答案, 然后加上一个等差数列再减去多加的部分即可

另外假设$F(a,l,r)$为答案的话, 显然$F(a,l,r) = F(a,0,r)-F(a,0,l-1)$, 这样可以忽略左端点, 少做一些特判

还有就是小心溢出(虽然我直接用了__int128过了就是了

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int ha=1e9+7;
const int N=1e6+5;

ll n,a,l,r;

void readll(ll &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

ll solve(ll a,ll r){
    if(a>r)return 0;
    ll ans=0;
    if((__int128)a*a<=r){
        ans+=r-a*a+1;
        r=a*a;
    }

    if((__int128)a*a>r){
        ll z=r/a;
        ans+=z*(z+1)/2;
        ll t=z*a+z-1;
        if(t>r)ans-=t-r;
    } else ans+=a*(a-1)/2;

    return ans;
}

int main(){

    //freopen("a.in","r",stdin);

    readll(n);

    while(n--){
        readll(a);
        readll(l);
        readll(r);

        ll ans=solve(a,r)-solve(a,l-1);
        printf("%lld\n",ans);

    }


    return 0;

}

H: 咕咕的搜索序列

从左向右扫描序列, 先忽略当前点 $A_i$ 对应的子树, 然后看下个点 $A_{i+1}$ 是否已经被忽略过

若没有, 直接暴力找 $LCA(A_i,A_{i+1})$ 在 $A_i$ 那侧的儿子 $P$, 然后忽略 $P$ 的整棵子树即可

而如果$A_{i+1}$之前被忽略过, 答案一定是不合法的

正确性证明:

  1. 由题意可得, 假设要写出一个点x, 那么x的所有后代一定已经被写出过或被忽略了(儿子永远比父亲先写出)
  2. 如果上次访问的点是x, 那么在不考虑忽略额外的点的情况下, y一定是x的父亲对应子树上的叶子节点(由题意显然可得)
  3. 考虑忽略父亲以外的点, 那么y可以是x的父亲对应子树上的任何节点, 只要忽略掉y的子树即可(当然, 除了y自身)
  4. 考虑忽略父亲, 那么此时直接忽略掉父亲的子树上所有未被写出过的点, y将可以是x的"父亲的父亲"对应子树上的任何节点(从2,3可以得到)
  5. 由4推广得到, 只要x向上不断忽略父亲对应的子树, y一定可以被合法写出, 除非y已经被忽略

复杂度证明

首先证明忽略子树的操作是均摊O(1)的

不难发现我们每次忽略某个点都一定会忽略整棵子树

所以我们遇到被忽略的点就可以直接跳过并忽略下一棵子树了

显然每个点最多只会做一次忽略, 所以复杂度是O(n+m), 因为是树所以总体复杂度是O(n)

然后证明LCA部分的复杂度是均摊O(1)的

暴力求LCA的复杂度其实就是求LCA时每个点会被"经过"次数的总和

求过LCA后, 上个点那侧的子树会被全部忽略, 所以显然经过次数不会再增加了(仅本次+1)

而另一侧的那个点, 在下一次求LCA后仍然是本侧的子树被忽略

但只有在LCA以下的那些点才会经过次数+1(且被忽略), LCA的祖先不会被忽略也不会被经过

到此时不难发现, 每个点最多只会被经过两次, 一次是作为"目标点"那边找LCA(不被忽略), 另一次是作为"出发点"那边找LCA(被忽略)

特别地, LCA本身可能会被"经过"多次, 但由于是单点, 且每次求LCA只会有一个LCA, 所以均摊后的复杂度仍然是O(1)

理论上, 倍增或ST之类的东西来预处理求LCA也是可行的, 但是由于巨大的常数和空间开销反而容易出现MLE和TLE

总结: 暴力出奇迹(划)

什么那LCA怎么求? 把深度暴力对齐然后不断暴力找父亲就好了

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int ha=1e9+7;
const int N=1e6+5;

void readll(ll &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

void readint(int &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

struct node{node *t;int v;}E[N];
node *G[N];
int D[N],V[N],B[N],fa[N];

void dfs(int u,int d){
    D[u]=d;
    for(node *vv=G[u];vv;vv=vv->t)
        dfs(vv->v,d+1);
}

void rush(int u){
    for(node *vv=G[u];vv;vv=vv->t)
        if(!V[vv->v])rush(vv->v);
    V[u]=1;
}

int get(int x,int y){

    while(D[x]<D[y])y=fa[y];
    while(D[x]>D[y])x=fa[x];

    while(fa[x]!=fa[y])x=fa[x],y=fa[y];
    return x;

}

int main(){

    ll T,n,m,ttt;
    readll(T);

    while(T--){
        readll(n); readll(m);
        for(int i=1;i<=n;++i)G[i]=0,V[i]=0;
        for(int i=2;i<=n;++i){
            readint(fa[i]);
            E[i].t=G[fa[i]]; E[i].v=i;
            G[fa[i]]=E+i;
        }
        dfs(1,0);

        int ans=1;

        for(int i=1;i<=m;++i)readint(B[i]);
        for(int i=1;i<=m;++i){
            if(!V[B[i]]){
                rush(B[i]);
                if(i>1){
                    int x=get(B[i-1],B[i]);
                    rush(x);
                }
            } else {
                ans=0;
                break;
            }
        }

        puts(ans?"NOT BAD":"BAD GUGU");
    }

}

I: Childhood dream

暴力枚举每一个状态然后用猜测串不断删掉不符合条件的状态即可, 想办法压压常剪剪枝就过了

sbzdw把输出的前导零吃了结果场上并没有过, 太菜了

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int ha=1e9+7;
const int N=1e6+5;

void readll(ll &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

void readint(int &x){
    char s=getchar();
    while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
    while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}

struct node{
    int v;
    node *nxt;
    node(){}
}*S,g[10000000]; int tot;

//int f[1000][1000],tot;

int now,n,m;
int V[10];
/*
int culc(int x,int y){
    int cnt=0;
    if(x%10==y%10)++cnt; x/=10; y/=10;
    if(x%10==y%10)++cnt; x/=10; y/=10;
    if(x%10==y%10)++cnt;
    return cnt;
}
*/
void dfs(int i){
    if(i==m){
        //assert(now>=0);
        //    printf("%d\n",now);
        g[tot].nxt=S;
        g[tot].v=now;
        S=g+tot++;
        return;
    }
    for(int x=0;x<=9;++x){
        if(!V[x]){
            V[x]=1;
            now=now*10+x;
            dfs(i+1);
            now/=10;
            V[x]=0;
        }
    }
}

void init(){/*
    for(int i=0;i<1000;++i){
        for(int j=i;j<1000;++j)
            f[i][j]=f[j][i]=culc(i,j);
    }*/
    readint(n);readint(m); S=0; now=0;
    dfs(0);
    g[tot].nxt=S;
    S=g+tot++;
}

int judge(int x,int y){
    int cnt1=0,cnt2=0;
    int C1[10],C2[10];
    for(int i=0;i<=9;++i)C1[i]=C2[i]=0;
    for(int i=1;i<=m;++i){
        if(x%10==y%10)++cnt1;
        else ++C1[x%10],++C2[y%10];
        x/=10; y/=10;
    }
    for(int i=0;i<=9;++i)cnt2+=min(C1[i],C2[i]);
    return cnt1*100+cnt2;
}

int32_t main(){

    init();
    //int ww=0;
    for(int i=1,md,y,x;i<=n;++i){
        readint(md);readint(x);readint(y);
        node *fa=S;
        while(fa->nxt){
            node *now=fa->nxt;
            if(judge(now->v,md)!=x*100+y){
                fa->nxt=now->nxt;//++ww;
                continue;
            }
            fa=fa->nxt;
        }
    }
    //cout<<ww<<" "<<tot<<endl;
    printf(((string)"%0"+(char)('0'+m)+"d\n").c_str(),S->nxt->v);
}

评论

1
1234
1
1234

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

Server time: 2024-09-22 03:40:40