PAT甲級10741075解題報告

10286 ワード

1074 Reversing Linked List (25 point(s))
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next

where  Address  is the position of the node,  Data  is an integer, and  Next  is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

チェーンテーブルが反転します.
问题の考え方:実はとても水で、1つの穴が反転する时注意しなければなりません.一度反転するとは限らず、何度も反転する可能性があります.彼の意味は前のK個の反転ではなく、K個ごとに反転することです.
コードは次のとおりです.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Node {
	int addr;
	int data;
	int next;
};
map a;
vector res;
int main() {
	int begin; int N, K;
	scanf("%d %d %d", &begin,&N,&K);
	for (int i = 0; i < N; i++) {
		Node tmp;
		scanf("%d %d %d", &tmp.addr, &tmp.data, &tmp.next);
		a[tmp.addr] = tmp;
	}
	while (true) {
		if (begin == -1)break;
		res.push_back(a[begin]);
		begin = a[begin].next;
	}
	int kao = 0;
	for (int i = 0; i < res.size() / K; i++) {
		reverse(res.begin() + kao, res.begin() + kao + K);
		kao = kao+K;
	}
	for (int i = 0; i < res.size(); i++) {
		if (i != res.size()-1)
		printf("%05d %d %05d
",res[i].addr,res[i].data,res[i+1].addr); else printf("%05d %d -1
", res[i].addr, res[i].data); } return 0; }

1075 PAT Judge (25 point(s))
The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive integers, N (≤10​4​​), the total number of users, K (≤5), the total number of problems, and M (≤10​5​​), the total number of submissions. It is then assumed that the user id's are 5-digit numbers from 00001 to N, and the problem id's are from 1 to K. The next line contains K positive integers  p[i]  ( i =1, ..., K), where  p[i]  corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submission in the following format:
user_id problem_id partial_score_obtained

where  partial_score_obtained  is either −1 if the submission cannot even pass the compiler, or is an integer in the range [0,  p[problem_id] ]. All the numbers in a line are separated by a space.
Output Specification:
For each test case, you are supposed to output the ranklist in the following format:
rank user_id total_score s[1] ... s[K]

where  rank  is calculated according to the  total_score , and all the users with the same  total_score  obtain the same  rank ; and  s[i]  is the partial score obtained for the  i -th problem. If a user has never submitted a solution for a problem, then "-"must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.
The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id's. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.
Sample Input:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

Sample Output:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

PAT试験のランキングを模拟してみます
問題を解く構想:穴が死ぬ!どのようにすべて最后のサンプルを过ごすことができなくて、他の人のコードを探して交际するしかなくて、先に私の考えを言って、実は正常な人のしたシミュレーションで、1つのidで构造体の配列に関连して、それから最后のサンプルはずっとタイムアウトして、それから私は発见します.mapはkeyが存在しない場合に自動的に対応するvalueを作成するが、このプロセスは極めて時間がかかるので初期化を開始するが、初期化が完了するとタイムアウトはタイムアウトせず、WAを開始する.なぜか、私は今考えてみると、多くの人がいるからかもしれませんが、誰もランクインできない状況では、私のコードは走ることができません.もちろん推測だけです.私も絶望しています.
マイコード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int K;
struct stu {
	int id;
	map score;
	bool flag=false;
	int solans = 0;
	int total = 0;
	//map ansp;
	int index;
		
	stu() :flag(false){
		for (int i = 0; i < K; i++) {
		score[i + 1] = -1;
	    }
	}
};
int pro[6];
vector res;
map lt;
bool cmp(stu a, stu b) {
	if (a.total > b.total) {
		return true;
	}
	else if (a.total == b.total) {
		if (a.solans > b.solans) {
			return true;
		}
		else if (a.solans == b.solans) {
			return a.id < b.id;
		}
		else
			return false;
	}
	else {
		return false;
	}
}
int main() {
	int N, M;
	scanf("%d %d %d",&N,&K,&M);
	for (int i = 0; i < N; i++) {
		stu a;
		lt[i + 1] = a;
	}
	for (int i = 0; i < K; i++)scanf("%d", &pro[i]);
	for (int i = 0; i < M; i++) {
		int tmpid;
		int tmpto;
		int tmpsco;
		scanf("%d %d %d", &tmpid, &tmpto, &tmpsco);
			if (tmpsco == -1) {
				lt[tmpid].id = tmpid;
				//lt[tmpid].ansp[tmpto] = true;
				lt[tmpid].score[tmpto] = 0;
			}
			else {
				lt[tmpid].id = tmpid;
				//lt[tmpid].ansp[tmpto] = true;
				if (lt[tmpid].score[tmpto] < tmpsco) {
					//lt[tmpid].total = lt[tmpid].total - lt[tmpid].score[tmpto] + tmpsco;
					lt[tmpid].score[tmpto] = tmpsco;
				}
				if (lt[tmpid].score[tmpto] == pro[tmpto - 1])
					lt[tmpid].solans += 1;
				lt[tmpid].flag = true;
			}
	}
	for (auto i = lt.begin(); i != lt.end(); i++) {
		if (i->second.flag) {
			for (int j = 0; j < K; j++) {
				if(i->second.score[j + 1]!=-1)
				i->second.total += i->second.score[j + 1];
			}
			res.push_back(i->second);
		}
	}
	sort(res.begin(), res.end(), cmp);
	int index;
	res[0].index = 1;
	for (int i = 1; i < res.size(); i++) {
		if (res[i].total < res[i - 1].total) {
			index = i + 1;
			res[i].index = index;
		}
		else {
			res[i].index = index;
		}
	}
	for (int i = 0; i < res.size(); i++) {
		printf("%d %05d %d ", res[i].index,res[i].id,res[i].total);
		for (int j = 1; j <=K; j++) {
			if (res[i].score[j]!=-1) {
				printf("%d", res[i].score[j]);
			}
			else {
				printf("-");
			}
			if (j != K)
				printf(" ");
			else
				printf("
"); } } return 0; }

他人の満点コード
struct student {
    int id;
    int score[6];
    bool flag = false;
    int solve = 0;
    int total = 0;
}s[10010];

bool cmp(student a, student b) {
    if (a.total != b.total) return a.total > b.total;
    else if (a.solve != b.solve) return a.solve > b.solve;
    else return  a.id < b.id;
}

int main() {
    int n, k, m, i;
    scanf("%d %d %d", &n, &k, &m);
    int p[6];
    for (i = 1; i <= k; i++) {
        scanf("%d", &p[i]);
    }
    for ( i = 1; i <= n; i++) {//      ,    id  ,   s[id].id=id             ,        
        s[i].id = i;
        memset(s[i].score, -1, sizeof(s[i].score));
     }

    int id, num, temp;
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &id, &num, &temp);
        if (temp != -1) s[id].flag = true;
        if (temp == -1 && s[id].score[num] == -1) s[id].score[num] = 0;
        if (temp == p[num] && s[id].score[num] < p[num]) s[id].solve++;//             ,  temp      
        if (temp > s[id].score[num]) s[id].score[num] = temp;

    }
    for (i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (s[i].score[j] != -1 ) s[i].total += s[i].score[j];
        }
    }
    sort(s + 1, s + n + 1, cmp);
    int r = 1;
    for (i = 1; i <= n && s[i].flag == true; i++) {//        
        if (i > 1 && s[i].total != s[i - 1].total) r = i;
        printf("%d %05d %d", r, s[i].id, s[i].total);
        for (int j = 1; j <= k; j++) {
            if (s[i].score[j] == -1) printf(" -");
            else printf(" %d", s[i].score[j]);
        }
        printf("
"); } return 0; }

自閉した.