PAT 2019 秋

　　考试的还行。不过略微有点遗憾，但是没想到第一题会直接上排序和dfs，感觉这次的题目难度好像是倒着的一样。哈哈哈哈。

　　第一题实在是搞崩心态，这道题给我的感觉是，可以做，但事实上总是差点啥。

　　第二题，第三题，把我的心态稳住了，不然的话这次考试可能会雪崩。这两道题目都是提交一次，直接全红。

　　接着二三题带来的信心把第四题搞定了，好像提交了两次。

　　然后就又开始死磕第一题，关键是当时自己以为第一题不应该用dfs，就一直在修改细节。╮(╯▽╰)╭，还是超时。

　　感觉PAT不算很难，但是在新的环境、计时、排队提交等因素的影响下，对心理素质有相当大的考验（至少对不少人来说），第一题可能直接就导致整场考试稳不住了。

　　无论如何实力足够强可以减少这些因素的影响。

下面是考试时候的代码。

7-1 Forever

当时觉得第一题，3000ms，直接暴力计算了。（最后一个点超时）只需要把第二个for循环改成

for(int j = fac[K]+9; j < fac[K+1]; j += 10)

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <iostream>

 #include <map>

 #include <algorithm>

 using namespace std;

 int N, K, m;

 typedef struct NODE{

     int a, n;

     NODE(int tmpN, int tmpA):a(tmpA),n(tmpN){}

 }node;

 int gcd(int a, int b){

     if(b == )    return a;

     return gcd(b, a%b);

 }

 bool isPrimeB2(int n){

     if(n <= )

         return false;

     int sqr = (int)sqrt(1.0*n);

     for(int i = ; i <= sqr; ++ i)

         if(n % i == )

             return false;

     return true;

 }

 int getSumOfDigit(int n){

     int tmpSum = ;

     while(n > ){

         tmpSum += n %;

         n /= ;

     }

     return tmpSum;

 }

 bool cmpSort(node a, node b){

     if(a.n != b.n)

         return a.n < b.n;

     else if(a.a != b.a)

         return a.a < b.a;

 }

 vector<node> dstVec[];

 int fac[]={,,,,,,,,,,};

 int main(){

     cin >> N;

     int tmpN;

     for(int i = ; i <= N; ++ i){

         scanf("%d %d", &K, &m);

         int cnt = ;

         printf("Case %d\n", i);

         for(int j = fac[K]; j < fac[K+]; j++){

             if(getSumOfDigit(j) == m){

                 tmpN = getSumOfDigit(j+);

                 int tmpNum = gcd(m, tmpN);

                 if(isPrimeB2(tmpNum)){

                     cnt ++;

                     dstVec[tmpN].push_back(NODE(tmpN, j));

                 }

             }

         }

         if(cnt == )

             printf("No Solution\n");

         else{

             for(int k = ; k < ; ++ k){

                 sort(dstVec[k].begin(), dstVec[k].end(), cmpSort);

             for(auto it = dstVec[k].begin(); it != dstVec[k].end(); ++ it)

                 printf("%d %d\n", it->n, it->a);

                 dstVec[k].clear();

             }

         }

     }

     return ;

 }

7-2 Merging Linked Lists

这道题目没啥好说的，甲级真题里面有类似的。

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <iostream>

 #include <map>

 using namespace std;

 int L1, L2, N;

 typedef struct NODE{

     int val, next, addr;

     NODE(){}

     NODE(int a, int v, int n):addr(a),val(v),next(n){}

 }node;

 vector<node> inputNodeVec();

 vector<node> node1Vec, node2Vec, dstVec;

 void adjust(vector<node> &lVec1, vector<node> &lVec2){

     int len1 = , len2 = lVec2.size()-, cnt = ;

     while(len1 < lVec1.size() && len2 >= ){

         if(cnt < ){

             dstVec.push_back(lVec1[len1++]);

             cnt ++;

         }

         else{

             dstVec.push_back(lVec2[len2--]);

             cnt = ;

         }

     }

     while(len1 < lVec1.size())

         dstVec.push_back(lVec1[len1++]);

     while(len2 >= )

         dstVec.push_back(lVec2[len2--]);

 }

 int main()

 {

     cin >> L1 >> L2 >> N;

     int tmpAddr, tmpNext, tmpVal;

     while(N--){

         scanf("%d %d %d", &tmpAddr, &tmpVal, &tmpNext);

         inputNodeVec[tmpAddr].next = tmpNext;

         inputNodeVec[tmpAddr].val = tmpVal;

         inputNodeVec[tmpAddr].addr = tmpAddr;

     }

     int cnt1 = , cnt2 = ;

     tmpAddr = L1;

     while(tmpAddr != -){

         node1Vec.push_back(inputNodeVec[tmpAddr]);

         tmpAddr = inputNodeVec[tmpAddr].next;

     }

     tmpAddr = L2;

     while(tmpAddr != -){

         node2Vec.push_back(inputNodeVec[tmpAddr]);

         tmpAddr = inputNodeVec[tmpAddr].next;

     }

     if(node1Vec.size() > node2Vec.size()){

         adjust(node1Vec, node2Vec);

     }

     else{

         adjust(node2Vec, node1Vec);

     }

     int tmpLen = dstVec.size();

     for(int i = ; i < tmpLen; ++ i){

         if(i == tmpLen-)

             printf("%05d %d -1\n", dstVec[i].addr, dstVec[i].val);

         else

             printf("%05d %d %05d\n", dstVec[i].addr, dstVec[i].val, dstVec[i+].addr);

     }

     return ;

 }

7-3 Postfix Expression

　　这一题也是基础题目。

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <iostream>

 #include <map>

 #include <string>

 #include <stack>

 using namespace std;

 int L1, L2, N;

 typedef struct NODE{

     string symbolStr;

     int lChild, rChild;

     NODE(){}

     NODE(string str, int v, int n):symbolStr(str),lChild(v),rChild(n){}

 }node;

 vector<node> synTreeVec;

 vector<bool> visitFlagVec;

 string preStr;

 string preOrder(int u){

     if(u == -)

         return "";

     string tmpStr1 = preOrder(synTreeVec[u].lChild);

     string tmpStr2 = preOrder(synTreeVec[u].rChild);

     if(tmpStr1.empty())

         return    "(" + synTreeVec[u].symbolStr + tmpStr2 + ")";

     else

         return    "(" + tmpStr1 + tmpStr2 + synTreeVec[u].symbolStr + ")";

 }

 bool isSyn(char tmpC){

     if(tmpC == '+' || tmpC =='-' || tmpC=='*' || tmpC=='/' || tmpC =='%')

         return true;

     return false;

 }

 int main(){

     int N;

     cin >> N;

     synTreeVec.resize(N+);

     visitFlagVec.resize(N+, false);

     string tmpStr;

     int tmpL, tmpR;

     for(int i = ; i <= N; ++ i){

         cin >> synTreeVec[i].symbolStr >> tmpL >> tmpR;

         synTreeVec[i].lChild = tmpL;

         synTreeVec[i].rChild = tmpR;

         if(tmpL > )

             visitFlagVec[tmpL] = true;

         if(tmpR > )

             visitFlagVec[tmpR] = true;

     }

     int tmpRoot = ;

     for(int i = ; i <= N; ++ i){

         if(!visitFlagVec[i]){

             tmpRoot = i;

             break;

         }

     }

     preStr = preOrder(tmpRoot);

     cout << preStr;

     return ;

 }

7-4 Dijkstra Sequence

　　这一题主要是最后的判断。把与源点最短路径相同的点当做同一等级、位置可以互换的点。

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <iostream>

 #include <map>

 #include <string>

 #include <stack>

 using namespace std;

 int Nv, Ne;

 const int INF = 0x7f7f7f7f;

 typedef struct NODE{

     int val, next;

     NODE(){}

     NODE(int n, int v):val(v),next(n){}

 }node;

 vector<node> routeVec[];

 vector<int> numSequen,disVec;

 vector<int> sameLevelNode[];

 map<int, int> disMap, visFlagMap;

 bool dijkstra(int u){

     fill(disVec.begin(), disVec.end(), INF);

     vector<bool> dijVisFlagVec(Nv+,false);

     disVec[u] = ;

     for(int i = ; i < Nv; ++ i){

         int tmpMin = INF, v = -;

         for(int j = ; j <= Nv; j ++ ){

             if(!dijVisFlagVec[j] && disVec[j] < tmpMin){

                 v = j;

                 tmpMin = disVec[j];

             }

         }

         if(v == -)

             break;

         dijVisFlagVec[v] = true;

         for(auto it = routeVec[v].begin(); it != routeVec[v].end(); ++ it){

             int tmpV = it->next, tmpW = it->val;

             if(!dijVisFlagVec[tmpV] && disVec[tmpV] > disVec[v] + tmpW)

                 disVec[tmpV] = disVec[v] + tmpW;

         }

     }

     return true;

 }

 int main()

 {

     cin >> Nv >> Ne;

     int tmpSt, tmpEnd, tmpDis;

     while(Ne--){

         scanf("%d %d %d", &tmpSt, &tmpEnd, &tmpDis);

         routeVec[tmpSt].push_back(NODE(tmpEnd, tmpDis));

         routeVec[tmpEnd].push_back(NODE(tmpSt, tmpDis));

     }

     int K;

     disVec.resize(Nv+, INF);

     cin >> K;

     while(K--){

         disMap.clear();

         visFlagMap.clear();

         numSequen.resize(Nv, );

         for(int i = ; i < Nv; ++ i)

             scanf("%d", &numSequen[i]);

         bool tmpFlag = true;

         dijkstra(numSequen[]);

         for(auto i = ; i <= Nv; ++ i)

             disMap[disVec[i]] ++;

         int tmpIndex = , tmpMaxIndex = , tmpIndexDij = ;

         for(auto it = disMap.begin(); it != disMap.end(); ++ it){

             tmpMaxIndex += (it->second);

             tmpDis = it->first;

             int p = ;

             while(p <= Nv && tmpIndexDij <= tmpMaxIndex){

                 if(disVec[p] == tmpDis){

                     visFlagMap[p] = ;

                     tmpIndexDij ++;

                 }

                 p++;

             }

             while(tmpIndex < tmpMaxIndex){

                 int tmpNum = numSequen[tmpIndex++];

                 if(visFlagMap[tmpNum] != )

                     tmpFlag = false;

                 else

                     visFlagMap[tmpNum] = ;

             }

         }

         if(tmpFlag)

             printf("Yes\n");

         else

             printf("No\n");

     }

     return ;

 }

巴特西

PAT 2019 秋

最新文章

热门文章