断断续续的把排序和检索专题刷完了,感觉英语还是不够,题目太长以后看起来就会很吃力。
还有一点感触就是 STL 的广泛应用。学到了很多新东西。
当然,不能忍受的就是答案最后多输出一行空行,UVaOJ 会判 WA。
UVaOJ 340
简单模拟题,一开始没有看懂题目。百度以后才明白的题意。朴素模拟以后即可得到答案。
#include <iostream>
#include <memory.h>
using namespace std;
const int MAX = 1024;
int pCode[MAX], pGuess[MAX], pVisited[MAX];
int main()
{
int N, nCase = 0;
while(cin >> N)
{
if(N == 0) { break; }
memset(pCode, 0, sizeof(pCode));
for(int i = 1; i <= N; i++)
{ cin >> pCode[i]; }
cout << "Game " << ++nCase << ":" << endl;
while(1)
{
int x = 0, y = 0, nCnt = 0;
memset(pGuess, 0, sizeof(pGuess));
memset(pVisited, 0, sizeof(pVisited));
for(int i = 1; i <= N; i++)
{
cin >> pGuess[i];
if(pGuess[i] == 0) { nCnt++; }
}
if(nCnt == N) { break; }
for(int i = 1; i <= N; i++)
{
if(pCode[i] == pGuess[i])
{
x++;
pVisited[i] = 2;
}
}
for(int i = 1; i <= N; i++)
{
if(pVisited[i] == 2) { continue; }
for(int j = 1; j <= N; j++)
{
if(pVisited[j] != 0) { continue; }
if(pCode[i] == pGuess[j])
{
y++;
pVisited[j] = 1;
break;
}
}
}
cout << " (" << x << "," << y << ")" << endl;
}
}
return 0;
}
UVaOJ 10420
STL 中的 set
水过。
#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, int> pMap;
int main()
{
int N;
while(cin >> N)
{
pMap.clear();
string x, y;
for(int i = 1; i <= N; i++)
{
cin >> x;
getline(cin, y);
pMap[x]++;
}
map<string, int>::iterator it;
for(it = pMap.begin(); it != pMap.end(); it++)
{ cout << (*it).first << " " << (*it).second << endl; }
}
return 0;
}
UVaOJ 10474
水题,一开始没看见“CASE”是大写的,WA 了好几次。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 10240;
int pData[MAX];
int main()
{
int nCase = 0;
int N, Q, x;
while(cin >> N >> Q)
{
if(N == 0 && Q == 0) { break; }
for(int i = 1; i <= N; i++)
{ cin >> pData[i]; }
cout << "CASE# " << ++nCase << ":" << endl;
sort(pData + 1, pData + N + 1);
for(int i = 1; i <= Q; i++)
{
cin >> x;
bool bFlag = false;
for(int j = 1; j <= N; j++)
{
if(pData[j] == x)
{ cout << x << " found at " << j << endl; bFlag = true; break; }
}
if(!bFlag) { cout << x << " not found" << endl; }
}
}
return 0;
}
UVaOJ 152
这道题目一开始也没有看懂题意,百度以后才明白的题意。
为了避免 sqrt
的误差,可以直接判断平方的大小关系。
#include <iostream>
#include <iomanip>
#include <memory.h>
using namespace std;
const int MAX = 10240;
const int pTable[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 };
struct Point
{
int x, y, z;
};
int pOut[MAX];
Point pData[MAX];
int Calc(int i, int j);
int main()
{
int x, y, z, nCnt = 0;
memset(pOut, 0, sizeof(pOut));
while(cin >> x >> y >> z)
{
if(x == 0 && y == 0 && z == 0) { break; }
pData[++nCnt] = {x, y, z};
}
for(int i = 1; i <= nCnt; i++)
{
int nMin = 2147483647;
for(int j = 1; j <= nCnt; j++)
{
if(i == j) { continue; }
int nTmp = Calc(i, j);
if(nMin > nTmp) { nMin = nTmp; }
}
pOut[nMin]++;
}
for(int i = 1; i <= 10; i++)
{ cout << setw(4) << pOut[i]; }
cout << endl;
return 0;
}
int Calc(int i, int j)
{
int x = pData[i].x - pData[j].x;
int y = pData[i].y - pData[j].y;
int z = pData[i].z - pData[j].z;
int nTmp = x * x + y * y + z * z;
for(int k = 1; k <= 10; k++)
{
if(nTmp < pTable[k]) { return k; }
}
}
UVaOJ 299
学过线性代数以后直接想到了逆序数。
#include <iostream>
#include <memory.h>
using namespace std;
const int MAX = 10240;
int pData[MAX];
int main()
{
int T, N;
cin >> T;
for(int i = 1; i <= T; i++)
{
cin >> N;
int nCnt = 0;
memset(pData, 0, sizeof(pData));
for(int j = 1; j <= N; j++)
{ cin >> pData[j]; }
for(int j = 1; j <= N; j++)
{
for(int k = j + 1; k <= N; k++)
{
if(pData[j] > pData[k]) { nCnt++; }
}
}
cout << "Optimal train swapping takes " << nCnt << " swaps." << endl;
}
return 0;
}
UVaOJ 120
简单模拟题,也是百度以后才知道的题意。
如果当前区间最大的不是第一个,那么先将它翻转到第一个,然后在翻转到当前区间的最后一个。
如果它恰好是第一个,直接翻转到最后一个。
#include <iostream>
#include <string>
#include <sstream>
#include <deque>
#include <algorithm>
using namespace std;
deque<int> Q;
int main()
{
int nTmp;
string x;
while(getline(cin, x))
{
cout << x << endl;
istringstream iss(x);
Q.clear();
while(iss >> nTmp) { Q.push_front(nTmp); }
for(deque<int>::iterator it = Q.begin(); it != Q.end(); it++)
{
deque<int>::iterator iMax = max_element(it, Q.end());
if(iMax != it)
{
if(iMax != Q.end() - 1)
{
reverse(iMax, Q.end());
cout << iMax - Q.begin() + 1 << " ";
}
reverse(it, Q.end());
cout << it - Q.begin() + 1 << " ";
}
}
cout << "0" << endl;
}
return 0;
}
UVaOJ 156
STL 中的 map
水过。但是对于 map
内部的自动排序还不是非常的理解。
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int MAX = 10240;
map<string, int> pMap;
vector<string> pVec;
string pData[MAX], pSorted[MAX];
string ToLower(string x);
int main()
{
int nCnt = 0;
string x;
while(cin >> x)
{
if(x == "#") { break; }
nCnt++;
pData[nCnt] = x;
pSorted[nCnt] = ToLower(x);
sort(pSorted[nCnt].begin(), pSorted[nCnt].end());
pMap[pSorted[nCnt]]++;
}
for(map<string, int>::iterator it = pMap.begin(); it != pMap.end(); it++)
{
if((*it).second != 1) { continue; }
int nPos;
for(nPos = 1; nPos <= nCnt; nPos++)
{
if(pSorted[nPos] == (*it).first) { break; }
}
pVec.push_back(pData[nPos]);
}
sort(pVec.begin(), pVec.end());
for(int i = 0; i < pVec.size(); i++)
{ cout << pVec[i] << endl; }
}
string ToLower(string x)
{
for(int i = 0; i < x.length(); i++)
{
if(x[i] >= 'A' && x[i] <= 'Z') { x[i] += 32; }
}
return x;
}
UVaOJ 400
一开始没有注意到除数为 0 的情况,导致 RE 了好多次。
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 60;
vector<string> pVec;
int main()
{
int N;
string x;
while(cin >> N)
{
int nMax = 0;
pVec.clear();
for(int i = 1; i <= N; i++)
{
cin >> x;
pVec.push_back(x);
nMax = max(nMax, (int)x.length());
}
int nCnt = MAX / (nMax + 2);
if(nCnt == 0) { nCnt = 1; }
int nRow = N / nCnt + (N % nCnt != 0);
sort(pVec.begin(), pVec.end());
cout << "------------------------------------------------------------" << endl;
for(int i = 1; i <= nRow; i++)
{
for(int j = 1; j <= nCnt; j++)
{
int nPos = (j - 1) * nRow + i - 1;
if(nPos >= N) { continue; }
cout.setf(ios::left);
if(nPos >= (nCnt - 1) * nRow)
{ cout << setw(nMax) << pVec[nPos]; }
else { cout << setw(nMax + 2) << pVec[nPos]; }
}
cout << endl;
}
}
return 0;
}
UVaOJ 123
这道题目要求按照原来的顺序,而 sort
是非稳定排序,在这上面 WA 了好几次。
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
const int MAX = 10240;
int cmp(pair<string, pair<string, int> > x, pair<string, pair<string, int> > y)
{
if(x.first != y.first) { return x.first < y.first; }
else { return x.second.second < y.second.second; }
}
string pData[MAX];
set<string> pSet;
vector<pair<string, pair<string, int> > > pVec;
string ToLower(string x);
string ToUpper(string x);
int main()
{
int nPos = 0;
string x;
while(cin >> x)
{
if(x == "::") { break; }
pSet.insert(x);
}
cin.ignore();
while(getline(cin, x))
{
string strLow = ToLower(x);
istringstream iss(strLow);
int nCnt = 0;
while(iss >> x)
{
if(x != "") { pData[++nCnt] = x; }
}
for(int i = 1; i <= nCnt; i++)
{
if(!pSet.count(pData[i]))
{
string strTmp = "";
for(int j = 1; j <= nCnt; j++)
{
if(j != i) { strTmp += pData[j] + " "; }
else { strTmp += ToUpper(pData[j]) + " "; }
}
strTmp = strTmp.substr(0, strTmp.length() - 1);
pVec.push_back(make_pair(ToUpper(pData[i]), make_pair(strTmp, ++nPos)));
}
}
}
sort(pVec.begin(), pVec.end(), cmp);
for(int i = 0; i < pVec.size(); i++)
{ cout << pVec[i].second.first << endl; }
return 0;
}
string ToLower(string x)
{
for(int i = 0; i < x.length(); i++)
{
if(x[i] >= 'A' && x[i] <= 'Z')
{ x[i] += 32; }
}
return x;
}
string ToUpper(string x)
{
for(int i = 0; i < x.length(); i++)
{
if(x[i] >= 'a' && x[i] <= 'z')
{ x[i] -= 32; }
}
return x;
}
UVaOJ 10194
水题,直接模拟即可。注意写好排序的 cmp
函数即可。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 1024;
struct Player
{
Player()
{ Clear(); }
void Clear()
{
strName = "";
nPoint = nGame = 0;
nWin = nTie = nLose = 0;
nDiff = nScored = nAgainst = 0;
}
string strName;
string strTmp;
int nPoint, nGame;
int nWin, nTie, nLose;
int nDiff, nScored, nAgainst;
};
Player pData[MAX];
int GetPos(string x);
int Trans(string x);
string ToLower(string x);
int cmp(Player x, Player y)
{
if(x.nPoint != y.nPoint) { return x.nPoint > y.nPoint; }
if(x.nWin != y.nWin) { return x.nWin > y.nWin; }
if(x.nDiff != y.nDiff) { return x.nDiff > y.nDiff; }
if(x.nScored != y.nScored) { return x.nScored > y.nScored; }
if(x.nGame != y.nGame) { return x.nGame < y.nGame; }
return ToLower(x.strName) < ToLower(y.strName);
}
int main()
{
int N, nPlayer, nGame;
string x;
cin >> N;
cin.ignore();
for(int i = 1; i <= N; i++)
{
getline(cin, x);
cout << x << endl;
int nCnt = 0;
cin >> nPlayer;
cin.ignore();
for(int j = 1; j <= nPlayer; j++)
{
getline(cin, x);
pData[++nCnt].Clear();
pData[nCnt].strName = x;
pData[nCnt].strTmp = ToLower(x);
}
cin >> nGame;
cin.ignore();
for(int j = 1; j <= nGame; j++)
{
getline(cin, x);
int nLeft = x.find_first_of('#'), nRight = x.find_last_of('#'), nMid = x.find('@');
string strLeft = x.substr(0, nLeft);
string strRight = x.substr(nRight + 1, x.length() - nRight - 1);
string strLeftPoint = x.substr(nLeft + 1, nMid - nLeft - 1);
string strRightPoint = x.substr(nMid + 1, nRight - nMid - 1);
int nLeftPos = GetPos(strLeft), nRightPos = GetPos(strRight);
int nLeftPoint = Trans(strLeftPoint), nRightPoint = Trans(strRightPoint);
pData[nLeftPos].nGame++; pData[nRightPos].nGame++;
pData[nLeftPos].nScored += nLeftPoint; pData[nRightPos].nScored += nRightPoint;
pData[nLeftPos].nAgainst += nRightPoint; pData[nRightPos].nAgainst += nLeftPoint;
if(nLeftPoint > nRightPoint) { pData[nLeftPos].nWin++; pData[nRightPos].nLose++; }
else if(nLeftPoint < nRightPoint) { pData[nLeftPos].nLose++; pData[nRightPos].nWin++; }
else { pData[nLeftPos].nTie++; pData[nRightPos].nTie++; }
}
for(int i = 1; i <= nPlayer; i++)
{
pData[i].nPoint = pData[i].nWin * 3 + pData[i].nTie;
pData[i].nDiff = pData[i].nScored - pData[i].nAgainst;
}
sort(pData + 1, pData + nPlayer + 1, cmp);
for(int i = 1; i <= nPlayer; i++)
{
cout << i << ") " << pData[i].strName
<< " " << pData[i].nPoint << "p, "
<< pData[i].nGame << "g ("
<< pData[i].nWin << "-"
<< pData[i].nTie << "-"
<< pData[i].nLose << "), "
<< pData[i].nDiff << "gd ("
<< pData[i].nScored << "-"
<< pData[i].nAgainst << ")"
<< endl;
}
if(i != N) { cout << endl; }
}
return 0;
}
int GetPos(string x)
{
for(int nPos = 1; nPos < MAX; nPos++)
{
if(pData[nPos].strTmp == ToLower(x))
{ return nPos; }
}
}
int Trans(string x)
{
int nRet = 0;
for(int i = 0; i < x.length(); i++)
{
nRet *= 10;
nRet += x[i] - '0';
}
return nRet;
}
string ToLower(string x)
{
for(int i = 0; i <x.length(); i++)
{
if(x[i] >= 'A' && x[i] <= 'Z')
{ x[i] += 32; }
}
return x;
}
UVaOJ 755
直接 map
水过。多输出了一行空行,导致 WA 了一次。
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const char pTable[] = {
'2', '2', '2', '3', '3', '3',
'4', '4', '4', '5', '5', '5',
'6', '6', '6', '7', '*', '7',
'7', '8', '8', '8', '9', '9',
'9', '*' };
int cmp(pair<string, int> x, pair<string, int> y)
{ return x.first < y.first; }
vector<pair<string, int> > pVec;
map<string, int> pMap;
int main()
{
int T, N;
string x;
cin >> T;
for(int i = 1; i <= T; i++)
{
pVec.clear();
pMap.clear();
cin >> N;
cin.ignore();
for(int j = 1; j <= N; j++)
{
getline(cin, x);
string strTmp = "";
for(int k = 0; k < x.length(); k++)
{
if(x[k] >= '0' && x[k] <= '9') { strTmp += x[k]; }
if(x[k] >= 'A' && x[k] <= 'Z') { strTmp += pTable[x[k] - 'A']; }
}
while(strTmp.length() != 7) { strTmp = '0' + strTmp; }
pMap[strTmp]++;
}
for(map<string, int>::iterator it = pMap.begin(); it != pMap.end(); it++)
{
if((*it).second > 1) { pVec.push_back(*it); }
}
if(pVec.size() == 0) { cout << "No duplicates." << endl; }
else
{
sort(pVec.begin(), pVec.end(), cmp);
for(int j = 0; j < pVec.size(); j++)
{
cout << pVec[j].first.substr(0, 3) << "-"
<< pVec[j].first.substr(3, 4) << " "
<< pVec[j].second << endl;
}
}
if(i != T) { cout << endl; }
}
return 0;
}
UVaOJ 10785
类似归并的思想。一开始打错表了,WA 了一次。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const char pOdd[] = { 'A', 'U', 'E', 'O', 'I' };
const char pEven[] = {
'J', 'S', 'B', 'K', 'T',
'C', 'L', 'D', 'M', 'V',
'N', 'W', 'F', 'X', 'G',
'P', 'Y', 'H', 'Q', 'Z',
'R' };
string Solve(int x);
int main()
{
int T, N;
cin >> T;
for(int i = 1; i <= T; i++)
{
cin >> N;
cout << "Case " << i << ": "
<< Solve(N) << endl;
}
return 0;
}
string Solve(int x)
{
string strRet = "";
string strOdd = "";
string strEven = "";
int nOdd = (x + 1) / 2;
int nEven = x / 2;
int nOddCnt = nOdd / 21 + (nOdd % 21 != 0);
int nEvenCnt = nEven / 5 + (nEven % 5 != 0);
for(int i = 1; i <= nOddCnt; i++)
{
for(int j = 1; j <= 21; j++)
{ strOdd += pOdd[i - 1]; }
}
for(int i = 1; i <= nEvenCnt; i++)
{
for(int j = 1; j <= 5; j++)
{ strEven += pEven[i - 1]; }
}
strOdd = strOdd.substr(0, nOdd);
strEven = strEven.substr(0, nEven);
sort(strOdd.begin(), strOdd.end());
sort(strEven.begin(), strEven.end());
int nOddPos = 0, nEvenPos = 0;
for(int i = 1; i <= x; i++)
{
if(i & 1) { strRet += strOdd[nOddPos++]; }
else { strRet += strEven[nEvenPos++]; }
}
return strRet;
}
这一组题目做下来,感觉英语还是要提升,有时候题目一长,干扰信息一多,读起来就感觉很有难度了。