BruceJay's Blog

Bruce贪心噩梦一场

| Comments

扯淡

Bruce的解法永远都是那么低端。

Problem and Solution

flight

[Description]

[Solution]

贪心策略很显然,令飞机上的奶牛尽量早下飞机,这样可以满足更多奶牛的要求。
同J房的同学都想到非常高端的线段树(这个我还不会)解法,klogk的复杂度。
我只会低端的kc的有序数组的合并,时间复杂度上被完爆。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int K = 50100;
const int N = 10100;
const int M = 110;
int f[N][M]; int g[N];
int l[K]; int r[K]; int x[K];
int tmp[M]; int n,m,k,ans=0,tot=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Merge(int a[],int& lena,int b[],int lenb)
{
    int c[M]; memset(c,0,sizeof(c));
    int pa=1,pb=1;
    for(int i=1;i<=min(lena+lenb,m);i++){
        if(pa>lena) c[i]=b[pb++];
        else if(pb>lenb) c[i]=a[pa++];
        else if(a[pa]<b[pb]) c[i]=a[pa++];
        else c[i]=b[pb++];
    }
    lena=min(lena+lenb,m);
    memcpy(a,c,sizeof(c));
}

void Del(int t)
{
    int c[M]; int cnt=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=tot;i++)
        if(tmp[i]!=t) c[++cnt]=tmp[i];
    tot=cnt; memcpy(tmp,c,sizeof(c));
}

int Solve()
{
    int res=0; int b[M];
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    for(int i=1;i<=k;i++) if(l[i]<r[i]){
        for(int j=1;j<=min(x[i],m);j++) b[j]=r[i];
        Merge(f[l[i]],g[l[i]],b,min(x[i],m));
    }
    for(int i=1;i<=n;i++){
        Del(i); int last=tot;
        Merge(tmp,tot,f[i],g[i]);
        res+=tot-last;
    }
    return res;
}

int main()
{
    freopen("flight.in","r",stdin);
    freopen("flight.out","w",stdout);
    k=read(); n=read(); m=read();
    for(int i=1;i<=k;i++){
        l[i]=read(); r[i]=read(); x[i]=read();
    }
    ans+=Solve();
    for(int i=1;i<=k;i++){
        l[i]=n-l[i]+1; r[i]=n-r[i]+1;
    }
    ans+=Solve();
    printf("%d",ans);
    return 0;
}

lot

[Description]

给定n个点和这n个点的度数,求一张满足条件无向图。

[Hint]

n<=500,数据保证有解

[Solution]

每次找出当前度数最大的点u,将其度数变为0(与其他点连d[u]条边,我选的是当前度数第2~d[u]+1大的点),证明在此不赘述。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;
int d[N]; int a[N]; bool f[N][N];
bool cmp(int x,int y)
{return d[x]>d[y];}
int n,m=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("lot.in","r",stdin);
    freopen("lot.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) d[i]=read();
    for(int i=1;i<=n;i++) m+=d[i]; m>>=1;
    for(int i=1;i<=n;i++) a[i]=i;
    for(int i=1;i<=n;i++){
        sort(a+i,a+n+1,cmp);
        for(int j=i+1;d[a[i]];j++){
            printf("%d %d\n",a[i],a[j]);
            d[a[i]]--; d[a[j]]--;
        }
    }
    return 0;
}

shopping

[Description]

[Solution]

连线段树都不会的Bruce,怎可能会最小树形图呢?先贴一发题解:
很显然一个物品买了还是没买是有很大差别的,所以考虑把每类需要的物品拆成两份,第一份包含该类的一个物品,第二份包含该类的剩余物品。
显然第二份物品一定可以享受到它能享受到的最好的优惠,但是所有物品的第一份,我们需要一个拓扑方案,使得总价格最少
而且最后的方案的拓扑图一定是一个树形结构的,因为每个物品的价格唯一,所以肯定只有唯一的前驱。
那么此时问题就得以简化,不是求一个图的,而是求一棵树,使得边权总和尽量小。
看到这,也许你会马上欣喜地去敲个最小生成树,但是很不幸的是,这些边都是有向边,不能套用该算法。
但是值得庆幸的是,这个是有算法的,叫最小树形图。

记pre[i]为连到i点所有前驱中边权最小的一个。
可以理解如果没有环,那么这个方案即为所求。
如果有环肯定就有bug,因为点显然不连通。
那么随便找个环。
先默认环上的边都加入答案(后面重构边权会导致最后方案把环上一条边去掉)。
然后缩环,记环为v,环上点为vv,环外点为u,重构边权
(v,u)=min{(vv,u)}
(u,v)=min{(u,vv)-(pre[vv],vv)}(这个使得最后方案肯定去掉环上一条边,最后就不存在环了)
这样缩环后重新找pre,直到不存在环。
这样重新构图后,虽然开始有环,但重构的边权会使最后删掉环上的某条边。
保证了最后肯定是一个树形图,而且还是最小的。
这道题比较特殊,还要设一个虚点,以虚点为根即可。

这道题的难点,就在于拆点和模型的发现,并套用最小树形图的算法。

repair

[Description]

[Solution]

按照t2排序,记录now为当前抢修所用时间:
若now+t1[i]<=t2[i],抢修建筑i,now+=t1[i]。
若now+t1[i]>t2[i],则将其与之前抢修的所有建筑中t1最大的j对比,看是否能用建筑i替换建筑j(t1[i]<t1[j]),可以的话就替换,now-=(t1[j]-t1[i])。

[Code]

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 150100;
struct node{ll t,ed;}a[N];
bool cmp(const node& a1,const node& a2)
{return a1.ed<a2.ed;}
priority_queue<int> q;
int n,ans=0;

inline ll read()
{
    ll t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ll)ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("repair.in","r",stdin);
    freopen("repair.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i].t=read(); a[i].ed=read();
    }
    sort(a+1,a+n+1,cmp);
    ll now=0;
    for(int i=1;i<=n;i++){
        if(now+a[i].t<=a[i].ed){
            now+=a[i].t; ans++;
            q.push(a[i].t);
        }
        else{
            if(q.empty()) continue;
            if(a[i].t<q.top()){
                now+=a[i].t-q.top();
                q.pop(); q.push(a[i].t);
            }
        }
    }
    printf("%d",ans); return 0;
}

Comments

comments powered by Disqus