我的PAT系列文章更新重心已移至Github，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容片林。此處文章目前已更新至與Github Pages同步。歡迎star我的repo。
題目
批改多選題是比較麻煩的事情码荔，有很多不同的計(jì)分方法。有一種最常見的計(jì)分方法是：如果考生選擇了部分正確選項(xiàng)感挥，并且沒有選擇任何錯(cuò)誤選項(xiàng)缩搅，則得到 50%
分?jǐn)?shù)；如果考生選擇了任何一個(gè)錯(cuò)誤的選項(xiàng)触幼，則不能得分硼瓣。本題就請你寫個(gè)程序幫助老師批改多選題，并且指出哪道題的哪個(gè)選項(xiàng)錯(cuò)的人最多置谦。
輸入格式：
輸入在第一行給出兩個(gè)正整數(shù) N（ 1000）和 M（
100）堂鲤，分別是學(xué)生人數(shù)和多選題的個(gè)數(shù)。隨后 M
行媒峡，每行順次給出一道題的滿分值（不超過 5 的正整數(shù)）瘟栖、選項(xiàng)個(gè)數(shù)（不少于 2 且不超過 5
的正整數(shù)）、正確選項(xiàng)個(gè)數(shù)（不超過選項(xiàng)個(gè)數(shù)的正整數(shù)）谅阿、所有正確選項(xiàng)半哟。注意每題的選項(xiàng)從小寫英文字母 a 開始順次排列酬滤。各項(xiàng)間以 1 個(gè)空格分隔。最后 N
行镜沽，每行給出一個(gè)學(xué)生的答題情況敏晤，其每題答案格式為 (選中的選項(xiàng)個(gè)數(shù) 選項(xiàng)1 ……)，按題目順序給出缅茉。注意：題目保證學(xué)生的答題情況是合法的嘴脾，即不存在選中的選項(xiàng)數(shù)超過實(shí)際選項(xiàng)數(shù)的情況。
輸出格式：
按照輸入的順序給出每個(gè)學(xué)生的得分蔬墩，每個(gè)分?jǐn)?shù)占一行译打，輸出小數(shù)點(diǎn)后 1 位。最后輸出錯(cuò)得最多的題目選項(xiàng)的信息拇颅，格式為：錯(cuò)誤次數(shù) 題目編號(hào)（題目按照輸入的順序從1開始編號(hào)）-選項(xiàng)號(hào)奏司。如果有并列，則每行一個(gè)選項(xiàng)樟插，按題目編號(hào)遞增順序輸出韵洋；再并列則按選項(xiàng)號(hào)遞增順序輸出。行首尾不得有多余空格黄锤。如果所有題目都沒有人錯(cuò)搪缨，則在最后一行輸出
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
思路
這一道題和1058題是很類似的鸵熟，但是稍微復(fù)雜一點(diǎn)副编。
一樣的方面詳見上面鏈接，下面只說1058題中沒有的兩點(diǎn)流强。
-
正確性的判斷痹届。這道題中需要判斷“沒有全部選對”的情況，和1058題的解法一樣打月，我使用按位存儲(chǔ)的方法記錄題目的答案队腐，如選項(xiàng)A、C和D則記錄為01101=13奏篙。那么分析方法為：
正確：
學(xué)生選項(xiàng)==正確答案柴淘，顯然正確，為了后面方便报破，計(jì)算學(xué)生選項(xiàng)<異或>正確答案==0。-
錯(cuò)誤：
學(xué)生選項(xiàng)<異或>正確答案這個(gè)數(shù)的每一位實(shí)際上表示學(xué)生在這一選項(xiàng)上是否正確千绪，如正確答案為BC(00110)充易，學(xué)生選了AC(00101)，那么兩者異或值為00011荸型，即表示AB兩選項(xiàng)出現(xiàn)錯(cuò)誤盹靴。分析起來就是：- 存在正確答案是0的位，上述異或值為1這樣的情況，則說明學(xué)生有多選錯(cuò)誤選項(xiàng)
- 正確答案是0的位稿静，異或值也全是0梭冠，則學(xué)生只選擇了部分正確答案
判斷這兩者的方法就是將異或值與正確答案取邏輯或，如果這個(gè)結(jié)果大于正確答案改备，則說明有異或值為1而正確答案為0的位控漠，如果二者一樣，說明沒有悬钳。
我的方法可能理解起來比較困難（當(dāng)然大多是因?yàn)槲冶硎霾缓茫┭谓荩俏矣X得算是提供一個(gè)新的視角，供大家借鑒默勾。
選項(xiàng)的錯(cuò)誤次數(shù)
這個(gè)就比較簡單了碉渡，我是用的int[M][5]矩陣記錄每一道題每一個(gè)選項(xiàng)錯(cuò)誤的次數(shù)，最后就好處理了母剥。
代碼
最新代碼@github滞诺，歡迎交流
#include <stdio.h>
#define MAX_M 100
#define MAX_OPTIONS 5
int readanswer()
{
char c;
int answer = 0, count;
scanf("%d", &count);
for(int i = 0; i < count; i++)
{
while((c = getchar()) == ' ');
answer |= 1 << (c - 'a');
}
return answer;
}
int main()
{
int N, M, full_score[MAX_M] = {0}, correct_ans[MAX_M] = {0},
wrong_ans[MAX_M] = {0}, wrong_count[MAX_M][5] = {{0}},
wrong_count_max = 0;
scanf("%d %d", &N, &M);
/* Read M lines */
int count_options;
for(int i = 0; i < M; i++)
{
scanf("%d %d", full_score + i, &count_options);
correct_ans[i] = readanswer();
}
/* Read N lines */
for(int i = 0; i < N; i++)
{
float score = 0;
int answer;
for(int j = 0; j < M; j++)
{
while(getchar() != '(');
answer = readanswer();
wrong_ans[j] = answer ^ correct_ans[j];
if(wrong_ans[j] == 0) /* all correct */
score += full_score[j];
else if((wrong_ans[j] | correct_ans[j]) == correct_ans[j])
score += 0.5 * full_score[j]; /* partially corrent */
/* For every option, record the number of students got wrong */
for(int k = 0; k < MAX_OPTIONS; k++)
{
wrong_count[j][k] += wrong_ans[j] >> k & 1; /* k-th bit */
if(wrong_count[j][k] > wrong_count_max)
wrong_count_max = wrong_count[j][k];
}
while(getchar() != ')');
}
printf("%.1f\n", score);
}
if(wrong_count_max == 0)
printf("Too simple");
else
for(int i = 0; i < M; i ++)
for(int j = 0; j < MAX_OPTIONS; j++)
if(wrong_count[i][j] == wrong_count_max)
printf("%d %d-%c\n", wrong_count_max, i + 1, j + 'a');
return 0;
}
