ATCoder 332 A-D

A : Online Shopping (读懂题即可)

package AtCoder.begin332;

import java.util.Scanner;

public class A {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), s = sc.nextInt(), k = sc.nextInt();
        int[] p = new int[n + 10], q = new int[n + 10];

        for (int i = 1; i <= n; i ++ ) {
            p[i] = sc.nextInt();
            q[i] = sc.nextInt();
        }

        long ans = 0;
        for (int i = 1; i <= n; i ++ ) ans += (long) p[i] * q[i];

        if (ans >= s) System.out.println(ans);
        else System.out.println(ans + k);
    }
}

B : Glass and Mug (读懂题然后模拟即可)

package AtCoder.begin332;

import java.util.Scanner;

public class B {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int k = sc.nextInt(), g = sc.nextInt(), m = sc.nextInt();
        int ng = 0, nm = 0;
        for (int i = 1; i <= k; i ++ ) {
            if (ng == g) ng = 0;
            else if (nm == 0) nm = m;
            else {
                ng += nm;
                if (ng >= g) {
                    nm = ng - g;
                    ng = g;
                } else nm = 0;
            }
        }

        System.out.println(ng + " " + nm);
    }
}

C : T-shirts (读清题意然后求解即可)

package AtCoder.begin332;

import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt();
        String s = sc.next();

        int np = 0, nl = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i ++ ) {
            if (s.charAt(i) == '0') {
                ans = Math.max(ans, Math.max(np - m, 0) + nl);
                np = 0;
                nl = 0;
            } else if (s.charAt(i) == '1') np ++ ;
            else nl ++ ;
        }

        ans = Math.max(ans, Math.max(np - m, 0) + nl);
        System.out.println(ans);
    }
}

package AtCoder.begin332;

import javax.swing.plaf.nimbus.State;
import java.util.*;

public class D {

    /**
     * 思路比较简单 :
     *      因为交换相邻的行和相邻的列其实就等同于随意交换 -> 可以自己试一试
     *      dfs枚举行和列的全排列, 然后判断每一个状态的 a 是否和 b 相同
     *      相同了如何更新答案 -> 这个状态的交换次数就是行排列和列排列的逆序数之和
     *
     * 实现过程被edu了 :
     *      不必真的取交换, 直接记录行号和列号, 然后到时候根据行号和列号去原数据查就好了
     *      因为交换行和交换列是互不影响的
     *
     * 总结 :
     *      dfs还是需要多练习一下, 光有思路无法实现是最难受的
     * */

    static int[][] a, b;
    static int[] ri, wi;
    static int n, m, ans = Integer.MAX_VALUE;
    static Set<Integer> sr = new HashSet<>();
    static Set<Integer> sw = new HashSet<>();

    private static void init() {
        a = new int[n + 10][m + 10];
        b = new int[n + 10][m + 10];
        ri = new int[n + 10]; // 记录行当前的排列
        wi = new int[m + 10]; // 记录列当前的排列
    }

    private static void dfs_row(int u) { // 枚举行的全排列
        if (u > n) dfs_col(1);
        for (int i = 1; i <= n; i ++ ) {
            if (sr.contains(i)) continue;
            ri[u] = i;
            sr.add(i);
            dfs_row(u + 1);
            sr.remove(i);
        }
    }

    private static void dfs_col(int u) { // 枚举列的全排列
        if (u > m) {
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= m; j ++ )
                    if (a[ri[i]][wi[j]] != b[i][j]) return ; // 不符合要求

            // 算出这个状态的答案
            int res = 0;
            for (int i = 1; i <= n; i ++ )
                for (int j = i + 1; j <= n; j ++ )
                    if (ri[i] > ri[j]) res ++ ;

            for (int i = 1; i <= m; i ++ )
                for (int j = i + 1; j <= m; j ++ )
                    if (wi[i] > wi[j]) res ++ ;

            ans = Math.min(ans, res); // 尝试更新答案
            return ;
        }

        for (int i = 1; i <= m; i ++ ) {
            if (sw.contains(i)) continue;
            wi[u] = i;
            sw.add(i);
            dfs_col(u + 1);
            sw.remove(i);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); m = sc.nextInt();
        init();

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                a[i][j] = sc.nextInt();

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                b[i][j] = sc.nextInt();

        dfs_row(1);
        if (ans == Integer.MAX_VALUE) System.out.println(-1); // 无解
        else System.out.println(ans);
    }
}