1007,1008
久しぶりのPKU。
PKUはむつかしいw
1007
DNAを完全ソートするまでソートしなければいけない回数が少ない順に並び替え。
自分では思いつかなかったけど隣と交換してソートするからある文字より右のその文字よりアルファベット順に小さい文字の数を調べれば良い。
#include <iostream> #include <map> #include <algorithm> #include <cmath> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<string> input(m); for (int i=0; i<m; i++) cin >> input[i]; pair<int, string> pis[m],spis[m]; for (int i=0; i<m; i++) { pis[i].first=0; spis[i].second=pis[i].second=input[i]; for (int j=0; j<n-1; j++) { for (int k=j+1; k<n; k++) { if (input[i][j]>input[i][k]) pis[i].first++; } } spis[i].first=pis[i].first; } sort(spis, spis+m); for (int i=0; i<m; i++) { cout << spis[i].second << endl; } }
1008
マヤの二つの暦のうち一方から一方へ変換するプログラム。
日にちの数え方が0から始めるからと言ってpastに1足したらダメ
なんかyearの計算でずれるっぽい。
#include <iostream> #include <vector> using namespace std; string haab[19] = {"pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol", "chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax", "koyab", "cumhu","uayet"}; string tzo[20] = {"imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb", "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"}; int found(string mon) { for (int i=0; i<19; i++) { if (haab[i]==mon) return i; } } int main() { int n; cin >> n; int day, year; string mon; vector<int> aday, ayear; vector<string> amon; for (int ix=0; ix<n; ix++) { string t; cin >> day >> t >> mon >> year; int past = year*365+found(mon)*20+day; ayear.push_back(past/260); amon.push_back(tzo[past%20]); aday.push_back(past%13+1); } cout << n << endl; for (int i=0; i<n; i++) cout << aday[i] << " " << amon[i] << " " << ayear[i] << endl; }