A Shortest Distance

　　题意相当于一个环，找出两点间从不同方向得到的距离中的最小值。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <vector>
 5 
 6 using namespace std;
 7 vector<int> disVec;
 8 int main()
 9 {
10     int N, tmpDis;
11     cin >> N;
12     disVec.resize(N+1,0);
13     for(int i = 2; i <= N; ++ i)
14     {
15         cin >> tmpDis;
16         disVec[i] = disVec[i-1] + tmpDis;
17     }
18     cin >> disVec[0];
19     int M, tmpSt, tmpEnd;
20     cin >> M;
21     for(int i = 0; i < M; ++ i)
22     {
23         cin >> tmpSt >> tmpEnd;
24         if(tmpSt > tmpEnd)
25             swap(tmpSt, tmpEnd);
26         tmpDis = min(disVec[tmpEnd]-disVec[tmpSt], disVec[tmpSt]+disVec[0]-disVec[tmpEnd]+disVec[N]);
27         cout << tmpDis << endl;
28     }
29 }

View Code

B Student List for Course

　　课程清单，这个题目有点意思，我是通过把cin，cout 改成printf和scanf让它不超时的。

　　试过用set会超时，暂时没有想到更好的方法。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <string>
 6 #include <vector>
 7 
 8 using namespace std;
 9 vector<int> disVec;
10 vector<string> classInfo[2510];
11 int main()
12 {
13     int N, K, tmpNum, tmpClass;
14     string tmpStr;
15     cin >> N >> K;
16     for(int i = 1; i <= N; ++ i)
17     {
18         cin >> tmpStr;scanf("%d", &tmpNum);
19         while(tmpNum--)
20         {
21             scanf("%d", &tmpClass);
22             classInfo[tmpClass].push_back(tmpStr);
23         }
24     }
25     for(int i = 1; i <= K; ++ i)
26     {
27         vector<string> tmpVec = classInfo[i];
28         sort(tmpVec.begin(), tmpVec.end());
29         printf("%d %d\n", i, tmpVec.size());
30         for(auto it = tmpVec.begin(); it != tmpVec.end(); ++ it)
31         {
32             printf("%s\n", (*it).c_str());
33         }
34     }
35     return 0;
36 }

View Code

C Find Coins

　　因为需要两个硬币，所以可以排序后，用双指针法，从两端向中间找，因为在找到合适两个硬币前，一旦左侧硬币加右侧硬币超过了所需面值，右边这个硬币肯定是不可能满足条件的。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <string>
 6 #include <vector>
 7 
 8 using namespace std;
 9 vector<int> coinVal;
10 int main()
11 {
12     int N, M, tmpVal;
13     cin >> N >> M;
14     coinVal.resize(N);
15     for(int i = 0; i < N; ++ i)
16         cin >> coinVal[i];
17     int tmpLast = N-1;
18     sort(coinVal.begin(), coinVal.end());
19     for(int i = 0; i < tmpLast; ++ i)
20     {
21         while(coinVal[i] + coinVal[tmpLast] > M)
22             tmpLast --;
23         if(tmpLast != i && coinVal[i] + coinVal[tmpLast] == M)
24         {
25             cout << coinVal[i] << " " << coinVal[tmpLast];
26             return 0;
27         }
28     }
29     cout << "No Solution";
30     return 0;
31 }

View Code

D Counting Ones

　　这个题目需要先利用数学知识找一下规律，会发现每一位产生的1的个数是有规律的，见代码while循环部分。

　　（其中numArray[i]是第i位数值，multBase是0-9、0-99、0-999...中包含1的个数，digitBase是0,10,100,1000...）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <string>
 6 #include <vector>
 7 
 8 using namespace std;
 9 int charToNum(char c)
10 {
11     return c-'0';
12 }
13 int n;
14 char numStr[15];
15 int numArray[15];
16 int len;
17 int numDeal(int tmpN)
18 {
19     int tmpNum = 0;
20     int digitBase = 1;
21     int multBase = 0;
22     while(tmpN >= 0)
23     {
24         if(numArray[tmpN] == 1)
25         {
26             tmpNum += numArray[tmpN] * multBase + n%digitBase+1;
27         }
28         else if(numArray[tmpN] > 1)
29         {
30             tmpNum += numArray[tmpN] * multBase + digitBase;
31         }
32         multBase = 10 * multBase + digitBase;
33         digitBase *= 10;
34         tmpN--;
35     }
36     return tmpNum;
37 }
38 int main()
39 {
40 
41     cin >> n;
42     sprintf(numStr, "%d", n);
43     len = strlen(numStr);
44     for(int i = 0; i < len; ++ i)
45         numArray[i] = charToNum(numStr[i]);
46     int num = numDeal(len-1);
47     cout << num;
48     return 0;
49 }

View Code