复合词
原题：UVa 10391
算法
这题我一开始是拼接来做的结果超时，部分代码如下：
for(int i = 0; i < cnt; i++){
for(int j = i + 1; j < cnt; j++){
s1 = words[i] + words[j];
s2 = words[j] + words[i];
if(dict.count(s1)) cout << s1 << "\n";
if(dict.count(s2)) cout << s2 << "\n";
}
}
这里的时间复杂度有O(n²)了，换一种思考方式，改成字符串分割，因为每个字符串长度不一，所以时间复杂度为O(mn)，结果通过了，其中用到了 string类里面的 substr()函数,具体用法参见下面的代码
程序代码
#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 120000 + 5;
set<string> dict;
string words[maxn];
int main(){
// freopen("input.txt", "r", stdin);
string s;
int cnt = 0;
dict.clear();
while(cin >> s){
dict.insert(s);
words[cnt] = s;
cnt++;
}
string a, b;
for(int i = 0; i < cnt; i++){
for(int j = 0; j < words[i].size() - 1; j++){
a = words[i].substr(0,j + 1);//从下标为0的元素开始到长度为j+1的元素结束
if(!dict.count(a)) continue;
b = words[i].substr(j + 1);//从下标为j+1的元素开始，到字符串结束
if(!dict.count(b)) continue;
cout << words[i]<<"\n";
break;
}
}
return 0;
}
打印队列
原题：UVa 12100
算法
用一个普通队列来放任务，用一个优先队列来按优先级放任务，如果普通队列里的队首元素在优先级队列里也是队首，则出列，否则放到队尾。
程序代码
#include <cstdio>
#include <queue>
using namespace std;
struct project{
int x;
int flag;
};
queue<project> q;
priority_queue<int> pq;
int main(int argc, char const *argv[])
{
int T;
scanf("%d", &T);
while(T--){
while(!q.empty()) q.pop();
while(!pq.empty()) pq.pop();
int n,t;
project m;
scanf("%d%d", &n, &t);
for(int i = 0; i < n; i++){
scanf("%d", &m.x);
m.flag = 0;
if(i == t) m.flag = 1;//记录关注的任务
q.push(m);
pq.push(m.x);
}
int cnt = 0;
while(1){
project t1;
int t2;
t1 = q.front();
t2 = pq.top();
if(t1.x == t2 && t1.flag) {cnt++; printf("%d\n", cnt);break;}
else if(t1.x == t2 && !t1.flag){
cnt++;
q.pop();
pq.pop();
}
else{
q.pop();
q.push(t1);
}
}
}
return 0;
}
图书馆管理系统
原题：UVa 230
算法
字符串变成数字来处理，这个思想很重要！！！将字符串变成数字后，无论是排序，还是插入删除，都会简单不少，而且速度更快；其他其实没什么算法，不过有点烦而已，要细心。
程序代码
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct book{
string title;
string author;
//重载图书排序方式
bool operator < (const book& ob){
if(this->author == ob.author) return this->title < ob.title;
return this->author < ob.author;
}
};
vector<book> All_books;// 存储所有图书信息
map<string, int> ID;//每本书对应一个唯一的ID
vector<int > LIB;//图书馆中现存的书
vector<int > SHELVE;//已经还来的书，还未上架
int main(int argc, char const *argv[])
{
// freopen("input.txt", "r", stdin);
string s;
book tb;
while(getline(cin, s)){
if(s[0] == 'E') break;
int t = s.find("by", 0);
tb.title = s.substr(0, t - 1);
tb.author = s.substr(t + 3);
All_books.push_back(tb);//按格式分割字符串后存储每一本图书
}
sort(All_books.begin(), All_books.end());
for(int i = 0; i < All_books.size(); i++){
ID[All_books[i].title] = i;//未每本书建立唯一的ID，作者可能相同但书名不会
LIB.push_back(i);
}
while(getline(cin, s)){
//结束操作
if(s[0] == 'E') break;
//借书
if(s[0] == 'B'){
string temp = s.substr(7);
int t = ID[temp];
int i = 0,size = LIB.size();
while(LIB[i] != t) i++;//找到目标书籍的ID
for(; i < size - 1; i++){
LIB[i] = LIB[i + 1];
}
LIB.resize(size - 1);//更改现存的书的数量
}
//还书
if(s[0] == 'R'){
string temp = s.substr(7);
int t = ID[temp];
SHELVE.push_back(t);//放到待还书架上
}
if(s[0] == 'S'){
sort(SHELVE.begin(), SHELVE.end());
for(int i = 0; i < SHELVE.size(); i++){
//如果图书馆没书了
if(LIB.size()== 0){
LIB.push_back(SHELVE[i]);
cout << "Put " << All_books[SHELVE[i]].title <<" first" << "\n";
}
else{
int size = LIB.size();
int j = 0;
while(SHELVE[i] > LIB[j] && j < size) j++;//找到插入位置
LIB.push_back(-1);//为放上来的书预留一个空位
for( int k = size; k > j; k--){
LIB[k] = LIB[k - 1];
}
LIB[j] = SHELVE[i];
if(j > 0)//插入的位置不是首位
cout << "Put " << All_books[LIB[j]].title << " after "
<< All_books[LIB[j - 1]].title << "\n";
else//放在首位
cout << "Put " << All_books[SHELVE[j]].title <<" first" << "\n";
}
}
SHELVE.clear();//清空书架
cout <<"END\n";
}
}
return 0;
}
集合栈计算机
原题：UVa 12096
算法
同样是字符串变成数字来处理
程序代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <stack>
#include <map>
using namespace std;
typedef set<int> Set;
map<Set,int> IDcache;
vector<Set> Setcache;
int ID(Set x){
if(IDcache.count(x)) return IDcache[x];
Setcache.push_back(x);
return IDcache[x] = Setcache.size()-1;
}
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x,x.begin())
stack<int> s;
int main(){
int n,T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
while(!s.empty()) s.pop();
for(int i = 0; i < n; i++){
string op;
cin >> op;
if (op[0] == 'P') s.push(ID(Set()));
else if (op[0] == 'D') s.push(s.top());
else {
Set x1 = Setcache[s.top()]; s.pop();
Set x2 = Setcache[s.top()]; s.pop();
Set x;
if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
if (op[0] == 'A') { x = x2; x.insert(ID(x1));}
s.push(ID(x));
}
cout << Setcache[s.top()].size() << endl;
}
cout << "***" <<endl;
}
return 0;
}
数据库
原题：UVa 1592
算法
算法同上，用数字编号进行预处理
程序代码
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <sstream>
using namespace std;
typedef pair<int, int> PII;
const int maxcol = 10 + 5;
const int maxrow = 10000 + 5;
int n, m, cnt, db[maxrow][maxcol];
map<string, int> id;
int ID(const string& s){
if(!id.count(s)){
id[s] = ++cnt;
}
return id[s];
}
void find(){
for(int c1 = 0; c1 < m; c1++)
for(int c2 = c1 + 1; c2 < m; c2++){
map<PII,int> d;
for(int r = 0; r < n; r++){
PII p = make_pair(db[r][c1], db[r][c2]);
if(d.count(p))
{
printf("NO\n");
printf("%d %d\n", d[p] + 1, r + 1);
printf("%d %d\n", c1 + 1, c2 + 1);
return ;
}
d[p] = r;
}
}
printf("YES\n");
}
int main(){
// freopen("input.txt", "r", stdin);
string s;
while(getline(cin, s)){
stringstream ss(s);
if(!(ss >> n >> m)) break;
cnt = 0;
id.clear();
for(int i = 0; i < n; i++){
getline(cin, s);
int lastpos = -1;
for(int j = 0; j < m; j++){
int p = s.find(',',lastpos + 1);
if(p == string::npos) p = s.length();
db[i][j] = ID(s.substr(lastpos + 1, p - lastpos -1));
lastpos = p;
}
}
find();
}
}
找bug
原题：UVa 1596
算法
用栈来保存 []，用 map来保存数组，这一题比较繁琐，首先考虑是赋值语句还是定义语句，就是看有没有“=”，定义语句比较简单，变量名直接放到map里，再用一个map保存该数组的长度。如果是赋值语句，就要考虑一下情况：
- 是否存在变量名
- 如果是嵌套的话，每一层嵌套的值在外层的数组中有没有超过外层数组的长度
- 如果没有超过长度，每一层嵌套的值在外层的数组中是否被赋值
程序代码
#include <iostream>
#include <map>
#include <string>
#include <stack>
using namespace std;
map<char, map<int, int> > dict;
map<char, int> d2;
stack<char > nameache;
int main(int argc, char const *argv[])
{
string s;
int flag = 0;//用来识别是否为.的标志
int bug_flag = 0;//是否出现bug
int line = 0;
while(getline(cin, s))
{
if(bug_flag == 1 && s[0] != '.') continue;
if(s == "." && flag == 0){
flag++;
if(!bug_flag) cout <<"0\n";
bug_flag = 0;
dict.clear();
d2.clear();
line = 0;
while(!nameache.empty()) nameache.pop();
continue;
}
if(s == "." && flag == 1){break;}
flag = 0;
++line;
//定义
if(s.find("=") == string::npos)
{
int k = 2, num = 0;
while(s[k] != ']'){
num *= 10;
num += s[k] - '0';
++k;
}
d2[s[0]] = num;
}
//赋值
else{
int pos = s.find("=");
int i = 0, num = 0;
while(s[i] != ']'){
if(isalpha(s[i])) {
if(!d2.count(s[i])) {cout << line << endl; bug_flag = 1; break;}
nameache.push(s[i]);
}
else if(s[i] == '[') {i++;continue;}
else if(s[i] >= '0' && s[i] <= '9'){
num *= 10;
num += s[i] - '0';
}
i++;
}
if(bug_flag) continue;
int t = num, left;
char ch, chleft;
while(nameache.size() > 1){
ch = nameache.top();
if(!d2.count(ch)){cout << line << endl; bug_flag = 1; break;}
if(t >= d2[ch]) {cout << line << endl; bug_flag = 1; break;}
if(!dict[ch].count(t)){cout << line << endl; bug_flag = 1; break;}
nameache.pop();
t = dict[ch][t];
}
if(bug_flag) continue;
ch = nameache.top(); nameache.pop();
if(!d2.count(ch)){cout << line << endl; bug_flag = 1; continue;}
if(t >= d2[ch]) {cout << line << endl; bug_flag = 1; continue;}
left = t;
chleft = ch;
i = pos + 1;
num = 0;
if(s[i] >= '0' && s[i] <= '9'){
while(s[i]!='\0'){
num *= 10;
num += s[i] - '0';
++i;
}
dict[chleft][left] = num;
continue;
}
while(s[i] != ']'){
if(isalpha(s[i])) {
if(!d2.count(s[i])) {cout << line << endl; bug_flag = 1; break;}
nameache.push(s[i]);
}
else if(s[i] == '[') {i++;continue;}
else if(s[i] >= '0' && s[i] <= '9'){
num *= 10;
num += s[i] - '0';
}
i++;
}
if(bug_flag) continue;
t = num;
while(!nameache.empty()){
ch = nameache.top();
if(!d2.count(ch)){cout << line << endl; bug_flag = 1; break;}
if(t >= d2[ch]) {cout << line << endl; bug_flag = 1; break;}
if(!dict[ch].count(t)){cout << line << endl; bug_flag = 1; break;}
nameache.pop();
t = dict[ch][t];
}
if(!bug_flag)
dict[chleft][left] = t;
}
}
return 0;
}