该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod[2] = {(ll)1e9 + 7, (ll)1e9 + 9}, p[2] = {10591,14637};
string s1, s2;
ll s1_num[2],s2_num[2];
ll quick_pow(ll a, ll m, ll mod) {
    ll r = 1;
    while (m) {
        if (m & 1) r = r * a % mod;
        a = a * a % mod;
        m >>= 1;
    }
    return r;
}
ll solw_pow(ll a, ll m, ll mod){
    ll r = 1;
    for (ll i = 1; i <= m; i++) {
        r = r * a % mod;
    }
    return r;
}
int main() {
    cin >> s1 >> s2;
    for (auto i : s2) {
        for (int j = 0; j < 2; j++) {
            s2_num[j] = (s2_num[j] * p[j] % mod[j] + i) % mod[j];
        }
    }
    for (int i = 0; i < s2.size(); i++) {
        for (int j = 0; j < 2; j++) {
            s1_num[j] = (s1_num[j] * p[j] % mod[j] + s1[i] ) % mod[j];
        }
    }
    if (s1_num[0] == s2_num[0] && s1_num[1] == s2_num[1]) {
        cout << "1 ";
    }
    for (int i = s2.size(); i < s1.size(); i++) {
        for (int j = 0; j < 2; j++) {
            s1_num[j] = ((s1_num[j] - s1[i - s2.size()] * quick_pow(p[j],s2.size() - 1, mod[j]) % mod[j]) + mod[j]) %  mod[j];
            s1_num[j] = (s1_num[j] * p[j] % mod[j] + s1[i] ) % mod[j];
        }
        if (s1_num[0] == s2_num[0] && s1_num[1] == s2_num[1]) {
            cout << i - s2.size() + 2 << ' ';
        }
    }
    return 0;
}

1<=|s1,s2|<=10^6

判断题

1. **将p数组改为{54861,16871}不影响结果 **{{ select(1) }}

• 正确
• 错误

2. **将mod数组改为{101,151}不影响结果 **{{ select(2) }}

• 正确
• 错误

3. **若删去40行，则43行的判断条件不会成立 **{{ select(3) }}

• 正确
• 错误

4. **若|s2|<=50,|s1|<=10^6，则使用quick_pow函数与使用slow_pow函数的程序速度差距没有超过45倍 **{{ select(4) }}

• 正确
• 错误

选择题

5. 该算法的空间复杂度为(){{ select(5) }}

• |s1| + |s2|
• min(|s1|^2**,|s2|^2 )**
• max(|s1|^2**,|s2|^2 )**
• max(|s1|^2**,|s2|^2 ) - min(|s1|^2,|s2|^2 )**

6. 当输入为

AAAAAAAA
AAAAAA

时，输出为(){{ select(6) }}

• 不会有输出
• 0 1 2
• 1 3 5
• 1 2 3

7. 当输入为

ABBCCCDDDD······ZZ····ZZ（一个A，两个B，依此类推直到26个Z）
ABCDEFGHIJKLMNOPQRSTUVWXYZ

时，输出为(){{ select(7) }}

• 不会有输出
• 0 1 2
• 1 3 5
• 1 2 3

完善程序（单选题，每小题 3 分）

给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

**第一行两个正整数 **n,m

第二行 n 个整数，其中第 i 个数 a_i 表示点 i 的点权。

第三至 m+2 行，每行两个整数 u,v，表示一条 u\rightarrow v 的有向边。

输出格式

共一行，最大的点权之和。

样例 #1

样例输入 #1

2 2
1 1
1 2
2 1

样例输出 #1

2

提示

对于 100\% 的数据，1\le n \le 10^4，1\le m \le 10^5，0\le a_i\le 10^3。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
#include<unordered_map>
#include<stack>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f;
int mod=1000000007;
const int N=10100;
int n,m,cnt,x,y,indx,top,k;
int head[N],node[N],low[N],st[N],vis[N],dfn[N];
int a[N],in[N],dis[N];
struct edge{
    int next;
    int from,to;
}e[N*10],E[N*10];
void add(int from,int to){
    e[k].next=head[from];
    e[k].from=from;
    e[k].to=to;
    head[from]=k++;
}
void addE(int from,int to){
    E[k].next=head[from];
    E[k].from=from;
    E[k].to=to;
    head[from]=k++;
}
void tarjan(int from){
    low[from]=dfn[from]=++indx;
    st[++top]=from;
    vis[from]=1;
    for(int i=head[from];i!=-1;i=e[i].next){
        int to=e[i].to;
        if((8)______){
            tarjan(to);
            low[from]=min(low[from],low[to]);
        }
        else if(vis[to]){
            (9)______;
        }
    }
    if((10)______){
        int t;
        while(1){
            t=st[top--];
            (11)______;//缩点
            vis[t]=0;
            if(from==t)break;
            a[from]+=a[t];
        }
    }
}
int topo(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(node[i]==i&&!in[i]){
            q.push(i);
            dis[i]=a[i];
        }
    }
    while(!q.empty()){
        k=q.front();q.pop();
        for(int i=head[k];i!=-1;i=E[i].next){
            int to=E[i].to;
            (12)______;
            in[to]--;
            if(in[to]==0)
                q.push(to);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)
    ans=max(ans,dis[i]);
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])
            tarjan(i);
    }
    k=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        x=node[e[i].from],y=node[e[i].to];
        if(x!=y){
            addE(x,y);
            in[y]++;
        }
    }
    printf("%d",topo());
    return 0;
}
​

(8){{ select(8) }}

• dfs[i]
• !dfn[i]
• dfn[to]
• !dfn[to]

(9){{ select(9) }}

• low[from]=min(low[from],low[to])
• low[from]=min(low[from],dfn[to])
• low[from]=min(dfn[from],dfn[to])
• low[from]=min(dfn[from],low[to])

(10){{ select(10) }}

• dfn[from]=low[from]
• dfn[from]=low[to]
• dfn[from]=dfn[to]
• low[from]=low[to]

(11){{ select(11) }}

• node[t]=low[from]
• node[t]=dfn[from]
• node[t]=from
• node[t]=0

(12){{ select(12) }}

• dis[to]=max(dis[to],dis[k]+a[to])
• dis[i]=max(dis[i],dis[k]+a[i])
• dis[k]=max(dis[k],dis[to]+a[k])
• dis[to]=max(dis[k],dis[k]+a[to])