|
|
思路：先求第一個(gè)的天數(shù)，然后用這個(gè)天數(shù)求第二個(gè)的表示方式，個(gè)人覺(jué)得不是水題
#include<stdio.h>
#include<string.h>
char hm[19][7]={"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen","yax",
"zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};
char tm[20][9]={"imix","ik","akbal","kan","chicchan","cimi","manik","lamat","muluk","ok",
"chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};
int main()
{
int i,m,n,day,year;
char month[9];
scanf("%d",&n);
printf("%d\n",n);
while (n--)
{
scanf("%d.%s%d",&day,month,&year);
for(i=0; i<19; i++)
if(strcmp(hm[i],month) == 0)
{
m=365*year+20*i+day;
break;
}
printf("%d %s %d\n",m%260%13+1,tm[m%20],m/260);
}
return 0;
}
此程序耗費(fèi)我盡3個(gè)小時(shí)之久，原因是做題前的規(guī)劃沒(méi)做好，一直沒(méi)有想到整體排序的好辦法，最后還是用了注意匹配的方法才解決了問(wèn)題，我不知道為什么用冒泡不行，第一個(gè)字符串總是亂碼。我覺(jué)得整體思路還是比較清晰的，只是方法可能有點(diǎn)傻，效率還行。 C 編譯器 : 172K 0MS
 #include <stdio.h>
#include <string.h>
typedef struct DNA
   {
 char str[50]; // 存儲(chǔ)字符串
int count[2]; // [0] [1]都存放串的逆序數(shù)
 }DNA; // [1]中作為參考,用來(lái)和排序后的[0]匹配
int main()
{
int i=0,j,k=0,n,m,temp;
DNA or[100];
scanf("%d%d",&n,&m);
while (k<m) //獲得數(shù)據(jù)并求各自逆序數(shù)
  {
scanf("%s",&or[k].str);
or[k].count[0]=0; // 此步不能忘
for (i=0; i<n; i++)
for (j=i+1; j<n; j++)
if (or[k].str[i] > or[k].str[j])
or[k].count[0]++;
k++;
 }
for (i=0; i<m; i++)
or[i].count[1]=or[i].count[0]; // 原逆序數(shù)存放順序
for (i=1; i<m; i++) // 對(duì)于各組串的逆序數(shù)進(jìn)行排序,count[0]內(nèi)容已打亂
{
k=i-1;
for (j=i; j<m; j++)
if (or[j].count[0] < or[k].count[0])
k=j;
temp=or[i-1].count[0];
or[i-1].count[0]=or[k].count[0];
or[k].count[0]=temp;
} // 這是典型的選擇排序,只是對(duì)[0]單元的處理,穩(wěn)定與否沒(méi)關(guān)系
for (i=0; i<m; i++)
for (j=0; j<m; j++)
if (or[i].count[0] == or[j].count[1]) // [0] 和 [1] 中逐一相比較
{
or[j].count[1]=-1; // 此步是相等時(shí)順序不變的保證,相當(dāng)于做了訪問(wèn)標(biāo)記!
printf("%s\n",or[j].str);
}
return 0;
}
典型的 閱讀理解題 , 讀懂意思基本上思路就出來(lái)了，恰巧又是一道中文題，這里用枚舉，其他不解釋。
#include <stdio.h>
int main()
{
int i,a,b,c,d,days=0;
while(1)
{
days++;
scanf("%d%d%d%d",&a,&b,&c,&d);
if (a+b+c+d == -4) break;
for (i=d+1; ; i++) // pay attention: from d+1
{
if ((i-a)%23==0)
if ((i-b)%28==0)
if ((i-c)%33==0)
{
printf("Case %d: the next triple peak occurs in %ld days.\n",days,i-d);
break;
}
}
}
return 0;
}
Description
Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square miles each year, due to erosion caused by the Mississippi River. Since Fred is hoping to live in this house the rest of his life, he needs to know if his land is going to be lost to erosion. After doing more research, Fred has learned that the land that is being lost forms a semicircle. This semicircle is part of a circle centered at (0,0), with the line that bisects the circle being the X axis. Locations below the X axis are in the water. The semicircle has an area of 0 at the beginning of year 1. (Semicircle illustrated in the Figure.)
Input
The first line of input will be a positive integer indicating how many data sets will be included (N). Each of the next N lines will contain the X and Y Cartesian coordinates of the land Fred is considering. These will be floating point numbers measured in miles. The Y coordinate will be non-negative. (0,0) will not be given.
Output
For each data set, a single line of output should appear. This line should take the form of: “Property N: This property will begin eroding in year Z.” Where N is the data set (counting from 1), and Z is the first year (start from 1) this property will be within the semicircle AT THE END OF YEAR Z. Z must be an integer. After the last data set, this should print out “END OF OUTPUT.”
把題意弄明白，就知道這道題是水題了，由坐標(biāo) (0,0) 開(kāi)始，以半圓為形狀每年侵蝕50 平方 miles ，問(wèn)你從 (0,0) 開(kāi)始到 (x,y) 結(jié)束需要多長(zhǎng)時(shí)間，水題不需要太關(guān)注效率，所以變量定義上沒(méi)有深究，其他不解釋。
編譯器 C + + :
#include <iostream>
using namespace std;
#define PI 3.1415926
int main()
{
int n,i=0,year;
double x,y,area;
cin>>n;
while (i<n)
{
cin>>x>>y;
area = 0.5 * PI * (x*x+y*y); // semicircle area equation
year = area/50;
printf("Property %d: This property will begin eroding in year %d.\n",i+1,year+1);
i++;
}
printf("END OF OUTPUT.\n");
return 0;
}
正宗水題，就是輸入12個(gè)浮點(diǎn)數(shù)，讓你求平均值，不解釋。
#include<stdio.h>
int main()
{
float i=0,m,s=0;
for(;i<12;i++)
{
scanf("%f",&m);
s+=m;
}
printf("$%.2f\n",s/12);
return 0;
}
正宗水題，題目把最主要的公式都給你了，只要計(jì)算1/2+1/3+1/4+......+1/(n+1) >= x中最小的n值即可，我這里的cards用的是整形，注意底下一定要乘以1.0，否則會(huì)讓你調(diào)試的生不如死的，要不你就讓cards 是浮點(diǎn)型，其他的不解釋。
#include<stdio.h>
int main()
{
int cards;
float length,c;
for(scanf("%f",&c); c!=0.0; scanf("%f",&c))
{
for(cards=0,length=0; length<c; )
{
cards++;
length+=1/(cards*1.0+1);
}
printf("%d card(s)\n",cards);
}
return 0;
} //180K 0MS
事先申明，該程序雖然AC，但是效率極其低下，低下到讓人發(fā)指的程度，我也不知道為什么。估計(jì)是用了STL的原因，具體我也說(shuō)不清楚。其實(shí)思路不難，就是將字符轉(zhuǎn)化成對(duì)應(yīng)數(shù)字，然后將結(jié)果存放在一個(gè)整型向量中，接收字符串用的是字符串向量，處理的時(shí)候跟一般的字符串處理時(shí)一模一樣的。處理結(jié)束之后要進(jìn)行字典排序，顯然要用排序函數(shù)，可以用冒泡，選擇，快排，甚至是Hash，但是據(jù)說(shuō)STL的sort 效率比快排還要快。源程序后附加了MSDN上的一些簡(jiǎn)單解釋。沒(méi)有翻譯！
Description
Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their ``three tens'' number 3-10-10-10.
The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:
A, B, and C map to 2
D, E, and F map to 3
G, H, and I map to 4
J, K, and L map to 5
M, N, and O map to 6
P, R, and S map to 7
T, U, and V map to 8
W, X, and Y map to 9
There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.
Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)
Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.
Input
The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.
Output
Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:
No duplicates.
C++ 編譯器:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // STL sort function
using namespace std;
char map[] = "2223334445556667#77888999#";
//ABCDEFGHIJKLMNOPQRSTUVWXYZ
void visited(char &ch) // visit and format strings
{
if (ch >= 'A' && ch <= 'Z')
ch=map[ch-'A']; // ch equals to its real number
}
int main()
{
int N,i=0,j,flag=0;
string s;
vector<string> stored(100000); // be visited & stored (up to 100,000)
cin>>N;
vector<int> counter(N,1); // stored times
for (; i<N; i++)
{
cin>>s;
for (j=0; j<s.length(); j++) // MSDN
{
visited(s[j]);
if (s[j]!='-')
{
stored[i] += s[j];
if (stored[i].length()==3)
stored[i] += '-'; // 487 -[3] 3279
}
}
}
sort(stored.begin(),stored.begin()+N); // Quicker than QuickSort!
// should not used stored.end() !
i=0; j=1;
while (i<N)
{
while(stored[i] == stored[j])
{
counter[i]++;
j++;
flag=1;
}
i=j;
j++;
}
if (flag)
for (i=0; i<N; i++)
{
if (counter[i]>1)
cout<<stored[i]<<" "<<counter[i]<<endl;
} // must have { }
else cout<<"No duplicates."<<endl;
return 0;
}
Sort ：
Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate.
template<class RandomAccessIterator>
void sort(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
分類(lèi)開(kāi)篇語(yǔ): 第一個(gè)程序搞了好幾天，發(fā)現(xiàn)了很多問(wèn)題。POJ不保證按順序做且更新速度肯定不會(huì)很快。有些題自己做不出來(lái)借鑒別人的會(huì)注明出處。很多算法都需要從網(wǎng)上找，第一題的大浮點(diǎn)數(shù)相乘的核心算法就是這樣找來(lái)的。我心里明白，雖然AC了，但是邊緣數(shù)據(jù)處理的很粗糙，我自己都發(fā)現(xiàn)幾個(gè)bug了，但是依然AC了。
本題主要注意將字符串轉(zhuǎn)化為實(shí)際的數(shù)字然后借鑒數(shù)制的思想來(lái)進(jìn)行大數(shù)相乘。
Description
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.
Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
編譯器C++ 源碼:
#include <iostream>
#include <string>
using namespace std;
#define MAX 255
int getnum(string s,int *c) // get real number of R
{
int i=0,j=0,t[MAX];
memset(t,0,sizeof(int)*MAX); // a stores 0
while (i < 6) // R value 1 through 6
{
if (s[i] != '.')
{
t[j]=s[i]-'0';
j++;
}
i++;
} // a`s length = 5
for (j=0; j<5; j++)
c[j]=t[4-j]; // c stores in order from a
for (i=0; s[i] != '.'; i++); // find decimal point
return (5-i); // the position of . point
}
void multi(int *a,int *b) // big-multiplication
{
int i=0,j,r=0,t[MAX];
memset(t,0,sizeof(int)*MAX); // t stores 0
for (; i<5; i++)
for (j=0; j<255; j++)
t[i+j] += a[i]*b[j]; // core algorithms!
for (i=0; i<255; i++)
{
b[i]=(r+t[i])%10; // r always stores remainder
r=(r+t[i])/10; // b stores the result
}
} // basic algorithms of b-m
int main()
{
int i,j,d_pos,n,a[MAX],b[MAX];
string s;
while (cin>>s>>n)
{
memset(b,0,sizeof(int)*MAX);
memset(a,0,sizeof(int)*MAX);
d_pos=getnum(s,a);
getnum(s,b);
for (i=0; i<n-1; i++)
multi(a,b); // a is a loop invariant
for (i=254; !b[i]; i--); //find last non-zero
for (j=0; !b[j]; j++); // find first non-zero
for (; i >= n*d_pos; i--) // loop n times
cout<<b[i];
if (n*d_pos >= j+1) cout<<"."; //pay attention
for (i=n*d_pos-1; i>=j; i--)
cout<<b[i]; //from back formating output
cout<<endl;
}
return 0;
}
1. 計(jì)算復(fù)雜性 O
這是描述一種算法需要多少 Running time 的度量。（也有空間復(fù)雜性，但因?yàn)樗鼈兡芟嗷マD(zhuǎn)換，所以通常我們就說(shuō)時(shí)間復(fù)雜性。對(duì)于大小為 n 的輸入，我們用含 n 的簡(jiǎn)化式子來(lái)表達(dá)。（所謂簡(jiǎn)化式子，就是忽略系數(shù)、常數(shù)，僅保留最“大”的那部分）。
比如找出 n 個(gè)數(shù)中最大的一個(gè)，很簡(jiǎn)單，就是把第一個(gè)數(shù)和第二個(gè)比，其中大的那個(gè)再和第三個(gè)比，依次類(lèi)推，總共要比 n-1 次，我們記作 O(n) (對(duì)于 n 可以是很大很大的情況下，-1可以忽略不計(jì)了）。
再比如從小到大排好的 n 個(gè)數(shù)，從中找出等于 x 的那個(gè)。一種方法是按著順序從頭到尾一個(gè)個(gè)找，最好情況是第一個(gè)就是 x，最壞情況是比較了 n 次直最后一個(gè)，因此最壞情況下的計(jì)算復(fù)雜度也是 O(n)。還有一種方法：先取中間那個(gè)數(shù)和 x 比較，如偏大則在前一半數(shù)中找，如偏小則在后一半數(shù)中找，每次都是取中間的那個(gè)數(shù)進(jìn)行比較，則最壞情況是 lg(n)/lg2。忽略系數(shù)lg2，算法復(fù)雜度是O(lgn)。
2. 計(jì)算復(fù)雜性的排序
根據(jù)含 n 的表達(dá)式隨 n 增大的增長(zhǎng)速度，可以將它們排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常數(shù)）< ... < 2^n （不用死記，想象它們的函數(shù)曲線，一看便明）。最后這個(gè) 2 的n 次方就是級(jí)數(shù)增長(zhǎng)了，讀過(guò)棋盤(pán)上放麥粒故事的人都知道這個(gè)增長(zhǎng)速度有多快。而之前的那些都是 n 的多項(xiàng)式時(shí)間的復(fù)雜度。為什么我們?cè)谶@里忽略所有的系數(shù)、常數(shù)，例如 2*n^3+9*n^2 可以被簡(jiǎn)化為 n^3？老師上課也沒(méi)有說(shuō)原因，所以我也不知道。但是如果對(duì)對(duì) (2*n^3+9*n^2)/(n^3) 求導(dǎo)，結(jié)果是0，仔細(xì)想想，我也沒(méi)有想出所以然來(lái)。
3. P 問(wèn)題
對(duì)一個(gè)問(wèn)題，凡是能找到計(jì)算復(fù)雜度可以表示為多項(xiàng)式的確定算法，這個(gè)問(wèn)題就屬于 P (polynomial) 問(wèn)題。
4. NP 問(wèn)題
NP 中的 N 是指非確定的(non-deterministic）算法，這是這樣一種算法：
（1）猜一個(gè)答案。（2）驗(yàn)證這個(gè)答案是否正確。（3）只要存在某次驗(yàn)證，答案是正確的，則該算法得解。
NP (non-deterministic polynomial)問(wèn)題就是指，用這樣的非確定的算法，驗(yàn)證步驟（2）有多項(xiàng)式時(shí)間的計(jì)算復(fù)雜度的算法。
5. 問(wèn)題的歸約
想象一下函數(shù)的映射是怎么一回事吧。這個(gè)概念需要弄懂。
大致就是這樣：找從問(wèn)題1的所有輸入到問(wèn)題2的所有輸入的對(duì)應(yīng)，如果相應(yīng)的，也能有問(wèn)題2的所有輸出到問(wèn)題1的所有輸出的對(duì)應(yīng)，則若我們找到了問(wèn)題2的解法，就能通過(guò)輸入、輸出的對(duì)應(yīng)關(guān)系，得到問(wèn)題1的解法。由此我們說(shuō)問(wèn)題1可歸約到問(wèn)題2。
再給一個(gè)我找到的高端解釋：
問(wèn)題歸約是人求解問(wèn)題常用的策略，其把復(fù)雜的問(wèn)題變換為若干需要同時(shí)處理的較為簡(jiǎn)單的子問(wèn)題后再加以分別求解。只有當(dāng)這些子問(wèn)題全部解決時(shí)，問(wèn)題才算解決，問(wèn)題的解答就由子問(wèn)題的解答聯(lián)合構(gòu)成。問(wèn)題歸約可以遞歸地進(jìn)行，直到把問(wèn)題變換為本原問(wèn)題的集合。所謂本原問(wèn)題就是不可或不需再通過(guò)變換化簡(jiǎn)的"原子"問(wèn)題，本原問(wèn)題的解可以直接得到或通過(guò)一個(gè)"黑箱"操作得到。
6. NP-Hard
有這樣一種問(wèn)題，所有 NP 問(wèn)題都可以歸約到這種問(wèn)題，我們稱之為 NP-hard 問(wèn)題。
7. NP完全問(wèn)題 (NP-Complete)
如果一個(gè)問(wèn)題既是 NP 問(wèn)題又是 NP-Hard 問(wèn)題，則它是 NP-Complete 問(wèn)題。可滿足性問(wèn)題就是一個(gè) NP 完全問(wèn)題，此外著名的給圖染色、哈密爾頓環(huán)、背包、貨郎問(wèn)題都是 NP 完全問(wèn)題。
解壓縮版本的Eclipse打開(kāi)時(shí)遇到此類(lèi)問(wèn)題：
解決方法：
打開(kāi)安裝目錄下的eclipse.config（或eclipse.ini）配置文件，大致的內(nèi)容如下，
-startup
plugins/org.eclipse.equinox.launcher_1.0.200.v20090520.jar
--launcher.library
plugins/org.eclipse.equinox.launcher.win32.win32.x86_1.0.200.v20090519
-product
org.eclipse.epp.package.jee.product
--launcher.XXMaxPermSize
256M
-showsplash
org.eclipse.platform
--launcher.XXMaxPermSize
256m
-vmargs
-Dosgi.requiredJavaVersion=1.5
-Xms40m
-Xmx512m
其中的“Xmx512m” 改成“Xmx256m”
|