列表

详情

NC222884. MeUmy的海底捞抽奖旅程

描述

这一天咩栗与大白狗去吃海底捞，海底捞服务员告诉他们，海底捞推出来一个新的活动。
海底捞给他们提供了一张地图.
上面包含了N家海底捞，编号从0到N-1,和M条可以连接两个海底捞店的路，和每家店的开业时间为t。（出题人没见过只能单向的路）
并且提供了一条很长很长的字符串S和ST条比较短的字符串Si。短的字符串是从0到ST-1编号的。
然后让呜米说Q次，每次说三个数字 ,第一个数字代表店 x ,第二个数字代表店 y，第三个数字代表时间 t 。
求出 t 时间 x 店到 y 店之间最短的路径长度LEN，用LEN%ST的结果取出编号相同的Si字符，Si字符串在长字符串S内出现的次数，会被记录下来。
如果 t 时间的时候x店或者y店没有开业或者t时间x店与y店还不能互通，就视为不能互相到达,会记录下-ST。(负的ST)
需要中转才能互通或者可以通过中转减少最短距离的情况下，只能在t 时间以及之前，已经开业的店可以进行中转。
最后把记录下的数字加起来，如果大于R就可以免单。
请问记录下的数字加起来是多少，能不能免单？

注:
aaa
aa
算aa出现两次

ababa

aba
算aba出现两次
而且S和Si只存在小写字母

输入描述

第一行五个整数 N M ST R Q
第二行N个整数 t  保证t不降 

第三行一个字符串S
接下来ST条字符串Si 
接下来M行每行三个整数x,y,w ( x到y距离w)
接下来Q行每行三个整数x,y,t  保证t不降

输出描述

输出两行
第一行能不能免单 能YES 不能NO
第二行一个整数 记录下的数字加起来是多少

示例1

输入: 

4 5 5 20 4
1 2 3 4
aaaaaaaaa
a
a
a
a
a
2 3 1
0 2 1
2 1 4
0 3 5
3 1 2
0 1 2
2 1 3
0 1 3
0 1 4

输出: 

YES
22

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 130ms, 内存消耗: 888K, 提交时间: 2021-06-27 16:26:19 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=210;
const int M=2e6+7;
typedef long long ll;
const ll INF=1e16;
ll dp[N][N];
int tt[N];
char s[M],str[M];
int que[M],lens,lenstr;
int cnt[M],idx;
void kmp(int u){
    int res=0;
    for(int i=2,j=0;i<=lenstr;i++){
        while(j&&str[i]!=str[j+1])j=que[j];
        if(str[i]==str[j+1])j++;
        que[i]=j;
    }
    for(int i=1,j=0;i<=lens;i++){
        while(j&&s[i]!=str[j+1])j=que[j];
        if(s[i]==str[j+1])j++;
        if(j==lenstr)res++;
    }
    cnt[u]=res;
    //cout<<cnt[u]<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,m,st,r,q,res=0;
    cin>>n>>m>>st>>r>>q;
    for(int i=0;i<n;i++)
        cin>>tt[i];
    cin>>s+1;
    lens=strlen(s+1);
    for(int i=0;i<st;i++){
        cin>>str+1;
        lenstr=strlen(str+1);
        kmp(i);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=INF;
    for(int i=0;i<n;i++)
        dp[i][i]=0;
    for(int i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        dp[x][y]=dp[y][x]=min(dp[x][y],z);
    }
    for(int i=1;i<=q;i++){
        ll x,y,t;
        cin>>x>>y>>t;
        for(;t>=tt[idx]&&idx<n;idx++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    dp[j][k]=min(dp[j][k],dp[j][idx]+dp[idx][k]);
        if(t>=tt[x]&&t>=tt[y]&&dp[x][y]<INF)
            res+=cnt[dp[x][y]%st];
        else res-=st;
    }
    if(res>r)cout<<"YES\n"<<res;
    else cout<<"NO\n"<<res;
}

上一题

© 2025 nowcoder.com