果然还是王道征途，PAT吧
PAT应试解题纪录&笔记
Table of Contents
资料/博客存放
解题纪录-Basic
3 入门模拟
1001 害死人不偿命的(3n+1)猜想 （15 分）
卡拉兹(Callatz)猜想：
对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？
输入格式：
每个测试输入包含 1 个测试用例，即给出正整数 n 的值。
输出格式：
输出从 n 计算到 1 需要的步数。
输入样例：
3
输出样例：
5
#include <iostream>
using namespace std;
int main()
{
int n=0,i=0;
cin>>n;
while(n!=1)
{
if((n%2)==0)
{
n = n/2;
}
else
{
n = (3*n+1)/2;
}
i++;
};
cout<<i;
}
1011 A+B 和 C （15 分）
给定区间 [−231,231] 内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。
输入格式：
输入第 1 行给出正整数 T (≤10)，是测试用例的个数。随后给出 T 组测试用例，每组占一行，顺序给出 A、B 和 C。整数间以空格分隔。
输出格式：
对每组测试用例，在一行中输出 Case #X: true 如果 A+B>C，否则输出 Case #X: false，其中 X 是测试用例的编号（从 1 开始）。
输入样例：
4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647
输出样例：
Case #1: false
Case #2: true
Case #3: true
Case #4: false
#include "iostream"
#include <stdlib.h>
using namespace std;
int main()
{
int n;
cin >> n;
int i;
for (i = 0; i < n; i++)
{
long long a, b, c;
cin >> a;
cin >> b;
cin >> c;
if ((a + b) > c)
{
cout << "Case #" << i+1 << ": true" << endl;
}
else
{
cout << "Case #" << i+1 << ": false" << endl;
}
}
return 0;
}
1016 部分A+B （15 分）
正整数 A 的“DA（为 1 位整数）部分”定义为由 A 中所有 DA 组成的新整数 PA。例如：给定 A=3862767，DA=6，则 A 的“6 部分”PA 是 66，因为 A 中有 2 个 6。
现给定 A、DA、B、DB，请编写程序计算 PA+PB。
输入格式：
输入在一行中依次给出 A、DA、B、DB，中间以空格分隔，其中 0<A,B<1010。
输出格式：
在一行中输出 PA+PB 的值。
输入样例 1：
3862767 6 13530293 3
输出样例 1：
399
输入样例 2：
3862767 1 13530293 8
输出样例 2：
0
#include <iostream>
#include <cstdio>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
int a,b,a1,b1;
int ai=0,bi=0;
int temp_a=0,temp_b=0;
// cin>>a>>a1>>b>>b1;
scanf("%d %d %d %d",&a,&a1,&b,&b1);
do{
if(a%10 == a1)
temp_a= temp_a*10+a1;
a = a/10;
}while(a!=0);
do{
if(b%10 == b1)
temp_b = temp_b*10+b1;
b = b/10;
}while(b!=0);
printf("%d",temp_a+temp_b);
return 0;
}
1026 程序运行时间 （15 分）
要获得一个 C 语言程序的运行时间，常用的方法是调用头文件 time.h，其中提供了 clock() 函数，可以捕捉从程序开始运行到 clock() 被调用时所耗费的时间。这个时间单位是 clock tick，即“时钟打点”。同时还有一个常数 CLK_TCK，给出了机器时钟每秒所走的时钟打点数。于是为了获得一个函数 f 的运行时间，我们只要在调用 f 之前先调用 clock()，获得一个时钟打点数 C1；在 f 执行完成后再调用 clock()，获得另一个时钟打点数 C2；两次获得的时钟打点数之差 (C2-C1) 就是 f 运行所消耗的时钟打点数，再除以常数 CLK_TCK，就得到了以秒为单位的运行时间。
这里不妨简单假设常数 CLK_TCK 为 100。现给定被测函数前后两次获得的时钟打点数，请你给出被测函数运行的时间。
输入格式：
输入在一行中顺序给出 2 个整数 C1 和 C2。注意两次获得的时钟打点数肯定不相同，即 C1 < C2，并且取值在 [0,107]。
输出格式：
在一行中输出被测函数运行的时间。运行时间必须按照 hh:mm:ss（即2位的 时:分:秒）格式输出；不足 1 秒的时间四舍五入到秒。
输入样例：
123 4577973
输出样例：
12:42:59
#include <iostream>
#include <cstdio>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv) {
int time1,time2;
cin>>time1>>time2;
int delta = time2 -time1;
if(delta%100 >= 50)
delta = delta /100 + 1;
else
delta = delta /100;
printf("%02d:%02d:%02d",delta/3600,(delta%3600)/60,delta%60);
return 0;
}
1046 划拳 （15 分）
划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就赢了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。
下面给出甲、乙两人的划拳记录，请你统计他们最后分别喝了多少杯酒。
输入格式：
输入第一行先给出一个正整数 N（≤100），随后 N 行，每行给出一轮划拳的记录，格式为：
甲喊 甲划 乙喊 乙划
其中喊是喊出的数字，划是划出的数字，均为不超过 100 的正整数（两只手一起划）。
输出格式：
在一行中先后输出甲、乙两人喝酒的杯数，其间以一个空格分隔。
输入样例：
5
8 10 9 12
5 10 5 10
3 8 5 12
12 18 1 13
4 16 12 15
输出样例：
1 2
#include <iostream>
#include <cstdio>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
int i,a,aa,b,bb;
int ai = 0, bi = 0;
scanf("%d",&i);
int counter;
for(counter = 0; counter < i; counter++){
scanf("%d%d%d%d",&a,&aa,&b,&bb);
if(aa==(a+b)){
if(bb!=(a+b))
ai++;
}
else if(bb==(a+b))
bi++;
}
printf("%d %d",bi,ai);
return 0;
}
1008 数组元素循环右移问题 （20 分）
一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0A1⋯AN−1）变换为（AN−M⋯AN−1A0A1⋯AN−M−1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
输入格式:
每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。
输出格式:
在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4
#include <iostream>
#include <cstdio>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
vector<int> a;
int i,j;
scanf("%d%d",&i,&j);
int counter;
for(counter = 0; counter < i; counter++){
int temp;
scanf("%d",&temp);
a.push_back(temp);
}
j = j % i;
auto ii=a.begin();
for(ii=a.begin() + (i-j); ii != a.end(); ii++)
{
printf("%d",*ii);
if(ii!= (a.end()-1) )
printf(" ");
else if(j!=i)
printf(" ");
}
for(auto ii=a.begin(); ii != a.end()-j; ii++)
{
printf("%d",*ii);
if(ii!= (a.end()-1-j) )
printf(" ");
}
return 0;
}
1018 锤子剪刀布 （20 分）
大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：
现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。
输入格式：
输入第 1 行给出正整数 N（≤105），即双方交锋的次数。随后 N 行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C 代表“锤子”、J 代表“剪刀”、B 代表“布”，第 1 个字母代表甲方，第 2 个代表乙方，中间有 1 个空格。
输出格式：
输出第 1、2 行分别给出甲、乙的胜、平、负次数，数字间以 1 个空格分隔。第 3 行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有 1 个空格。如果解不唯一，则输出按字母序最小的解。
输入样例：
10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J
输出样例：
5 3 2
2 3 5
B B
#include <iostream>
#include <cstdio>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
int a[3]={0,0,0};
int score_a[3]={0,0,0};
int score_b[3]={0,0,0};
int i,j;
scanf("%d",&i);
for(j=0; j<i; j++)
{
char A,B;
cin>>A>>B;
// scanf("%c %c",&A,&B);
if(A == 'C'){
if(B =='J'){
a[0]++;
score_a[0]++;
}
else if(B=='B'){
a[2]++;
score_b[2]++;
}
else if(B=='C'){
a[1]++;
}
}
if(A=='J'){
if(B=='B'){
a[0]++;
score_a[1]++;
}
else if(B=='C'){
a[2]++;
score_b[0]++;
}
else if(B=='J'){
a[1]++;
}
}
if(A=='B'){
if(B=='C'){
a[0]++;
score_a[2]++;
}
else if(B=='J'){
a[2]++;
score_b[1]++;
}
else if(B=='B'){
a[1]++;
}
}
}
printf("%d %d %d\n",a[0],a[1],a[2]);
printf("%d %d %d\n",a[2],a[1],a[0]);
if(score_a[2]>=score_a[1] && score_a[2]>=score_a[0])
printf("B");
else if(score_a[0]>=score_a[1] && score_a[0]>=score_a[2])
printf("C");
else printf("J");
printf(" ");
if(score_b[2]>=score_b[1] && score_b[2]>=score_b[0])
printf("B");
else if(score_b[0]>=score_b[1] && score_b[0]>=score_b[2])
printf("C");
else printf("J");
return 0;
}
1010 一元多项式求导 （25 分）
设计函数求一元多项式的导数。（注：xn（n为整数）的一阶导数为nxn−1。）
输入格式:
以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。
输出格式:
以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是表示为 0 0。
输入样例:
3 4 -5 2 6 1 -2 0
输出样例:
12 3 -10 1 6 0
#include <iostream>
#include <cstdio>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int temp[10010][2];
int main() {
int i,j;
int counter = 0;
while( scanf("%d%d",&i,&j) != EOF ){
if(j!=0){
temp[counter][0] = i;
temp[counter][1] = j;
counter++;
}
}
int count = 0;
for(i=0;i<counter;i++)
{
printf("%d %d",temp[i][0]*temp[i][1],temp[i][1]-1);
count++;
if(i!= counter - 1)
printf(" ");
}
if(count == 0)
printf("0 0");
return 0;
}
5 数学问题
B1013 数素数 （20 分）
输入格式：
输入在一行中给出 和 ，其间以空格分隔。
输出格式：
输出从 到 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。
输入样例：
5 27
输出样例：
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103代码：
#include <iostream>
#include <algorithm>
using namespace std;
int flag[500000];
int prime[10000];
void find_prime(int m, int n){
int i=2,j=0;
do{
if(flag[i]== 0 ){
prime[j] = i;
j++;
int k;
for(k = i+i;k<500000;k+=i){
flag[k]=1;
}
}
i++;
}while(i<500000);
}
int main(int argc, char *argv[])
{
int counter = 0;
for(counter = 0; counter <500000; counter++)
flag[counter] = 0;
int m,n;
cin>>m>>n;
find_prime(m,n);
int i=0,k=0;
for(i=m-1;i<n;i++){
cout<<prime[i];
k++;
if(k%10 == 0) cout<<endl;
else if(i!=(n-1))cout<<" ";
}
return 0;
}
笔记：
使用了筛选法选择素数；最开始布尔数组范围为10000 部分测试用例不通过，改到50000顺利通过。
解题纪录-Advanced
7 Data Structure
1051 Pop Sequence （25 分）
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
int main() {
int m,n,k;
int i,j;
cin>>m>>n>>k;
for(i = 0; i < k; i++){
stack<int> st;
int num2push = 1;
int flag = 0;
for(j = 0; j < n; j++){
int temp;
cin>>temp;
if(st.empty()){
do{
st.push(num2push);
num2push++;
}while(st.top() != temp);
if(st.size()>m){
flag = 1;
}
st.pop();
}
else{
if(st.empty()){
flag = 1;
break;
}
else{
if(temp > st.top()){
do{
st.push(num2push);
num2push++;
}while(st.top() != temp);
st.pop();
}
else{
if(st.top() == temp){
st.pop();
}
else{
flag = 1;
}
}
}
}
if(st.size()>m){
flag = 1;
}
}
if(!st.empty()){
flag = 1;
}
if(flag == 0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
;// cout<<"Line Finshed! i="<<i<<endl;
}
return 0;
}
注：此题使用了STL实现栈；用模拟的方法实现；
目前还是有一组测试用例无法通过，只获得了23分；原因待查中，书上有更简洁的实现方法；
1056 Mice and Rice （25 分）
Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.
First the playing order is randomly decided for NP programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (≤1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player's list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,⋯,NP−1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,⋯,NP−1 (assume that the programmers are numbered from 0 to NP−1). All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
/*
1. 用结构体存储状态，只用队列保存排序状态（queue int)来节省内存和操作时间。
2. 找出可以持续迭代的条件 ： 队列不等于空
3. 排名为每次选出的人数+1
最开始部分答案超时 全部改为scanf后仍然超时。
其他用例在3ms左右，应该为死循环了，而不是cout cin带来的时间损耗。
*/
struct mice_struct{
int weight;
int rank;
};
bool cmp(mice_struct a, mice_struct b){
return a.rank>b.rank;
}
int main() {
int n,m;
cin>>n>>m;
mice_struct mice[n];
int i,j;
for(i=0;i<n;i++){
scanf("%d",&mice[i].weight);
}
queue<int> qe;
for(i=0;i<n;i++){
int temp;
scanf("%d",&temp);
qe.push(temp);
}
//已经获得竞赛队列qe
while(qe.size()!=0){
int round = 0;
int rest = 0;
//开始计算需要进行的回合数
//最开始忘了整除情况的rest，因为最后一回合依据是rest，已改正
if((qe.size()%m) == 0){
round = qe.size() / m;
rest = m;
}
else{
round = qe.size() / m + 1;
rest = qe.size() % m;
}
for(i=0;i<round-1;i++){
int temp_max=-1;
int id_max=-1;
int temp[m];
for(j=0;j<m;j++){
temp[j]=qe.front();
qe.pop();
if(mice[temp[j]].weight > temp_max){
temp_max = mice[temp[j]].weight;
id_max = temp[j];
}
}
qe.push(id_max);
for(j=0;j<m;j++){
if(temp[j]!=id_max){
mice[temp[j]].rank = round + 1;
}
else{
mice[temp[j]].rank = round;
}
}
}
//特殊处理最后一回合
//注意冠军已经生成的的条件，要停止进队了
int temp_max=-1;
int id_max=-1;
int temp[m];
for(j=0;j<rest;j++){
temp[j]=qe.front();
qe.pop();
if(mice[temp[j]].weight > temp_max){
temp_max = mice[temp[j]].weight;
id_max = temp[j];
}
}
if(round != 1) qe.push(id_max);
for(j=0;j<rest;j++){
if(temp[j]!=id_max){
mice[temp[j]].rank = round + 1;
}
else{
mice[temp[j]].rank = round;
}
}
}
for(i=0;i<n;i++){
if(i!=(n-1))
printf("%d ",mice[i].rank);
// cout<<mice[i].rank<<" ";
else
printf("%d",mice[i].rank);
}
return 0;
}
1074 Reversing Linked List （25 分）
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 (≤105) 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
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int data[100001];
int next[100001];
int root,total,k;
// scanf("%d %d %d\n",&root,&total,&k);
cin>>root>>total>>k;
int a,d,n;
int cc;
for(cc = 0;cc<total; cc++){
//scanf("%d %d %d\n",&a,&d,&n);
cin>>a>>d>>n;
data[a] = d;
next[a] = n;
}
int round,rest;
if(total%k == 0){
round = total/k;
rest = 0;
}
else{
round = total/k;
rest = total%k;
}
int i,j;
int temp_root;
int last_tail;
for(i=0;i<round;i++){
int temp_addr[k];
if(i==0){
temp_root = root;
for(j=0;j<k;j++){
temp_addr[j]=temp_root;
temp_root=next[temp_root];
}
root = temp_addr[k-1];
for(j=0;j<k;j++){
if(j==0){
next[temp_addr[j]]=temp_root;
}
else{
next[temp_addr[j]]=temp_addr[j-1];
}
}
last_tail = temp_addr[0];
}
else{
for(j=0;j<k;j++){
temp_addr[j]=temp_root;
temp_root=next[temp_root];
}
for(j=0;j<k;j++){
if(j==0){
next[temp_addr[j]]=temp_root;
}
else{
next[temp_addr[j]]=temp_addr[j-1];
}
}
next[last_tail] = temp_addr[k-1];
last_tail = temp_addr[0];
}
}
int cout_temp;
cout_temp=root;
while(next[cout_temp]!=(-1)){
printf("%.5d %d %.5d\n",cout_temp,data[cout_temp],next[cout_temp]);
cout_temp=next[cout_temp];
}
printf("%.5d %d %d\n",cout_temp,data[cout_temp],next[cout_temp]);
return 0;
}
1 注意5位数的地址输出，最后用了printf
最后还是有1个时间比较短的用例不通过，24分。各种情况后来都是尝试了，包括格式控制的疏忽等等，最后仍然没通过，原因待查中
1032 Sharing （25 分）
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.
Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
bool hash[100001] = {false};
char data[100001];
int next[100001];
int a_start,b_start,k;
cin>>a_start>>b_start>>k;
int i,j;
for(i=0;i<k;i++){
int temp_add,temp_data,temp_next;
scanf("%d %c %d",&temp_add,&temp_data,&temp_next);
// cin>>temp_add>>temp_data>>temp_next;
data[temp_add]=temp_data;
next[temp_add]=temp_next;
}
int temp_root;
temp_root = a_start;
while(temp_root!=(-1)){
hash[temp_root]=true;
temp_root=next[temp_root];
}
temp_root = b_start;
int flag = 0;
while((flag == 0) && (temp_root != (-1))){
if(hash[temp_root] == true){
printf("%.5d",temp_root);
flag = 1;
}
temp_root=next[temp_root];
}
if(flag == 0){
printf("-1");
}
return 0;
}
此题比较简单，貌似所有用例都是尾缀相同的；考虑到情况没做，试着秒一下直接通过了
DFS
1103 Integer Factorization （30 分）
The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.
Input Specification:
Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.
Output Specification:
For each case, if the solution exists, output in the format:
N = n[1]^P + ... n[K]^P
where n[i] (i = 1, ..., K) is the i-th factor. All the factors must be printed in non-increasing order.
Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen -- sequence { a1,a2,⋯,aK } is said to be larger than { b1,b2,⋯,bK } if there exists 1≤L≤K such that ai=bi for i<L and aL>bL.
If there is no solution, simple output Impossible.
Sample Input 1:
169 5 2
Sample Output 1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2:
169 167 3
Sample Output 2:
Impossible
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int N,K,P;
vector<int> temp,ans;
int flag = 0;
int ans_sumD=0;
int pre_n[401];
void DFS(int temp_sum,int n,int counter,int sumD){
//temp_sum临时立方和，n选到的数，counter已选的数 ,sumD底数的和
//死胡同条件
if(((n<1) || temp_sum>N || counter >K))
{
return;
}
//符合条件
if(((temp_sum == N) && (counter == K))) {
if(sumD > ans_sumD){
ans_sumD = sumD;
ans = temp;
}
flag = 1;
}
//开始DFS
//选该n
temp.push_back(n);
DFS(temp_sum + pre_n[n],n,counter+1,sumD+n);
temp.pop_back();
//不选该N
DFS(temp_sum,n-1,counter,sumD);
}
int main() {
cin>>N>>K>>P;
int NN;
int i,j;
j=0;
int pre_flag = 0;
while(pre_flag == 0){
pre_n[j]=j;
for(i=0;i<P-1;i++){
pre_n[j] = pre_n[j]*j;
}
if(pre_n[j]<=N){
NN = j;
}
if(pre_n[j]>N){
pre_flag = 1;
}
j++;
}
DFS(0,NN,0,0);
if(flag == 0){
cout<<"Impossible"<<endl;
}
else{
cout<<N<<" = ";
auto i = ans.begin();
for(i = ans.begin(); i !=ans.end();i++){
if(i !=(ans.end()-1)){
cout<<*i<<"^"<<P<<" + ";
}
else{
cout<<*i<<"^"<<P<<endl;
}
}
}
return 0;
}
//忽略了1 1 2极端条件
忽略了1 1 2极端条件,后来在幂计算处修正
必须预处理幂计算，否则直接超时，高阶运算非常耗时！
另一个超时的问题，是不对幂计算进行剪枝
注：不要太聚焦于示例输入，而导致未注意到KNP等参数变化
BFS
1091 Acute Stroke （30 分）
One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M×N matrix, and the maximum resolution is 1286 by 128); L (≤60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).
Then L slices are given. Each slice is represented by an M×N matrix of 0's and 1's, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1's to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.
【插图】
Figure 1
Output Specification:
For each case, output in a line the total volume of the stroke core.
Sample Input:
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0
Sample Output:
26
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int M,N,L,T;
int counter;
int X[6]={0,0,0,0,1,-1};
int Y[6]={0,0,1,-1,0,0};
int Z[6]={1,-1,0,0,0,0};
bool inq[60][128][1286] = {false};
int img[60][128][1286];
struct node{
int l;
int m;
int n;
}Node;
bool judge(int l, int m, int n){
if( (l<0) || (l>=L)
|| (m<0) || (m>=M)
|| (n<0) || (n>=N)){
return false;
}
else{
if((img[l][m][n] == 1) && inq[l][m][n] == false ){
// cout<<"judge true\n";
return true;
}
else{
// cout<<"judge false\n";
return false;
}
}
}
void BFS(int l, int m, int n){
// cout<<"BFS!"<<endl;
queue<node> Q;
if(inq[l][m][n] == false){
Node.l = l;
Node.m = m;
Node.n = n;
Q.push(Node);
inq[l][m][n] = true;
// cout<<"Push In Q!"<<endl;
}
while(!Q.empty()){
Node = Q.front();
Q.pop();
// cout<<"POP!"<<endl;
if(img[Node.l][Node.m][Node.n] == 1){
counter++;
// cout<<"coutner:"<<counter<<endl;
// cout<<"Find!"<<endl;
}
node nowNode;
int i;
for(i=0;i<6;i++){
nowNode.l = Node.l + X[i];
nowNode.m = Node.m + Y[i];
nowNode.n = Node.n + Z[i];
if(judge(nowNode.l,nowNode.m,nowNode.n)){
// if(inq[nowNode.l][nowNode.m][nowNode.n] == false){
Q.push(nowNode);
// cout<<"Push Next Door."<<endl;
inq[nowNode.l][nowNode.m][nowNode.n] = true;
// }
}
}
}
}
int main() {
vector<int> sum;
int sumF=0;
cin>>M>>N>>L>>T;
int i,j,k;
for(i=0;i<L;i++){
for(j=0;j<M;j++){
for(k=0;k<N;k++){
scanf("%d",&(img[i][j][k]));
}
}
}
/*
for(i=0;i<L;i++){
for(j=0;j<M;j++){
for(k=0;k<N;k++){
printf("%d ",(img[i][j][k]));
}
cout<<endl;
}
}
*/
for(i=0;i<L;i++){
for(j=0;j<M;j++){
for(k=0;k<N;k++){
if((inq[i][j][k] == false) && (img[i][j][k] == 1)){
counter = 0;
BFS(i,j,k);
if(counter !=0){
sum.push_back(counter);
}
}
}
}
}
auto ii = sum.end();
for(ii = sum.begin();ii!=sum.end();ii++){
if(*ii>=T){
sumF += *ii;
}
}
cout<<sumF<<endl;
return 0;
}
/*
写BFS就应该相信自己的思路，因为已经理解了这东西，不要太依赖于教材。
在遍历所有节点进行BFS时，应该及时剪枝，不合适的节点根本不让他进BFS，节省程序开销。
最后一个例一直出错，对进入BFS的遍历进行限制之后成功，并且耗时大大减小。
*/
Tree
1020 Tree Traversals （25 分）
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
struct node{
int data;
node* lchild;
node* rchild;
};
int post[30];
int in[30];
int N;
node* create(int posti,int postj, int ini, int inj){
//cout<<"posti:"<<posti<<" postj:"<<postj<<" ini"<<ini<<" inj"<<inj<<endl;
if(postj < posti){
//cout<<"NULL"<<endl;
return NULL;
}
if(posti<0 || postj<0 || ini<0 || inj<0){
//cout<<"NULL"<<endl;
return NULL;
}
node* root = new node;
root->data = post[postj];
//cout<<"Node:"<<root->data<<endl;
if(posti==postj){
root->lchild = NULL;
root->rchild = NULL;
return root;
}
//开始寻找根节点
int i=0;
int counter=0;
do{
if(in[ini+i] == post[postj]){
counter = ini+i;
}
i++;
}while(counter == 0 && i<N);
//counter-ini要统一，用来判断存在与否
root->lchild = create(posti,posti+(counter-ini)-1,ini,ini+(counter-ini)-1);
root->rchild = create(postj-1+1-(inj-counter),postj-1,counter+1,inj);
return root;
}
void BFS(node* root){
queue<node*> Q;
Q.push(root);
int j=0;
while(!Q.empty()){
if(j!=N-1){
cout<<Q.front()->data<<" ";
j++;
}
else{
cout<<Q.front()->data<<endl;
}
if(Q.front()->lchild != NULL){
Q.push((Q.front())->lchild);
}
if(Q.front()->rchild != NULL){
Q.push((Q.front())->rchild);
}
Q.pop();
}
}
int main() {
cin>>N;
int i,j,k;
for(i = 0; i < N; i++){
cin>>post[i];
}
for(i = 0; i < N; i++){
cin>>in[i];
}
//cout<<"Cin OK!"<<endl;
node* root;
root = create(0,N-1,0,N-1);
BFS(root);
return 0;
}
树的中序和后序创建，加一层DFS
1102 Invert a Binary Tree （25 分）
The following is from Max Howell @twitter:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.
Now it's your turn to prove that YOU CAN invert a binary tree!
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node from 0 to N−1, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int lchild[10];
int rchild[10];
int root;
bool root_flag[10]={false};
int counter = 0;
int N;
void BFS(int root){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
if(counter == N-1){
cout<<Q.front();
}
else{
cout<<Q.front()<<" ";
}
counter++;
if(lchild[Q.front()] != -1){
Q.push(lchild[Q.front()]);
}
if(rchild[Q.front()] != -1){
Q.push(rchild[Q.front()]);
}
Q.pop();
}
}
void DFS(int root){
if(lchild[root] != -1){
DFS(lchild[root]);
}
if(counter == N-1){
cout<<root;
}
else{
cout<<root<<" ";
counter++;
}
if(rchild[root] != -1){
DFS(rchild[root]);
}
}
int main() {
char a,b;
cin>>N;
int i,j;
for(i=0;i<N;i++){
cin>>a>>b;
if(a == '-'){
rchild[i] = -1;
}
else{
rchild[i] = int(a) - int('0');
root_flag[rchild[i]] = true;
}
if(b == '-'){
lchild[i] = -1;
}
else{
lchild[i] = int(b - '0');
root_flag[lchild[i]] =true;
}
}
for(i=0;i<N;i++){
if(root_flag[i] == false){
root = i;
}
}
counter = 0;
BFS(root);
cout<<endl;
counter = 0;
DFS(root);
return 0;
}
非常简单的静态二叉树+BFS+DFS
1079 Total Sales of Supply Chain （25 分）
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one's supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the total sales from all the retailers.
Input Specification:
Each input file contains one test case. For each case, the first line contains three positive numbers: N (≤105), the total number of the members in the supply chain (and hence their ID's are numbered from 0 to N−1, and the root supplier's ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:
Ki ID[1] ID[2] ... ID[Ki]
where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID's of these distributors or retailers. Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed 1010.
Sample Input:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
Sample Output:
42.4
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
vector<int> chain[100000];
//map<int,double> sale;
double sale[100000];
int N;
double price;
double rate;
double final_cost = 0;
double total = 0;
double price_cache[100000];
void DFS(int root, int tier){
if(!chain[root].empty()){
//cout<<"DFS"<<endl;
auto ii = chain[root].begin();
for(ii = chain[root].begin();ii != chain[root].end();ii++){
DFS(*ii, tier+1);
}
}
else{
int i=0;
double final_rate = 1;
if(tier<1000000){
final_cost += price_cache[tier] * sale[root];
}
else{
for(i = 0; i<tier; i++){
final_rate = final_rate * (1 + rate/100);
}
final_cost += final_rate * price * sale[root];
//cout<<"end: "<<final_cost<<endl;
}
}
}
int main() {
cin>>N>>price>>rate;
int i,j,k;
double sale_temp;
int child_temp;
price_cache[0] = price;
//计算cache，高阶乘法会导致最后一个算力超时！多次尝试发现有高达100000的tier。
//On复杂度缓存价格，用内存换时间
for(i = 1; i < 100000; i++){
price_cache[i] = price_cache[i-1] * (1 + rate/100);
}
for(i = 0; i < N; i++){
scanf("%d",&j);
//cout<<j<<endl;
if(j == 0){
scanf("%lf",&sale_temp);
//cout<<sale_temp<<endl;
sale[i] = sale_temp;
}
else{
for(k = 0; k < j; k++){
scanf("%d",&child_temp);
//cout<<child_temp<<endl;
chain[i].push_back(child_temp);
}
}
}
// return 0;
DFS(0, 0);
printf("%.1f\n",final_cost);
return 0;
}
//计算cache，高阶乘法会导致最后一个算力超时！多次尝试发现有高达100000的tier。 //On复杂度缓存价格，用内存换时间
1004 Counting Leaves （30 分）
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 01.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.
Sample Input:
2 1
01 1 02
Sample Output:
0 1
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<int> child[100];
queue<int> q[101];
void DFS(int root){
q[0].push(root);
int floor;
int flag = 0;
int counter = 0;
while(!q[counter].empty()){
int tick=0;
while(!q[counter].empty()){
int temp = q[counter].front();
if(child[temp].empty()){
tick++;
}
else{
auto j = child[temp].begin();
for(j = child[temp].begin(); j!=child[temp].end(); j++){
q[counter+1].push(*j);
}
}
q[counter].pop();
}
cout<<tick;
counter++;
if(!q[counter].empty()){
cout<<" ";
}
}
}
int main(){
int N,M;
cin>>N>>M;
int i,j,k;
for(i=0;i<M;i++){
int counter;
cin>>counter>>k;
for(j=0;j<k;j++){
int temp_child;
scanf("%d",&temp_child);
child[counter].push_back(temp_child);
}
}
DFS(1);
return 0;
}
简单的静态树存储于层级罗列
BST
1043 Is It a Binary Search Tree （25 分）
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1:
7
8 6 5 7 10 8 11
Sample Output 1:
YES
5 7 6 8 11 10 8
Sample Input 2:
7
8 10 11 8 6 7 5
Sample Output 2:
YES
11 8 10 7 5 6 8
Sample Input 3:
7
8 6 8 5 10 9 11
Sample Output 3:
NO
作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
#include <stdio.h>
#include <iostream>
using namespace std;
int seq[1000];
int rchild[1000];
int lchild[1000];
int rev_flag = 0; //0不反转 1反转
int check_flag = 0; //0 YES 1 NO
struct node{
int data;
node *lchild;
node *rchild;
};
node *build(int l, int r){
// cout<<"Build "<<l<<"-"<<r<<endl;
if(l>=r){
return NULL;
}
else{
node* root = new node;
root->data = seq[l];
// cout<<"Added "<<root->data<<endl;
if(rev_flag == 0)//不反转
{
int i=l+1;
while(i < r && seq[i] < seq[l]) {
i++;
}
root->lchild = build(l+1,i);
root->rchild = build(i,r);
}
else if(rev_flag == 1)//反转
{
int i=l+1;
while(i < r && seq[i] >= seq[l]) {
i++;
}
root->lchild = build(l+1,i);
root->rchild = build(i,r);
}
return root;
}
}
int temp_max,temp_min;
void findMax(node* root){
if(temp_max<root->data){
temp_max = root->data;
}
if(root->lchild != NULL){
findMax(root->lchild);
}
if(root->rchild != NULL){
findMax(root->rchild);
}
}
void findMin(node* root){
if(temp_min > root->data){
temp_min = root->data;
}
if(root->lchild != NULL){
findMin(root->lchild);
}
if(root->rchild != NULL){
findMin(root->rchild);
}
}
void check(node* root){
int data = root->data;
// cout<<"Checking root."<<"data:"<<root->data;
if(root->lchild != NULL){
// cout<<" lchild"<<root->lchild->data;
}
if(root->rchild != NULL){
// cout<<" rchild"<<root->rchild->data;
}
// cout<<endl;
if(rev_flag == 0){
if(root->lchild != NULL){
temp_max = root->lchild->data;
findMax(root->lchild);
// cout<<"Find Max:"<<temp_max<<endl;
if(temp_max >= data){
check_flag = 1;
// cout<<"flag = 1"<<endl;
// cout<<"CMP"<<data<<"&"<<(root->lchild)->data<<" "<<"flag = 1"<<endl;
}
check(root->lchild);
}
if(root->rchild != NULL){
temp_min = root->rchild->data;
findMin(root->rchild);
// cout<<"Find Min:"<<temp_min<<endl;
if(temp_min < data){
check_flag = 1;
// cout<<"flag = 1"<<endl;
// cout<<"CMP"<<data<<"&"<<(root->rchild)->data<<" "<<"flag = 1"<<endl;
}
check(root->rchild);
}
}
if(rev_flag == 1){
int data = root->data;
if(root->lchild != NULL){
temp_min = root->lchild->data;
findMin(root->lchild);
// cout<<"Find Min:"<<temp_min<<endl;
if(temp_min < data){
check_flag = 1;
// cout<<"CMP"<<data<<"&"<<(root->lchild)->data<<" "<<"flag = 1"<<endl;
}
check(root->lchild);
}
if(root->rchild != NULL){
temp_max = root->rchild->data;
findMax(root->rchild);
// cout<<"Find Max:"<<temp_max<<endl;
if(temp_max >= data){
check_flag = 1;
// cout<<"CMP"<<data<<"&"<<(root->rchild)->data<<" "<<"flag = 1"<<endl;
}
check(root->rchild);
}
}
}
void postorder(node* root){
if(root->lchild!=NULL){
postorder(root->lchild);
}
if(root->rchild!=NULL){
postorder(root->rchild);
}
cout<<root->data<<" ";
}
void postorder_1st(node* root){
if(root->lchild!=NULL){
postorder(root->lchild);
}
if(root->rchild!=NULL){
postorder(root->rchild);
}
cout<<root->data;
}
int main(){
int N;
cin>>N;
int i,j,k;
for(i = 0; i < N; i++){
cin>>seq[i];
}
if(seq[0]>seq[1]){
rev_flag = 0;
}
else{
rev_flag = 1;
}
node* root;
root = build(0,N);
// cout<<"Build Complete!"<<endl;
check(root);
if(check_flag == 1){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
postorder_1st(root);
}
return 0;
}
具体记录在笔记里。尝试了动态写法，注意结构体传递
Dijkstra
1030 Travel Plan （30 分）
A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and Dare the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:
City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.
Output Specification:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.
Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40
#include <iostream>
#include <cstdio>
#include <vector>
#define INF 1000000000
#define MAXV 510
using namespace std;
int N,M,S,D;
int G[MAXV][MAXV];
int cost[MAXV][MAXV];
int n[MAXV],d[MAXV],c[MAXV];
bool vis[MAXV] = {false};
vector<int> pre[MAXV];
void dijkstra(int s){
n[s] = 1;
d[s] = 0;
c[s] = 0;
int i,j,k;
for(i=0;i<N;i++){
//先找最小值
// cout<<"Round Start!"<<endl;
int u = -1;
int MIN = INF;
for(j=0;j<N;j++){
if(vis[j] == false && d[j]<MIN){
u = j;
MIN = d[j];
}
}
if(u==-1){
// cout<<"Failed"<<endl;
return;
}
// cout<<"Find Min:"<<u<<endl;
vis[u] = true;
for(j=0;j<N;j++){
if(G[u][j]!=INF){
// cout<<"Detecting:"<<u<<"->"<<j<<" G="<<G[u][j]<<endl;
if(vis[j]==false && (d[u]+G[u][j])<d[j]){
d[j]=d[u]+G[u][j];
pre[j].clear();
pre[j].push_back(u);
// cout<<"<<<<<<"<<j<<endl;
}
else if(vis[j]==false && (d[u]+G[u][j])==d[j]){
pre[j].push_back(u);
// cout<<"======"<<u<<endl;
}
}
}
}
}
int num=0;
int minCost=INF;
vector<int> tempPath;
vector<int> Path;
void DFS(int d){
// cout<<"DFS:"<<d<<endl;
if(d==S){
tempPath.push_back(d);
// cout<<"Push Back:"<<d<<endl;
auto i = tempPath.begin();
int tempCost = 0;
for(i;i!=(tempPath.end()-1);i++){
tempCost+=cost[*i][*(i+1)];
// cout<<"cost|"<<*i<<"+"<<*(i+1)<<endl;
}
// cout<<"tempCost="<<tempCost<<endl;
if(tempCost<minCost){
minCost = tempCost;
Path = tempPath;
}
// cout<<"Pop out"<<tempPath.back()<<endl;
tempPath.pop_back();
return;
}
tempPath.push_back(d);
// cout<<"Push Back:"<<d<<endl;
auto i=pre[d].begin();
for(i;i!=pre[d].end();i++){
DFS(*i);
//cout<<"Pop out"<<tempPath.back()<<endl;
//tempPath.pop_back();
}
// cout<<"Pop out"<<tempPath.back()<<endl;
tempPath.pop_back();
}
int main(){
cin>>N>>M>>S>>D;
int i,j,k;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G[i][j] = INF;
}
n[i] = 0;
d[i] = INF;
c[i] = INF;
}
for(i=0;i<M;i++){
int c1,c2,D,C;
cin>>c1>>c2>>D>>C;
G[c1][c2] = D;
G[c2][c1] = D;
cost[c1][c2] = C;
cost[c2][c1] = C;
}
// cout<<"Init Complete!dijkstra-"<<endl;
dijkstra(S);
// cout<<"DFS"<<endl;
DFS(D);
auto m=Path.end()-1;
int counter=0;
for(m;m!=Path.begin();m--){
cout<<*m<<" ";
counter++;
}
cout<<*m<<" ";
counter++;
cout<<d[D]<<" "<<minCost<<endl;
return 0;
}
1003 Emergency （25 分）
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input Specification:
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains Nintegers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define INF 1000000000
#define MAXV 510
using namespace std;
//G为图；res为点权；
//d[]为起点到各点最小距离；w[]为最大点权
//n为最小路径数目
int G[MAXV][MAXV];
int res[MAXV];
int d[MAXV],w[MAXV],n[MAXV];
bool vis[MAXV] = {false};
int N,M,C1,C2;
void dijkstra(int s){
int i,j;
for(i=0; i<MAXV; i++){
d[i] = INF;
w[i] = 0;
n[i] = 0;
}
d[s] = 0;
w[s] = res[s];
n[s] = 1;
//循环N次
for(i=0; i<N; i++){
// cout<<"---- Round "<<i<<" ----"<<endl;
//先找可到达的最短距离点
int u=-1;
int MIN = INF;
for(j=0;j<N;j++){
if(vis[j]==false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
// cout<<"Find min target: "<<u<<endl;
if(u == -1) {
return;
// cout<<"Failed"<<endl;
}
//一定记得标记已访问
vis[u] = true;
//然后找以d为起点，可到达点是否能更新距离信息
for(j=0; j<N; j++){
//此处注意筛选，需要非INF才进入
if(G[u][j]!=INF){
if(vis[j] == false && (G[u][j]+d[u])<d[j]){
//开始更新
d[j] = G[u][j]+d[u];
w[j] = w[u]+res[j];
n[j] = n[u];
// cout<<"Update << d["<<j<<endl;
}
else if(vis[j]==false && (G[u][j]+d[u])==d[j]){
if(w[u]+res[j]>w[j]){
w[j] = w[u]+res[j];
// cout<<"Update == w["<<j<<endl;
}
//最短路径和权值无关，写在外面
n[j] += n[u];
// cout<<"Update == n["<<j<<endl;
}
}
}
}
}
int main(){
cin>>N>>M>>C1>>C2;
int i,j,k;
for(i=0; i<N; i++) {
cin>>res[i];
}
//初始化图G
for(i=0;i<MAXV;i++){
for(j=0;j<MAXV;j++){
G[i][j] = INF;
}
}
//写入图G
for(i=0; i<M; i++){
int c1,c2,L;
cin>>c1>>c2>>L;
G[c1][c2] = L;
G[c2][c1] = L;
}
// cout<<"digkstra!"<<endl;
dijkstra(C1);
cout<<n[C2]<<" "<<w[C2];
return 0;
}