section1.1主要包括四道题和两个编程知识介绍。下面将对这6个部分内容进行学习。
Your Ride Is Here
这道题没什么难度，读懂题目意思就行：把两个字符串按照题目要求转换成数字，然后对47取模，比较是否相等。
代码如下
/*
LANG: JAVA
TASK: ride
*/
import java.io.*;
import java.util.*;
public class ride {
public static void main (String [] args) throws IOException {
BufferedReader f = new BufferedReader(new FileReader("ride.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("ride.out")));
Scanner in = new Scanner(f);
String comet = null;
String group = null;
while (in.hasNextLine()) {
comet = in.nextLine();
group = in.nextLine();
}
if (caculate(group) == caculate(comet)) {
out.println("GO");
}else {
out.println("STAY");
}
out.close(); // close the output file
}
public static int caculate(String str) {
int size = str.length();
int result = 1;
for (int i = 0; i < size; i++) {
result = result * (str.charAt(i) - 'A' + 1);
}
return result % 47;
}
}
Programming Contest Problem Types
这个内容介绍了编程比赛中的题目类型，Hal Burch有研究发现：编程比赛里面只有16种比赛类型。这16种比赛类型的前几个几乎占了IOI比赛题目的80%。
这16种题型分别是：
- Dynamic Programming
- Greedy
- Complete Search
- Flood Fill
- Shortest Path
- Recursive Search Techniques
- Minimum Spanning Tree
- Knapsack
- Computational Geometry
- Network Flow
- Eulerian Path
- Two-Dimensional Convex Hull
- BigNums
- Heuristic Search
- Approximate Search
- Ad Hoc Problems
稍微复杂一点的程序就结合例上述多个类型，所以呀，想把USACO刷完，还是挺不容易的。
Ad Hoc Problems
这种问题也叫“临时问题”，是上面16种类型中最后一种。它不属于标准的，具有精心研究的解决方案，反而是每个问题都没有特定的方法来解决。
这种问题一般需要仔细阅读，也需要一些合理的优化和一些分析。解决方案可能需要一个新颖的数据结构等。
Greedy Gift Givers
这道题就是典型的Ad Hoc Problems问题。题目的大概意思是分礼物。难点在于读懂题目和如何读数据。难度倒是不大，代码如下
/*
LANG: JAVA
TASK: gift1
*/
import java.io.*;
import java.util.*;
public class gift1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new FileReader("gift1.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("gift1.out")));
int size = Integer.parseInt(br.readLine());
String[] names = new String[size];
HashMap<String, Integer> net = new HashMap<String, Integer>();
for (int i = 0; i < size; i++) {
String name = br.readLine();
net.put(name, 0);
names[i] = name;
}
for (int i = 0; i < size; i++) {
String name = br.readLine();
String gift = br.readLine();
String[] temp = gift.split(" ");
int sum = Integer.parseInt(temp[0]);
int div = Integer.parseInt(temp[1]);
if (div != 0) {
for (int j = 0; j < div; j++) {
String target = br.readLine();
net.put(target, net.get(target) + sum / div);
}
net.put(name, net.get(name) - (sum - sum % div));
}
}
for (String nameToPrint : names) {
pw.println(nameToPrint + " " + net.get(nameToPrint));
}
pw.close();
br.close();
}
}
Friday the Thirteenth
这道题也是需要读懂题目。判断闰年和计算天数的函数比较简单，关键是最后输出的时候，数组里面的值分别对应星期几容易出错。
/*
LANG: JAVA
TASK: friday
*/
import java.io.*;
public class friday {
public static void main(String[] args) throws Exception {
int count[] = new int[7];
BufferedReader br = new BufferedReader(new FileReader("friday.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("friday.out")));
int years = Integer.parseInt(br.readLine());
int allDays = 0;
for (int i = 1900; i < 1900 + years; i++) {
for (int j = 1; j <= 12; j++) {
count[(allDays + 13) % 7]++;
allDays += countDaysInMonth(j, i);
}
}
pw.println(count[6] + " " + count[0] + " " + count[1] + " " + count[2] + " " + count[3] + " " + count[4] + " " + count[5]);
pw.close();
br.close();
}
public static boolean isLeapYear(int year) {
if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
return true;
}else {
return false;
}
}
public static int countDaysInMonth(int month, int year) {
switch (month) {
case 4:
case 6:
case 9:
case 11:
return 30;
case 2:
if (isLeapYear(year)) {
return 29;
}else {
return 28;
}
default:
return 31;
}
}
}
Broken Necklace
这个题算的上是secion1.1里最难的题了。题目也不太好读懂。看懂题目后直观感觉是暴力求解。这是我写的代码。
/*
LANG: JAVA
TASK: beads
*/
import java.io.*;
public class beads {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new FileReader("beads.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("beads.out")));
int numOfBeads = Integer.parseInt(br.readLine());
String necklace = br.readLine();
necklace = necklace + necklace;
int maxTotal = 0;
for (int i = 1; i < necklace.length() - 1; i++) {
int total = 0;
char start = necklace.charAt(i);
char end = necklace.charAt(i - 1);
//找到有意义的起始点
for (int j = i; j < necklace.length() - 1; j++) {
if (necklace.charAt(j) == 'w') {
continue;
} else {
start = necklace.charAt(j);
break;
}
}
for (int j = i; j < necklace.length() - 1; j++) {
if (necklace.charAt(j) == 'w') {
total++;
} else {
if (necklace.charAt(j) == start) {
total++;
}else {
break;
}
}
}
//找到有意义的起始点
for (int j = i - 1; j >= 0; j--) {
if (necklace.charAt(j) == 'w') {
continue;
} else {
end = necklace.charAt(j);
break;
}
}
for (int j = i - 1; j >= 0; j--) {
if (necklace.charAt(j) == 'w') {
total++;
} else {
if (necklace.charAt(j) == end) {
total++;
}else {
break;
}
}
}
maxTotal = maxTotal > total?maxTotal:total;
}
maxTotal = maxTotal < numOfBeads?maxTotal:numOfBeads;
pw.println(maxTotal);
pw.close();
br.close();
}
}
如果要算复杂度的话，估计有4×N^2，可能比一般人写的更慢。提交通过后看了官网给的答案，有一个复杂度为O(n)的方法。
/*
LANG: JAVA
TASK: beads
*/
import java.io.*;
public class beads1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new FileReader("beads.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("beads.out")));
int numOfBeads = Integer.parseInt(br.readLine());
String necklace = br.readLine();
necklace = necklace + necklace;
int[][] left = new int[necklace.length() + 1][2];
int[][] right = new int[necklace.length() + 1][2];
left[0][0] = left[0][1] = 0;
for (int i = 1; i <= necklace.length(); i++) {
if (necklace.charAt(i - 1) == 'r') {
left[i][0] = left[i - 1][0] + 1;//第0列存r，假如为r，则加一
left[i][1] = 0;//第1列存b，假如为r，则置为0
} else if (necklace.charAt(i - 1) == 'b') {
left[i][1] = left[i - 1][1] + 1;
left[i][0] = 0;
} else {
left[i][0] = left[i - 1][0] + 1;
left[i][1] = left[i - 1][1] + 1;
}
}
right[necklace.length()][0] = right[necklace.length()][1] = 0;
for (int i=necklace.length() - 1; i >= 0; i--){
if (necklace.charAt(i) == 'r'){
right[i][0] = right[i + 1][0] + 1;//第0列存r，假如为r，则加一
right[i][1] = 0;//第1列存b，假如为r，则置为0
} else if (necklace.charAt(i) == 'b'){
right[i][1] = right[i + 1][1] + 1;
right[i][0] = 0;
} else {
right[i][0] = right[i + 1][0] + 1;
right[i][1] = right[i + 1][1] + 1;
}
}
int m = 0;
for (int i = 0; i < necklace.length(); i++) {
m = Math.max(m, Math.max(left[i][0], left[i][1]) + Math.max(right[i][0], right[i][1]));
}
m = Math.min(m, numOfBeads);
pw.println(m);
pw.close();
br.close();
}
}