【Educational Codeforces Round 19】

时间：2024-01-21 11:33:03

这场edu蛮简单的……

连道数据结构题都没有……

A.随便质因数分解凑一下即可。

#include<bits/stdc++.h>

#define N 100005

using namespace std;

int a[N],cnt,k,x,n;

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;k>&&n>;i++)

    for(;k>&&n%i==;--k,n/=i)a[++cnt]=i;

    if(n==){puts("-1");return ;}

    for(int i=;i<=cnt;i++)printf("%d ",a[i]);

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

}

B.读入的时候贪心选一下即可。

#include<bits/stdc++.h>

#define inf 1000000007

using namespace std;

int n,q,ans,mmp=inf;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        int x;scanf("%d",&x);

        if(x>)ans+=x;

        if(x%!=)mmp=min(abs(x),mmp);

    }

    if(ans%==)ans-=mmp;

    printf("%d\n",ans);

}

C.贪心

#include<bits/stdc++.h>

#define N 100010

using namespace std;

char a[N],t[N],ans[N],s[N],minv[N];

int main(){

    scanf("%s",s);int len=strlen(s),m=,k=;

    minv[len]='z'+;minv[len-]=s[len-];

    for(int i=len-;i>=;i--)minv[i]=min(minv[i+],s[i]);

    for(int i=;i<len;i++){

        t[m++]=s[i];

        while(m&&t[m-]<=minv[i+])ans[k++]=t[--m];

    }

    ans[k]=;

    printf("%s\n",ans);

}

D.扫一下树，计算可能的出现次数（值域过大用map比较好）

然后总共的减去sum即为答案。

#include<bits/stdc++.h>

#define N 100010

#define inf 2147483640

using namespace std;

int n,val[N],lc[N],rc[N],fa[N],ans;

map<int,int> mp;

void dfs(int u,int ql,int qr){

    if(u==-)return;if(ql>qr)return;

    if(ql<=val[u]&&val[u]<=qr)ans+=mp[val[u]];

    dfs(lc[u],ql,min(val[u]-,qr));

    dfs(rc[u],max(val[u]+,ql),qr);

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    n=read();

    for(int i=;i<=n;i++){

        val[i]=read();lc[i]=read();rc[i]=read();

        mp[val[i]]++;fa[lc[i]]=fa[rc[i]]=i;

    }

    for(int i=;i<=n;i++)if(!fa[i])dfs(i,,inf);

    printf("%d\n",n-ans);

}

E.正解应该是dp，然而记忆化搜索还是能水过去……

#include<bits/stdc++.h>

#define N 100010

using namespace std;

int n,a[N],f[][N];

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int dfs(int u,int k){

    if(u>n)return ;

    if(k>)return dfs(u+a[u]+k,k)+;

    if(f[k][u])return f[k][u];

    else return f[k][u]=dfs(u+a[u]+k,k)+;

}

int main(){

    n=read();for(int i=;i<=n;i++)a[i]=read();

    int q=read();

    while(q--){

        int u=read(),v=read();

        printf("%d\n",dfs(u,v));

    }

}

F.比较裸的单调队列优化。

#include<bits/stdc++.h>

#define inf 1000000000000000000ll

#define N 5005

using namespace std;

typedef long long ll;

int n,m,sum,a[N],q[N],l,r;

ll dp[N][N],s[N];

struct Node{int x,y;}b[N];

bool operator <(Node a,Node b){return a.x<b.x;}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    n=read();m=read();

    for(int i=;i<=n;i++)a[i]=read(),dp[][i]=inf;

    sort(a+,a+n+);

    for(int i=;i<=m;i++){b[i].x=read();b[i].y=read();sum+=b[i].y;}

    if(sum<n){puts("-1");return ;}sort(b+,b+m+);

    for(int i=;i<=m;i++){

        for(int j=;j<=n;j++)s[j]=s[j-]+abs(a[j]-b[i].x);

        l=;r=;

        for(int j=;j<=n;j++){

            if(l<=r&&q[l]<j-b[i].y)l++;

            while(l<=r&&dp[i-][j]-s[j]<=dp[i-][q[r]]-s[q[r]])r--;

            q[++r]=j;if(l<=r)dp[i][j]=dp[i-][q[l]]-s[q[l]]+s[j];

            else dp[i][j]=inf;

        }

    }

    cout<<dp[m][n]<<endl;

}

总结：这场题目其实没多大意思……但是思维题比较多。

相关文章