UVa 11069 A Graph Problem

題意：

1. 子集合內數字不能相鄰
2. 要盡可能填滿，比如n=6，那麼就不能有{3,6}而是要{1,3,6}，不能是{1,4}而是要{1,4,6}

想法：

　　一開始很直覺的使用遞迴一直往下尋找，但是使用遞迴會TLE，換個想法，很類似高中排列組合的階梯問題，本題是一次走2階或3階：

• n=1{1} : 1
• n=2{1,2} : 2
• n=3{1,2,3} : 2
• 當n=4{1,2,3,4}，有哪些情況會選到'4'? n=1({1,4})或n=2({2,4})的情況，所以n(4)=n(1)+n(2)=3
• 當n=5{1,2,3,4,5}，會選到'5'的情況有n=2({2,5})或n=3({1,3,5})，所以n(5)=n(2)+n(3)=4
• 以此類推..

	#include <cstdio>
	using namespace std;
	int main()
	{
	int ans[77];
	ans[1]=1;
	ans[2]=2;
	ans[3]=2;
	for(int i=4;i<=76;i++)
	ans[i]=ans[i-2]+ans[i-3];
	int n;
	while(scanf("%d",&n)!=EOF)
	printf("%d\n",ans[n]);
	return 0;
	}
	//*********遞迴版**********
	#include <cstdio>
	using namespace std;
	void graph(int n,int i);
	int numOfSub;
	int main()
	{
	int n;
	while(scanf("%d",&n)!=EOF){
	numOfSub=0;
	for(int i=1;i<=2&&i<=n;i++)
	graph(n,i);
	printf("%d\n\n",numOfSub);
	}
	return 0;
	}
	void graph(int n,int i)
	{
	if(i+2>=n){
	numOfSub++;
	return;
	}
	graph(n,i+2);
	graph(n,i+3);
	}

view raw [UVa] 11069 A Graph Problem.cpp hosted with ❤ by GitHub

UVa 10098 Generating Fast

2014.2.13更新：
這題使用STL_next_permunation即可，不過效率較慢，1.035秒，底下自幹的方法0.119秒。

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	int n;
	string str;
	cin >> n;
	while (n--){
	cin >> str;
	sort(str.begin(), str.end());
	do{
	for (char &c : str) // c++11 new standard：用來走遍所有元素
	cout << c;
	cout << endl;
	} while (next_permutation(str.begin(), str.end()));
	cout << endl;
	}
	}

view raw [UVa] 10098-2 Generating Fast.cpp hosted with ❤ by GitHub

想法：

char str[]存原本所有的字元

char temp[]來存已選擇的字元

bool choosed[]來表示哪些字元已被選擇

int all表示總共幾個字元

int left表示剩下幾個字元還沒選到

舉例子解釋，本題比如是"abc"，那麼第一個位置可能放a或b或c

所以在遞迴第一層用for loop從i=0~i=2。

假設現在i=1 將'b'放入temp

同時將choosed[1]標記為1  

那麼進入下一層遞迴就不會選到'b'

進入下層遞迴後 一樣for loop從i=0~2

但是'b'因為choosed[1]=1就不會選到

以此類推，例如現在第二層遞迴i=0選'a'

就將'a'放入temp(此時temp[]="ba")，choosed[0]=1;

再進入第三層時因為其他choosed皆=1，

所以只剩'c'，將'c'放入temp，

最後進入第四層因為left==0(所有字元都被選到了)，就可以print結果

返回第三層，將'c'從temp剔除，choosed[2]=0，此時i值已經到底了(i==2)

然後返回第二層，將'a'剔除，choosed[0]=0，此時i++，

到i==2時，把'c'放入temp(此時temp[]="bc")，進入第三層

之後以此類推。

從以上可寫成遞迴式:

permu(all,left,str,choosed,temp)
{
   if(left==0) printf結果;
   else{
      for(int i=0;i<all;i++){
         if(choosed[i]==0){
            choosed[i]=1;
            temp.push_back(str[i]);

            permu(all,left-1,str,choosed,temp);

            temp.pop_back();
            chooses[i]=0;
         }
      }
   }
}


注意： "aab" 會重複排列字元的問題，加入一條判斷式避免
if(choosed[i]==0 && choosed[i+1]==1 && str[i]==str[i+1]) continue;

	#include <cstdio>
	#include <algorithm>
	#include <string.h>
	#include <vector>
	using namespace std;
	void permu(int all,int left,char str[],bool choosed[],vector<char> &temp);
	bool cmp(char a,char b){
	return a<b;
	}
	/*
	temp[]來存已選擇的字元
	choosed[]來表示哪些字元已被選擇
	all表示總共幾個字元
	left表示剩下幾個字元還沒選到
	*/
	int main()
	{
	int n;
	char str[15];
	scanf("%d",&n);
	while(n--){
	scanf("%s",str);
	sort(str,str+strlen(str),cmp);
	bool choosed[15]={0};
	vector<char> temp;
	permu(strlen(str),strlen(str),str,choosed,temp);
	printf("\n");
	}
	return 0;
	}
	void permu(int all,int left,char str[],bool choosed[],vector<char> &temp)
	{
	if(left==0){
	for(int i=0;i<all;i++)
	printf("%c",temp[i]);
	printf("\n");
	}
	else{
	for(int i=0;i<all;i++){
	//避免aab會重複的問題
	if(choosed[i]==0 && choosed[i+1]==1 && str[i]==str[i+1]) continue;
	if(choosed[i]==0){
	choosed[i]=1;
	temp.push_back(str[i]);
	permu(all,left-1,str,choosed,temp);
	temp.pop_back();
	choosed[i]=0;
	}
	}
	}
	}

view raw [UVa] 10098 Generating Fast.cpp hosted with ❤ by GitHub

UVa 10815 Andy's First Dictionary

想法：
　　用%s讀入temp(可略過空白和換行)=>判斷temp裡每個字放到dic[].word裡=>排序=>輸出

注意：

• 如A's 要分成A跟s
• 不用考慮最後一行換行的問題
• 陣列開很大時要放在global，避免Runtime Error(放在local會有大小限制，array開很大就會overflow)

	#include <cstdio>
	#include <algorithm>
	#include <string.h>
	using namespace std;
	struct dictionary_type
	{
	char word[250];
	}dic[100000];
	bool cmp(dictionary_type a,dictionary_type b)
	{
	return strcmp(a.word,b.word)<0;
	}
	int main()
	{
	char temp[250];
	int i,j,dic_i=0;
	while(scanf("%s",temp)!=EOF){
	for(i=0,j=0;temp[i];i++){
	if(temp[i]>='A' && temp[i]<='Z')
	dic[dic_i].word[j++]=temp[i]-'A'+'a'; //換成小寫
	else if(temp[i]>='a' && temp[i]<='z')
	dic[dic_i].word[j++]=temp[i];
	else if(j) {dic_i++; j=0;} // apple'is 要被分成兩個字apple跟is
	}
	if(j) dic_i++; //if(j) 避免words'的情況
	}
	sort(dic,dic+dic_i,cmp);
	for(i=0;i<dic_i;){
	printf("%s",dic[i].word);
	for(j=i+1; j<dic_i ;j++)
	if(strcmp(dic[i].word,dic[j].word)) break;
	i=j;
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10815 Andy's First Dictionary.cpp hosted with ❤ by GitHub

POJ 3067 Japan

　　本題東邊有N個城市，西邊有M個城市，現在欲蓋多條高速公路連接東西邊，求路線的交點數。

ps.不會有三邊共點的情形

struct city{

     int e;  // 存東邊城市編號

     int w;  // 存西邊城市編號

}

想法1：每次讀入(e,w)時(設第k次)就檢查(k-1)次之前所有情況，若city[k-1].e<city[k].e，則city[k-1].w>city[k].w才會有交點，反之。此算法為O(n^2)會TLE。

	#include<cstdio>
	using namespace std;
	int main()
	{
	int T,t,N,M,K,k,i;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
	int e[100000],w[100000];
	int cross=0;
	scanf("%d %d %d",&N,&M,&K);
	for(k=0;k<K;k++){
	scanf("%d %d",&e[k],&w[k]);
	for(i=0;i<k;i++){
	if(e[i]<e[k])
	if(w[i]>w[k]) cross++;
	else if(e[i]>e[k])
	if(w[i]<w[k]) cross++;
	}
	}
	printf("Test case %d: %d\n",t,cross);
	}
	return 0;
	}

view raw [POJ] 3067 Japan 1.cpp hosted with ❤ by GitHub

想法2: 可依e由小到大(若e相等則依w小到大排)將city[K]排序，此時將只討論city[k-1].e<city[k].e的情況，只要檢察前(k-1)次的w值大於第k次的w值的總和就是解答，但如果又用兩個for loop來跑又變成O(n^2)的算法，本題可簡化為求city[K]的逆序數，使用mergesort求逆序數(可參考UVa 10810)，此算法為O(nlgn)會AC。

	#include<cstdio>
	#include<algorithm>
	using namespace std;
	struct city{
	int e;
	int w;
	};
	bool cmp(city a,city b);
	void mergesort(int l,int h,city a[]);
	void combine(int l,int mid,int h,city a[]);
	long long int cross=0;
	int buffer[500001];
	int main()
	{
	int T,t,N,M,K,k,i;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
	city a[100000]; cross=0;
	scanf("%d %d %d",&N,&M,&K);
	for(k=0;k<K;k++)
	scanf("%d %d",&a[k].e,&a[k].w);
	sort(a,a+K,cmp);
	mergesort(0,k-1,a);
	printf("Test case %d: %lld\n",t,cross);
	}
	return 0;
	}
	bool cmp(city a,city b)
	{
	if (a.e==b.e) return a.w<b.w;
	return a.e<b.e;
	}
	void mergesort(int l,int h,city a[])
	{
	if(l==h) return;
	int mid=(l+h)/2;
	mergesort(l,mid,a);
	mergesort(mid+1,h,a);
	combine(l,mid,h,a);
	}
	void combine(int l,int mid,int h,city a[])
	{
	int lcnt=l,hcnt=mid+1,bufcnt=0;
	while(lcnt<=mid && hcnt<=h){
	if(a[hcnt].w<a[lcnt].w){
	buffer[bufcnt++]=a[hcnt++].w;
	cross+=(mid-lcnt+1);
	}
	else buffer[bufcnt++]=a[lcnt++].w;
	}
	while(lcnt<=mid) buffer[bufcnt++]=a[lcnt++].w;
	while(hcnt<=h) buffer[bufcnt++]=a[hcnt++].w;
	for(bufcnt=0;l<=h;l++)
	a[l].w=buffer[bufcnt++];
	}

view raw [POJ] 3067 Japan 2.cpp hosted with ❤ by GitHub

UVa 10810 Ultra-Quicksort

本題求數字陣列的逆序數

算法：使用mergesort

	#include<cstdio>
	using namespace std;
	void mergesort(int l,int h,int a[]);
	void combine(int l,int mid,int h,int a[]);
	long long int ans=0;
	int buffer[500001];
	int main()
	{
	int n;
	while(scanf("%d",&n)){
	if(n==0) return 0;
	int arr[500001],i; ans=0;
	for(int i=0;i<n;i++){
	scanf("%d",&arr[i]);}
	mergesort(0,n-1,arr);
	printf("%lld\n",ans);
	}
	}
	void mergesort(int l,int h,int a[])
	{
	if(l==h) return;
	int mid=(l+h)/2;
	mergesort(l,mid,a);
	mergesort(mid+1,h,a);
	combine(l,mid,h,a);
	}
	void combine(int l,int mid,int h,int a[])
	{
	int lcnt=l,hcnt=mid+1,bufcnt=0;
	while(lcnt<=mid && hcnt<=h){
	if(a[hcnt]<a[lcnt]){
	buffer[bufcnt++]=a[hcnt++];
	ans+=(mid-lcnt+1);
	}
	else buffer[bufcnt++]=a[lcnt++];
	}
	while(lcnt<=mid) buffer[bufcnt++]=a[lcnt++];
	while(hcnt<=h) buffer[bufcnt++]=a[hcnt++];
	for(bufcnt=0;l<=h;l++)
	a[l]=buffer[bufcnt++];
	}

view raw [UVa] 10810 Ultra-Quicksort.cpp hosted with ❤ by GitHub

UVa 10026 Shoemaker's Problem

　　本題是指鞋匠一次只能選一個工作做，以Sample Input為例，如果先選第一件工作，它需要完成的時間為3天，那麼這3天就無法做其他工作，罰金就為3*(1000+2+5)元，本題要找出選擇工作的次序使得罰金最小。

想法：
　　兩相鄰事件a(Ta,Fa),b(Tb,Bb)無論排成ab或是ba，其他部分的罰金是固定的所以差異在於ab(Ta*Fb)還是ba(Tb*Fa)的損失較小

假如是ab較小，則

• (Ta*Fb)<(Tb*Fa) 
• => (Fa/Ta)>(Fb/Tb) 

a的(罰金/時間)比較大

因此本題解法是將每個工作(Fi/Ti)由大到小排序

	#include<algorithm>
	#include<cstdio>
	using namespace std;
	struct Node{
	double tf;
	int order;
	};
	bool cmp(Node a,Node b){
	return a.tf>b.tf;
	}
	int main(){
	int Case,N;
	scanf("%d",&Case);
	while(Case--){
	scanf("%d",&N);
	int time[1011],fine[1011],i;
	Node a[1011];
	for(i=0;i<N;i++){
	scanf("%d %d",&time[i],&fine[i]);
	a[i].tf=fine[i]*1.0/time[i]; //轉double記得*1.0
	a[i].order=i+1;
	}
	sort(a,a+N,cmp);
	printf("%d",a[0].order);
	for(i=1;i<N;i++)
	printf(" %d",a[i].order);
	printf("\n");
	if(Case) //注意最後一個Case不能有換行
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10026 Shoemaker's Problem.cpp hosted with ❤ by GitHub

UVa 10420 List of Conquests

前言寫很多，其實就只是找每個國家的重複個數而已
想法：
　　只存國家名稱=>按名稱排序=>找重複數量

	#include<cstdio>
	#include<iostream>
	#include<algorithm>
	#include<string>
	using namespace std;
	int main()
	{
	int n;
	char a[76];
	string b[2001];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
	gets(a);
	cin>>b[i];
	}
	sort(b,b+n);
	for(int i=0;i<n;){
	cout<<b[i]<<' ';
	int num=1,j;
	for(j=i+1;j<n;j++){
	if(b[i]!=b[j]) break;
	num++;
	}
	printf("%d\n",num);
	i=j;
	}
	return 0;
	}

view raw [UVa] 10420 List of Conquests.cpp hosted with ❤ by GitHub

UVa 156 Ananagrams

　　本題是輸入一堆單字，come, EoMc, emoc, ECMO這四個單字是一樣的，輸出的單字找不到其他字與其相同。輸出按ABC..abc..順序。

想法：

　　將字母皆視為小寫，而替每個字母產生一個亂數，單字將字母的值加起來存成一個value，如果兩個單字的value一樣則為相同。

	#include<cstdio>
	#include<algorithm>
	using namespace std;
	struct ana_type{
	char word[30];
	long long int value;
	int num;
	};
	bool cmp(ana_type a,ana_type b){
	if(a.num==b.num) return a.value<b.value;
	return a.num<b.num;
	}
	bool cmp2(char *a,char *b){
	int i=0;
	for(;a[i]==b[i];i++);
	return a[i]<b[i];
	}
	int main()
	{
	int i,j,n;
	ana_type a[10000];
	int EtoNum[150];
	for(i='a';i<='z';i++) //隨機替字母產生value
	EtoNum[i]=101*i*i+31*i+51;
	for(i=0;;i++){
	scanf("%s",a[i].word);
	if (a[i].word[0]=='#') break;
	a[i].value=0;
	for(j=0;a[i].word[j];j++)
	a[i].value+=EtoNum[a[i].word[j]<'a'?a[i].word[j]+32:a[i].word[j]]; //存小寫的value 'a'-'A'=32 32-26=6
	a[i].num=j;
	}
	n=i;
	sort(a,a+n,cmp); //依照字母個數排，若一樣則依value排
	char *ans[10000]; int ans_i=0;
	for(i=0;i<n;){
	for(j=i+1;a[i].value==a[j].value;j++){
	;
	}
	if(j==i+1) ans[ans_i++]=a[i].word;
	i=j;
	}
	sort(ans,ans+ans_i,cmp2);
	for(i=0;i<ans_i;i++)
	printf("%s\n",ans[i]);
	return 0;
	}

view raw [UVa] 156 Ananagrams.cpp hosted with ❤ by GitHub

UVa 374 Big Mod

已知 (A^n)%M=(A%M)*(A%M)*(A%M)*......*(A%M)%M

可用遞迴 (A^n)%M = (A^(n/2))%M * (A^(n/2))%M %M

	#include<cstdio>
	using namespace std;
	typedef long long int llt;
	llt mod(llt B,llt P,llt M);
	int main()
	{
	llt B,P,M;
	while(scanf("%lld %lld %lld",&B,&P,&M)!=EOF){
	printf("%lld\n",mod(B,P,M));
	}
	return 0;
	}
	llt mod(llt B,llt P,llt M)
	{ //遞迴 (A^n)%M = (A^(n/2))%M * (A^(n/2))%M %M
	if(P==0) return 1;
	if(P==1) return B%M;
	llt temp = mod(B,P/2,M); //temp=(A^(n/2))%M
	if(P%2==1) return temp*temp*B%M; //P為奇數
	else return temp*temp%M;
	}

view raw UVa 374 Big Mod.cpp hosted with ❤ by GitHub

UVa 755 487-3279

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	//English to number
	int EtoN[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
	int main()
	{
	int Case,n,i,j,k;
	int tel[100005]; //用int來存電話
	char line[200];
	scanf("%d",&Case);
	while(Case--){
	scanf("%d\n",&n);
	for(i=0;i<n;i++){
	scanf("%s",line);
	tel[i]=0;
	for(j=0;line[j];j++){
	if(line[j]=='-') continue;
	if(line[j]<='9' && line[j]>='0')
	tel[i]=tel[i]*10+(line[j]-'0');
	else if(line[j]<'Z' && line[j]>='A')
	tel[i]=tel[i]*10+EtoN[line[j]-'A'];
	}
	}
	sort(tel,tel+n);
	bool duplicate=1;
	for(i=0;i<n;){
	for(j=i+1;j<n && tel[i]==tel[j];j++)
	;
	if(j>i+1){
	printf("%.3d-%.4d %d\n",tel[i]/10000,tel[i]%10000,j-i);
	duplicate=0;
	}
	i=j;
	}
	if(duplicate) printf("No duplicates.\n");
	if (Case) printf("\n"); //注意最後一個Case不能有換行
	}
	return 0;
	}

view raw UVa 755.cpp hosted with ❤ by GitHub

UVa 10017 The Never Ending Towers of Honoi

想法：
　　河內塔問題可先簡化成只有一個，那麼只要將它從A移到C，而如果有兩個的話，那就把上面那個移到B，再把下面那個移到C，B再移到C即完成，因此如果有n個，先把上面(n-1)個從A移到B，再把下面那個移到C，最後把(n-1)個從B移到C。

• Honoi(n,a,b,c) 表示將"n"個從A移到C(從第二個參數移到第四個參數)
• Move(a,c) 表示將最下面一個從A移到C

因此可寫成遞迴式：

Hanoi(n,a,b,c)   //將"n"個從A移到C

{

    if(n==1) Move(a,c);  //只有一個，直接移到C

    else{

        Hanoi(n-1,a,c,b);  // 將"n-1"個從A移到B

        Move(a,c);  //將最底下那個從A移到C

        Hanoi(n-1,b,a,c); //最後將"n-1"個從B移到C

    }

}

注意本題output的要求：

• 如果A=>之後沒有數字必須沒有空格
• 每個問題後面都要有一個換行(包含最後一個問題)

	#include <cstdio>
	#include <iostream>
	#include <vector>
	using namespace std;
	void Hanoi(int,vector<int>&,vector<int>&,vector<int>&,vector<int> **);
	void Move(vector<int>&,vector<int>&,vector<int> **);
	int n,m;
	int num;
	int main()
	{
	for(int i=0;;i++){
	scanf("%d %d",&n,&m);
	if (n==0 && m==0) break;
	num=0;
	printf("Problem #%d\n\n",i+1);
	vector<int> a,b,c;
	vector<int> *manage[3]={&a,&b,&c}; //指向A,B,C(因為在函數裡面ABC順序會亂掉)
	printf("A=> ");
	for(int j=n;j>0;j--) {a.push_back(j); printf(" %d",j);}
	printf("\nB=>\nC=>\n");
	Hanoi(n,a,b,c,manage);
	printf("\n");
	}
	return 0;
	}
	void Hanoi(int n,vector<int> &a,vector<int> &b,vector<int> &c,vector<int> *manage[])
	{
	if (n==1 && num<m) Move(a,c,manage);
	else if(num<m){
	Hanoi(n-1,a,c,b,manage);
	if (num>=m) return;
	Move(a,c,manage);
	if (num>=m) return;
	Hanoi(n-1,b,a,c,manage);
	}
	}
	void Move(vector<int> &a,vector<int> &c,vector<int> *manage[])
	{
	c.push_back(a.back());
	a.pop_back();
	printf("\n");
	printf("A=>"); if(manage[0]->size()) printf(" ");
	for(int i=0;i<manage[0]->size();i++) printf(" %d",(*manage[0])[i]); printf("\n");
	printf("B=>"); if(manage[1]->size()) printf(" ");
	for(int i=0;i<manage[1]->size();i++) printf(" %d",(*manage[1])[i]); printf("\n");
	printf("C=>"); if(manage[2]->size()) printf(" ");
	for(int i=0;i<manage[2]->size();i++) printf(" %d",(*manage[2])[i]); printf("\n");
	num++;
	}

view raw UVa 10017.cpp hosted with ❤ by GitHub