洛谷10月月赛Round.3

2023-01-30 20:37:09

Rank11:260=60+100+100

P2409 Y的积木

题目背景

Y是个大建筑师，他总能用最简单的积木拼出最有创意的造型。

题目描述

Y手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的k种取法的重量分别是多少。（只要任意更换一块积木，就视为一种不同的取法。如果多种取法重量总和一样，我们需要输出多次。）

输入输出格式

输入格式：

第一行输入两个整数，n,k，意义如题目所描述。

每组数据接下来的n行，第一个整数为mi，表示第i盒积木的数量，在同一行有mi个整数，分别表示每个积木的重量。

输出格式：

一行，重量最小的k种取法的重量，要求对于每个数据，从小到大输出

输入输出样例

输入样例#1：

输出样例#1：

3 4 5 5 6 6 7 7 7 7

说明

对于30%的数据：2<=mi<=10,1<=n<=10

对于50%的数据：2<=mi<=50,1<=n<=50

对于100%的数据：2<=mi<=100,1<=n<=100,1<=k<=10000,每个积木的重量为不超过100的正整数，所有mi的积大于等于k。本题不卡常。

先想的分组背包前k优值问题，可以把01背包的变形一下，二路归并改多路归并

后发现每个组就选一个，直接多路归并就行了

然后........就60分了，后面的全T了，复杂度O(n*k*logk)，k太大

正解：f[i][j]表示前i组重量为j的方案数，O(m[i])转移，复杂度O(n*最大重量*m)，本题重量很小

1.这样的DP用刷表法快；2.注意打印解的时候

//60 多路归并

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

const int N=,M=1e4+;

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 n,k,m[N],w[N][N];

int f[M];

struct data{

    int s,p;//s=f[a]+w[m][p]

    data(int x=,int y=):s(x),p(y){}

    bool operator <(const data &r)const{return s>r.s;}

};

void merge(int w[],int m){

    priority_queue<data> q;

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

        if(f[i]!=-) q.push(data(f[i]+w[],));

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

        else break;

    }

    for(int i=;i<=k&&!q.empty();i++){

        data now=q.top();q.pop();

        int s=f[i]=now.s;

        int p=now.p;

        if(p+<=m) q.push(data(s-w[p]+w[p+],p+));

        //printf("now %d %d\n",s,p);

    }

}

void dp(){

    memset(f,-,sizeof(f));

    f[]=;

    for(int i=;i<=n;i++) merge(w[i],m[i]);

}

int main(int argc, const char * argv[]) {

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

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

        m[i]=read();

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

        sort(w[i]+,w[i]++m[i]);

    }

    dp();

    for(int i=;i<=k;i++) printf("%d ",f[i]);

    return ;

}

//AC 递推

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

const int N=,M=;

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 n,sum,v=,m[N],w[N][N];

int f[N][M];void dp(){

    f[][]=;

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

        for(int j=;j<=v;j++) if(f[i-][j])

            for(int k=;k<=m[i];k++)

                f[i][j+w[i][k]]+=f[i-][j];

}

int main(int argc, const char * argv[]) {

    n=read();sum=read();

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

        m[i]=read();

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

        sort(w[i]+,w[i]++m[i]);

    }

    dp();

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

        if(f[n][i]>=sum){

            for(int j=;j<=sum;j++) printf("%d ",i);

            break;

        }else{

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

            sum-=f[n][i];

        }

    }

    return ;

}

P1371 NOI元丹

题目描述

小A打算开始炼NOI元丹（什么鬼），据说吃了可以提高NOI时的成绩。

是这么练的。元丹有三种元核，'N','O','I'。现有很多个这样原核，按顺序排成一行。炼元丹时，从左往右分别挑出'N','O','I'三个原核吞下。

现在他关心，有几种服用方式……且慢！

他觉得服用方式太少，以至于不能成仙。所以他可以通过某个途径，得到'N','O','I'的三种原核中的任意一个，至于哪一种由他决定。然后他将获得这个原核的插入到这一排原核中的任意位置（包括最前最后）。

现在你要知道，新的元核序列中能有多少种'N','O','I'的取出方式。子串的字母并不要求连续。

输入输出格式

输入格式：

第一行，一个整数N，表示字符串的长度。

第二行，一行字符串，里面只有只有'N','O','I'三种字母。

输出格式：

表示出最多可以提炼出来的NOI元丹的方案种数。

输入输出样例

输入样例#1：

5

NOIOI

输出样例#1：

说明

样例解释

他可以获取一个N元核，加到最前面。

NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI

~ ~~   | ~ ~  ~ | ~   ~~ |  ~~~   |  ~~  ~ |  ~  ~~

30%的数据N<=200

50%的数据N<=2000

100%的数据3<=N<=100000

很容易想到序列DP

f[i][0/1/2]表示i之前N NO NOI个数，d[i][0/1/2]表示i之后I OI NOI个数

可以很快计算在i到i+1之间加字母的贡献

tn=sum+d[i+1][1],ti=sum+f[i][1],to=sum+d[i+1][0]*f[i][0]

PS：其实加N的话一定在开始处，加I的话一定在结尾处最优

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

const int N=1e5+;

typedef long long ll;

int n;

char s[N];

ll f[N][],d[N][],sum=,ans=;

void dp(){

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

        f[i][]=f[i-][];

        if(s[i]=='N') f[i][]++;

        f[i][]=f[i-][];

        if(s[i]=='O') f[i][]+=f[i-][];

        f[i][]=f[i-][];

        if(s[i]=='I') f[i][]+=f[i-][];

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

        int ti=i;i=n-i+;

        d[i][]=d[i+][];

        if(s[i]=='I') d[i][]++;

        d[i][]=d[i+][];

        if(s[i]=='O') d[i][]+=d[i+][];

        d[i][]=d[i+][];

        if(s[i]=='N') d[i][]+=d[i+][];

        i=ti;

    }

    sum=f[n][];

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

        ll tn=sum+d[i+][],ti=sum+f[i][],to=sum+d[i+][]*f[i][];

        ans=max(ans,max(tn,max(to,ti)));

        //printf("t %d %d %d %d\n",i,tn,to,ti);

    }

}

int main(int argc, const char * argv[]){

    scanf("%d%s",&n,s+);

    dp();

    printf("%lld",ans);

    return ;

}

P1710 地铁涨价

题目背景

本题开O2优化，请注意常数

题目描述

博艾市除了有海底高铁连接*、*与日本，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站，同时有M小段地铁连接两个不同的站。

地铁计价方式很简单。从A站到B站，每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取1博艾元。也就是说，从A站到B站，选择的路径不一样，要价也会不同。

我们认为凡华中学在1号地铁站。学生们通过地铁通勤，他们当然知道选择最短路来坐车的话，票价最便宜。

然而博艾地铁公司经营不善，一直亏损，于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。

学生们知道，如果他们到学校的一条最短路径中的一小段提价了，可以改变路径，使总票价不变。然而随着一条一条的铁路被提价，当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。

现在地铁公司希望知道，对于每一次涨价，有多少个站，学生会因为涨价而不满呢？

输入输出格式

输入格式：

第一行为三个整数N,M,Q。

接下来M行，每行2个整数ai,bi,表示第i条铁路连接的两个站。i表示铁路编号。

接下来Q行，每行一行整数rj，表示每次涨价的铁路编号。

输出格式：

Q行。每行一个整数表示不满的车站数量。

输入输出样例

输入样例#1：

输出样例#1：

说明

【样例解释】

次数 车站2 车站3 车站4 车站5

初始 1     1     2     2

1    1     1     2     2

2    1     2     2     3

3    1     2     2     3

4    2     2     3     3

5    2     2     4     3

【数据范围】

对于20%的数据 N≤100, Q≤30

对于40%的数据 Q≤30

对于70%的数据正确的输出结果中，不会有超过50种不一样的整数（数据范围剧透解法系列）

对于100%的数据 N≤100000, Q≤M≤200000

可以发现涨价后不可能在经过那里

增加一个涨价时间t，其实就是要找出每个车站到1的最短路中t最小的铁路的t最大值(因为可能有多条最短路)

刚做了NOIP2009最优贸易，一样的思想啊用SPFA即可

一些理解：

DP可以处理DAG

spfa可以处理带环的(dij也可以，但只能是最短路问题)

spfa有点像DP，计算一个图上的状态，只不过一个状态可能被计算多次(因为有环)

貌似还有个很厉害的做法

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

const int N=1e5+,M=2e5+,INF=1e9;

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,m,Q,u,v;

struct edge{

    int v,ne,t;//time of raise

    edge(int a=INF):v(),ne(),t(a){}

}e[M<<];

int h[N],cnt=;

void ins(int u,int v){

    cnt++;

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

    cnt++;

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

}

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

struct node{

    int id,t;

    node(int a=,int b=):id(a),t(b){}

    bool operator <(const node &r)const{return t<r.t;}

}a[N];

inline void lop(int &x){if(x==N-) x=;}

void spfa(){

    for(int i=;i<=n;i++) a[i].id=i,d[i]=INF;

    q[tail++]=;

    a[].t=INF;d[]=;

    while(head!=tail){

        int u=q[head++];inq[u]=;lop(head);

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

            int v=e[i].v;

            if(d[v]>d[u]+){

                d[v]=d[u]+;

                a[v].t=min(a[u].t,e[i].t);

                if(!inq[v]){q[tail++]=v;inq[v]=;lop(tail);}

            }else if(d[v]==d[u]+)

                a[v].t=max(a[v].t,min(a[u].t,e[i].t));

        }

    }

}

int main(int argc, const char * argv[]) {

    n=read();m=read();Q=read();

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

    for(int i=;i<=Q;i++){u=read();e[*u-].t=e[*u].t=i;}

    spfa();

    sort(a+,a++n);

    int p=,ans=;

    //for(int i=1;i<=n;i++) printf("node %d %d\n",a[i].id,a[i].t);

    //for(int i=1;i<=2*m;i++ ) printf("edge %d %d %d\n",i,e[i].v,e[i].t);

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

        while(a[p].t<=i) ans++,p++;

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

    }

    return ;

}

码农公寓

P2409 Y的积木

题目背景

题目描述

输入输出格式

输入输出样例

说明

P1371 NOI元丹

题目描述

输入输出格式

输入输出样例

说明

P1710 地铁涨价

题目背景

题目描述

输入输出格式

输入输出样例

说明

相关文章