头像

上进的向阳花木

小学五年级




离线:3小时前



题目描述

凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很神奇。

工厂里有 n 位工人,工人们从 1∼n 编号。

某些工人之间存在双向的零件传送带。

保证每两名工人之间最多只存在一条传送带。

如果 x 号工人想生产一个被加工到第 L(L>1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L−1 阶段的零件(但 x 号工人自己无需生产第 L−1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

轩轩是 1 号工人。

现在给出 q 张工单,第 i 张工单表示编号为 ai 的工人想生产一个第 Li 阶段的零件。

轩轩想知道对于每张工单,他是否需要给别人提供原材料。

他知道聪明的你一定可以帮他计算出来!

输入格式
第一行三个正整数 n,m 和 q,分别表示工人的数目、传送带的数目和工单的数目。

接下来 m 行,每行两个正整数 u 和 v,表示编号为 u 和 v 的工人之间存在一条零件传输带。保证 u≠v。

接下来 q 行,每行两个正整数 a 和 L,表示编号为 a 的工人想生产一个第 L 阶段的零件。

输出格式
共 q 行,每行一个字符串 “Yes” 或者 “No”。如果按照第 i 张工单生产,需要编号为 1 的轩轩提供原材料,则在第 i 行输出 “Yes”;否则在第 i 行输出 “No”。注意输出不含引号。

数据范围
1≤u,v,a≤n。
测试点 1∼4,1≤n,m≤1000,q=3,L=1。
测试点 5∼8,1≤n,m≤1000,q=3,1≤L≤10。
测试点 9∼12,1≤n,m,L≤1000,1≤q≤100。
测试点 13∼16,1≤n,m,L≤1000,1≤q≤10^5。
测试点 17∼20,1≤n,m,q≤10^5,1≤L≤10^9。

样例

输入样例1:
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2
输出样例1:
No
Yes
No
Yes
No
Yes
输入样例2:
5 5 5
1 2
2 3
3 4
4 5
1 5
1 1
1 2
1 3
1 4
1 5
输出样例2:
No
Yes
No
Yes
Yes
样例解释
样例#1: 

编号为 1 的工人想生产第 1 阶段的零件,需要编号为 2 的工人提供原材料。

编号为 2 的工人想生产第 1 阶段的零件,需要编号为 1 和 3 的工人提供原材料。

编号为 3 的工人想生产第 1 阶段的零件,需要编号为 2 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件,需要编号为 2 的工人生产第 1 阶段的零件,需要为编号 1 和 3 的工人提供原材料。

编号为 2 的工人想生产第 2 阶段的零件,需要编号为 1 和 3 的工人生产第 1 阶段的零件,他/她们都需要编号为 2 的工人提供原材料。

编号为 3 的工人想生产第 2 阶段的零件,需要编号为 2 的工人生产第 1 阶段的零件,需要编号为 1 和 3 的工人提供原材料。

样例#2:


编号为 1 的工人想生产第 1 阶段的零件,需要编号为 2 和 5 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件,需要编号为 2 和 5 的工人生产第 1 阶段的零件,需要编号为 1,3,4 的工人提供原材料。

编号为 1 的工人想生产第 3 阶段的零件,需要编号为 2 和 5 的工人生产第 2 阶段的零件,需要编号为 1,3,4 的工人生产第 1 阶段的零件,需要编号为 2,3,4,5 的工人提供原材料。

编号为 1 的工人想生产第 4 阶段的零件,需要编号为 2 和 5 的工人生产第 3 阶段的零件,需要编号为 1,3,4 的工人生产第 2 阶段的零件,需要编号为 2,3,4,5 的工人生产第 1 阶段的零件,需要全部工人提供原材料。

编号为 1 的工人想生产第 5 阶段的零件,需要编号为 2 和 5 的工人生产第 4 阶段的零件,需要编号为 1,3,4 的工人生产第 3 阶段的零件,需要编号为 2,3,4,5 的工人生产 第 2 阶段的零件,需要全部工人生产第 1 阶段的零件,需要全部工人提供原材料。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef pair <int,int>  PII ;

const int N=100010,M=200010;

int n,query;
int h[N],ne[M],e[M],idx,m;
int dist[N][2];
PII q[N*2];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void BFS()
{
    memset(dist,1,sizeof(dist));

    dist[1][0]=0;

    int tt=0,hh=0;
    q[0]={1,0};

    while(hh<=tt)
    {
        PII t=q[hh++];

        int ver=t.first,type=t.second,distance=dist[ver][type];

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j][type^1]>distance+1)
            {
                dist[j][type^1]=distance+1;
                q[++tt]={j,type^1};
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&query);
    memset(h,-1,sizeof(h));
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }

    BFS();

    while(query--)
    {
        int a,l;
        scanf("%d%d",&a,&l);
        if(h[1]==-1 && a==1) puts("No");
        else if(l>=dist[a][l&1]) puts("Yes");
        else puts("No");
    }

    return 0;
}



活动打卡代码 AcWing 1164. 加工零件

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef pair <int,int>  PII ;

const int N=100010,M=200010;

int n,query;
int h[N],ne[M],e[M],idx,m;
int dist[N][2];
PII q[N*2];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void BFS()
{
    memset(dist,1,sizeof(dist));

    dist[1][0]=0;

    int tt=0,hh=0;
    q[0]={1,0};

    while(hh<=tt)
    {
        PII t=q[hh++];

        int ver=t.first,type=t.second,distance=dist[ver][type];

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j][type^1]>distance+1)
            {
                dist[j][type^1]=distance+1;
                q[++tt]={j,type^1};
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&query);
    memset(h,-1,sizeof(h));
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }

    BFS();

    while(query--)
    {
        int a,l;
        scanf("%d%d",&a,&l);
        if(h[1]==-1 && a==1) puts("No");
        else if(l>=dist[a][l&1]) puts("Yes");
        else puts("No");
    }

    return 0;
}



题目描述

小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。

某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品,注意同一个纪念品可以在同一天重复买;
卖出持有的任意一个纪念品,以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。

当然,一直持有纪念品也是可以的。

T 天之后,小伟的超能力消失。

因此他一定会在第 T 天卖出所有纪念品换回金币。

小伟现在有 M 枚金币,他想要在超能力消失后拥有尽可能多的金币。

输入格式
第一行包含三个正整数 T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量 N,小伟现在拥有的金币数量 M。

接下来 T 行,每行包含 N 个正整数,相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 Pi,1,Pi,2,……,Pi,N,其中 Pi,j 表示第 i 天第 j 种纪念品的价格。

输出格式
输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

数据范围
对于 10% 的数据,T=1。

对于 30% 的数据,T≤4,N≤4,M≤100,所有价格 10≤Pi,j≤100。

对于 15% 的数据,T≤100,N=1。

对于 15% 的数据,T=2,N≤100。

对于 100% 的数据,T≤100,N≤100,M≤10^3,所有价格 1≤Pi,j≤10^4,数据保证任意时刻,小明手上的金币数不可能超过 10^4。

样例

输入样例1:
6 1 100
50
20
25
20
25
50
输出样例1:
305
输入样例2:
3 3 100
10 20 15
15 17 13
15 25 16
输出样例2:
217
样例解释
样例#1:
最佳策略是:

第二天花光所有 100 枚金币买入 5 个纪念品 1;

第三天卖出 5 个纪念品 1,获得金币 125 枚;

第四天买入 6 个纪念品 1,剩余 5 枚金币;

第六天必须卖出所有纪念品换回 300 枚金币,第四天剩余 5 枚金币,共 305 枚金币。

超能力消失后,小伟最多拥有 305 枚金币。

样例#2:
最佳策略是:

第一天花光所有金币买入 10 个纪念品 1;

第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3,剩余 1 枚金币;

第三天必须卖出所有纪念品换回 216 枚金币,第二天剩余 1 枚金币,共 217 枚金币。

超能力消失后,小伟最多拥有 217 枚金币。

算法 贪心+DP

其实转换后就是完全背包问题

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int f[10010];
int a[1010][1010];

int main()
{
    int t,n,m;
    cin>>t>>n>>m;

    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];

    for(int i=1;i<t;i++)
    {
        memset(f,0,sizeof(f));
        for(int j=1;j<=n;j++)
            if(a[i+1][j]>a[i][j])
            {
                for(int k=a[i][j];k<=m;k++)
                    f[k]=max(f[k],f[k-a[i][j]]-a[i][j]+a[i+1][j]);
            }
        m+=f[m];
    }
    printf("%d",m);
    return 0;
}

也许我题解写得不太好,但你看得这么认真,不点个赞再走吗?




活动打卡代码 AcWing 1163. 纪念品

#include <bits/stdc++.h>

using namespace std;

int f[10010];
int a[1010][1010];

int main()
{
    int t,n,m;
    cin>>t>>n>>m;

    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];

    for(int i=1;i<t;i++)
    {
        memset(f,0,sizeof(f));
        for(int j=1;j<=n;j++)
            if(a[i+1][j]>a[i][j])
            {
                for(int k=a[i][j];k<=m;k++)
                    f[k]=max(f[k],f[k-a[i][j]]-a[i][j]+a[i+1][j]);
            }
        m+=f[m];
    }
    printf("%d",m);
    return 0;
}



题目描述

学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为 1。  

现在有 n 名同学准备接水,他们的初始接水顺序已经确定。

将这些同学按接水顺序从 1 到 n 编号,i 号同学的接水量为 wi。

接水开始时,1 到 m 号同学各占一个水龙头,并同时打开水龙头接水。

当其中某名同学 j 完成其接水量要求 wj 后,下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。

这个换人的过程是瞬间完成的,且没有任何水的浪费。

即 j 同学第 x 秒结束时完成接水, 则 k 同学第 x+1 秒立刻开始接水。 

若当前接水人数 n’ 不足 m,则只有 n’ 个龙头供水,其它 m−n’ 个龙头关闭。  

现在给出 n 名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入格式
第 1 行 2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。 

第 2 行 n 个整数 w1、w2、…、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。

输出格式
输出只有一行,1 个整数,表示接水所需的总时间。

数据范围
1≤n≤10000,
1≤m≤100,m≤n,
1≤wi≤100

样例

输入样例:
5 3
4 4 1 2 1
输出样例:
4

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int w[10010];
int q[110];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++) scanf("%d",&w[i]);

    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=0;j<m;j++)
            if(q[j]<q[t]) t=j;
        q[t]+=w[i];
    }
    int res=0;
    for(int i=0;i<m;i++) res=max(res,q[i]);
    printf("%d",res);
    return 0;
}

也许我的题解写得不好,但你看得这么认真,不点一个赞再走吗?



活动打卡代码 AcWing 442. 接水问题

#include <iostream>
#include <cstdio>

using namespace std;

int w[10010];
int q[110];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++) scanf("%d",&w[i]);

    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=0;j<m;j++)
            if(q[j]<q[t]) t=j;
        q[t]+=w[i];
    }
    int res=0;
    for(int i=0;i<m;i++) res=max(res,q[i]);
    printf("%d",res);
    return 0;
}



题目描述

一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。

现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。

注意:匹配单词时,不区分大小写,但要求完全匹配, 即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例 1), 如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例 2)。

输入格式
输入共 2 行。

第 1 行为一个字符串,其中只含字母,表示给定单词。

第 2 行为一个字符串,其中只可能包含字母和空格,表示给定的文章。

输出格式
输出只有一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开, 分别是单词在文章中出现的次数和第一次出现的位置。(即在文章中第一次出现时,单词首字母在文章中的位置,位置从 0 开始)

如果单词在文章中没有出现,则直接输出一个整数-1。

数据范围
1≤单词长度≤10,
1≤文章长度≤10^6

样例

输入样例 1:
To
to be or not to be is a question
输出样例 1:
2 0
输入样例 2:
to
Did the Ottoman Empire lose its power at that time
输出样例 2:
-1

C++ 代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

string a,b;

int main()
{
    int la,lb,count=0,k1=0,t;
    bool flag=1;
    getline(cin,a);
    getline(cin,b);

    la=a.size();
    lb=b.size();

    for(int i=0;i<la;i++) 
        if(a[i]>='a' && a[i]<='z') a[i]=a[i]-'a'+'A';

    for(int i=0;i<lb;i++) 
        if(b[i]>='a' && b[i]<='z') b[i]=b[i]-'a'+'A';

    for(int i=0,j;i<lb;i++) 
    {   
        flag=1;
        if(b[i]==' ') continue; 

        for(j=i;b[j]!=' '&&j<lb;j++); 

        if(j-i!=la) flag=0;

        for(int k=0;k<la;k++)
        {
            if(b[i+k]!=a[k]) {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            count++; 
            if(count==1) k1=i; 
        }
        i=j; 
    }   
    if(count==0) printf("-1");
    else printf("%d %d",count,k1);
}

也许我的题解不够清楚,但你看得那么认真,不点个赞再走吗???



活动打卡代码 AcWing 446. 统计单词数

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

string a,b;

int main()
{
    int la,lb,count=0,k1=0,t;
    bool flag=1;
    getline(cin,a);
    getline(cin,b);

    la=a.size();
    lb=b.size();


    for(int i=0;i<la;i++) 
        if(a[i]>='a' && a[i]<='z') a[i]=a[i]-'a'+'A';

    for(int i=0;i<lb;i++) 
        if(b[i]>='a' && b[i]<='z') b[i]=b[i]-'a'+'A';

    for(int i=0,j;i<lb;i++) 
    {   
        flag=1;
        if(b[i]==' ') continue;

        for(j=i;b[j]!=' '&&j<lb;j++); 

        if(j-i!=la) flag=0;

        for(int k=0;k<la;k++)
        {
            if(b[i+k]!=a[k]) 
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            count++; 
            if(count==1) k1=i; 
        }
        i=j; 
    } 
    if(count==0) printf("-1");
    else printf("%d %d",count,k1);
}



题目描述

传说很遥远的藏宝楼顶层藏着诱人的宝藏。

小明历尽千辛万苦终于找到传说中的这个藏宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。

说明书的内容如下: 

藏宝楼共有N+1层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。

除了顶层外,藏宝楼另有N层,每层M个房间,这M个房间围成一圈并按逆时针方向依次编号为0,…,M-1。

其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。

每个房间里有一个指示牌,指示牌上有一个数字x,表示从这个房间开始按逆时针方向选择第x个有楼梯的房间(假定该房间的编号为k),从该房间上楼,上楼后到达上一层的k号房间。

比如当前房间的指示牌上写着2,则按逆时针方向开始尝试,找到第2个有楼梯的房间,从该房间上楼。如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。 

请帮助小明算出这个打开宝箱的密钥。

输入格式
第一行2个整数N和M,之间用一个空格隔开。

N表示除了顶层外藏宝楼共N层楼,M表示除顶层外每层楼有M个房间。 

接下来NM行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况,其中第(i-1)M+j行表示第i层j-1号房间的情况(i=1, 2, …, N;j=1, 2, … ,M)。

第一个整数表示该房间是否有楼梯通往上一层(0表示没有,1表示有),第二个整数表示指示牌上的数字。

注意,从j号房间的楼梯爬到上一层到达的房间一定也是j号房间。 

最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:房间编号从0开始)。

输出格式
输出只有一行,一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对20123取模的结果即可。

数据范围
0<N≤10000,
0<M≤100,
0<x≤10^6

样例

输入样例:
2 3
1 2
0 3
1 4
0 1
1 5
1 2
1
输出样例:
5

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

bool f[10010][110];
int a[10010][110],sum;

int main()
{
    int n,m,k;
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d%d",&f[i][j],&a[i][j]);

    scanf("%d",&k);

    for(int i=0;i<n;i++)
    {
        int s=0;
        for(int j=0;j<m;j++) s+=f[i][j];
        int t=a[i][k]; 
        sum=(sum+t)%20123;
        t%=s;
        if(!t) t=s;
        for(int j=k;;j=(j+1)%m)
        {
            if(f[i][j])
            {
                if(--t==0)
                {
                    k=j;
                    break;
                }
            }
        }
    }
    printf("%d",sum);
    return 0;
}



活动打卡代码 AcWing 450. 寻宝

#include <iostream>
#include <cstdio>

using namespace std;

bool f[10010][110];
int a[10010][110],sum;

int main()
{
    int n,m,k;
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d%d",&f[i][j],&a[i][j]);

    scanf("%d",&k);

    for(int i=0;i<n;i++)
    {
        int s=0;
        for(int j=0;j<m;j++) s+=f[i][j];
        int t=a[i][k]; 
        sum=(sum+t)%20123;
        t%=s;
        if(!t) t=s;
        for(int j=k;;j=(j+1)%m)
        {
            if(f[i][j])
            {
                if(--t==0)
                {
                    k=j;
                    break;
                }
            }
        }
    }
    printf("%d",sum);
    return 0;
}