hgoi#20190516

muronglin
muronglin 2019年05月16日
  • 在其它设备中阅读本文章

T1-Buying A House

给你一个长度为 n 的序列 a,给你目标房子 m,最多花的钱 k 如果 a[i]为 0,这座房子无法购买,否则可以购买,求能买的距离目标房子最近的房子,输出最小距离 两座房子之间距离为 10

解法

显然贪心的从目标房子开始左右扫就可以了

ac 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,lim,ans,a[110];
int main()
{
    scanf("%d%d%d",&n,&m,&lim);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;;i++)
    {
        if(m-i>=1)if(a[m-i]&&a[m-i]<=lim){ans=i;break;}
        if(m+i<=n)if(a[m+i]&&a[m+i]<=lim){ans=i;break;}
    }
    printf("%dn",ans*10);
    return 0;
}

T2-Find The Bone

一个长度为 n 的线段,线段上有 m 个坑,k 次操作,骨头一开始在 1,每次操作给定 x,y,交换 x,y,如果骨头掉到坑里,就会一直在那里,求最后骨头所在位置

解法

模拟一遍就好了 QAQ

ac 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,ans=1,a[1000010];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d",&x),a[x]=1;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        if(x==ans&&!a[x])ans=y;
        else if(y==ans&&!a[y])ans=x;
    }
    printf("%dn",ans);
    return 0;
}

T3-Bank Hacking

给定一棵带点权树,选出一个最佳的根节点,使得根节点的点权不变,它的儿子点权加 1,其余点点权加 2,并使最大点权最小,输出这个最小的最大点权

解法

暴力的对每一个点扫它所有的儿子,然后 check,设 ans 为原来的最大值,答案只可能是 ans,ans+1,ans+2,复杂度是 n +m

ac 代码

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}e[600010];
int n,cnt=0,res,ans=-0x3f3f3f3f,flg,x,y,a[300010],head[300010];
map<int,int>mp;
void add(){e[++cnt]={y,head[x]},head[x]=cnt,e[++cnt]={x,head[y]},head[y]=cnt;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),mp[a[i]]++,ans=max(ans,a[i]);
    res=ans+2;
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),add();
    for(int i=1;i<=n;i++)
    {
        flg=0;
        for(int j=head[i];j;j=e[j].next){mp[a[e[j].to]]--;if(a[e[j].to]==ans)flg=1;}
        if(!mp[ans])res=ans+1;
        if(ans==a[i]&&mp[ans]==1)
        {
            if(mp[ans-1])res=ans+1;
            else if(flg)res=ans+1;
            else{res=ans;break;}
        }
        for(int j=head[i];j;j=e[j].next)mp[a[e[j].to]]++;
    }
    printf("%dn",res);
    return 0;
}

T4-Police Stations

给定一棵树,树上有一些点是警察局,要求所有点到最近的警察局的距离不大于 d,求最多能删几条边

解法

建一个超级源连着所有警察局,或者一开始就把所有警察局压入队列,跑 bfs 如果这条边过去的点被访问过,那这条边就可以删除 bfs 的退出条件不是点有没有被搜过,而是边有没有被搜索和距离是否超过 d

ac 代码

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next,v;}e[600010];
struct Node{int num,d;};
int n,k,d,cnt=1,ans=0,x,y,head[300010],vis[300010],flg[300010],res[300010];
queue<Node>q;
void add(){e[++cnt]={y,head[x],0},head[x]=cnt,e[++cnt]={x,head[y],0},head[y]=cnt;}
void bfs()
{
    while(!q.empty())
    {
        Node u=q.front();
        q.pop();
        flg[u.num]=0;
        if(u.d>d)continue;
        for(int i=head[u.num];i;i=e[i].next)
        {
            if(e[i].v)continue;
            e[i].v=e[i^1].v=1;
            if(vis[e[i].to])res[++ans]=i/2;
            if(!flg[e[i].to])q.push({e[i].to,u.d+1}),flg[e[i].to]=vis[e[i].to]=1;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&d);
    for(int i=1;i<=k;i++)scanf("%d",&x),q.push({x,0}),vis[x]=1;
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),add();
    bfs(),printf("%dn",ans);
    for(int i=1;i<=ans;i++)printf("%d ",res[i]);
    return 0;
}

T5-Exam Cheating

muronglin 是个学渣,考试的时候,她一道题也不会做 她的左右桌分别是学霸 chhokmah 和学霸 lukelin,虽然学霸并不是题题都会做,但他们做了的题一定都对 现在 muronglin 想要作弊,但是为了不被监考员抓住,她最多偷看 p 次,一次能看连续的 k 道题 给定 n 和 la 和 lb,分别为题目总数,chhokmah 做出题目数和 lukelin 做出题目数,再给出两位学霸做出题目序列,问 muronglin 最多能偷看到几道题的答案

解法

可以看出是个 dp,设 dp[i][j][x][y]表示前 i 个问题,用 j 次机会,chhokmah 还能看 x 道题,lukelin 还能看 y 道题的最优值 转移时分情况讨论,如果都没有机会,分 4 种:都不偷看,偷看任意 1 位,偷看 2 位 如果任意 1 位没有机会,分 3 种:只偷看 1 位,偷看 2 位,重新开始偷看 2 位 如果都有机会,就顺着模拟

ac 代码

#include<bits/stdc++.h>
#define get(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,p,k,la,lb,ans=0,x,y=1,a[1010],b[1010],dp260;
int main()
{
    memset(dp,-0x3f,sizeof(dp)),dp00=0,scanf("%d%d%d",&n,&p,&k);
    scanf("%d",&la);FOR(i,1,la)scanf("%d",&x),a[x]=1;
    scanf("%d",&lb);FOR(i,1,lb)scanf("%d",&x),b[x]=1;
    if(pk>=2n){FOR(i,1,n)ans+=a[i]|b[i];printf("%dn",ans);return 0;}
    FOR(i,1,n)
    {
        x=y,y^=1,memset(dp[x],-0x3f,sizeof(dp[x]));
        FOR(j,0,p)FOR(ii,0,k)FOR(jj,0,k)if(!ii&&!jj)
        {
            get(dpx0,dpy0);
            get(dpxk-1,dpy0+a[i]);
            get(dpx0,dpy0+b[i]);
            get(dpxk-1,dpy0+(a[i]|b[i]));
        }
        else if(!ii)
        {
            get(dpx0,dpy0+b[i]);
            get(dpxk-1,dpy0+(a[i]|b[i]));
            get(dpxk-1,dpy0+(a[i]|b[i]));
        }
        else if(!jj)
        {
            get(dpxii-1,dpyii+a[i]);
            get(dpxii-1,dpyii+(a[i]|b[i]));
            get(dpxk-1,dpyii+(a[i]|b[i]));
        }
        else get(dpxii-1,dpyii+(a[i]|b[i]));
    }
    FOR(l,0,p)FOR(i,0,k)FOR(j,0,k)get(ans,dpxi);printf("%dn",ans);
    return 0;
}