题目地址

https://ac.nowcoder.com/acm/contest/102896#question

做题情况

A 题

输出两个不是同一方位的字符中的任意一个就行

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        char a=sc.nextChar();
        if(a=='U'||a=='D') {
            dduoln('L');
        }else {
            dduoln('U');
        }
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

B 题

可以稍微贪心一下

构造 1 2 1 2 1 2 1 2 1 2

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        int n=sc.nextInt();
        for(int i=0;i<n;i++) {
            if(i%2==0) {
                dduo(1+" ");
            }else {
                dduo(2+" ");
            }
        }
        dduoln("");
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}
    
}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

C 题

通过打表发现

1212/12

123123/123

112112/112

都能除尽

所以 我 直接 (str+""+str) /str 求出结果

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        String str=sc.next();
        BigInteger b=new BigInteger(str+str);
        BigInteger c=new BigInteger(str);
        dduoln(b.divide(c));
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}
    
}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

D 题

模拟题

我的解法是先求出位于 (1,1)(2,2)(3,3)(4,4) 点要多少步

不难是 9 ，25， 49， 81...步

我们发现是奇数的平方

所以先求出要求的这个点是从哪个开始的 即(a，a)

然后算到(a,a)一共要多少步

求出还剩多少步

剩下了多少步然后是 在上面走 在右边走 在下面走 在左边走 在上面走 根据 a 可以算出每条边各需要多少步

在每条边上更新剩下要走的步数

即可求出

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        long n=sc.nextLong();
        long ii=0;
        
        ii=(long) Math.sqrt(n);
        ii+=1;
        if(ii%2==0) {
            ii++;
        }
        ii-=2;
//        dduoln(ii);
//        
//        for(int i=1;i<=1e9;i+=2) {
//            if(i*i>n) {
//                ii=i-2;
//                break;
//            }
//        }
//        dduoln(ii);
        
        
        long a=(ii-1)/2; // 起始位置(a,a)
//        dduoln(a+" "+a);
        long ans=(n-ii*ii); // 剩下多少步
//        dduoln(ans);
        
        if(ans==0) {
            dduoln(a+" "+a);
            return;
        }else if(ans==1) {
            dduoln( (a+1) +" "+a);
            return;
        }
        
        long duanbian=a*2+1;
        long changbian=(a+1)*2;
        ans-=1;
        
        // 右
        if(ans<duanbian) {
            dduoln((a+1)+" "+(a-ans));
            return;
        }
        ans-=duanbian;
        
        // 下
        if(ans<changbian) {
            dduoln((a+1-ans)+" "+(-a-1));
            return;
        }
        ans-=changbian;
        
        // 左
        if(ans<changbian) {
            dduoln((-a-1)+" "+(-a-1+ans));
            return;
        }
        ans-=changbian;
        
        dduoln((-a-1+ans)+" "+(a+1));
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

E 题

动态规划

首先知道了 第一次可以到达 1 6

第二次可以到达 2 12

第三次可以到达 3 18

以此类推

维护一个 dp 数组 代表的是到达当前位置获取到的最大贡献值

再在每次运动 都要 for(1-6) 找一下这六步对 dp 数组的更新

需要注意的是 不要访问到数组外面去

最后找出 dp 数组中的最大值就行

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        int n = sc.nextInt();  // n个数
        int k = sc.nextInt();  // 两次
        
        int[] a = new int[n]; // 每个数的数值
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        long[] dp = new long[n + 1];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;
        
        for (int step = 1; step <= k; step++) {
            long[] current = new long[n + 1];
            Arrays.fill(current, Long.MIN_VALUE);
            
            // 求出当前可到达的位置
            int xmin = step - 1;
            int xmax = Math.min(6 * (step - 1), n); 
//            dduoln(xmin+" "+xmax);
            
            for (int x = xmin; x <= xmax; x++) {
                for (int d = 1; d <= 6; d++) {
                    int j = x + d;
                    if (j > n) {
                        continue;
                    }
                    current[j]=Math.max(current[j],dp[x] + a[j - 1]);
                }
            }
            dp = current;
        }
        
        int maxfoot = Math.min(6 * k, n); // 最大步数
        
        long max = Long.MIN_VALUE;
        for (int i = k; i <= maxfoot; i++) {
            max=Math.max(dp[i], max);
        }
        dduoln(max);
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

F 题

BFS

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static IOS sc=new IOS();
    static final int MOD = 998244353;

    public static void solve() throws IOException {
        
        int startX=0, startY=0, endX=0, endY=0;
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int h = sc.nextInt();
         
        char[][] grid = new char[n + 1][m + 1];  
        int[][] minTime = new int[n + 1][m + 1];
         
        for (int i = 0; i <= n; i++) {
            Arrays.fill(minTime[i], Integer.MAX_VALUE);
        }
         
        for (int i = 1; i <= n; i++) {
            String s = sc.next();
            for (int j = 1; j <= m; j++) {
                grid[i][j] = s.charAt(j-1);
                if (grid[i][j] == '*') { // 记录水源的位置
                    startX = i;
                    startY = j;
                } else if (grid[i][j] == '%') { // 记录终点的位置
                    endX = i;
                    endY = j;
                }
            }
        }
         
        int ans=0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, startX, startY, 1});
         
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int time = cur[0], x = cur[1], y = cur[2], state = cur[3];
             
            if (x == endX && y == endY) { // 到达了终点
                ans=time;
                break;
            }
             
            if (state == 0 && minTime[x][y] <= time) continue;
             
            minTime[x][y] = Math.min(minTime[x][y], time);
             
            if (x + 1 <= n) {
                if (grid[x + 1][y] == '#') {
                    if (y - 1 >= 1 && grid[x][y - 1] != '#') {
                        pq.offer(new int[]{time + 1, x, y - 1, 0});
                    }
                    if (y + 1 <= m && grid[x][y + 1] != '#') {
                        pq.offer(new int[]{time + 1, x, y + 1, 0});
                    }
                    if (state == 1) {
                        pq.offer(new int[]{time + h + 1, x + 1, y, 1});
                    }
                }
                else {
                    pq.offer(new int[]{time + 1, x + 1, y, 1});
                }
            }
            ans=Integer.MAX_VALUE;
        }
        
        dduoln(ans == Integer.MAX_VALUE ? -1 : ans);
        
    }
    
    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {solve();}
    }
    
    static <T> void dduo(T t) {System.out.print(t);}
    static <T> void dduoln(T t) {System.out.println(t);}

}

class Node implements Comparable<Node> {
    int x, y, nowT, abi;

    public Node(int x, int y, int nowT, int abi) {
        this.x = x;
        this.y = y;
        this.nowT = nowT;
        this.abi = abi;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(other.nowT, this.nowT); // 按照 nowT 值进行比较，形成最大堆
    }
}

class IOS{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public IOS(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public BigDecimal nextDecimal() throws IOException{
        return new BigDecimal(next());
    }
}

牛客竞赛主页