6.26 ，学校举行了程序设计大赛校赛，给我的印象就是，题目简单，没有难度梯度。
以下是对每道题的解析：
第一题：母猪的故事
这个题看着挺简单，写起来，也挺简单。。。
如果你自己一下想不通，可以用最死的方法递推，当然，如果你自己分析分析，列举一下，就会发现这是个裴波那契数列。
所以，解决方案简单粗暴：
#include <stdio.h>
#include <memory.h>
int fun(int n)
{
if (n == 1)
return 1;
if(n == 2)
return 2;
return fun(n - 1) + fun(n - 2);
}
int main()
{
int t;
int x;
scanf("%d", &t);
while (t--)
{
scanf("%d", &x);
printf("%d\n", fun(x));
}
return 0;
}
第二题：开门人和关门人
主要就是一个计算时间大小的题，其实再简单一点，因为它时间格式很规范，所以，直接比较字符串就好了。-0-
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
for (int tt = 0; tt<t; tt++){
int n = cin.nextInt();
List<Test> l = new ArrayList<>();
for (int y = 0; y<n; y++){
cin.nextLine();
Test tmp = new Test();
tmp.no = cin.next();
tmp.in = cin.next();
tmp.out = cin.next();
l.add(tmp);
}
int fi = 0, lo = 0;
for(int y = 0; y<l.size(); y++){
if(l.get(y).in.compareTo(l.get(fi).in) < 0){
fi = y;
}
if (l.get(y).out.compareTo(l.get(lo).out) > 0){
lo = y;
}
}
System.out.println(l.get(fi).no + " " + l.get(lo).no);
}
}
public static class Test{
public String no;
public String in;
public String out;
}
}
第三题：Zhuge Liang’s Password
看黑体字就好，其实不管怎样，说简单一点，这道题目考得就是矩阵旋转，一直向一个方向旋转就好了。
#include <stdio.h>
#include <memory.h>
int N1[30][30];
int N2[30][30];
void rotate(int l)
{
int m[30][30];
int i, j;
memset((void*)m, 0, sizeof(int)* 30 * 30);
for (i = 0; i < l; i++)
{
for (j = 0; j < l; j++)
{
m[j][l - i - 1] = N2[i][j];
}
}
memcpy((void*)N2, (void*)m, sizeof(int)*30*30);
}
int f(int l)
{
int i,j;
int count = 0;
for (i = 0; i < l; i++)
{
for (j = 0; j < l; j++)
{
if (N1[i][j] == N2[i][j])
{
count++;
}
}
}
return count;
}
int main()
{
int t;
int x;
int i, j;
while (scanf("%d", &t) != EOF)
{
if(t == 0)
break;
memset((void*)N1, 0, sizeof(int)* 30 * 30);
memset((void*)N2, 0, sizeof(int)* 30 * 30);
for (i = 0; i < t; i++)
{
for (j = 0; j < t; j++)
scanf("%d", &N1[i][j]);
}
for (i = 0; i < t; i++)
{
for (j = 0; j < t; j++)
scanf("%d", &N2[i][j]);
}
x = 0;
for (i = 0; i < 4; i++)
{
rotate(t);
j = f(t);
if (j > x)
x = j;
}
printf("%d\n", x);
}
return 0;
}
第四题：最少拦截系统
这道题，是以前遇到过的题，解决方案无非贪心。
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n = cin.nextInt();
Test t = new Test();
List<Test> list = new ArrayList<>();
int l = 0;
for(int i = 0; i<n; i++){
if(i == 0){
t.max = cin.nextInt();
l = t.max;
}
else{
int tmp = cin.nextInt();
boolean flag = false;
for (int q = 0; q < list.size(); q++){
if (tmp < list.get(q).min){
flag = true;
list.get(q).min = tmp;
break;
}
}
if(tmp > l){
t.min = l;
list.add(t);
t = new Test();
t.max = tmp;
}
if(!flag)
l = tmp;
}
}
t.min = l;
if (n > 0)
list.add(t);
merge(list);
System.out.println(list.size());
}
}
private static void merge(List<Test> list){
for(int i = 0; i<list.size(); i++){
Test t = list.get(i);
for (int j = i + 1; j < list.size(); j++){
if(list.get(j).max < t.min){
t.min = list.get(j).min;
list.remove(j);
if(j < i)
j--;
}
}
}
}
public static class Test{
int max;
int min;
}
}
第五题：最短区间版大家来找碴
我开始拿到这道题的时候好像也无从下手，觉得应该是个动态规划类的题目，比较麻烦，但是后面我发现并没有那么难，直接上深度搜索解决掉（性能很低）。- –
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
int n, m;
n = cin.nextInt();
m = cin.nextInt();
if(n == m && n == 0)
break;
int[] n1 = new int[n];
for (int i = 0; i<n; i++){
n1[i] = cin.nextInt();
}
int x;
for (int i = 0; i<m; i++){
x = cin.nextInt();
List<Integer> q = new ArrayList<>();
for(int j = 0; j<x; j++){
q.add(cin.nextInt());
}
int xx= 0xffffff;
for(int j = 0; j<n; j++){
int t = f(n1, c(q), j);
xx = t<xx?t:xx;
}
System.out.println(xx);
}
}
}
private static int f(int[] n, List<Integer> q, int start){
int i;
for(i = start; i<n.length; i++){
if (in(q, n[i])){
int j;
for(j = i+1; j<n.length; j++){
if (n[j] != n[i])
break;
}
i = j-1;
break;
}
}
return dp(n, q, i, 0);
}
private static int dp(int[] n, List<Integer> q, int pos, int deep){
if(q.size() == 0){
return deep;
}
if(pos >= n.length){
return 0xfffff;
}
d(q, n[pos]);
return dp(n, q, pos+1, deep+1);
}
private static List<Integer> c(List<Integer> q){
List<Integer> qq = new ArrayList<>();
for(int qqq : q){
qq.add(qqq);
}
return qq;
}
private static void d(List<Integer> q, int t){
for(int i = 0; i<q.size(); i++){
if (q.get(i) == t){
q.remove(i);
i--;
}
}
}
private static boolean in(List<Integer> q, int t){
for(int i = 0; i<q.size(); i++){
if (q.get(i) == t){
return true;
}
}
return false;
}
}
第六题：Dating with girls
No talking, just show the code.
import java.util.HashSet;
import java.util.Scanner;
public class Main {
static class Pair{
public int x , y;
public Pair(int i , int j){
x = i ; y = j;
}
public boolean equals(Object i){
if(i instanceof Pair){
return ((Pair)i).x == x && ((Pair)i).y == y;
}
return false;
}
public int getVal(){
return x + y;
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int caseNum = s.nextInt() , n = 0 , k = 0;
while(caseNum -- > 0){
n = s.nextInt() ; k = s.nextInt();
int[] data = new int[n];
for(int i = 0 ; i < n ; i ++){
data[i] = s.nextInt();
}
Pair x = null;
HashSet<Pair> set = new HashSet<Pair>();
boolean flag = false;
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
flag = false;
x = new Pair(data[i] , data[j]);
if(x.getVal() == k){
for(Pair y : set){
if(x.equals(y)){
flag = true;
break;
}
}
if(!flag){
set.add(x);
}
}
}
}
System.out.println(set.size());
}
s.close();
}
}
第七题：计算直线的交点数
对于以前没有接触过这个题的我来说，确实比较难了，因为撸了六道题之后已经没有多少脑力了，快虚脱了。。。这道题也没做出来。等我下去学习指导再来补充算法和思路。
第八题：命运
话不多说，就是简单的额深度搜索。
#include <stdio.h>
#include <memory.h>
int N[21][1001];
int f(int x, int y, int n, int m)
{
int down, r1, r2;
int k, t;
if (x == n && y == m)
{
return N[x][y];
}
if (x > n || y > m)
return -0xffffff;
down = f(x + 1, y, n, m);
r1 = f(x, y+1, n, m);
r2 = -0xffffff;
for (k = 2; y * k <= m; k++)
{
t = f(x, y * k, n, m);
if (t > r2)
r2 = t;
}
t = down > r1 ? down : r1;
t = t > r2 ? t : r2;
return t + N[x][y];
}
int main()
{
int t;
int i, j;
int n, m;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
memset((void*)N, 0, sizeof(int)* 21 * 1001);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
scanf("%d", &N[i][j]);
printf("%d\n", f(1, 1, n, m));
}
return 0;
}
总之，这次比赛给我的感受就是，只要自己平时稍微有点基础，一个人做出4、5道题是没有任何问题的，然而，真正做出4道题以上的只有13个队，挺为我们学校的算法担心的。- –
最后申明，这些代码可能不太规范，性能不够好，我只是为了快速实现算法，所以没优化代码，请勿模仿。
最后，感谢我的小伙伴@Sunflyer 和 @dayupnie