说明
题目选自《算法竞赛入门经典》，题目先后顺序和它们在这本书里出现的顺序相同。
10340
字符串子序列：从s中删除一些字符，能否得到字符串t，如果是，输出Yes，否则，输出No
#include <iostream>
int main(int argc, char** argv) {
std::string s, t;
int sb,se,tb,te;
while(std::cin>>t>>s){
sb=0;
se=s.size()-1;
tb=0;
te=t.size()-1;
while(tb<te){
while(sb<s.size() && s[sb] != t[tb])
++sb;
while(se>=0 && s[se] != t[te])
--se;
if(sb==s.size() || se<0 || sb >= se){
std::cout<<"No"<<std::endl;
break;
}else{
++sb;
--se;
++tb;
--te;
}
}
if(tb==te){
while(sb<s.size() && s[sb] != t[tb])
++sb;
if(sb==s.size() || sb > se)
std::cout<<"No"<<std::endl;
else
std::cout<<"Yes"<<std::endl;
}else if(tb>te)
std::cout<<"Yes"<<std::endl;
}
return 0;
}
202
循环小数
给定一个数的分子和分母，输出它的循环小数及循环小数的长度
#include <iostream>
#include <vector>
#include <map>
int main(int argc, char** argv) {
int numerator, denominator;
while(std::cin>>numerator>>denominator){
std::vector<int> decimal;
int itger=numerator/denominator;
int remainder=(numerator%denominator)*10;
std::map<int, int> rem2idx;
int t;
int idx=0;
while(true){
rem2idx[remainder]=idx++;
t=remainder/denominator;
decimal.push_back(t);
remainder=(remainder%denominator)*10;
if(rem2idx.find(remainder) != rem2idx.end())
break;
}
std::cout<<numerator<<"/"<<denominator<<" = "<<itger<<"."<<std::flush;
if(rem2idx[remainder]>=50){
int i;
for(i=0; i<50; ++i)
std::cout<<decimal[i]<<std::flush;
std::cout<<"..."<<std::endl;
}else{
int i;
for(i=0; i<rem2idx[remainder]; ++i)
std::cout<<decimal[i]<<std::flush;
std::cout<<"("<<std::flush;
for(; i<decimal.size() && i<50; ++i)
std::cout<<decimal[i]<<std::flush;
if(i<decimal.size() && i==50)
std::cout<<"..."<<std::flush;
std::cout<<")"<<std::endl;
}
std::cout<<" "<<decimal.size()-rem2idx[remainder]
<<" = number of digits in repeating cycle"<<std::endl;
std::cout<<std::endl;
}
return 0;
}
679小球下落
一棵完全二叉树，节点按广度遍历的顺序编号1,2,...,2^n-1其中n是层数，根节点是第一层。每个节点有一个开关，开关开，小球流向右子树，否则就流向左子树。小球每落到一个节点上后，该节点的开关状态就发生改变。最开始，所有开关都是关的，求第n个球最终位置。
#include <iostream>
int pow2(int n){
if(n<1)
return -1;
int rv=1;
while(n--)
rv=rv*2;
return rv;
}
int main(int argc, char** argv) {
int l;
while(true){
std::cin>>l;
if(l==-1)
break;
int d, n;
while(l--){
std::cin>>d>>n;
int r=pow2(d-1);
int incre=r/2;
while(incre){
if(n%2 == 0)
r+=incre;
n=(n+1)/2;
incre=incre/2;
}
std::cout<<r<<std::endl;
}
}
return 0;
}
572油田
求联通块个数，上下左右还有斜着的@都算同一块
其实就是用递归实现，符号说明：
0----*或者已经遍历过的@
@----没有遍历过
依次遍历图，遇到@，说明找到新块，于是将block增1，然后，递归将和它相连的@变成0
#include <iostream>
static int a[100][100];
void dfs(int (&a)[100][100] , int r , int c , const int m, const int n){
if(r<0 || r>=m || c<0 ||c>=n )
return;
if(a[r][c] != -1)
return;
a[r][c]=0;
for(int i=-1 ; i <=1 ; ++i)
for(int j=-1 ; j<=1 ; ++j)
if(i || j)
dfs(a, r+i , c+j, m , n);
}
int main(int argc, char** argv) {
int m , n;
char temp;
while(true){
std::cin>>m>>n;
if(m==0)
break;
for(int i=0; i <m; ++i)
for(int j=0; j<n; ++j){
std::cin>>temp;
if(temp=='*')
a[i][j]=0;
else
a[i][j]=-1;
}
int block=0;
for(int i=0; i<m ;++i)
for(int j=0 ; j<n ; ++j)
if(a[i][j]==-1){
++block;
dfs(a,i,j,m,n);
}
std::cout<<block<<std::endl;
}
return 0;
}
1599理想路径
理想路径：求出从节点1到节点n的最短路径，如果有多个解，输出边的字典序最小的那个。
1）错误的代码：
节点和边的数量在10^5数量级，显然不能用O(n*n)的时间和空间复杂度了，尤其是空间。。。
采用vector<multimap<int,int> > G, G的小标i表示节点i，G[i]是个multimap，键是color，值是和i相邻的节点。
之所以采用multimap，是因为想给这些颜色排个序（后面证明这个想法并不能实现按字典排序T_T），尽管查找单个节点花费O(logn)，但遍历整个节点并非是O(nlogn)，而是O(n)，因此采用map并不会带来时间上的开销。
length记录起点到每一个节点的长度，-1表示还没遍历到
father记录最短路径下的父节点
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <utility>
void print_path(std::vector<int> &father, int n){
if(n==0){
std::cout<<1<<std::flush;
return;
}
print_path(father, father[n]);
std::cout<<n+1<<std::flush;
}
int main()
{
int n,m;
int node1, node2, color;
while(std::cin>>n>>m){
if(n==0)
break;
std::vector<int> father(n,-1);
std::vector<int> length(n,-1);
std::vector<std::multimap<int, int> > G(n);
int p=m;
while(p--){
std::cin>>node1>>node2>>color;
G[node1-1].insert(std::make_pair(color, node2-1));
G[node2-1].insert(std::make_pair(color, node1-1));
//G[node1-1][color]=node2-1;
//G[node2-1][color]=node1-1;
}
std::deque<int> d;
d.push_back(0);
length[0]=0;
int curr;
while(!d.empty()){
curr=d.front();
d.pop_front();
for(auto &s : G[curr]){
if(length[s.second]==-1){
d.push_back(s.second);
length[s.second]=length[curr]+1;
father[s.second]=curr;
}
}
std::cout<<std::endl;
}
std::cout<<length[n-1]<<std::endl;
print_path(father, n-1);
}
return 0;
}
如果不按字典序，或者说，不用处理重复元素（大多数都是这两种情况，这个题是有点。。。非主流。。。），那么上述代码是对的，按字典序后，尽管使用multimap存储相邻节点，仍然不能保证正确，例如测试样例
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
对于节点1，边121和311颜色相同，但根据广度优先的原理，边121先被遍历，这样，首先到达4的路径就是1->2->4，边的字典序是14，然而，正确的解确是1->3->4，字典序是13. 根本原因就是它不能正确处理颜色相同的情况。
尽管不正确，但仍能学到广度优先搜索的方法，以及stl中一些容器的使用。
2）改进后的解法
可以考虑倒着进行bfs，也就是说，从终点开始，通过bfs寻找它到起点的最短路径。为了让结果取字典序，除了判断节点是否被遍历过外，还要判断如果遍历过节点最短路径和当前计算的最短路径相同，则判断二者字典序，然后选择字典序最小的那个
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <utility>
void print_path(std::vector<int> &child, std::vector<int> &color,int n){
int p=0;
std::cout<<color[p]<<std::flush;
p=child[p];
while(p != n-1){
std::cout<<" "<<color[p]<<std::flush;
p=child[p];
}
std::cout<<std::endl;
return;
}
int main()
{
int n,m;
int node1, node2, color;
while(std::cin>>n>>m){
if(n==0)
break;
std::vector<int> child(n,-1);
std::vector<int> length(n,-1);
std::vector<int> vcolor(n,-1);
std::vector<std::multimap<int, int> > G(n);
int p=m;
while(p--){
std::cin>>node1>>node2>>color;
G[node1-1].insert(std::make_pair(color, node2-1));
G[node2-1].insert(std::make_pair(color, node1-1));
}
std::deque<int> d;
d.push_back(n-1);
length[n-1]=0;
int curr;
while(!d.empty()){
curr=d.front();
d.pop_front();
for(auto &s : G[curr]){
if(length[s.second]==-1){
d.push_back(s.second);
length[s.second]=length[curr]+1;
child[s.second]=curr;
vcolor[s.second]=s.first;
}else if(length[s.second]==length[curr]+1){
if(s.first<vcolor[s.second]){
child[s.second]=curr;
vcolor[s.second]=s.first;
}
}
}
}
std::cout<<length[0]<<std::endl;
print_path(child, vcolor, n);
}
return 0;
}
UVa725
输入正整数n，输出所有abcde/efghil=n的表达式，其中abcdefghil是0到9的一个排列，有前导0, n 的范围[2,79].
暴力解，一共枚举A(10,5)中情况
通过dfs的方式进行字典序搜索，迭代次数是109876，当然，暴力点的话直接五层for循环，迭代次数10^5，也是可以解决问题的。
注意输出格式：当输入0的时候，表示结束，没有任何空格
还有一个坑爹的格式要求是：最后一个有效输出后没有空格，也就是输入0之前的那个输入不产生空格
#include <iostream>
#include <vector>
#include <string.h>
//const int flag=0^1^2^3^4^5^6^7^8^9;//bug
int judge(int *a, int v){
int r=0;
for(int i=0 ; i < 5 ; ++i)
r=r*10+a[i];
if(r%v)
return -1;
int u=r/v;
for(int i=5; i< 10 ;++i){
a[i]=u%10;
u=u/10;
}
int aa[10];
memset(aa, -1 , 10*sizeof(int));
for(int i=0 ; i < 10; ++i){
if(aa[a[i]] != -1)
return -1;
else
aa[a[i]]=a[i];
}
return r;
}
bool is_exist(int *a, int k, int n){
for(int i=0 ; i < n ; ++i )
if(a[i]==k)
return true;
return false;
}
int count=0;
void dfs(int a[10] , int n, int v, std::vector<int> &r){
if(n==5){
int j;
if( (j=judge(a, v)) != -1 ){
r.push_back(j);
}
return;
}
for(int i=0; i<10 ;++i){
if(!is_exist( a, i , n )){
a[n]=i;
dfs(a, n+1,v, r);
}
}
}
int main()
{
int a[10];
int v;
bool blank=false;
while(std::cin>>v){
if(v==0)
break;
if(blank)
std::cout<<std::endl;
std::vector<int> r;
dfs(a, 0 , v, r);
if(r.empty())
std::cout<<"There are no solutions for "<<v<<"."<<std::endl;
else{
for(auto &s : r){
std::cout<<s<<" / "<<std::flush;
int div=s/v;
if(div<10000)
std::cout<<0<<std::flush;
std::cout<<s/v<<" = "<<v<<std::endl;
}
}
blank=true;
}
return 0;
}
UVa10976
输入正整数k，找出所有的x>y，满足1/k=1/x+1/y
解法：暴力枚举，枚举y，枚举范围[k+1,2*k]
#include <iostream>
#include <vector>
#include <stdio.h>
int main()
{
int k;
while((scanf("%d", &k))==1){
if(k==0)
break;
std::vector<int> x;
for(int i=k+1 ; i < 2*k+1 ; ++i)
if(i*k%(i-k)==0)
x.push_back(i);
printf("%d\n", x.size());
for(size_t i=0 ; i < x.size() ; ++i){
printf("1/%d = 1/%d + 1/%d\n", k, k*x[i]/(x[i]-k), x[i]);
}
}
return 0;
}
UVa524 素数环
把整数1,2,3,...,n组成一个环，使得相邻数的和都是素数，环从数字1开始。
暴力枚举解决，为了减少枚举量，采用回溯法。
1)一个解法
这个解法并没有ac，出错原因是它的输出没有按字典排序
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
std::vector<int> prim{1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(int *A, int n , int cur){
if(cur==n && std::binary_search(&prim[0], &prim[0]+12, A[n-1]+A[0])){
std::cout<<A[0]<<std::flush;
for(int i=1; i< n ; ++i)
std::cout<<" "<<A[i]<<std::flush;
std::cout<<std::endl;
}else for(int i=cur ; i<n ; ++i ){
if(std::binary_search(&prim[0], &prim[0]+12, A[cur-1]+A[i])){
std::swap(A[cur], A[i]);
dfs(A, n, cur+1);
std::swap(A[cur], A[i]);
}
}
}
int main()
{
FILE *fp;
if((fp=freopen("/home/xmqv/code/c/test.txt", "w", stdout)) == NULL){
std::cout<<"dakaishibai!"<<std::endl;
return 0;
}
int n;
bool blanc=false;
int case_=1;
while(std::cin>>n){
if(n==0)
break;
if(blanc)
std::cout<<std::endl;
std::cout<<"Case "<<case_<<":"<<std::endl;
int *A=new int[n];
for(int i=0 ; i< n ; ++i)
A[i]=i+1;
dfs(A, n , 1);
blanc=true;
++case_;
delete[] A;
}
return 0;
}
2）对上述解法进行改进，使它按字典序输出
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
std::vector<int> prim{1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(int *A, int n , int cur){
if(cur==n && std::binary_search(&prim[0], &prim[0]+12, A[n-1]+A[0])){
std::cout<<A[0]<<std::flush;
for(int i=1; i< n ; ++i)
std::cout<<" "<<A[i]<<std::flush;
std::cout<<std::endl;
}else{
for(int i=cur ; i<n ; ++i ){
std::swap(A[cur], A[i]);
if(std::binary_search(&prim[0], &prim[0]+12, A[cur-1]+A[cur]))
dfs(A, n, cur+1);//假设递归返回后，能够恢复递归前的样子
}
for(int i=cur+1 ; i<n ; ++i)//恢复递归前的样子
std::swap(A[i-1], A[i]);
}
}
int main()
{
/*
FILE *fp;
if((fp=freopen("/home/xmqv/code/c/test.txt", "w", stdout)) == NULL){
std::cout<<"dakaishibai!"<<std::endl;
return 0;
}
*/
int n;
bool blanc=false;
int case_=1;
while(std::cin>>n){
if(n==0)
break;
if(blanc)
std::cout<<std::endl;
std::cout<<"Case "<<case_<<":"<<std::endl;
int *A=new int[n];
for(int i=0 ; i< n ; ++i)
A[i]=i+1;
dfs(A, n , 1);
blanc=true;
++case_;
delete[] A;
}
return 0;
}
3)用一个数组记录是否被用到来进行深度优先搜索：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
std::vector<int> prim{1,2,3,5,7,11,13,17,19,23,29,31};
bool is_prim(int value){
return std::binary_search(&prim[0], &prim[0]+12, value);
}
void dfs(int *A, int *set_, int n , int cur){
if(cur==n && is_prim(A[n-1]+1)){
std::cout<<A[0];
for(int i=1; i<n ; ++i)
std::cout<<" "<<A[i];
std::cout<<std::endl;
}else for(int i=2 ; i<=n ; ++i){
if(set_[i] && is_prim(i+A[cur-1])){
A[cur]=i;
set_[i]=0;
dfs(A, set_, n , cur+1);
set_[i]=1;
}
}
}
int main()
{
//FILE *fp;
//if((fp=freopen("/home/xmqv/code/c/test.txt", "w", stdout)) == NULL)
//std::cout<<"dakaishibai!\n"<<std::endl;
int A[17];
A[0]=1;
int set_[17];
int n;
bool blanc=false;
int case_=1;
while(std::cin>>n){
if(n==0)
break;
if(blanc)
std::cout<<std::endl;
std::cout<<"Case "<<case_<<":"<<std::endl;
for(int i=0 ; i< n+1 ; ++i)
set_[i]=1;
dfs(A, set_, n , 1);
blanc=true;
++case_;
}
return 0;
}
UVa124 困难的串
题目
对于一个字符串，如果存在相同且相邻的两个子串，则该字符串是“容易的串”，否则就叫困难串。对于基数是n的字符串，字符由A，B，... （n个字符）组成，给定n和L，求基数为n的字符串中第L大的困难串。
解法
暴力解，从第一个困难串开始，根据当前困难串，计算下一个困难串，一直计算到第L大的困难串。
其实这个也是深度优先搜索过程，跟之前有点不同的是，一旦搜索到想要的答案，就立刻终止。。。
#include <iostream>
#include <stdio.h>
bool is_hard(const int *A, const int n, const int cur){
if(A==NULL || cur>=n)
return false;
for(int i=1; 2*i<=cur+1 ; ++i){
int j;
for(j=0; j<i ; ++j)
if(A[cur-j] != A[cur-i-j])
break;
if(j==i)
return false;
}
return true;
}
void print_hard(int *A, int cur){
int i;
for(i=0; i<cur; ++i){
if(i && i%4==0){
if(i%64==0)
std::cout<<std::endl;
else
std::cout<<" "<<std::flush;
}
std::cout<<(char)('A'-1+(char)A[i])<<std::flush;
}
std::cout<<std::endl;
std::cout<<cur<<std::endl;
}
bool dfs(int *A, const int n, const int cur, int *tot, const int count, const int l){
if( A==NULL || cur>=n || count<=0 || l<1)
return true;
bool ok=true;
if(cur==0){
for(int i=1; i<l+1 && ok; ++i){
A[cur]=i;
++(*tot);
if(*tot>=count){
print_hard(A, cur+1);
return false;
}
ok=dfs(A, n, cur+1, tot, count, l);
}
}else{
for(int i=1; i<l+1 && ok; ++i){
A[cur]=i;
if(is_hard(A, n, cur)){
++(*tot);
if(*tot>=count){
print_hard(A,cur+1);
return false;
}
ok=dfs(A, n, cur+1, tot, count, l);
}
}
}
return ok;
}
int main()
{
int n, l;
//bool blanc=false;
int A[81];
/*
FILE *fp;
if((fp=freopen("/home/xmqv/code/output.tex", "w", stdout))==NULL)
std::cout<<"can't open testfile!"<<std::endl;
*/
while(std::cin>>n>>l){
if(n==0)
break;
//if(blanc)
//std::cout<<std::endl;
for(int i=0; i<81; ++i)
A[i]=-1;
int tot=0;
bool ok=dfs(A, 80, 0, &tot, n, l);
if(ok)
std::cout<<std::endl;
//blanc=true;
}
return 0;
}
UVa140 Bandwidth
解法：深度优先搜索+剪枝
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
void dfs(char A[], int n, int cur, int &min_, std::map<char, std::set<char> > &G, std::vector<char> &result_){
if(A==NULL || n<1 || cur>n || cur<0 || min_<1 || G.empty())
return;
if(cur==n){
int max_=-1;
for(int i=0; i< cur ; ++i)
for(int j=i+1; j <cur ; ++j)
if(G[A[i]].find(A[j]) != G[A[i]].end() )
max_=max_<(j-i)?(j-i):max_;
if(min_>max_)
for(int i=0; i<cur ; ++i)
result_[i]=A[i];
min_=max_;
return;
}
bool ok;
for(int i=cur ; i<n; ++i){
std::swap(A[cur], A[i]);
/*
if(G[A[cur]].size() >= min_)
continue;
*/
ok=true;
for(int j=0; j<cur ; ++j )
if( G[A[cur]].find(A[j]) != G[A[cur]].end())
if(min_<=cur-j){
ok=false;
break;
}
if(ok)
dfs(A, n, cur+1, min_, G, result_);
}
for(int i=cur+1; i< n ; ++i)
std::swap(A[i-1], A[i]);
}
int main()
{
std::string s;
while(std::cin>>s){
if(s==std::string("#")){
break;
}
std::map<char, std::set<char> > G;
for(int i=0; i<s.size() ; ++i){
char c=s[i];
std::set<char> &temp=G[c];
i=i+2;
for(; i<s.size() && s[i] != ';' ; ++i){
temp.insert(s[i]);
G[s[i]].insert(c);
}
}
char A[8];
char *p=A;
for( auto &s:G)
*(p++)=s.first;
int min_=G.size();
std::vector<char> result_(8);
dfs(A, min_, 0, min_, G, result_);
if(min_==G.size())
min_=0;
for(int i=0; i<G.size(); ++i)
std::cout<<result_[i]<<" "<<std::flush;
std::cout<<"-> "<<min_<<std::endl;
}
return 0;
}
