算法竞赛入门经典(UVA之路)

dalao必备开头

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define sf scanf

#define pf printf

#define pi 2*acos(0.0)

//再加一份vector的输入典范

//感觉输入单词就像是二维数组,没错,其实每一个元素都是一个单词

#include<bits/stdc++.h>
using namespace std;
vector<string> a[1000];
int main()
{
string code;
string buffer;
int count1=0;
freopen(“in.txt”,”r”,stdin);
while(cin>>code)
{
stringstream ppd(code);
while(ppd>>buffer)
{
a[count1].push_back(buffer);
}
count1++;
}
for(int i=0;i<count1;i++)
{
for(int j=0;j<a[i].size();j++)
{
cout<<a[i][j]<<endl;
}
cout<<endl;
}
}

//更为简单的方式,甚至还可以vector[i][j].size()….比较强啊

#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<string> dict[1000];
freopen(“in.txt”,”r”,stdin);
string str;
int key=0;
while(cin>>str)
{
dict[key].push_back(str);
key++;
}
for(int i=0;i<key;i++)
{
for(int j=0;j<dict[i].size();j++)
{
cout<<dict[i][j]<<” “;
}
cout<<endl;
}
}

//第二种是map,很显然,map的insert显得更为方便,但是貌似map会自动进行排序,而且会消除重复的元素

#include<bits/stdc++.h>
using namespace std;
vector<string> a[1000];
set<string> b;
int main()
{
string code;
string buffer;
freopen(“in.txt”,”r”,stdin);
while(cin>>code)
{
stringstream ppd(code);//stringstream可以过滤空格
while(ppd>>buffer)
{
b.insert(buffer);
}
}
/*for(int i=0;i<count1;i++)
{
for(int j=0;j<a[i].size();j++)
{
cout<<a[i][j]<<endl;
}
cout<<endl;
}*/
for(set<string>::iterator it=b.begin();it!=b.end();it++)
{
cout<<*it<<endl;
}
}

//第三种就是所推荐的map了,map算是最方便的了,直接it->second

#include<bits/stdc++.h>
using namespace std;
vector<string> a[1000];
map<int,string> b;
int main()
{
string code[10000];
string buffer;
int count1=0;
freopen(“in.txt”,”r”,stdin);
while(cin>>code[count1])
{
stringstream ppd(code[count1]);//stringstream可以过滤空格
while(ppd>>buffer)
b[count1]=buffer;
count1++;
}
for(map<int,string>::iterator it=b.begin();it!=b.end();it++)
{
cout<<it->second<<endl;
}
}

//好像这样也行

#include<bits/stdc++.h>
using namespace std;
vector<string> a[1000];
map<int,string> b;
int main()
{
string code[10000];
string buffer;
int count1=0;
freopen(“in.txt”,”r”,stdin);
while(cin>>code[count1])
{
/*stringstream ppd(code[count1]);//stringstream可以过滤空格
while(ppd>>buffer)*/
b[count1]=code[count1];
count1++;
}
for(map<int,string>::iterator it=b.begin();it!=b.end();it++)
{
cout<<it->second<<endl;
}
}

//make_pair看起来并没有什么区别

#include<bits/stdc++.h>
using namespace std;
vector<string> a[1000];
map<int,string> b;
int main()
{
string code[10000];
string buffer;
int count1=0;
freopen(“in.txt”,”r”,stdin);
while(cin>>code[count1])
{
/*stringstream ppd(code[count1]);//stringstream可以过滤空格
while(ppd>>buffer)*/
b.insert(make_pair(count1,code[count1]));
count1++;
}
for(map<int,string>::iterator it=b.begin();it!=b.end();it++)
{
cout<<it->second<<endl;
}
}

 

A – Score

UVA – 1585 

//附个人辣鸡代码,一发a的

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
int a;
cin>>a;
char x[1000];
int flag=1;
int sum;
while(a–)
{
flag=1;
sum=0;
scanf(“%s”,x);
int ppt=0;
for(int i=0;i<strlen(x);i++)
{
if(x[i]==’O’)
{
ppt++;
sum+=ppt;
flag=1;
}
if(x[i]==’X’)
{
//flag=0;
ppt=0;
}

}
cout<<sum<<endl;
}

}

C – Andy’s First Dictionary

UVA – 10815

//好吧,有点弄懂了

#include<iostream>
#include<cctype>
#include<set>
#include<string>
#include<sstream>
using namespace std;
set<string> dict;
int main ()
{
string s,buf;

freopen(“in.txt”,”r”,stdin);//这种输入方式直接输入到文件尾,但是在oj上不用写
//freopen(“out.txt”,”w”,stdout);
while (cin >> s)
{
int i;
for(i=0;i<s.size();i++)
{
if(isalpha(s[i])) //判断是否为字母 类似的函数还有isupper islower isdigit
s[i]=tolower(s[i]); //将字母转化成小写 类似的还有toupper
else s[i]=’ ‘; //此处将不是字母的都转化为空格 而stringstream会滤掉空格 最后只会剩下单词
}
stringstream ss(s);
//ss>>buf; 不能写成这样 因为有可能在单词前面有标点 而在上面被转化成了空格就无法读入单词,还是应该用while将流中的东西读干净~
while(ss >> buf)//有可能有空格,就读入不到流中,但是空格也是必须的,为了区分单词
dict.insert(buf); //插入到set中 set保证里面的元素不重复
}
set<string>::iterator it; //此处为STL中的迭代器。。 要记住用法.begin() .end()
for(it=dict.begin();it!=dict.end();it++)
cout << *it << endl;
return 0;
}

D – Ananagrams

UVA – 156

//只想说确实是一道经典的关于map的题

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<vector>
using namespace std;
vector<string> words;
map<string,int> cnt;
string rept(string a)
{
for(int i=0;i<a.length();i++)
a[i]=tolower(a[i]);
sort(a.begin(),a.end());
return a;
}
int main()
{
string s;
while(cin>>s)
{
string r;
if(s[0]==’#’)
break;
words.push_back(s);
r=rept(s);
if(cnt.count(r)==0)
cnt[r]=0;
cnt[r]++;
}
vector<string> ans;
for(int i=0;i<words.size();i++)
{
if(cnt[rept(words[i])]==1)
ans.push_back(words[i]);
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
cout<<ans[i]<<endl;
}
}

E – Compound Words

UVA – 10391 

//又是一道经典的map题,map作为高级数组,配合vector等使用确实威力无穷,但是灵活得使用也是不容易的

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#define INF 1E9
using namespace std;
map<string,bool>hash1;
string s[150000];
int main()
{
int i,j;
int cnt=0;
//freopen(“in.txt”,”r”,stdin);
while(cin>>s[cnt])
{
hash1[s[cnt]]=1;
cnt++;
}
string a,b;
for(i=0;i<cnt;i++)
for(j=0;j<s[i].size()-1;j++)
{
a=s[i].substr(0,j+1);
if(!hash1[a])continue;//如果是0的话,就终止这次循环
b=s[i].substr(j+1);
if(!hash1[b])continue;//同理
cout<<s[i]<<endl;
break;
}
return 0;
}

C – Throwing cards away I

UVA – 10935 

//双向队列,感觉就像2b一样,双向队列确实很方便

#include<bits/stdc++.h>
using namespace std;
int main()
{
deque<int> q;
int k;
while(cin>>k&&k)
{
q.clear();
cout<<“Discarded cards:”;
for(int i=0;i<k;i++)
q.push_back(i+1);
for(int i=0;i+1<k;i++)
{
if(i) printf(“,”);
cout<<” “<<q.front();
q.pop_front();
q.push_back(q.front());
q.pop_front();

}
cout<<endl;
cout<<“Remaining card: “;
cout<<q.front()<<endl;
}
}

F – Symmetry

UVA – 1595

//一个很有意思的题目,找一个竖直的对称轴,将坐标点是否被坐标轴分成两半

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int x[N], y[N], n, mx;
int main()
{
int cas, lx, rx, a, i;
scanf(“%d”, &cas);
while(cas–)
{
lx = rx = 0;
scanf(“%d”, &n);
int a1=0;
int a2=10000;
for(i = 0; i < n; ++i)
{
scanf(“%d%d”, &a, &y[i]);//a是x,y是y
x[i] = a * 2;
if(x[i]>a1)
a1=x[i];
if(x[i]<a2)
a2=x[i];
}
mx=(a1+a2)/2;
int flag=0;
for(i = 0; i < n; ++i)
for(int j=0;j<n;j++)
{
if(y[i] == y[j] && x[i] + x[j] == 2 * mx)
flag++;

}

if(flag==n) puts(“YES”);
else puts(“NO”);
}
}

B – Ducci Sequence

UVA – 1594 

//很水的一道题,笑!,之前还以为很难。。。。,但很大一部分原因是数据水吧

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
int n;
cin>>n;
while(n–)
{
int k;
cin>>k;
for(int i=0;i<k;i++)
cin>>a[i];
int turn=0;
while(1){

int flag=0;
int pp=a[0];//就这里需要注意一下,因为a[0]已经改变了
for(int i=0;i<k;i++)
{
if(i<k-1)
a[i]=abs(a[i]-a[i+1]);
else
a[k-1]=abs(a[k-1]-pp);
}
for(int j=0;j<k;j++)
{
if(a[j]==0)
flag++;
}
if(flag==k)
{
cout<<“ZERO”<<endl;
break;
}
turn++;
if(turn==200)
{
cout<<“LOOP”<<endl;
break;
}
}
}
}

//vector版

#include<bits/stdc++.h>
using namespace std;
//int a[1000000];
int main()
{
vector<int> a;
int n;
cin>>n;
while(n–)
{
a.clear();
int k;
cin>>k;
int kp;
for(int i=0;i<k;i++)
{
cin>>kp;
a.push_back(kp);
}
int turn=0;
while(1){

int flag=0;
int pp=a[0];
for(int i=0;i<k;i++)
{
if(i<k-1)
a[i]=abs(a[i]-a[i+1]);
else
a[k-1]=abs(a[k-1]-pp);
}
for(int j=0;j<k;j++)
{
if(a[j]==0)
flag++;
}
if(flag==k)
{
cout<<“ZERO”<<endl;
break;
}
turn++;
if(turn==200)
{
cout<<“LOOP”<<endl;
break;
}
}
}
}

D – Foreign Exchange

UVA – 10763

//给你N组关系,每组关系是a,b,最后问你所有的a,b出现的次数和所有的b,a出现的此时是否全部都一样。

//放到邻接矩阵中即可,最后判断矩阵是否全为0

#include<bits/stdc++.h>
using namespace std;
int x[10000][10000];
int main()
{
int k;
int p1,p2;
while(cin>>k&&k)
{
memset(x,0,sizeof(x));
int flag=0;
for(int i=0;i<k;i++)
{
cin>>p1>>p2;
x[p1][p2]++;
x[p2][p1]–;
}
for(int i=0;i<1000;i++)
{
for(int j=0;j<1000;j++)
{
if(x[i][j]!=0)
{
cout<<“NO”<<endl;
flag=1;
goto end;
}

}
}
end:;
if(flag==0)
cout<<“YES”<<endl;
}
}

A – Alignment of Code

UVA – 1593

//关于这一题的输入

#include<bits/stdc++.h>
using namespace std;
int main()
{
string time;
vector<string> dict[10000];
string bb;
string code;
freopen(“in.txt”,”r”,stdin);
int key=0;
while(getline(cin,code))//getline是输入了整个句子,但应该是一行一行输入
{
stringstream ss(code);//这个stringstream就是把输入的变成一个个单词,且过滤了空格
while(ss>>time)//这个time就是一个单词
{
dict[key].push_back(time);//push_back自动往每一行后面自动添加
//key++ 就会变成多少单词就有多少行了
}
key++;//行数加1
}
//cout<<dict<<dict[1][0]<<endl;
cout<<key<<endl;
for(int i=0;i<key;i++)
{
for(int j=0;j<dict[i].size();j++)
{
cout<<dict[i][j]<<” “;
}
cout<<endl;
}
}

A – Alignment of Code

UVA – 1593 

//一道可以从中学到很多东西的题目,虽然此题年代有点久远了,vector的熟练运用吧

#include<bits/stdc++.h>
using namespace std;
void shuchu(string s,int len)
{
cout<<s;
for(int i=0;i<=len-s.size();i++)//这里被坑了一次,是<=,可能是计算上出现了失误
{
cout<<‘ ‘;
}
}
int main()
{
int length[10000];
vector<string> dict[10000];//相当于一个二维数组
string s1,s2;
int count1=0;
int count2=0;
//freopen(“in.txt”,”r”,stdin);
while(getline(cin,s1))//getline保证每次只输入一行
{
stringstream ss(s1);
while(ss>>s2)
{
length[count1]=max(length[count1],(int)s2.size());//至于这个为什么要强转成int,就不是很明白了
count1++;
dict[count2].push_back(s2);
}
count2++;//行每次累加,getline每次读入一行
count1=0;//列每次都要清空,且都要比较,比较出最大的length[count1]
}
for(int i=0;i<count2;i++)
{
int j=0;//在这里初始化也可以,因为要输出cout<<dict[i][j]<<endl;
for(;j<dict[i].size()-1;j++)
{
shuchu(dict[i][j],length[j]);
}
cout<<dict[i][j]<<endl;//对最后一行进行特殊处理,最后一列的后面没有空格
}
}

迷宫的最短路径(bfs用队列做,小白书上的一道题)

10 10
#S######.#
……#..#
.#.##.##.#
.#……..
##.##.####
….#….#
.#######.#
….#…..
.####.###.
….#…G#

输入如上数据,迷宫长为10,宽为10,

S为起点,G为终点

需要寻找一条最短路径从S到G,并求出最短路径,因为bfs搜索路径的特性,如下所示,100表示墙

100 0 100 100 100 100 100 100 13 100
2 1 2 3 4 5 100 13 12 100
3 100 3 100 100 6 100 100 11 100
4 100 4 5 6 7 8 9 10 11
100 100 5 100 100 8 100 100 100 100
8 7 6 7 100 9 10 11 12 100
9 100 100 100 100 100 100 100 13 100
10 11 12 13 100 17 16 15 14 15
11 100 100 100 100 18 100 100 100 16
12 13 14 15 100 19 20 21 22 100

可以得出最短路径为22

#include<bits/stdc++.h>
#define inf 100
using namespace std;
int d[10000][10000];
char map1[10000][10000];
int m,n;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
typedef pair<int,int> P;//常见套路
queue<P> pp;
int sx,sy,gx,gy;
int bfs()
{
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
d[i][j]=inf;
}
}
pp.push(P(sx,sy));
d[sx][sy]=0;
while(pp.size())
{
P ppp=pp.front();
pp.pop();
if(ppp.first==gx&&ppp.second==gy)
break;
for(int i=0;i<4;i++)
{
int nx=ppp.first+dx[i];
int ny=ppp.second+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&map1[nx][ny]!=’#’&&d[nx][ny]==inf)
{
pp.push(P(nx,ny));
d[nx][ny]=d[ppp.first][ppp.second]+1;
}
}
}

return d[gx][gy];
}
int main()
{
freopen(“inn.txt”,”r”,stdin);
cin>>m>>n;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>map1[i][j];
if(map1[i][j]==’S’)
{
sx=i;
sy=j;
}
if(map1[i][j]==’G’)
{
gx=i;
gy=j;
}
}
}
cout<<bfs()<<endl;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cout<<d[i][j]<<” “;
}
cout<<endl;
}

}

————————————————————————————————————————

poj3984
//一道bfs题,求出最短路径,所经过的点,运用了pair,双向队列,队列
//队列里的每一个元素都是一个双向队列,双向队列的每一个元素都是一个pair,层层嵌套,目不暇接
————————————————————————————————————————
#include<bits/stdc++.h>
using namespace std;
int map1[6][6];
typedef pair<int,int> ss;//直接用pair,也可以用int x,int y的吧,方便多了
typedef deque<ss>TnT;//有两个属性x和y
int vis[6][6] , dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};
TnT bfs(int x , int y) {
memset(vis , 0 , sizeof(vis));
TnT gg;
ss gl;
gl.first = x , gl.second = y;
vis[x][y] = 1;
gg.push_back(gl);//双向队列里只存了一个pair
queue<TnT>q;//q是级别最高的
q.push(gg);//push了一个双向队列
int count1=0;
TnT sg;
while(!q.empty()) {
TnT ml = q.front();//取队头,队头就是一个双向队列,是从0,0 1,0开始
TnT pg=ml;
/* while(pg.size())
{
ss sl = pg.front();
pg.pop_front();
cout << “*” << sl.first<< “, ” << sl.second<< “*” <<count1<<endl;
}
count1++;*/
//cout<<q.size()<<“sb1 “<<count1++<<endl;
// cout<<ml.size()<<“sb2 “<<count1++<<endl;
ss xg = ml.back();//取队尾,在第一次队头就是队尾
if(xg.first == 4 && xg.second == 4) {
return ml;
}
for(int i = 0 ; i < 4 ; i++) {
TnT sg = ml;//更新
ss xl = ml.back();//从后面开始
xl.first += dr[i][0];
xl.second += dr[i][1];
if(xl.first >= 0 && xl.first < 5 && xl.second >= 0 && xl.second < 5 && !map1[xl.first][xl.second] && !vis[xl.first][xl.second])
{
vis[xl.first][xl.second] = 1;//标记
sg.push_back(xl);//sg是一个双向队列
q.push(sg);//q是一个队列,但是里面的每一个元素都是一个双向队列
}
//cout<<sg.size()<<“ggg”<<++count1<<endl;

}
// cout<<sg.size()<<“ggg”<<endl;

q.pop();//把0,0pop
}
}
int main()
{
freopen(“inn.txt”,”r”,stdin);
for(int i = 0 ; i < 5 ; i++) {
for(int j = 0 ; j < 5 ; j++) {
cin >> map1[i][j];
}
}
TnT q = bfs(0 , 0);
while(!q.empty()) {
ss sl = q.front();
q.pop_front();
cout << “(” << sl.first<< “, ” << sl.second<< “)” << endl;
}
return 0;
}

23 thoughts on “算法竞赛入门经典(UVA之路)

发表评论