【Java/补题/牛客/ACM赛制】黑龙江职业学院校赛第二场(同步赛)

• • 题目链接
  • 知识一览
  • 题目列表
  • • 快输
    • C 送你们一个字符串的经典题吧（字符串/kmp与扩展kmp）
    • I 逛漫展（图论/多源最短路/Floyd）
    • J 面基（图论/单源最短路/Dijkstra）

黑龙江职业学院校赛第二场(同步赛)

01 - 字符串/kmp与扩展kmp
02 - 图论/多源最短路/Floyd
03 - 图论/单源最短路/Dijkstra

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        String tmp;

        public FastReader() {
            br=new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st==null||!st.hasMoreElements()) {
                try {
                    st=new StringTokenizer(br.readLine());
                }catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong(){return Long.parseLong(next());}

        String nextLine() {
            String str="";
            try {
                str=br.readLine();
            }catch(IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        boolean hasNext(){
            if(st!=null&&st.hasMoreTokens())return true;
            try {
                tmp=br.readLine();
                st=new StringTokenizer(tmp);
            }catch(IOException e) {
                return false;
            }
            return true;
        }
    }

    static PrintWriter out=new PrintWriter(
            new BufferedWriter(new OutputStreamWriter(System.out)));
    static FastReader sc=new FastReader();

题目描述
给你一个字符串S。S中只有大写字母。
你需要对字符串S的每个前缀Si进行以下运算。
在字符串Si中找到一个它的子串T。T 既是 Si 的前缀也是 Si 的后缀，且T不能是Si本身。
请输出每个字符串S的前缀Si中，T的最长长度。
输入描述:
一行一个字符串S
1≤S.length()≤10^6
输出描述:
输出一行S.length()个整数，第i个整数表示S的长度为i的前缀，最长的T的长度。
示例1
输入
AAAAAAAAAAA
输出
0 1 2 3 4 5 6 7 8 9 10
示例2
输入
ABBCCACABABB
输出
0 0 0 0 0 1 0 1 2 1 2 3

	static int mod=(int)1e9+7;
    static int maxn=(int)1e8+10;
    public static void main(String[] args) {
        //int T=sc.nextInt();
        int T=1;
        while(T-->0){
            solve();
        }
    }
    private static void solve(){
        char s[]=(" "+sc.next()).toCharArray();
        out.print(0);
        int j=0;
        for(int i=2;i
            out.print(" ");
            if(j!=0&&s[i]!=s[j+1])j=0;
            if(s[i]==s[j+1])j++;
            out.print(j);
        }
        out.flush();
    }

题目描述
xmy这里有一份漫展的详细地图。
上面有N个展览场所，M条连接场馆的人行道。
xmy想要个程序处理这些数据，方便他和cr知道t时间从A场馆到B场馆的最短路程。
保证：每次查询的时间t，不小于上次查询的。
以下为地图上的已知信息：
每个场所都标注了一个编号ai和开馆时间Ti，ai的范围是0到N-1。并且编号小的场馆，开馆时间不会晚于编号大的,也就是说开馆时间是Ti−1≤Ti 的。
没有开馆的场馆是封锁的，不可以进入也不可以经过。
A与B之间的最短路径，是可以通过已经开馆的场馆进行中转来缩短的。
注：不要想太多，最短路程只计算场馆之间人行道的长度，不需要考虑利用场馆中转时需要在场馆内走的。
注：开馆后不会关馆。
输入描述:
第一行三个整数 N M Q （N个场馆 M条人行道 Q次查询）
1≤N≤200，1≤M≤2×10^4 ，1≤Q≤5×10^4
第二行N个整数，为开馆时间Ti，以及据上文，给出的数据Ti−1≤T i
0≤Ti≤10^9
以下M行 每行三个整数 A B W （表示场馆A与场馆B之间存在一条长度W的人行道），0≤B,A 以下Q行 每行三个整数 A B T (表示要查询场馆A与场馆B之间在时间T的最短路径长度)，0≤B,A 输出描述:
共Q行，对每一个询问输出对应的答案
如果T时间 A，B未互通则输出-1
示例1
输入
4 4 4
1 2 3 4
1 2 1
3 1 1
2 3 2
0 1 4
2 1 2
3 1 2
1 2 3
0 3 4
输出
-1
-1
1
5

	static int N=201;
    static int MAXN=(int)1e9;
    static int n,m,q;
    static int t[]=new int[N],dis[][]=new int[N][N];
    public static void main(String[] args) {
        //int T=sc.nextInt();
        int T=1;
        while(T-->0){
            solve();
        }
    }
    private static void solve(){
        n=sc.nextInt();m=sc.nextInt();q=sc.nextInt();
        for(int i=0;i
            a=sc.nextInt();b=sc.nextInt();w=sc.nextInt();
            dis[a][b]=dis[b][a]=Math.min(w,dis[a][b]);
        }
        for(int i=0;i0) {
            a=sc.nextInt();b=sc.nextInt();w=sc.nextInt();
            while (t[k]<=w&&k
                floyd(k++);
            }

            if (t[a]>w||t[b]>w)out.println(-1);
            else {
                if (dis[a][b]==MAXN)out.println(-1);
                else out.println(dis[a][b]);
            }
        }
        out.flush();
    }
    private static void floyd(int k) {
        for(int i=0;i
            for(int j=0;j
                dis[i][j]=Math.min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }

题目描述
xmy拿出了一张地图。地图上有M段路。
每段路连接着两个路口。
并且标记出了两个路口的编号A和B，长度L(单位米)。还有一个标记W(标记是1为单向边 标记是2为双向边)。
xmy每秒可以走S米。
注:每个路口的编号是唯一的 编号相同的话 代表是同一个路口。
已知哈东站所在位置的编号为Xa，黑职所在的路口编号为Xb。
你只需要算好，最少需要多少秒可以从哈东站到达黑职就可以。如果出现小数向上取整。
如果不能从哈东站到达黑职，请输出-1。
输入描述:
第一行四个整数 M Xa Xb S
(1≤M≤2×10^5) (1≤Xa,Xb≤10^18) (1≤S≤10^5)
以下M行，每行为四个整数 A B L W
(1≤A,B≤10^18) (1≤L≤10^5) (1≤W≤2)
输出描述:
输出一个整数 需要多少秒（向上取整）
如果不能从哈东站到达黑职，请输出-1。
示例1
输入
6 1 3 2
1 2 2 1
2 3 2 1
2 4 1 1
1 3 5 1
3 4 3 1
1 4 4 1
输出
2
说明
起点在1 终点在3 1到3的最短路 1-2 2-3 4米

	static int N=(int)1e6+10;
    static long MAXN=(long)1e18;
    static boolean vis[]=new boolean[N];
    static long dis[]=new long[N];
    static ArrayList> g=new ArrayList<>();//存储边
    static ArrayList> w=new ArrayList<>();//存储边长
    //给每个路口的编号标序号
    static HashMap mp=new HashMap<>();
    static int idx=0;
    public static void main(String[] args) {
        //int T=sc.nextInt();
        int T=1;
        while(T-->0){
            solve();
        }
    }
    private static void solve(){
        int m=sc.nextInt();
        long xa=sc.nextLong(),xb=sc.nextLong();
        int s=sc.nextInt();
        for(int i=0;i<=2*m+1;i++) {
            g.add(new ArrayList<>());
            w.add(new ArrayList<>());
        }
        while(m-->0) {
            long A=sc.nextLong(),B=sc.nextLong();//路口编号
            int L=sc.nextInt(),W=sc.nextInt();//长度L(单位米)；标记W(标记是1为单向边 标记是2为双向边)。
            A=f(A);B=f(B);
            if(W==1) {
                g.get((int)A).add((int)B);
                w.get((int)A).add(L);
            }else {
                g.get((int)A).add((int)B);
                w.get((int)A).add(L);
                g.get((int)B).add((int)A);
                w.get((int)B).add(L);
            }
        }
        xa=f(xa);xb=f(xb);
        dijkstra((int)xa);
        long ans=(dis[(int)xb]+s-1)/s;//向上取整
        if(dis[(int)xb]==MAXN) ans=-1;
        out.println(ans);
        out.flush();
    }
    static void dijkstra(int sx){
        Arrays.fill(dis,MAXN);
        dis[sx]=0;
        PriorityQueue pq=new PriorityQueue<>();
        pq.add(new Node(sx,0));
        while(!pq.isEmpty()){
            //获取优先队列中路径最短的顶点
            Node t=pq.poll();
            int x=t.x;
            long distance=t.d;
            if(vis[x]) continue;
            vis[x]=true;
            //更新链表中的顶点到起点的长度
            for(int i=0;i
                int j=g.get(x).get(i);//获得顶点
                int l=w.get(x).get(i);//获得顶点到x的长度
                if(dis[j]>distance+l) {
                    dis[j]=distance+l;
                    pq.add(new Node(j,dis[j]));
                }
            }
        }
    }
    //给每个路口的编号标序号
    static int f(long x) {
        if(mp.get(x)==null){
            mp.put(x,++idx);
            return idx;
        }else return mp.get(x);
    }

//顶点类
class Node implements Comparable{
    int x;//顶点序号
    long d;//该顶点到起点的距离

    Node(int x,long d) {
        this.x = x;
        this.d = d;
    }

    @Override
    public int compareTo(Node o) {
        return d>o.d?1:-1;//距离升序排列
    }
}