CF595 Div31249A,1249B1,1249B2,1249C1,1249C2,1249D1,1249D2,1249E,1249F）题解

A：水题，先排序，有相连的输出2，否则输出1.

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>

#define mkp make_pair

#define pb push_back

#define fi first

#define se second

typedef long long ll;

const int INF=0x3f3f3f3f;

int q,n;

const int maxn=;

int a[maxn];

int main()

{

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;++i) scanf("%d",a+i);

        sort(a+,a++n);

        int cnt=;

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

        {

            if(a[i]-a[i-]==) {cnt=;break;}

        }

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

    }

    return ;

}

B1和B2: 水题:同一个循环里面的步数一样，O(N)跑一遍即可。

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>

#define mkp make_pair

#define pb push_back

#define fi first

#define se second

typedef long long ll;

const int INF=0x3f3f3f3f;

int q,n;

const int maxn=2e5+;

int p[maxn],cnt[maxn],vis[maxn];

int main()

{

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;++i) scanf("%d",p+i),cnt[i]=vis[i]=;

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

        {

            if(vis[i]) continue;

            int ans=,num=p[i];vis[i]=i;

            while(num!=i)

            {

                num=p[num];

                vis[num]=i;

                ans++;

            }

            cnt[i]=ans;

        }

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

            printf("%d%c",cnt[vis[i]],i==n?'\n':' ');

    }

    return ;

}

C1和C2: 水题：很显然>=n的最大的只要把n里面所有的3的幂去除，然后把剩下未选中的挑一个最小的且比去除之后的n大的加入答案就行。注意到样例里面给的最大的那个是3^38.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[];

void prework()

{

    a[]=;

    for(int i=;i<=;++i) a[i]=a[i-]*;

}

int q;

ll n,cn;

int main()

{

    prework();

    scanf("%d",&q);

    while(q--)

    {

        scanf("%lld",&n);

        ll ans=; cn=n;

        int flag=-,tmp=-,tt=;

        for(int i=;i>=;--i)

        {

            if(n==a[i]){ans=a[i];tt=;break;}

            if(a[i]<n){tmp=i+;break;}

        }

        if(tt){printf("%lld\n",ans);continue;}

        for(int i=tmp-;i>=;--i)

        {

            if(n==a[i]){ans+=a[i];tt=;break;}

            if(n>a[i]) {n-=a[i];ans+=a[i];}

            else flag=i;

        }

        if(tt){printf("%lld\n",ans);continue;}

        if(flag!=-)

        {

            for(int i=;i<flag;++i) ans-=a[i];

            ans+=a[flag];

        }

        else ans=a[tmp];

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

    }

    return ;

}

D1和D2:

D1可以暴力：set维护答案。

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>

#define mkp make_pair

#define pb push_back

#define fi first

#define se second

typedef long long ll;

const int INF=0x3f3f3f3f;

const int maxn=;

int k,n,cnt[maxn],vis[maxn];

struct Node{

    int l,r,id;

}p[maxn];

bool cmp(Node &a,Node &b){return a.r<b.r;}

vector<Node> v[maxn];

set<int> st;

int main()

{

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

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

    {

        scanf("%d%d",&p[i].l,&p[i].r);p[i].id=i;

        for(int j=p[i].l;j<=p[i].r;++j)

            v[j].push_back(Node{p[i].l,p[i].r,i}),cnt[j]++;

    }

    //for(int i=1;i<=200;++i) cout<<cnt[i]<<endl;

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

        sort(v[i].begin(),v[i].end(),cmp);

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

    {

        if(cnt[i]>k)

        {

            int nn=cnt[i]-k;

            for(int j=v[i].size()-;j>=&&nn;--j)

            {

                if(vis[v[i][j].id]) continue;

                st.insert(v[i][j].id),nn--;

                vis[v[i][j].id]=;

                for(int k=v[i][j].l;k<=v[i][j].r;++k)

                    cnt[k]--;

            }

        }

    }

    int len=st.size();

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

    set<int>::iterator it;

    for(it=st.begin();it!=st.end();++it)

        printf("%d ",(*it));

    puts("");

    return ;

}

D2用线段树。按照 r 从小到大排序。然后从i 1-n枚举，如果区间最大值<k,则加入该线段,否则该线段必须去掉，加入答案集合里面即可。

最后依次输出答案；

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int res[maxn],ans,s[maxn],add[maxn],x,cnt,k,n,Max;

struct Node{

    int l,r,id;

    bool operator<(const Node&p)const{

        return r^p.r?r<p.r:l<p.l;

    }

}a[maxn];

void pushdown(int l,int r,int rt)

{

    int mid=l+r>>;

    add[rt<<]+=add[rt],add[rt<<|]+=add[rt];

    s[rt<<]+=add[rt],s[rt<<|]+=add[rt];

    add[rt]=;

}

void update(int l,int r,int rt,int u,int v)

{

    if(l>v||r<u) return;

    if(l>=u&&r<=v)

    {

        s[rt]+=x,add[rt]+=x;

        return;

    }

    if(add[rt]) pushdown(l,r,rt);

    int mid=l+r>>;

    update(l,mid,rt<<,u,v);

    update(mid+,r,rt<<|,u,v);

    s[rt]=max(s[rt<<],s[rt<<|]);

}

void query(int l,int r,int rt,int u,int v)

{

    if(l>v||r<u) return;

    if(l>=u&&r<=v)

    {

        ans=max(ans,s[rt]);

        return;

    }

    if(add[rt]) pushdown(l,r,rt);

    int mid=l+r>>;

    query(l,mid,rt<<,u,v);query(mid+,r,rt<<|,u,v);

    s[rt]=max(s[rt<<],s[rt<<|]);

}

int main()

{

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

    Max=cnt=;

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

    {

        scanf("%d%d",&a[i].l,&a[i].r);a[i].id=i;

        Max=max(Max,a[i].r);

    }

    sort(a+,a++n);x=;

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

    {

        int u=a[i].l,v=a[i].r; ans=;

        query(,Max,,u,v);

        if(ans<k) update(,Max,,u,v);

        else res[++cnt]=a[i].id;

    }

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

    sort(res+,res++cnt);

    for(int i=;i<=cnt;++i)

        printf("%d%c",res[i],i==cnt?'\n':' ');

    return ;

}

E：水题：DP即可。设f[i][0],f[i][1]表示选择楼梯和电梯的状态，直接按照题意模拟就行。

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+;

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

int main()

{

    scanf("%d%d",&n,&c);--n;

    for(int i=;i<=n;++i) scanf("%d",a+i);

    for(int i=;i<=n;++i) scanf("%d",b+i);

    f[][]=1e9;

    for(int i=;i<=n;++i) f[i][]=min(f[i-][],f[i-][])+a[i],f[i][]=min(f[i-][]+c,f[i-][])+b[i];

    printf("0 ");for(int i=;i<=n;++i) printf("%d ",min(f[i][],f[i][])); puts("");

    return ;

}

F题：暴力贪心。n<=200直接暴力找从深度为n开始距离k以内的点集和。

贪心的取比较大的值即可。
将所有点按照深度从大到小排序，如果当前点点权a[i]大于0，则将距离为k以内的所有点减a[i]
代表取了当前点，为答案贡献a[i]
如果下面又扫到大于零的点权，说明那个点比这个大，于是取那个

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int n,k,a[maxn],t,nw,u,v,d[maxn],ans;

vector<int> g[maxn];

struct Edge{

    int v,nxt;

} edge[maxn<<];

int head[maxn],tot;

void AddEdge(int u,int v)

{

    edge[tot].v=v;edge[tot].nxt=head[u];head[u]=tot++;

    edge[tot].v=u;edge[tot].nxt=head[v];head[v]=tot++;

}

void dfs(int x,int fa)

{

    g[d[x]=d[fa]+].push_back(x);

    for(int i=head[x],j;~i;i=edge[i].nxt)

        if((j=edge[i].v)!=fa) dfs(j,x);

}

void dfs2(int x,int fa,int dep)

{

    a[x]-=nw;

    if(dep==k) return;

    for(int i=head[x],j;~i;i=edge[i].nxt)

        if((j=edge[i].v)!=fa) dfs2(j,x,dep+);

}

int main()

{

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

    for(int i=;i<=n;++i) scanf("%d",a+i),head[i]=-;

    for(int i=;i<n;++i) scanf("%d%d",&u,&v),AddEdge(u,v);

    dfs(,);

    for(int i=n;i;--i)

        for(int j=,sz=g[i].size(),x;j<sz;++j)

            if((x=a[g[i][j]])>) nw=x,ans+=x,dfs2(g[i][j],,);

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

    return ;

}

巴特西

CF595 Div31249A,1249B1,1249B2,1249C1,1249C2,1249D1,1249D2,1249E,1249F）题解

最新文章

热门文章