北大POJ 1000 ~ 1009
1. A+B
🍑 POJ1000 a+b
🍔 签到题
import java.io.*;
import java.util.*;
public class Main
{public static void main(String args[]) throws Exception{Scanner cin=new Scanner(System.in);int a=cin.nextInt(),b=cin.nextInt();System.out.println(a+b);}
}
2. 高精度
🍑 POJ1001 求高精度幂
输入
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
输出
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
🍔 BigDecimal
🍑 BigDecimal.stripTrailingZeros()：移除尾部所有没有意义的 0
🍑 BigDecimal.toPlainString()：原值转成字符串返回
🍑 BigDecimal.toString()：有可能会返回科学计数法🍑 String.replaceFirst(String regex, String replacement);
🍁 正则匹配前导零：^0*
import java.math.BigDecimal;
import java.util.*;public class N1001高精度
{public static void main(String[] args){Scanner sc = new Scanner(System.in);while (sc.hasNext()){
// double a = sc.nextDouble();
// BigDecimal bd = new BigDecimal(a);BigDecimal bd = sc.nextBigDecimal();int b = sc.nextInt();String value = bd.pow(b).stripTrailingZeros().toPlainString().replaceFirst("^0*", "");System.out.println(value);}}
}
3. 487-3279
🍑 POJ1002 487-3279
输入
12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
输出
310-1010 2
487-3279 4
888-4567 3
🍔 AC代码：字符串存电话号码
🥞 Treeset：自动按升序对元素进行排序
🥞
import java.util.*;public class Main
{public static void main(String[] args){char[] key = new char[128];// 对 字母 映射成 对应的数字key['A'] = key['B'] = key['C'] = '2';key['D'] = key['E'] = key['F'] = '3';key['G'] = key['H'] = key['I'] = '4';key['J'] = key['K'] = key['L'] = '5';key['M'] = key['N'] = key['O'] = '6';key['P'] = key['R'] = key['S'] = '7';key['T'] = key['U'] = key['V'] = '8';key['W'] = key['X'] = key['Y'] = '9';// HashMap<String,Integer> map = new HashMap();
//不知道为什么使用HashMap超时，TreeMap通过，可能散列函数对样例不太适用吧TreeMap<String, Integer> map = new TreeMap();// TreeMap 默认排升序String tmp[] = null;Scanner sc = new Scanner(System.in);
// sc = new Scanner(new File("in.txt"));int n = sc.nextInt();boolean flag = false;for (int i = 0; i < n; i++){String ss = sc.next();char[] arr = ss.toCharArray();// 转为数组处理String num = "";for (int j = 0; j < arr.length; j++){if (arr[j] >= '0' && arr[j] <= '9'){num += arr[j];// 字符串拼接} else if (arr[j] >= 'A' && arr[j] <= 'Z'){num += key[arr[j]];}}if (map.containsKey(num)){flag = true;map.put(num, map.get(num) + 1);} else{map.put(num, 1);}}if (!flag)System.out.println("No duplicates.");else{for (String k : map.keySet()){int value = map.get(k);if (value > 1){for (int i = 0; i < k.length(); i++){System.out.print(k.charAt(i));if (i == 2)System.out.print("-");}System.out.println(" " + value);}}}}
}
🍑 没考虑高位为 0 的情况
😪 WA版本
import java.util.*;
import java.io.*;public class Main
{static int[] st = new int[256];static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException{
// Scanner sc = new Scanner(System.in);
// int n = sc.nextInt();//注意 scanf 不处理回车键（会留在缓冲区影响下一次输入）int n = Integer.parseInt(in.readLine());TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();// key 表示电话号码，value 表示出现次数st['A'] = st['B'] = st['C'] = 2;st['D'] = st['E'] = st['F'] = 3;st['G'] = st['H'] = st['I'] = 4;st['J'] = st['K'] = st['L'] = 5;st['M'] = st['N'] = st['O'] = 6;st['P'] = st['R'] = st['S'] = 7;st['U'] = st['V'] = st['T'] = 8;st['W'] = st['X'] = st['Y'] = 9;for (int i = 0; i < 10; i++){st[i + '0'] = i;}boolean isDuplicate = false;for (int i = 0; i < n; i++){String s = in.readLine();s = s.replace("-", "");int len = s.length();int num = 0;
// 处理号码for (int j = 0; j < len; j++){char c = s.charAt(j);if (c != '-')num = num * 10 + st[c];}
// int t = map.getOrDefault(num, 0);int t = map.get(num) == null ? 0 : map.get(num);if (t > 0)isDuplicate = true;// 只要有一个号码出现一次重复map.put(num, t + 1);// 记录号码的次数}if (!isDuplicate){System.out.println("No duplicates.");} else{for (int k : map.keySet()){int value = map.get(k);if (value > 1){
// out.write(k / 10000 + "-" + k % 10000 + " " + value + "\\n");// k%10000 会出现 0 的情况，不可行System.out.printf("%03d-%04d %d", k / 10000, k % 10000, value);}}}out.flush();}
}
4. 叠卡片
🍑 POJ 1003 Hangover
输入
1.00
3.71
0.04
5.19
0.00
输出
3 card(s)
61 card(s)
1 card(s)
273 card(s)
🍑 大体题意：
🍤 从上到下，第1张卡片能伸出 1/2 的长度，第2张卡片 1/3，第三张 1/4 ……
🍤 问：需要多少张卡片才能伸出 输入 的长度 n
🍤 每张卡片的长度为 1
import java.util.Scanner;public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);while (sc.hasNext()){double n = sc.nextDouble();if (n == 0.00)break;double len = 0;int i = 2;int ans = 0;while (len < n){len += 1.0 / i;i++;}System.out.printf("%d card(s)\\n", i - 2);}}
}
5. 财务管理
🍑 POJ1004 Financial Management
输入
100.00
489.12
12454.12
1234.10
823.05
109.20
5.27
1542.25
839.18
83.99
1295.01
1.75
输出
$1581.42
🍑 输入12个数求平均数
import java.util.Scanner;public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);double sum = 0;for (int i = 0; i < 12; i++)sum += sc.nextDouble();System.out.printf("$%.2f", sum / 12);//浮点数输出用 %f}
}
6. 我想我需要一艘船屋
🍑 POJ 1005 I Think I Need a Houseboat
输入
2
1.0 1.0
25.0 0.0
输出
Property 1: This property will begin eroding in year 1.
Property 2: This property will begin eroding in year 20.
END OF OUTPUT.
🍑 Π：Math.PI
🍑 求出 坐标 到 原点 的 欧几里得距离 --> 半径 --> 面积 --> 年数（向上取整）
import java.util.Scanner;public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 1; i <= n; i++){double x = sc.nextDouble();double y = sc.nextDouble();double r = Math.sqrt(x * x + y * y);double s = Math.PI * r * r / 2;int year = (int) s / 50 + 1;System.out.printf("Property %d: This property will begin eroding in year %d.\\n", i, year);}System.out.println("END OF OUTPUT.");}
}
7. 生理周期
🍑 POJ 1006 Biohythms
输入
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
输出
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
🍑 跳跃枚举
🍤 缓冲流输入输出
🍤 判断条件放 for 里边
🍤 输出格式注意空格（Presentation Error）
import java.io.*;public class Main
{public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));for (int j = 1;; j++){String[] ss = in.readLine().split(" ");int p = Integer.parseInt(ss[0]);int e = Integer.parseInt(ss[1]);int i = Integer.parseInt(ss[2]);int d = Integer.parseInt(ss[3]);if (p == -1 && e == -1 && i == -1 && d == -1)break;int k = d + 1;for (; (k - p) % 23 != 0; k++);for (; (k - e) % 28 != 0; k += 23);for (; (k - i) % 33 != 0; k += 23 * 28);out.write("Case " + j + ": the next triple peak occurs in " + (k - d) + " days.\\n");}out.flush();}
}
🍑 中国剩余定理
🙈 线性同余方程、扩展欧几里得求逆元 （挖个坑）
import java.io.*;
import java.util.*;public class Main
{public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));int M = 21252;int cnt = 1;while (true){String[] ss = in.readLine().split(" ");int p = Integer.parseInt(ss[0]);int e = Integer.parseInt(ss[1]);int i = Integer.parseInt(ss[2]);int d = Integer.parseInt(ss[3]);if (p == -1 && e == -1 && i == -1 && d == -1)break;int res = (5544 * p + 14421 * e + 1288 * i) % M;res -= d;if (res <= 0)res = (res + M - 1) % M + 1;out.write("Case " + cnt + ": the next triple peak occurs in " + res + " days.\\n");}out.flush();}
}
8. DNA 排序
🍑 POJ 1007 DNA Sorting
🍑 HDOJ 1379 DNA Sorting
👨🏫 区别：杭电是多组输入
输入
110 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
输出
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
🍑 按 逆序数 进行 稳定排序
🥞 归并排序求逆序数
🥞 暴力求逆序数也行啦
🍑 HDOJ AC啦
import java.util.Scanner;public class Main
{static int l;static char[] a;static char[] tmp;static boolean[] st;public static void main(String[] args){Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0){l = sc.nextInt();int n = sc.nextInt();String[] ss = new String[n];long[] cnt = new long[n];// 记录每个字符串的逆序数for (int i = 0; i < n; i++){ss[i] = sc.next();}for (int i = 0; i < n; i++){a = new char[l];tmp = new char[l];a = ss[i].toCharArray();long t = mergeSort(0, l - 1);cnt[i] = t;}// 按逆序对升序排序int[] mk = new int[n];// 按升序存 DNA 数组下标int k = 0;st = new boolean[n];while (k < n){int min = -1;for (int i = 0; i < n; i++){if (!st[i] && (min == -1 || cnt[i] < cnt[min]))min = i;}mk[k++] = min;st[min] = true;}for (int i = 0; i < n; i++){System.out.println(ss[mk[i]]);}}}// 输入区间的左右边界，返回该区间的逆序数private static long mergeSort(int l, int r){if (l == r)return 0;int mid = l + r >> 1;
// 分治求解long ans = mergeSort(l, mid) + mergeSort(mid + 1, r);int i = l;// 左区间指针int j = mid + 1;// 右区间指针int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])tmp[k++] = a[i++];else{tmp[k++] = a[j++];ans += mid - i + 1;// 左区间剩余的元素都比当前元素大，更新结果}}// 处理掉剩余的元素while (i <= mid)tmp[k++] = a[i++];while (j <= r)tmp[k++] = a[j++];k = 0;for (i = l; i <= r; i++)a[i] = tmp[k++];return ans;}
}
😡 POJ RE啦
import java.util.Scanner;public class N1007DNA排序
{static int l;static char[] a;static char[] tmp;static boolean[] st;public static void main(String[] args){Scanner sc = new Scanner(System.in);l = sc.nextInt();int n = sc.nextInt();String[] ss = new String[n];long[] cnt = new long[n];// 记录每个字符串的逆序数for (int i = 0; i < n; i++){ss[i] = sc.next();}for (int i = 0; i < n; i++){a = new char[l];tmp = new char[l];a = ss[i].toCharArray();long t = mergeSort(0, l - 1);cnt[i] = t;}// 按逆序对升序排序int[] mk = new int[n];// 按升序存 DNA 数组下标int k = 0;st = new boolean[n];while (k < n){int min = -1;for (int i = 0; i < n; i++){if (!st[i] && (min == -1 || cnt[i] < cnt[min]))min = i;}mk[k++] = min;st[min] = true;}for (int i = 0; i < n; i++){System.out.println(ss[mk[i]]);}}// 输入区间的左右边界，返回该区间的逆序数private static long mergeSort(int l, int r){if (l == r)return 0;int mid = l + r >> 1;
// 分治求解long ans = mergeSort(l, mid) + mergeSort(mid + 1, r);int i = l;// 左区间指针int j = mid + 1;// 右区间指针int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])tmp[k++] = a[i++];else{tmp[k++] = a[j++];ans += mid - i + 1;// 左区间剩余的元素都比当前元素大，更新结果}}// 处理掉剩余的元素while (i <= mid)tmp[k++] = a[i++];while (j <= r)tmp[k++] = a[j++];k = 0;for (i = l; i <= r; i++)a[i] = tmp[k++];return ans;}
}
9. 玛雅日历
🍑 POJ 1008 Maya Calendar
输入
3
10. zac 0
11. pop 0
12. zac 1995
输出
3
3 chuen 0
1 imix 0
9 cimi 2801
🍑 思路
🥞 Haab --> 天数 --> Tzolkin
🥞 Tzolkin 的日期格式： a1 b2 c3 d4 e6 f7 g8 ……
🥞 注意边界值取模映射成 0 的问题
🙈 打表存映射值也行，代码可能会简短一些
import java.io.*;
public class Main
{static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException{int n = Integer.parseInt(in.readLine());System.out.println(n);while (n-- > 0){String[] ss = in.readLine().split(" ");String s = ss[0].replace(".", "").trim();int d = Integer.parseInt(s);int m = getHaab(ss[1]);int y = Integer.parseInt(ss[2]);int days = d + 1 + (m - 1) * 20 + y * 365;// 日 从0开始，每月 20 天，每年 365 天// Tzolkin：每年13个时期，每个时期20种符号，每年 260 天int year = days / 260;if(days % 260 == 0)//刚好整除说明是前一年最后一天year = year - 1;days %= 260;//除去整年的时间，剩下的天数int sym= days % 20;//标记符号 20天一个周期String symbol= getName(sym);// getName方法内部特殊处理了 sym = 0 映射到 20 的情况int num = days % 13;//数字 13 天一个周期if(num == 0)// 0 映射成13num = 13;System.out.println(num + " " + symbol+ " " + year);}}// 返回日期对应的代号public static String getName(int i){if (i == 1){return "imix";} else if (i == 2){return "ik";} else if (i == 3){return "akbal";} else if (i == 4){return "kan";} else if (i == 5){return "chicchan";} else if (i == 6){return "cimi";} else if (i == 7){return "manik";} else if (i == 8){return "lamat";} else if (i == 9){return "muluk";} else if (i == 10){return "ok";} else if (i == 11){return "chuen";} else if (i == 12){return "eb";} else if (i == 13){return "ben";} else if (i == 14){return "ix";} else if (i == 15){return "mem";} else if (i == 16){return "cib";} else if (i == 17){return "caban";} else if (i == 18){return "eznab";} else if (i == 19){return "canac";} else// 0 即第20个符号{return "ahau";}}// 返回月份名称对应 数值private static int getHaab(String str){if (str.equals("pop"))return 1;else if (str.equals("no"))return 2;else if (str.equals("zip"))return 3;else if (str.equals("zotz"))return 4;else if (str.equals("tzec"))return 5;else if (str.equals("xul"))return 6;else if (str.equals("yoxkin"))return 7;else if (str.equals("mol"))return 8;else if (str.equals("chen"))return 9;else if (str.equals("yax"))return 10;else if (str.equals("zac"))return 11;else if (str.equals("ceh"))return 12;else if (str.equals("mac"))return 13;else if (str.equals("kankin"))return 14;else if (str.equals("muan"))return 15;else if (str.equals("pax"))return 16;else if (str.equals("koyab"))return 17;else if (str.equals("cumhu"))return 18;else if (str.equals("uayet"))return 19;return -1;}
}
10. 图像边缘检测
🍑 POJ 1009 Edge Detection
输入
7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
输出
7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0
0
🍑 思路
🥞 奇特的输入模式，输入图片宽度每行输入 x n，x表示像素值，n 表示顺序数有多少个连续的 x
🥞 像素值有变化，差值才会有区别，关键点在于每一个连续段的起点位置（主要是暴力过不了啊）
🍑 红框/圈 表示原值连续段起点，蓝色位置表示最大差值连续段起点
🍤 假设 蓝色 只分布在 红色 周围 8 个点是正确的，我们暂且只计算每个点的周围8个点
🍑 照葫芦画瓢（不支持lambda表达式）
import java.util.*;public class Main
{static int N = 1010;static Px[] arow = new Px[8 * N];// 存起点周围的点static int[][] line = new int[N][2];// 存连续段，con[][0] 存值，con[][1]存长度static int wide, idx, total;// wide 存宽度，idx 存连续段数，total 存总像素点数public static void main(String[] args){Scanner sc = new Scanner(System.in);while (sc.hasNext()){wide = sc.nextInt();if (wide == 0)break;// 初始化idx = 0;total = 0;int val, len;while (true){val = sc.nextInt();len = sc.nextInt();if (len <= 0)break;line[idx][0] = val;line[idx++][1] = len;total += len;}System.out.println(wide);int pos = 1;// 记录当前位置int cnt = 0;for (int i = 0; i <= idx; i++)// 枚举每个连续片段{//减 1 是因为数组下标从 0 开始int row = (pos - 1) / wide;// 当前点所在行数int col = (pos - 1) % wide;// 当前点所处列数// 枚举起点周围的 8 个点for (int j = row - 1; j <= row + 1; j++){for (int k = col - 1; k <= col + 1; k++){int t = j * wide + k;// 点if (j < 0 || k < 0 || k >= wide || t >= total)// 越界continue;//周围 8 个点的值全部计算出来存着arow[cnt++] = new Px(t + 1, getCode(t + 1));}}pos += line[i][1];// 转到下一个起点}//按位置升序进行排序Arrays.sort(arow, 0, cnt, new Comparator<Px>(){public int compare(Px o1, Px o2){return o1.pos - o2.pos;}});Px tp = arow[0];//tp记录上一个连续段for (int i = 0; i < cnt; i++){if (arow[i].code == tp.code)//值相等跳过continue;System.out.println(tp.code + " " + (arow[i].pos - tp.pos));tp = arow[i];}//处理 一下最后一个 连续段System.out.println(tp.code + " " + (total - tp.pos+1));System.out.println("0 0");}System.out.println("0\\n");}// 输出位置，返回这个位置与周围点的最大差值static int getCode(int pos){int num = getnum(pos), ret = 0;int row = (pos - 1) / wide;// pos所处排数int col = (pos - 1) % wide;// pos所处列数for (int i = row - 1; i <= row + 1; i++)// 枚举pos周围八个方向for (int j = col - 1; j <= col + 1; j++){int tpos = i * wide + j;if (i < 0 || j >= wide || j < 0 || tpos == pos - 1 || tpos >= total)continue;int temp = getnum(tpos + 1);if (ret < Math.abs(temp - num))ret = Math.abs(temp - num);}return ret;}
// 在原图种找出这个位置所在连续段起点的值static int getnum(int pos){int p = 0, i = 0;while (p < pos)p += line[i++][1];return line[i - 1][0];}// 像素点类static class Px{int pos;// 表示这个像素点的位置int code;// 表示这个点的答案值public Px(int pos, int code){super();this.pos = pos;this.code = code;}}
}