文章目錄
- 問題A：Maya Calendar
- 問題B：Diplomatic License
- 問題C：Accordian“ Patience
- 問題D：Broken Keyboard (a.k.a. Beiju Text)
- 問題E：Satellites
- 問題F：Fourth Point !!
- 問題G： The Circumference of the Circle
- 問題H：Titanic
問題A：Maya Calendar
題目鏈接：poj1008
題目大意：有兩種計算日期的方式，給出Haab歷輸出Tzolkin歷，只需模擬轉換即可，具體細節看代碼
Haab歷：一年為365天，一年分為19個月，前18個月每個月都是20天，第19個月為5天，每一個月都有一個名字，分別為pop, no, zip, zotz, tzec,
xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu和uayet，每個月份中的天數用0到19表示，最后一個月份中的天數用0到4表示，
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| pop | no | zip | zotz | tzec | xul | yoxkin | mol | chen | yax | zac | ceh | mac | kankin | muan | pax | koyab | cumhu | uayet |
一種叫Tzolkin：一年為260天，一年分為13段，每段20天（260=13*20），每一天用一個數字和一個名字表示，總共20個名字： imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau，數字為1到13，數字和名字都順序回圈(類似中國的天干地支)，例如，第一年開始的幾天為：1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan
參考代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include <vector>
#include<stack>
#include<map>
#include<string>
#include<cstring>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define inf 0x3f3f3f3f
#define SC(a) scanf("%d",&a)
#define pr(a) printf("%d",a)
#define mem(a) memset(a,0,sizeof(a))
#define fn for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
string Haab[19] = {"pop", "no", "zip", "zotz",
"tzec", "xul", "yoxkin", "mol", "chen", "yax",
"zac", "ceh", "mac", "kankin", "muan", "pax",
"koyab", "cumhu", "uayet"};
/* 定義Tzolkin的20天*/
string Tzolkin[20] = {"imix", "ik", "akbal", "kan", "chicchan", "cimi",
"manik", "lamat", "muluk", "ok", "chuen", "eb",
"ben", "ix", "mem","cib", "caban",
"eznab", "canac", "ahau"};
// 日期表示的資訊
struct Data
{
int Date;
//string型別的month
string Month;
int Year;
};
//日期轉換函式
void convert(Data &x)
{
//代表從世界開始記起的天數
long current;
//代表月份
int month;
//尋找haab月份代表是那個數字
for (month = 0; month < 20; month++) //當前月份是Haab歷的哪個月
{
if (x.Month == Haab[month])
break;
}
current = x.Year * 365 + month * 20 + x.Date + 1;
int num, year = 0; // num為輸出中的數字,year為輸出中的年份
string word; // 月份名稱
//求月份的時候會遇到兩種情況
/* 余數為0則為一個整月num=13
余數不為零則月數等于余數
*/
if (current % 13 == 0)
{
num = 13;
}
else
{
num = current % 13;
}
//求年份
// 減260天即可
while ((current - 260) > 0)
{
++year;
current -= 260;
}
//開始判斷天數
//如果天數=0說明是上一年的最后一天
if (current == 0)
{
word = "ahau";
}
else
{
//除以20繼續判斷
current = current % 20;
//和之前判斷天數一樣
if (current == 0)
{
word = "ahau"; // 表示前一個月的最后一天
}
else
{
word = Tzolkin[current - 1];
}
cout<<num<<" "<<word<<" "<<year<<endl;
}
}
int main()
{
int i, n;
char ch; //儲存.字符
//輸入的第一行表示要轉化的日期數量n
cin>>n;
//創建一個一維陣列
Data *p = new Data[n];
for (int i = 0; i < n; i++)
{
cin>>p[i].Date>>ch>>p[i].Month>>p[i].Year;
}
printf("%d\n", n);
for (int i = 0; i < n; i++)
{
convert(p[i]);
}
return 0;
}
問題B：Diplomatic License
題目：poj1939
思路：簡而言之，讀題難度>>（遠大于）做題 ps：我用cin輸入會Output Limit scnaf輸入就AC了（離奇事件？~~~
題目意思：
給你n(n>=3且n為奇數)個點的坐標,這n(按構成多邊形的順序輸入的)個點必然構成一個多邊形,要你按輸入順序輸出這個多邊形各邊的中點坐標，結果保留6位有效數字，
參考代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include <vector>
#include<stack>
#include<map>
#include<string>
#include<cstring>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define inf 0x3f3f3f3f
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
struct point{
ll x,y;
}now,first,last;
int n;
int main()
{
while(cin>>n,n)
{
cout<< n << endl;
cin >> first.x >> first.y;
now = first;
for(int i = 1; i < n; ++i)
{
cin >> last.x >> last.y;
printf("%.6f%.6f",(last.x+now.x)/2.0,(now.y + last.y )/2.0);
now = last;
}
printf("%.6f%.6f",(last.x + first.x )/2.0 , (last.y + first.y)/2.0);
cout << "\n";
}
return 0;
}
問題C：Accordian“ Patience
題目：poj1214
題目大意：
給出52張牌的花色和點數，從左往右每個成為一個堆，
當某個堆的堆頂與它左邊第三個（優先考慮第三個）的花色或是點數相等，就將這堆放置在與之相等的堆上，倘若出現空隙，出現空隙，需要右邊所有堆向左移動來填補，
思路：
- 利用動態陣列vector來模擬鏈表
- 由題意可知是先入后出，可以采用stack堆疊來實作
- 易知牌由兩個成員組成，可以用結構體或者pair實作
參考代碼：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
using namespace std;
vector<stack<pair<char,char> > > v;//動態陣列vector中存放為堆疊，堆疊里可以用結構體或pair
void creat(char a, char b) // 創建
{
stack<pair<char,char> > s;
s.push(make_pair(a,b));
v.push_back(s);
}
bool move(int x) // 移動是否成功
{
char a=v[x].top().first, b=v[x].top().second;
// 優先考慮左邊第三個
if(x>=3)
{
char aa=v[x-3].top().first, bb=v[x-3].top().second;
if(aa==a || bb==b) // 花色或者點數相等
{
v[x].pop();
if(v[x].empty()) v.erase(v.begin() + x); // 如果該堆為空，需要這個右邊全部往左移
v[x-3].push(make_pair(a,b));
return true;
}
}
if(x>=1) //其次考慮左邊第一個
{
char aa=v[x-1].top().first, bb=v[x-1].top().second;
if(aa == a || bb == b){
v[x].pop();
if(v[x].empty()) v.erase(v.begin() + x);
v[x-1].push(make_pair(a,b));
return true;
}
}
return false;
}
int main()
{
string s;
while(1)
{
for(int i=1; i<=26; i++) //每行讀取26個，注：若需讀取帶空格的字串需用：getline（cin，s）
{
cin >> s;
if(s[0]=='#') break;
creat(s[0],s[1]);
}
if(s[0]=='#') break;//結束標志
for(int i = 1; i <= 26; i++)
{
cin >> s;
creat(s[0], s[1]);
}
while(1)
{
int f=1;
int n=v.size();
for(int i = 0; i < n; i++){
if(move(i)){
f = 0;
break;
}
}
if(f) break;
}
int res = v.size();
if(res >= 1) cout << res << " piles remaining:"; // 這里注意，講道理res=1應該輸出pile，但oj輸出了piles
else cout << res << " pile remaining:";
for(int i = 0; i < res; i++) cout << " " << v[i].size();
cout << endl;
v.clear() ;
}
return 0;
}
問題D：Broken Keyboard (a.k.a. Beiju Text)
題目鏈接：UVA11988
題意：
輸入字串，如果出現‘[’,就輸入游標跳到了字串的最前面，如果出現‘]’，則輸入游標跳到字串最后面，最后輸出實際顯示在螢屏上的字串
思路：
將輸出的字串用陣列模擬鏈表，用一個next陣列代替鏈表的next指標，設定cur來表示游標的位置，cur不是當前遍歷到的位置i表示位置i的字符應該插入cur的右側，，當出現‘[’ cur=0; 出現’]’ cur=last last用來保存字串最右邊的下標；
參考代碼：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int main()
{
char s[maxn];
while(~scanf("%s",s+1))
{
int next[maxn]={0};//清空，初始化
int cur=0,last=0;
for(int i=1; s[i]; ++i)
{
if(s[i]=='[') cur=0;
else if(s[i]==']') cur=last;
else
{
next[i]=next[cur];//插入鏈表
next[cur]=i;
if(cur==last) last=i;//last的更新
cur=i;
}
}
for(int i=next[0];i!=0;i=next[i])//輸出
{
if(s[i]!='['&&s[i]!=']') printf("%c",s[i]);
}
putchar('\n');
}
return 0;
}
問題E：Satellites
題目鏈接：UVA10221
題目大意及思路：
給出半徑跟夾角，求出弦長跟弧長；注意角度>180°，用360減去即可
如圖：易知弧長：2πra/360 直線弦：rsin（aπ/2*180）*2
注意： 0<a<180
參考代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include <vector>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<cstring>
#define inf 0x3f3f3f3f
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const double r=6440;
int main()
{
double ss,as;
char s[10];
while(cin >>ss >> as >> s)
{
if(s[0]=='m') as=as/60;//deg角度，min位分
double angle=M_PI*as/180;
double arc=angle*(ss+r);
double dis=2*(ss+r)*sin(angle/2);
if(as>180) arc=2*M_PI*(ss+r)-arc; // 如果大于180°，就用總的減去
printf("%.6f %.6f\n",arc,dis);
}
return 0;
}
問題F：Fourth Point !!
題目鏈接：UVA10242
題目大意及思路：
給出一個四邊形兩條邊的的四個點，求出第四個點，設為a,b,c,d,找出相同的點假設為bc，則第四個點 e就為a+d-c
注意輸出保留三位小數
完整代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
struct point{
double x,y;
};
int main()
{
point a,b,c,d,e;
while(~scanf("%lf%lf%lf%lf",&a.x ,&a.y,&b.x ,&b.y))
{
scanf("%lf%lf%lf%lf",&c.x ,&c.y,&d.x ,&d.y);
if(a.x==c.x && a.y==c.y)
{
e.x=b.x+d.x-a.x;
e.y=b.y+d.y-a.y;
}
else if(a.x==d.x && a.y==d.y)
{
e.x=b.x+c.x-a.x;
e.y=b.y+c.y-a.y;
}
else if(b.x==c.x && b.y==c.y)
{
e.x=a.x+d.x-b.x;
e.y=a.y+d.y-b.y;
}
else if(b.x==d.x && b.y==d.y)
{
e.x=a.x+c.x-b.x;
e.y=a.y+c.y-b.y;
}
printf("%.3f %.3f\n",e.x,e.y );
}
return 0;
}
問題G： The Circumference of the Circle
題目鏈接：poj2242
思路：
根據坐標，算出三邊長，讓根據海倫公式計算面積，再根據s=abc/4r 計算出外接圓半徑，然后算出周長
海倫公式
外接圓半徑
參考代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#define maxn 1000000
#define pi 3.141592653589793
using namespace std;
int main(){
double x1,x2,x3,y1,y2,y3,l;
while(cin>>x1>>y1>>x2>>y2>>x3>>y3){
double a,b,c;
a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
c=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
l=a+b+c;
l/=2;
l=sqrt(l*(l-a)*(l-b)*(l-c));
l=a*b*c/2/l;
l*=pi;
printf("%.2f\n",l);
}
return 0;
}
問題H：Titanic
題目鏈接：poj2354
題目大意：
給你一些字串，其中包括了兩個這個個球的經緯度，求距離，雖然是個理科生，對經緯度都不了解，但必應一下還是能找到公式：
公式：dis(A,B) = R*arccos(cos(wA)*cos(wB)*cos(jB-JA)+sin(wA)*sin(wB));
(wA表示A點的緯度，jA表示A點的精度，B類似），注意默認正方向為’N’，’E’；
關于公示的推導程序
輸入就比較煩；
參考代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
char s[100010];
char c;
int f;
double r=6875/2.0;
int main()
{
scanf("%*s%*s");
scanf("%*s%*s%*s");
scanf("%*s%*s%*s%*s");
int a,b,c;
scanf("%d^%d\'%d\"",&a,&b,&c);
cin>>s;
if(s[0]=='N') f=1;
else f=-1;
double wa=(a+b/60.0+c/3600.0)*f/180*acos(-1.0);
scanf("%*s%d^%d\'%d\"",&a,&b,&c);
cin>>s;
if(s[0]=='E') f=1;
else f=-1;
double ja=(a+b/60.0+c/3600.0)*f/180*acos(-1.0);
scanf("%*s%*s%*s%*s%*s");
scanf("%d^%d\'%d\"",&a,&b,&c);
cin>>s;
if(s[0]=='N') f=1;
else f=-1;
double wb=(a+b/60.0+c/3600.0)*f/180*acos(-1.0);
scanf("%*s%d^%d\'%d\"",&a,&b,&c);
cin>>s;
if(s[0]=='E') f=1;
else f=-1;
double jb=(a+b/60.0+c/3600.0)*f/180*acos(-1.0);
cin>>s;
double dis=r*acos(cos(wa)*cos(wb)*cos(jb-ja)+sin(wb)*sin(wa));
printf("The distance to the iceberg: %.2f miles.\n",dis);
if(dis+0.005<100) printf("DANGER!\n");
return 0;
}
寫了這么久，總結一下：
- 對于A，B題來說，讀題，理解，碼代碼應該還可以再快一點，
- 最大的識訓就是CD題的鏈表題，學會了動態陣列模擬鏈表
- 后面的計算幾何了解了球上兩點最短距離
長路漫漫，唯有堅持！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/252177.html
標籤：其他