鹏鹏的旧OI博客

高二及以前的哦,只剩文字了,图片、附件等都没了



YZOI20170606模拟

老师最近给的题目都是好高级的样子呀,都是一眼题!(一眼看去就不会的题…………)


奶牛观光

给一张n个点m条边的有向图G,寻找出一条闭合的点a->b->c->...->a就是从某点出发绕一圈的路径,使经过的点的点权和与边权和比值最大,输出最大值。
一开始做,我就没想到正道上。直接上暴力。(出题人坏坏的,暴力分才10分)
从某个点出发绕一圈,至于是哪一个点呢,这是无所谓的,因为这就是一个环嘛,哪个点出发都一样。假设答案是ans,那么ans满足\( ans >= sum_{i}{e[i]} / sum_{i}{w[i]} \),其中e[i]表示点权,w[i]表示边权,\( sum_{i}{e[i]} / sum_{i}{w[i]} \)表示任意一个环的点权与边权比值,对原式进行变形。\( ans × sum_{i}{w[i]} >= sum_{i}{e[i]} \),\( sum_{i}{(w[i]×ans)} >= sum_{i}{e[i]} \),\( sum_{i}{ ( w[i]×ans-e[i]} ) >= 0 \)。所以假设枚举一个可能解k时,如果k能满足上面那个式子,那么k就小于等于ans,否则就大于ans。那么如何判断上面的式子是否成立呢,可以令一个新的图G',使新图的边权都变成w[i]×k-e[i],这样就可以通过spfa判断是否存在负权回路来实现判断,k可以二分答案得到。


派遣

给一棵树,每个节点有一个权值和一个代价,要求从这棵树中选出一棵子树,再从子树上选出若干个节点,使得这些节点的代价和不大于给定值m,求:子树的根节点的权值乘上选出的节点个数的最大值。
在看到数据范围以前,我还以为是道树型动态规划的题目。。。
主席树,有辣么厉害嘛。。这又是一道主席树可以做的题目。。
先求出dfs序,离散化每个点的代价,然后根据dfs序用主席树维护1->i每个区间的代价和,然后枚举每个节点来充当子树根节点,然后在主席树里找出这个子树所控制的点中代价和不大于m的点的个数,乘一下就是答案了。


最勇敢的机器人

有n件物品,每件物品的价值和重量为Vi、Wi,载重为wmax的包,某一些物品不能一起取,比如(a和b,b和c),这样一来a和c也不能取,问最大价值。
这题比较是水了,一遍过,并查集玩一玩就AC了。


奶牛观光代码

//暴力
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1010];
struct Edge{
    int v,w,nxt;
}edge[5010];
int head[1010],tot;
void addedge(int u,int v,int w){
    edge[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
double ans=0;
int s,v[1010];
void dfs(int now,int sumf,int sumw){
    v[now]++;
    if(now==s&&sumw){
        if((double)sumf/sumw>ans)ans=(double)sumf/sumw;
        v[now]--;
        return;
    }
    for(int i=head[now];i;i=edge[i].nxt)
        if(v[edge[i].v]<2)dfs(edge[i].v,sumf+(v[edge[i].v]==0)*f[edge[i].v],sumw+edge[i].w);
    v[now]--;
}
int main(){
    freopen("sightsee.in","r",stdin);
    freopen("sightsee.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&f[i]);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    for(s=1;s<=n;++s)dfs(s,f[s],0);
    printf("%.2f",ans);
    return 0;
}

//AC
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1010];
struct Edge{
    int v,w,nxt;
}edge[5010];
int head[1010],tot;
void addedge(int u,int v,int w){
    edge[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
queue<int> q;
double dis[1010];
int cnt[1010];
bool inQue[1010];
bool SPFA(double k){
    memset(cnt,0,sizeof(cnt));
    memset(inQue,0,sizeof(inQue));
    for(int i=1;i<=n;++i)dis[i]=1<<20;
    while(!q.empty())q.pop();
    q.push(1);inQue[1]=1;dis[1]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        inQue[u]=0;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(dis[v]>dis[u]+k*edge[i].w-f[v]){
                dis[v]=dis[u]+k*edge[i].w-f[v];
                if(!inQue[v]){
                    if(cnt[v]==n)return 1;
                    q.push(v);inQue[v]=1;cnt[v]++;
                }
            }
        }
    }
    return 0;
}
int main(){
    freopen("sightsee.in","r",stdin);
    freopen("sightsee.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&f[i]);
    for(int i=1;i<=m;++i){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    double L=0,R=10000,mid;
    while(L+0.00001<R){
        mid=(L+R)/2;
        if(SPFA(mid))L=mid;
        else R=mid;
    }
    printf("%.2f",L);
    return 0;
}

派遣代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
struct Ninja{int money,lead;}ninja[N];
struct Edge{int v,nxt;}ed[N];
int head[N];
int mon[N],lea[N],pos[N];
int moncnt;
int fir[N],sec[N],dfnt;
void dfs(int u){
    ninja[fir[u]=++dfnt]=(Ninja){pos[u],lea[u]};
    for(int i=head[u];i;i=ed[i].nxt)
        dfs(ed[i].v);
    sec[u]=dfnt;
}
struct treeNode{int l,r,cnt;long long sum;}tree[N*20];
int tree_cnt,root[N];
void update(int &x,int l,int r,int k){
    tree[++tree_cnt]=tree[x];x=tree_cnt;
    tree[x].sum+=mon[k];tree[x].cnt++;
    if(l==r)return;
    int mid=l+r>>1;
    if(k<=mid)update(tree[x].l,l,mid,k);
    else update(tree[x].r,mid+1,r,k);
}
int query(int x,int y,int l,int r,int k){
    if(l==r)return min(k/mon[l],tree[y].cnt-tree[x].cnt);
    int mid=l+r>>1;long long tmp=tree[tree[y].l].sum-tree[tree[x].l].sum;
    if(k<=tmp)return query(tree[x].l,tree[y].l,l,mid,k);
    else return tree[tree[y].l].cnt-tree[tree[x].l].cnt+query(tree[x].r,tree[y].r,mid+1,r,k-tmp);
}
int main(){
    freopen("dispatching.in","r",stdin);
    freopen("dispatching.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        int b;scanf("%d%d%d",&b,&mon[i],&lea[i]);
        ed[i]=(Edge){i,head[b]};head[b]=i;
        pos[i]=mon[i];
    }
    sort(mon+1,mon+n+1);
    moncnt=unique(mon+1,mon+n+1)-mon-1;
    for(int i=1;i<=n;++i)pos[i]=lower_bound(mon+1,mon+moncnt+1,pos[i])-mon;
    dfs(ed[head[0]].v);
    for(int i=1;i<=n;++i){
        root[i]=root[i-1];
        update(root[i],1,moncnt,ninja[i].money);
    }
    long long ans=0;
    for(int i=1;i<=n;++i)ans=max(ans,(long long)lea[i]*query(root[fir[i]-1],root[sec[i]],1,moncnt,m));
    cout<<ans;
    return 0;
}

最勇敢的机器人代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
class UFS{
private:
    int fat[N];
public:
    void init(int n){while(n--)fat[n]=n;}
    int find(int x){return x==fat[x]?x:fat[x]=find(fat[x]);}
    void merge(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        fat[x]=y;
    }
}ufs;
struct Thing{int v,w;}g[N];
int n,wmax,m,v[N],w[N],cnt,index[N],f[N];
vector<int> a[N];
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    while(~scanf("%d%d%d",&n,&wmax,&m)){
        ufs.init(n);cnt=0;memset(index,0,sizeof(index));memset(f,0,sizeof(f));
        for(int i=1;i<=n;++i)scanf("%d%d",&g[i].v,&g[i].w);
        for(int i=1;i<=m;++i){
            int a,b;scanf("%d%d",&a,&b);
            ufs.merge(a,b);
        }
        for(int i=1;i<=n;++i){
            int x=ufs.find(i);
            if(!index[x])a[index[x]=++cnt].clear();
            a[index[x]].push_back(i);
        }
        for(int i=1;i<=cnt;++i)
            for(int j=wmax;j;--j)
                for(int k=0;k<a[i].size();++k)
                    if(j>=g[a[i][k]].w)f[j]=max(f[j],f[j-g[a[i][k]].w]+g[a[i][k]].v);
        printf("%d\n",f[wmax]);
    }
    return 0;
}

题目