解題心得
這題滿簡單的，想不到會在第四題。
只要稍微推一下就知道是連續數字的相加，代入公式就好，但沒想到CPE測資比ZJ嚴格。
程式碼
#include <iostream>
using namespace std;
int main()
{
long long int t, n, m;
cin >> t;
while (t--)
{
cin >> n >> m;
cout << (m - 1 + m - n) * n / 2 << endl;
}
return 0;
}
2022年3月7日 星期一
f447: 12918 - Lucky Thief
f446: 1237 - Expert Enough
解題心得
每次有新的query，就掃過所有車種，看有幾個符合，以及記錄符合的index。
如果有零個或不只一個，那就不對。如果只有一個，那就可以用index找到車種名稱了。
程式碼
#include <iostream>
#include <string>
using namespace std;
struct carInfo
{
string name;
int low, high;
};
carInfo db[10000];
int main()
{
int t, d, l, h, q, p;
string m;
cin >> t;
while (t--)
{
cin >> d;
for (int i = 0; i < d; i++)
cin >> db[i].name >> db[i].low >> db[i].high;
cin >> q;
while (q--)
{
cin >> p;
int flag = 0, index = -1;
for (int i = 0; i < d; i++)
{
if (db[i].low <= p && p <= db[i].high)
flag++, index = i;
}
if (flag != 1) cout << "UNDETERMINED" << endl;
else cout << db[index].name << endl;
}
if (t != 0) cout << endl;
}
return 0;
}
f445: 263 - Number Chains
解題心得
照著題目敘述做就好。
程式碼
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int descending(int n)
{
int arr[10] = { 0 }, ans = 0;
while (n)
{
arr[n % 10]++;
n /= 10;
}
for (int i = 9; i >= 0; i--)
{
while (arr[i] != 0)
{
ans = ans * 10 + i;
arr[i]--;
}
}
return ans;
}
int ascending(int n)
{
int arr[10] = { 0 }, ans = 0;
while (n)
{
arr[n % 10]++;
n /= 10;
}
for (int i = 0; i < 10; i++)
{
while (arr[i] != 0)
{
ans = ans * 10 + i;
arr[i]--;
}
}
return ans;
}
int main()
{
int n;
while (cin >> n && n)
{
vector<int> v;
cout << "Original number was " << n << endl;
while (true)
{
int ascend = ascending(n), descend = descending(n), result = descend - ascend;
cout << descend << " - " << ascend << " = " << result << endl;
if (v.size() != 0 && find(v.begin(), v.end(), result) != v.end())
break;
v.push_back(result);
n = result;
}
cout << "Chain length " << v.size() + 1 << endl << endl;
}
return 0;
}
f444: 10268 - 498-bis
解題心得
CPE 的系統跟 zerojudge 的測資格式不太一樣，後者好像不是用 \n 換行，只好再用別的方法寫。
程式碼
[for CPE]
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
long long int x, a;
while (cin >> x)
{
vector<long long int> bits;
long long int ans = 0;
while (cin >> a && getchar() != '\n')
bits.push_back(a);
for (int i = 0; i < bits.size(); i++)
{
bits[i] *= bits.size() - i;
ans += bits[i] * pow(x, bits.size() - 1 - i);
}
cout << ans << endl;
}
return 0;
}[for ZJ]
#include <iostream>
#include <vector>
#include <sstream>
#include <math.h>
#include <string>
using namespace std;
int main()
{
long long int x, a;
string s;
while (cin >> x)
{
vector<long long int> bits;
long long int ans = 0;
cin.ignore();
getline(cin, s);
stringstream ss(s);
while (ss >> a)
bits.push_back(a);
bits.pop_back();
for (int i = 0; i < bits.size(); i++)
{
bits[i] *= bits.size() - i;
ans += bits[i] * pow(x, bits.size() - 1 - i);
}
cout << ans << endl;
}
return 0;
}
2022年3月6日 星期日
f439: 10191 - Longest Nap
解題心得
這題不難，只是很多瑣碎的地方要弄。
基本上就是把開始跟結束時間轉換成分鐘，然後用陣列來記錄哪些時候有空或沒空，最後再從頭掃到尾找最長的空檔。因為是10:00開始，把所有轉換後的時間減10*60分鐘。
寫完後覺得寫很醜，如果用開始跟結束時間作為標記，不知道會不會好看一點。
程式碼
#include <iostream>
#include <string>
using namespace std;
int t[480] = { 0 };
int to_int(string s)
{
int n = 0;
n = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)) - 600;
return n;
}
int main()
{
int testcase, counter = 1;
while (cin >> testcase)
{
cin.ignore();
for (int i = 0; i < 480; i++) t[i] = 0;
for (int days = 1; days <= testcase; days++)
{
string s, start, end;
getline(cin, s);
start = s.substr(0, 5);
end = s.substr(6, 5);
for (int i = to_int(start); i <= to_int(end); i++)
t[i] = 1;
//cout << to_int(start) << " " << to_int(end) << endl;
}
int prev = -1, count = 0, maxCount = 0, curTime = 0, time = 0;
for (int i = 0; i < 480; i++)
{
if (t[i] == 0)
count++;
if ((t[i] == 1 && prev == 0) || i == 479)
{
if (curTime == 0) count--;
if (count + 1 > maxCount)
{
maxCount = count + 1;
time = curTime;
}
count = 0;
//cout << "update: " << maxCount << endl;
}
if (t[i] == 0 && prev == 1)
curTime = i - 1;
prev = t[i];
}
cout << "Day #" << counter++ << ": the longest nap starts at " << (time + 600) / 60 << ":";
if ((time + 600) % 60 < 10) cout << "0" << (time + 600) % 60 ;
else cout << (time + 600) % 60;
cout << " and will last for ";
if (maxCount < 60) cout << maxCount << " minutes.\n";
else cout << maxCount / 60 << " hours and " << maxCount % 60 << " minutes.\n";
}
return 0;
}
// 18*60 - 10*60 = 8*60 = 480
2022年3月5日 星期六
f438: 855 - Lunch in Grid City
解題心得
最後好像也沒用到s跟a的值。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int t, s, a, f;
cin >> t;
while (t--)
{
int arrS[50001], arrA[50001];
cin >> s >> a >> f;
for (int i = 0; i < f; i++)
cin >> arrS[i] >> arrA[i];
sort(arrS, arrS + f);
sort(arrA, arrA + f);
if (f % 2 == 1) cout << "(Street: " << arrS[f / 2] << ", Avenue: " << arrA[f / 2] << ")" << endl;
else cout << "(Street: " << arrS[f / 2 - 1] << ", Avenue: " << arrA[f / 2 - 1] << ")" << endl;
}
return 0;
}
a941: 10041 - Vito's large family
解題心得
vito family的進化版(?)，如果直接重跑過一遍s[]把距離加起來會tle。
但最後還是用了黑魔法的那兩行才過的。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int s[2000000] = { 0 },record[30001] = { 0 };
int main()
{
cin.sync_with_stdio(false), cin.tie(0);
int t, r;
cin >> t;
while (t--)
{
cin >> r;
for (int i = 0; i < 30001; i++)
record[i] = 0;
for (int i = 0; i < r; i++)
{
cin >> s[i];
record[s[i]]++;
}
sort(s, s + r);
int mid = 0;
long long int d = 0;
if (r % 2 == 1) mid = s[r / 2];
else mid = s[r / 2 - 1];
for (int i = 0; i <= 30000; i++)
{
d += abs(i - mid) * record[i];
}
cout << d << " " << mid << endl;
}
return 0;
}
d501: 第二題：數列最小值
解題心得
很像高中數學曾經學過的題目，印象中解法是：
1. 當 n 為奇數，則答案為中位數
2. 當 n 為偶數，則答案為區間內的所有整數
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1000000] = { 0 };
int main()
{
while (cin >> n)
{
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
if (n % 2 == 1)
cout << "A=" << arr[n / 2] << endl;
else
{
cout << "A=";
for (int i = arr[n / 2 - 1]; i <= arr[n / 2]; i++)
{
if (i != arr[n / 2])
cout << i << "、";
else
cout << i << endl;
}
}
}
return 0;
}
f437: 1368 - DNA Consensus String
解題心得
要找到第 i 個會是哪個字母，就去統計所有的字串的第 i 個都是哪些字母，找出現最多的那個。如果出現次數相同，則按照字典序順序，所以判斷式的等於才會那樣寫。
要計算 hamming 距離，就是統計不符合的字元次數。
程式碼
#include <iostream>
using namespace std;
int main()
{
int t, m, n;
string s[50];
cin >> t;
while (t--)
{
cin >> m >> n;
for (int i = 0; i < m; i++)
cin >> s[i];
string ans = "";
int d = 0;
for (int i = 0; i < n; i++)
{
int countA = 0, countT = 0, countC = 0, countG = 0;
for (int j = 0; j < m; j++)
{
if (s[j][i] == 'A') countA++;
else if (s[j][i] == 'T') countT++;
else if (s[j][i] == 'C') countC++;
else if (s[j][i] == 'G') countG++;
}
if (countA >= countC && countA >= countG && countA >= countT)
ans += "A", d += countC + countG + countT;
else if (countC > countA && countC >= countG && countC >= countT)
ans += "C", d += countA + countG + countT;
else if (countG > countA && countG > countC && countG >= countT)
ans += "G", d += countC + countA + countT;
else
ans += "T", d += countC + countG + countA;
}
cout << ans << endl << d << endl;
}
return 0;
}
2022年3月3日 星期四
11498: Division of Nlogonia
解題心得
沒有心得。
程式碼
#include <iostream>
using namespace std;
int main()
{
int t, n, m, x, y;
while (cin >> t && t)
{
cin >> n >> m;
while (t--)
{
cin >> x >> y;
if (x > n && y > m)
cout << "NE" << endl;
else if (x < n && y > m)
cout << "NO" << endl;
else if (x > n && y < m)
cout << "SE" << endl;
else if (x < n && y < m)
cout << "SO" << endl;
else
cout << "divisa" << endl;
}
}
return 0;
}
訂閱：
意見 (Atom)