說(shuō)明
題目選自《算法競(jìng)賽入門(mén)經(jīng)典》山上，題目先后順序和它們?cè)谶@本書(shū)里出現(xiàn)的順序相同手报。
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
循環(huán)小數(shù)
給定一個(gè)數(shù)的分子和分母盏档，輸出它的循環(huán)小數(shù)及循環(huán)小數(shù)的長(zhǎng)度
#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小球下落
一棵完全二叉樹(shù)凶掰，節(jié)點(diǎn)按廣度遍歷的順序編號(hào)1,2,...,2^n-1其中n是層數(shù)，根節(jié)點(diǎn)是第一層蜈亩。每個(gè)節(jié)點(diǎn)有一個(gè)開(kāi)關(guān)懦窘，開(kāi)關(guān)開(kāi)，小球流向右子樹(shù)稚配，否則就流向左子樹(shù)畅涂。小球每落到一個(gè)節(jié)點(diǎn)上后，該節(jié)點(diǎn)的開(kāi)關(guān)狀態(tài)就發(fā)生改變道川。最開(kāi)始午衰，所有開(kāi)關(guān)都是關(guān)的，求第n個(gè)球最終位置冒萄。
#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油田
求聯(lián)通塊個(gè)數(shù)臊岸，上下左右還有斜著的@都算同一塊
其實(shí)就是用遞歸實(shí)現(xiàn)，符號(hào)說(shuō)明：
0----*或者已經(jīng)遍歷過(guò)的@
@----沒(méi)有遍歷過(guò)
依次遍歷圖尊流，遇到@帅戒，說(shuō)明找到新塊，于是將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理想路徑
理想路徑：求出從節(jié)點(diǎn)1到節(jié)點(diǎn)n的最短路徑，如果有多個(gè)解迎献，輸出邊的字典序最小的那個(gè)瞎访。
1）錯(cuò)誤的代碼：
節(jié)點(diǎn)和邊的數(shù)量在10^5數(shù)量級(jí)，顯然不能用O(n*n)的時(shí)間和空間復(fù)雜度了忿晕，尤其是空間装诡。。践盼。
采用vector<multimap<int,int> > G, G的小標(biāo)i表示節(jié)點(diǎn)i鸦采，G[i]是個(gè)multimap，鍵是color咕幻，值是和i相鄰的節(jié)點(diǎn)渔伯。
之所以采用multimap，是因?yàn)橄虢o這些顏色排個(gè)序（后面證明這個(gè)想法并不能實(shí)現(xiàn)按字典排序T_T）肄程，盡管查找單個(gè)節(jié)點(diǎn)花費(fèi)O(logn)锣吼，但遍歷整個(gè)節(jié)點(diǎn)并非是O(nlogn)，而是O(n)蓝厌，因此采用map并不會(huì)帶來(lái)時(shí)間上的開(kāi)銷(xiāo)玄叠。
length記錄起點(diǎn)到每一個(gè)節(jié)點(diǎn)的長(zhǎng)度，-1表示還沒(méi)遍歷到
father記錄最短路徑下的父節(jié)點(diǎn)
#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;
}
如果不按字典序拓提，或者說(shuō)读恃，不用處理重復(fù)元素（大多數(shù)都是這兩種情況，這個(gè)題是有點(diǎn)代态。寺惫。。非主流蹦疑。西雀。。）歉摧，那么上述代碼是對(duì)的艇肴，按字典序后，盡管使用multimap存儲(chǔ)相鄰節(jié)點(diǎn)叁温，仍然不能保證正確豆挽，例如測(cè)試樣例
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
對(duì)于節(jié)點(diǎn)1，邊121和311顏色相同券盅，但根據(jù)廣度優(yōu)先的原理帮哈，邊121先被遍歷，這樣锰镀，首先到達(dá)4的路徑就是1->2->4娘侍，邊的字典序是14，然而泳炉，正確的解確是1->3->4憾筏，字典序是13. 根本原因就是它不能正確處理顏色相同的情況。
盡管不正確花鹅，但仍能學(xué)到廣度優(yōu)先搜索的方法氧腰，以及stl中一些容器的使用。
2）改進(jìn)后的解法
可以考慮倒著進(jìn)行bfs，也就是說(shuō)古拴，從終點(diǎn)開(kāi)始箩帚，通過(guò)bfs尋找它到起點(diǎn)的最短路徑。為了讓結(jié)果取字典序黄痪，除了判斷節(jié)點(diǎn)是否被遍歷過(guò)外紧帕，還要判斷如果遍歷過(guò)節(jié)點(diǎn)最短路徑和當(dāng)前計(jì)算的最短路徑相同，則判斷二者字典序桅打，然后選擇字典序最小的那個(gè)
#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
輸入正整數(shù)n是嗜，輸出所有abcde/efghil=n的表達(dá)式，其中abcdefghil是0到9的一個(gè)排列挺尾，有前導(dǎo)0, n 的范圍[2,79].
暴力解鹅搪，一共枚舉A(10,5)中情況
通過(guò)dfs的方式進(jìn)行字典序搜索，迭代次數(shù)是109876遭铺，當(dāng)然涩嚣，暴力點(diǎn)的話直接五層for循環(huán)，迭代次數(shù)10^5掂僵，也是可以解決問(wèn)題的航厚。
注意輸出格式：當(dāng)輸入0的時(shí)候，表示結(jié)束锰蓬，沒(méi)有任何空格
還有一個(gè)坑爹的格式要求是：最后一個(gè)有效輸出后沒(méi)有空格幔睬，也就是輸入0之前的那個(gè)輸入不產(chǎn)生空格
#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
輸入正整數(shù)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 素?cái)?shù)環(huán)
把整數(shù)1,2,3,...,n組成一個(gè)環(huán)舱卡，使得相鄰數(shù)的和都是素?cái)?shù)辅肾，環(huán)從數(shù)字1開(kāi)始。
暴力枚舉解決轮锥，為了減少枚舉量矫钓，采用回溯法。
1)一個(gè)解法
這個(gè)解法并沒(méi)有ac舍杜，出錯(cuò)原因是它的輸出沒(méi)有按字典排序
#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）對(duì)上述解法進(jìn)行改進(jìn)新娜，使它按字典序輸出
#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);//假設(shè)遞歸返回后，能夠恢復(fù)遞歸前的樣子
}
for(int i=cur+1 ; i<n ; ++i)//恢復(fù)遞歸前的樣子
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)用一個(gè)數(shù)組記錄是否被用到來(lái)進(jìn)行深度優(yōu)先搜索：
#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 困難的串
題目
對(duì)于一個(gè)字符串既绩，如果存在相同且相鄰的兩個(gè)子串概龄，則該字符串是“容易的串”，否則就叫困難串饲握。對(duì)于基數(shù)是n的字符串私杜，字符由A蚕键，B，... （n個(gè)字符）組成衰粹，給定n和L锣光，求基數(shù)為n的字符串中第L大的困難串。
解法
暴力解寄猩，從第一個(gè)困難串開(kāi)始，根據(jù)當(dāng)前困難串骑疆，計(jì)算下一個(gè)困難串田篇，一直計(jì)算到第L大的困難串。
其實(shí)這個(gè)也是深度優(yōu)先搜索過(guò)程箍铭，跟之前有點(diǎn)不同的是泊柬，一旦搜索到想要的答案，就立刻終止诈火。兽赁。。
#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
解法：深度優(yōu)先搜索+剪枝
#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;
}
