NOIP模拟赛20161016R2

Problem 1 护花(flower.cpp/c/pas)

【题目描述】

约翰留下他的N(N<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚．牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间．写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．

【输入格式】

第1行输入N，之后N行每行输入两个整数Ti和Di

【输出格式】

一个整数，表示最小数量的花朵被吞食

【样例输入】

3 1

2 5

2 3

3 2

4 1

1 6

【样例输出】

【样例解释】

约翰用6，2，3，4，1，5的顺序来运送他的奶牛

POJ3262

yy各种贪心

国王游戏白做了，拿出相邻两个考虑.....

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+;

typedef long long ll;

inline ll read(){

    char c=getchar();ll x=,f=;

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

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

    return x*f;

}

int n;

struct cow{

    ll t,w;

    bool operator < (const cow &r)const{return t*r.w<r.t*w;}

}a[N];

ll sum=,ans=;

int main(){

    //freopen("flower.in","r",stdin);

    //freopen("flower.out","w",stdout);

    n=read();

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

        a[i].t=*read();a[i].w=read();

        sum+=a[i].w;

    }

    sort(a+,a++n);

    for(int i=;i<=n;i++){sum-=a[i].w;ans+=sum*a[i].t;}

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

}

Problem 2 修剪草坪(mowlawn.cpp/c/pas)

【题目描述】

在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，
新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N
(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，
奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。
靠近的奶牛们很熟悉，因此，如果FJ安排超过K（1<=K<=N）只连续的奶牛，那么，这些奶牛就会罢工
去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中
没有连续的超过K只奶牛。

【输入格式】
* 第一行：空格隔开的两个整数N和K
* 第二到N+1行：第i+1行有一个整数E_i

【输出格式】
* 第一行：一个值，表示FJ可以得到的最大的效率值。

【样例输入】

5 2

输入解释：

FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是

他不能选取超过2只连续的奶牛

【样例输出】

FJ可以选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。

codevs4654

想了一个DP

f[i][j]表示1到i连续选了j个的最大效率

f[i][j]可以转移到f[i+1][j+1](+e[i])或者f[i+1][0]

第一维可以滚动掉，但是时间还是n^2，可以拿60分

然后就开始发现每次就是弹出f[k]插入新f[0]其他f[j]变成f[j+1]只不过加了e[i]，开始用优先队列乱搞nlogn，没挑出来

正解：

f[i]表示i不选且之前的选取都合法情况下答案损失的最小值

则f[i]=f[j]+e[i]（i-j<=k）这个显然可以用单调队列来维护

单调队列保存下标，头到尾f递增

//

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+;

typedef long long ll;

const ll INF=1e18;

inline int read(){

    char c=getchar();int x=,f=;

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

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

    return x*f;

}

int n,k,w[N];

ll f[N];

void dp(){

    f[]=;

    for(int i=;i<=n;i++) f[i]=-INF;

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

        int tmp=f[];

        f[]=max(f[],f[k]);

        for(int j=k;j>=;j--){

            f[]=max(f[],f[j-]);

            f[j]=f[j-]+w[i];//printf("%d %d %d\n",i,j,f[j]);

        }

        f[]=tmp+w[i];//printf("%d 0 %d\n",i,f[0]);

        //printf("%d 1 %d\n",i,f[1]);

    }

}

int main(){

    freopen("mowlawn.in","r",stdin);

    freopen("mowlawn.out","w",stdout);

    n=read();k=read();

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

    dp();

    ll ans=-INF;

    for(int i=;i<=k;i++) ans=max(ans,f[i]);

    printf("%lld",ans);

}

//AC

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+;

typedef long long ll;

const ll INF=1e18;

inline int read(){

    char c=getchar();int x=,f=;

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

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

    return x*f;

}

int n,k,w[N];

ll f[N],sum=;

int q[N],head=,tail=;

void dp(){

    q[++tail]=;

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

        while(i-q[head]->k) head++;

        f[i]=f[q[head]]+w[i];

        while(f[q[tail]]>=f[i]&&head<=tail) tail--;

        q[++tail]=i;

        //printf("f %d %d\n",i,f[i]);

    }

}

int main(){

    //freopen("mowlawn.in","r",stdin);

    //freopen("mowlawn.out","w",stdout);

    n=read();k=read();

    for(int i=;i<=n;i++) w[i]=read(),sum+=w[i];

    dp();

    ll mn=INF;

    for(int i=n-k;i<=n;i++) mn=min(mn,f[i]);

    printf("%lld",sum-mn);

}

Problem 3 虫洞(wormhole.cpp/c/pas)

【题目描述】

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

【输入格式】

* Line 1: 一个整数 F, 表示农场个数。

* Line 1 of each farm: 三个整数 N, M, W。

* Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。

* Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。

【输出格式】

* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。

【样例输入】

3 3 1

1 2 2

1 3 4

2 3 1

3 1 3

3 2 1

1 2 3

2 3 4

3 1 8

【样例输出】

YES

POJ3259

负环

spfa

貌似题意不明确，没表达清楚是不是回到过去的必须是起点

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,M=1e4,INF=1e9;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

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

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

    return x*f;

}

int T,n,m,mm,u,v,w;

struct edge{

    int v,ne,w;

}e[M];

int cnt=,h[N];

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

}

int d[N],inq[N],num[N];

bool spfa(){

    queue<int> q;

    memset(inq,,sizeof(inq));

    memset(num,,sizeof(num));

    for(int i=;i<=n;i++) d[i]=INF;

    q.push();inq[]=;d[]=;

    while(!q.empty()){

        int u=q.front();q.pop();inq[u]=;

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v,w=e[i].w;

            if(d[u]<INF&&d[v]>d[u]+w){

                d[v]=d[u]+w;

                if(!inq[v]){q.push(v);inq[v]=;if(++num[v]>=n) return false;}

            }

        }

    }

    return true;

}

int main(){

    freopen("wormhole.in","r",stdin);

    freopen("wormhole.out","w",stdout);

    T=read();

    while(T--){

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

        cnt=;

        memset(h,,sizeof(h));

        for(int i=;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);ins(v,u,w);}

        for(int i=;i<=mm;i++){u=read();v=read();w=read();ins(u,v,-w);}

        if(!spfa()) printf("YES\n");

        else printf("NO\n");

    }

}

巴特西

NOIP模拟赛20161016R2

最新文章

热门文章