Skip to content
Menu
CFC Studio
  • 实验室主页
  • CFC 招新简章
  • 友情链接
  • RSS订阅
CFC Studio

ACM校赛解析?

Posted on 2016年7月1日2016年7月3日 by Kebe

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

 From: https://blog.kebe7jun.com/cqut-8-acm-analysis/

发表评论 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

分类

  • CFC 周刊 (4)
  • CFC 技术 (29)
  • CFC 日常 (3)
  • 未分类 (15)
  • 活动通知 (3)

标签

ACM Android anime animeloop animeloop-cli APP Apple aria2 Array Blog CFC数据结构与算法训练指南 CoreData CQUT Don't Starve Hexo iBooks JavaScript macOS Matlab moeoverflow OpenCV Programming README RxJS SQLite SQLite3 Steam Swift Theme Web Xcode 主题模板 动漫 博客 反编译 妹子 循环 教程 数据库 游戏 算法 装逼 视频 重庆理工大学 饥荒

登录
©2023 CFC Studio | Powered by WordPress & Superb Themes