Problem 1: 2月29日
描述
给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。
只有闰年有2月29日，满足以下一个条件的年份为闰年：
年份能被4整除但不能被100整除
- 年份能被400整除
输入
第一行为一个整数T，表示数据组数。
之后每组数据包含两行。每一行格式为”month day, year”，表示一个日期。month为
{
“January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”,”October”, “November” , “December”}中的一个字符串。day与year为两个数字。
数据保证给定的日期合法且第一个日期早于或等于第二个日期。
输出
对于每组数据输出一行，形如”Case #X: Y”。X为数据组数，从1开始，Y为答案。
package mike.code.oj.micro.y2015.qual;
import java.util.HashMap;
import java.util.Scanner;
/**
* @author Mike
* @project oj-code
* @date 4/17/15, 10:24 AM
* @e-mail mike@d0n9x1n.dev
*/
public class P1 {
static final HashMap<String, Integer> months = new HashMap<String, Integer>();
static {
months.put("January", 1);
months.put("February", 2);
months.put("March", 3);
months.put("April", 4);
months.put("May", 5);
months.put("June", 6);
months.put("July", 7);
months.put("August", 8);
months.put("September", 9);
months.put("October", 10);
months.put("November", 11);
months.put("December", 12);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int num = scanner.nextInt();
for (int i = 0; i < num; i++) {
int flag = 0; // years to reduce
int sum = 0;
String s_month_str = scanner.next();
int s_month = months.get(s_month_str);
String s_date_str = scanner.next();
int s_date = Integer.valueOf(s_date_str.substring(0,
s_date_str.length()-1)
);
long s_year = scanner.nextLong();
if ((s_year % 4 == 0 && s_year % 100 != 0) || (s_year % 400 == 0)) {
if (s_month > 2) {
flag++;
}
}
String e_month_str = scanner.next();
int e_month = months.get(e_month_str);
String e_date_str = scanner.next();
int e_date = Integer.valueOf(e_date_str.substring(0,
e_date_str.length()-1)
);
long e_year = scanner.nextLong();
if ((e_year % 4 == 0 && e_year % 100 != 0) || (e_year % 400 == 0)) {
if ((e_month < 2) || (e_month == 2 && e_date < 29)) {
flag++;
}
}
for (long year = s_year; year <= e_year; year++) {
if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
sum++;
}
}
sum -= flag;
System.out.println("Case #" + (i + 1) + ": " + sum);
}
}
}
}
Problem 2: 回文字符序列
描述
给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为”a”, “a”, “aa”, “b”, “aba”，共5个。内容相同位置不同的子序列算不同的子序列。
输入
第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。
输出
对于每组数据输出一行，格式为”Case #X: Y”，X代表数据编号（从1开始），Y为答案。答案对100007取模。
package mike.code.oj.micro.y2015.qual;
import java.util.Scanner;
/**
* @author Mike
* @project oj-code
* @date 4/17/15, 11:16 AM
* @e-mail mike@d0n9x1n.dev
*/
public class P2 {
private static int len;
private static int num = 0;
public static void setLen(int i) {
len = i;
}
public static void getStringCombination(char[] k,
int start,
int wanted,
String pre)
{
if (wanted == 0) {
if (check(pre)) {
num++;
}
return;
}
int last_index = len - wanted;
for (int i = start; i <= last_index; i++) {
getStringCombination(k, i + 1, wanted - 1, pre + k[i]);
}
}
public static void getRs(String content) {
for (int i = 1; i <= content.length(); i++) {
getStringCombination(content.toCharArray(), 0, i, "");
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int N = scanner.nextInt();
for (int i = 0; i < N; i++) {
String content = scanner.next();
setLen(content.length());
getRs(content);
System.out.println("Case #" + (i + 1) + ": " + num);
num = 0;
}
}
}
public static boolean check(String str) {
boolean b = true;
int n = str.length();
for (int i = 0; i < n; i++) {
if (str.charAt(i) != str.charAt(n - i - 1)) {
b = false;
break;
}
}
return b;
}
}
Problem 3: 基站选址
描述
需要在一个N × M的网格中建立一个通讯基站，通讯基站仅必须建立在格点上。
网格中有A个用户，每个用户的通讯代价是用户到基站欧几里得距离的平方。
网格中还有B个通讯公司，维护基站的代价是基站到最近的一个通讯公司的路程（路程定义为曼哈顿距离）。
在网格中建立基站的总代价是用户通讯代价的总和加上维护基站的代价，最小总代价。
输入
第一行为一个整数T，表示数据组数。
每组数据第一行为四个整数：N, M, A, B。
接下来的A+B行每行两个整数x, y，代表一个坐标，前A行表示各用户的坐标，后B行表示各通讯公司的坐标。
输出
对于每组数据输出一行”Case #X: Y”，X代表数据编号（从1开始），Y代表所求最小代价。
package mike.code.oj.micro.y2015.qual;
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author Mike
* @project oj-code
* @date 4/17/15, 1:46 PM
* @e-mail mike@d0n9x1n.dev
*/
public class P3 {
static class Location {
int x;
int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Location{" + "x=" + x + ", y=" + y + '}';
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int N = scanner.nextInt();
int M = scanner.nextInt();
int A = scanner.nextInt();
int B = scanner.nextInt();
ArrayList<Location> AL = new ArrayList<Location>(A);
ArrayList<Location> BL = new ArrayList<Location>(B);
for (int j = 0; j < A; j++) {
AL.add(new Location(scanner.nextInt(), scanner.nextInt()));
}
for (int j = 0; j < B; j++) {
BL.add(new Location(scanner.nextInt(), scanner.nextInt()));
}
long MinCost = Integer.MAX_VALUE;
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= M; k++) {
long cost = calc(AL, BL, j, k);
MinCost = MinCost < cost ? MinCost : cost;
}
}
System.out.println("Case #" + (i + 1) + ": " + MinCost);
}
}
}
public static long calc(ArrayList<Location> Al,
ArrayList<Location> Bl,
int lx, int ly)
{
int res = 0;
for (Location loc : Al) {
res += (lx - loc.x) * (lx - loc.x) + (ly - loc.y) * (ly - loc.y);
}
int cost = Integer.MAX_VALUE;
for (Location loc : Bl) {
int t = Math.abs(lx - loc.x) + Math.abs(ly - loc.y);
cost = cost < t ? cost : t;
}
return res + cost;
}
}