PAT 1073 多选题常见计分法（20 分）

批改多选题是比较麻烦的事情，有很多不同的计分方法。有一种最常见的计分方法是：如果考生选择了部分正确选项，并且没有选择任何错误选项，则得到 50% 分数；如果考生选择了任何一个错误的选项，则不能得分。本题就请你写个程序帮助老师批改多选题，并且指出哪道题的哪个选项错的人最多。

输入格式：

输入在第一行给出两个正整数 N（ $\leq1000）和 M（ \leq100），分别是学生人数和多选题的个数。随后 M 行，每行顺次给出一道题的满分值（不超过 5 的正整数）、选项个数（不少于 2 且不超过 5 的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母 a 开始顺次排列。各项间以 1 个空格分隔。最后 N 行，每行给出一个学生的答题情况，其每题答案格式为 (选中的选项个数选项1 \dots\dots) ，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。$

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行，输出小数点后 1 位。最后输出错得最多的题目选项的信息，格式为：错误次数题目编号（题目按照输入的顺序从1开始编号）-选项号。如果有并列，则每行一个选项，按题目编号递增顺序输出；再并列则按选项号递增顺序输出。行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出 Too simple。

输入样例 1：

3 4 
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (3 b d e) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (1 c) (4 a b c d)

输出样例 1：

3.5
6.0
2.5
2 2-e
2 3-a
2 3-b

输入样例 2：

2 2 
3 4 2 a c
2 5 1 b
(2 a c) (1 b)
(2 a c) (1 b)

输出样例 2：

5.0
5.0
Too simple

这个题写了好长时间，先是用java写的，写了之后最后一个测试点运行超时。试着改成set集合，想着能快点，但还是不行。最后同样的思路换成了C语言通过了。

  1 import java.util.Arrays;
  2 import java.util.Scanner;
  3 
  4 public class Hello {
  5     static int N,M;//学生个数，选项数
  6     public static void main(String[] args) {
  7         Scanner sc = new Scanner(System.in);
  8         N = sc.nextInt();
  9         M = sc.nextInt();
 10         Q[] q = new Q[M];
 11         Stu[] stu = new Stu[N];
 12         String temp;//临时变量
 13         char[] temp1;//临时变量
 14         char[] temp2;//临时变量
 15         for(int i=0;i<M;i++) {
 16             q[i] = new Q();
 17             q[i].a = sc.nextInt();
 18             q[i].b = sc.nextInt();
 19             q[i].c = sc.nextInt();
 20             q[i].e = new int[q[i].b];//选项初始化
 21             temp = sc.nextLine();
 22             temp1 = temp.toCharArray();
 23             int k = 0;
 24             //将正确选项存入问题类中的d属性中。
 25             for(int j=0;j<temp1.length;j++) {
 26                 if(temp1[j]!= ' ')
 27                     q[i].d[k++] = temp1[j];
 28             }
 29         }
 30         //学生答案的输入。最终将学生答题情况存入学生类的a属性中。
 31         for(int i=0;i<N;i++) {
 32             temp = sc.nextLine();
 33             stu[i] = new Stu();
 34             temp1  = temp.toCharArray();
 35             temp2 = new char[temp1.length];
 36             int k = 0;
 37             for(int j=0;j<temp1.length;j++) {
 38                 if(temp1[j]!=' '&&temp1[j]!='('&&temp1[j]!=')') {
 39                     temp2[k++] = temp1[j];
 40                 }
 41             }
 42             int k1 = -1;
 43             int k2 = 0;
 44             for(int j=0;j<k;j++) {
 45                 if(temp2[j]<='g'&&temp2[j]>='a') {
 46                     stu[i].a[k1].d[k2++] = temp2[j];
 47                 }else {
 48                     k1++;
 49                     stu[i].a[k1] = new Q();
 50                     stu[i].a[k1].c = temp2[j]-'0';
 51                     k2 = 0;
 52                 }
 53             }
 54             
 55         }
 56         for(int i=0;i<N;i++) {
 57             for(int j=0;j<M;j++) {
 58                 //如果学生答案个数比正确答案少
 59                 if(stu[i].a[j].c<=q[j].c) {
 60                     int flag = 0;//是否全部答对
 61                     char[] temp3  = q[j].d.clone();
 62                     
 63                     for(int k=0;k<stu[i].a[j].c;k++) {
 64                         int k1 = 0;
 65                         //检查学生某个答案是在正确答案中
 66                         for(k1=0;k1<q[j].c;k1++) {
 67                             //如果在则跳出，并标记此答案没有答错
 68                             if(q[j].d[k1]==stu[i].a[j].d[k]) {
 69                                 temp3[k1] = 'q';
 70                                 break;
 71                                 
 72                             }
 73                         }
 74                         //如果不在，则说明学生此答案答错
 75                         if(k1==q[j].c) {
 76                             q[j].e[stu[i].a[j].d[k]-'a']++;
 77                             flag = 1;//不得分
 78                         }
 79                         
 80                     }
 81                     //部分正确答案学生没有答出标记此答案也错了
 82                     for(int k=0;k<q[j].c;k++) {
 83                         if(temp3[k]!='q') {
 84                             q[j].e[temp3[k]-'a']++;
 85                         }
 86                     }
 87                     //如果没有答错
 88                     if(flag==0) {
 89                         //如果学生选项个数跟正确答案个数相同则满分
 90                         if(stu[i].a[j].c==q[j].c)
 91                             stu[i].mark += q[j].a;
 92                         //如果知只是部分答对
 93                         else
 94                             stu[i].mark += (double)q[j].a/2;
 95                     }
 96                 }
 97                 //处理学生答案比正确答案长的情况，处理相同，只是不得分。
 98                 else {
 99                     char[] temp3  = q[j].d.clone();
100                     for(int k=0;k<stu[i].a[j].c;k++) {
101                         int k1 = 0;
102                         for(k1=0;k1<q[j].c;k1++) {
103                             if(q[j].d[k1]==stu[i].a[j].d[k]) {
104                                 temp3[k1] = 'q';
105                                 break;
106                                 
107                             }
108                         }
109                         if(k1==q[j].c) {
110                             q[j].e[stu[i].a[j].d[k]-'a']++;
111                         }
112                         
113                     }
114                     for(int k=0;k<q[j].c;k++) {
115                         if(temp3[k]!='q') {
116                             q[j].e[temp3[k]-'a']++;
117                         }
118                     }
119                 }
120             }
121         }
122         //输出分数。
123         for(int i=0;i<N;i++) {
124             System.out.println(stu[i].mark);
125         }
126         int max = 0;
127         //统计答案错的最多的次数
128         for(int i=0;i<M;i++) {
129             for(int j=0;j<q[i].b;j++) {
130                 if(q[i].e[j]>max)
131                     max = q[i].e[j];
132             }
133         }
134         //没有答错
135         if(max==0) {
136             System.out.println("Too simple");
137         }else {
138             //找出错的最多的选项与答案并输出。
139             for(int i=0;i<M;i++) {
140                 for(int j=0;j<q[i].b;j++) {
141                     if(q[i].e[j]==max) {
142                         System.out.println(max+" "+(i+1)+"-"+(char) (j+'a'));
143                     }
144                         
145                 }
146             }
147         }
148     }
149     public static class Stu{
150         Q[] a = new Q[M];//学生答案
151         double mark = 0;//学生分数
152     }
153     
154     public static class Q{//问题类
155         int a;//满分
156         int b;//选项个数
157         int c;//正确选项数
158         char[] d = new char[5];//正确选项
159         int[] e;//选项错误次数
160     }
161 
162 }

JAVA版

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Test {
    static int N,M;//学生个数，选项数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        Q[] q = new Q[M];
        Stu[] stu = new Stu[N];
        String temp;//临时变量
        char[] temp1;//临时变量
        char[] temp2;//临时变量
        for(int i=0;i<M;i++) {
            q[i] = new Q();
            q[i].a = sc.nextInt();
            q[i].b = sc.nextInt();
            q[i].c = sc.nextInt();
            q[i].e = new int[q[i].b];//选项初始化
            temp = sc.nextLine();
            temp1 = temp.toCharArray();
            int k = 0;
            //将正确选项存入问题类中的d属性中。
            for(int j=0;j<temp1.length;j++) {
                if(temp1[j]!= ' ')
                    q[i].d.add(temp1[j]);
            }
        }
        //测试正确答案是否存入集合中
        /*for(int i=0;i<M;i++) {
            for(char a:q[i].d) {
                System.out.print(a);
            }
            System.out.println();
        }*/
        //学生答案的输入。最终将学生答题情况存入学生类的a属性中。
            for(int i=0;i<N;i++) {
                temp = sc.nextLine();
                stu[i] = new Stu();
                stu[i].d = new HashSet[M];
                temp1  = temp.toCharArray();
                temp2 = new char[temp1.length];
                int k = 0;
                for(int j=0;j<temp1.length;j++) {
                    if(temp1[j]!=' '&&temp1[j]!='('&&temp1[j]!=')') {
                        temp2[k++] = temp1[j];
                    }
                }
                int k1 = -1;
                int k2 = 0;
                for(int j=0;j<k;j++) {
                    if(temp2[j]<='g'&&temp2[j]>='a') {
                        stu[i].d[k1].add(temp2[j]);
                    }else {
                        k1++;
                        stu[i].d[k1] = new HashSet<>();
                        k2 = 0;
                    }
                }
                
            }
            //测试学生答案是否录入
            /*for(int i=0;i<N;i++) {
                for(int j=0;j<M;j++) {
                    for(char a:stu[i].d[j]) {
                        System.out.print(a);
                    }
                    System.out.print(" ");
                }
                System.out.println();
            }*/
            for(int i=0;i<N;i++) {
                Set<Character> temp3 = new HashSet();
                Set<Character> temp4 = new HashSet();
                for(int j=0;j<M;j++) {
                    temp3.addAll(q[j].d);
                    temp4.addAll(stu[i].d[j]);
                    for(char a:temp4) {
                        if(temp3.contains(a)) {
                            temp3.remove(a);
                            stu[i].d[j].remove(a);
                        }
                    }
                    for(char a:stu[i].d[j]) {
                        q[j].e[a-'a']++;
                    }
                    for(char a:temp3) {
                        q[j].e[a-'a']++;
                    }
                    if(stu[i].d[j].size()==0) {
                        if(temp3.size()==0)
                            stu[i].mark += q[j].a;
                        else
                            stu[i].mark += (double)q[j].a/2;
                    }
                    temp3.clear();
                    temp4.clear();
                }
            }
            //输出分数。
            for(int i=0;i<N;i++) {
                System.out.println(stu[i].mark);
            }
            int max = 0;
            //统计答案错的最多的次数
            for(int i=0;i<M;i++) {
                for(int j=0;j<q[i].b;j++) {
                    if(q[i].e[j]>max)
                        max = q[i].e[j];
                }
            }
            //没有答错
            if(max==0) {
                System.out.println("Too simple");
            }else {
                //找出错的最多的选项与答案并输出。
                for(int i=0;i<M;i++) {
                    for(int j=0;j<q[i].b;j++) {
                        if(q[i].e[j]==max) {
                            System.out.println(max+" "+(i+1)+"-"+(char) (j+'a'));
                        }
                            
                    }
                }
            }
            
            
        
    }
    
    public static class Stu{
        Set<Character>[] d;//学生答案
        double mark = 0;
    }
    public static class Q{
        int a;//满分
        int b;//选项个数
        int c;//正确选项数
        Set<Character> d = new HashSet();//正确答案
        int[] e;//选项错误次数
    }
}

JAVA版(Set)

  1 #include<stdio.h>
  2 
  3 typedef struct Q1{//问题类 
  4     int a;//满分 
  5     int b;//选项个数 
  6     int c;//正确选项个数 
  7     char d[5];//正确选项 
  8     int e[5];//选项错误次数 
  9 }Q;
 10 typedef struct Stu1{//学生类 
 11     double mark;//学生分数 
 12     Q q[101];//学生答案 
 13     
 14 }Stu; 
 15 Q q[101];
 16 Stu stu[1001];
 17 int main(){
 18     int N,M;//学生个数，选项数 
 19     scanf("%d %d",&N,&M);
 20     for(int i=0;i<M;i++){//录入问题 
 21         scanf("%d %d %d",&q[i].a,&q[i].b,&q[i].c);
 22         for(int j=0;j<q[i].c;j++){
 23             scanf(" %c",&q[i].d[j]);
 24         }
 25     }
 26     getchar();//接收回车符 
 27     for(int i=0;i<N;i++){//录入学生答题 
 28         for(int j=0;j<M;j++){
 29             //getchar();
 30             scanf("(%d",&stu[i].q[j].c);
 31             for(int k=0;k<stu[i].q[j].c;k++){
 32                 scanf(" %c",&stu[i].q[j].d[k]);
 33             }
 34             getchar();//接收'('符 
 35             getchar();//接收空格符 
 36         }
 37     }
 38     for(int i=0;i<N;i++){
 39         for(int j=0;j<M;j++){
 40             //如果学生答案个数比正确答案少 
 41             if(stu[i].q[j].c<=q[j].c){
 42                 int flag = 0;
 43                 int temp[5] = {0};
 44                 for(int k=0;k<stu[i].q[j].c;k++){
 45                     int k1 = 0;
 46                     //检查学生某个答案是否在正确答案中，可以用集合，比较方便 
 47                     for(k1=0;k1<q[j].c;k1++){
 48                         //如果在则跳出，并标记此答案没有答错 
 49                         if(q[j].d[k1]==stu[i].q[j].d[k]){
 50                             temp[k1] = 1;
 51                             break;
 52                         }
 53                     }
 54                     //如果不在，则说明学生此答案答错 
 55                     if(k1==q[j].c){
 56                         q[j].e[stu[i].q[j].d[k]-'a']++;
 57                         flag = 1;//不得分 
 58                     }
 59                     
 60                 }
 61                 //部分正确答案学生没有答出标记此答案也错了
 62                 for(int k=0;k<q[j].c;k++){
 63                     if(temp[k]!=1){
 64                         q[j].e[q[j].d[k]-'a']++;
 65                     }
 66                 }
 67                 //如果没有答错
 68                 if(flag==0){
 69                     if(stu[i].q[j].c==q[j].c)
 70                     //如果学生选项个数跟正确答案个数相同则满分
 71                         stu[i].mark += q[j].a;
 72                     else
 73                     //如果知只是部分答对
 74                         stu[i].mark += (double)q[j].a/2;
 75                         
 76                 }
 77             }
 78             //处理学生答案比正确答案长的情况，处理相同，只是不得分。
 79             else{
 80                 int temp[5] = {0};
 81                 for(int k=0;k<stu[i].q[j].c;k++){
 82                     int k1 = 0;
 83                     for(k1=0;k1<q[j].c;k1++){
 84                         if(q[j].d[k1]==stu[i].q[j].d[k]){
 85                             temp[k1] = 1;
 86                             break;
 87                         }
 88                     }
 89                     if(k1==q[j].c){
 90                         q[j].e[stu[i].q[j].d[k]-'a']++;
 91                     }
 92                     
 93                 }
 94                 for(int k=0;k<q[j].c;k++){
 95                     if(temp[k]!=1){
 96                         q[j].e[q[j].d[k]-'a']++;
 97                     }
 98                 }
 99             }
100             
101         }
102     }
103     //输出分数。
104     for(int i=0;i<N;i++){
105         printf("%0.1lf
",stu[i].mark);
106     }
107     int max =0;
108     //统计答案错的最多的次数
109     for(int i=0;i<M;i++){
110         for(int j=0;j<q[i].b;j++){
111             if(q[i].e[j]>max){
112                 max = q[i].e[j];
113             }
114         }
115     }
116     //没有答错
117     if(max==0){
118         printf("Too simple
");
119     }else{
120         //找出错的最多的选项与答案并输出。
121         for(int i=0;i<M;i++){
122             for(int j=0;j<q[i].b;j++){
123                 if(q[i].e[j]==max){
124                     printf("%d %d-%c
",max,i+1,j+'a');
125                 }
126             }
127         }
128     }
129     
130     
131 }