Codeforces Round 927 (Div. 3)

A. Thorns and Coins

题意：跑酷，每次移动一格或两格，遇到金币加一分，遇到陷阱停止跑酷，最多得多少分。

思路：n很小，顺着捋就行，一次一格，尽量避开陷阱，避不开的时候停止(两格以上连续陷阱)。

AC code：

void solve() {cin >> n;int ans = 0;string s; cin >> s;for (int i = 0; i < n; i ++) {if (s[i] == '@') ans ++;else if (s[i] == '*') {if (s[i + 1] != '*') continue;else {cout << ans << endl;return;}}}cout << ans << endl;
}

B. Chaya Calendar

题意：有n个征兆，第i个征兆会在ai年的整数倍年出现，求第n个征兆出现年份。

思路：累加年份即可，碰到非整数倍的年份向上取整即可。

AC code:

void solve() {cin >> n;for (int i = 0; i < n; i ++) cin >> a[i];int now = 0;for (int i = 0; i < n; i ++) {if (now < a[i]) now += (a[i] - now);else if (now == a[i]) {now += a[i];} else {int x = now / a[i];now = (x + 1) * a[i];}}cout << now << endl;
}

C. LR-remainders

题意：长度为n的整数数组a，给出n个命令，每个命令可以取出当前最左/右的元素，每次命令前输出当前剩余所有元素的积除m的余数。

思路：用栈模拟这个过程即可，因为已经提前得知命令取出元素的顺序了，最后取出的元素用的最久。、

AC code：

void solve() {cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> a[i];string s; cin >> s;s = " " + s;stack<int> q;int l = 1, r = n, t = 1;for (int i = 1; i <= n; i ++) {if (s[i] == 'L') q.push(a[l]), l ++;else q.push(a[r]), r --;}int sum = 1;vector<int> b;while (!q.empty()) {auto t = q.top();q.pop();sum *= t;sum %= m;b.pb(sum);} reverse(b.begin(), b.end());for (auto x : b) cout << x << " ";cout << endl;
}

D. Card Game

题意：略，太长了。

思路：顺着题意模拟，让非王牌内耗，再用王牌耗，看能不能耗完即可，大模拟。

AC code：

void solve() {cin >> n;char ki; cin >> ki;map<char, vector<string>> mp;for (int i = 0; i < 2 * n; i ++) {string s; cin >> s;mp[s[1]].pb(s);}vector<char> fi = {'C', 'D', 'H', 'S'};for (char c : fi) {sort(mp[c].begin(), mp[c].end());}int cnt = 0;for (char c : fi) {if (c != ki && mp[c].size() % 2 == 1) cnt ++;}if (cnt > mp[ki].size() || mp[ki].size() % 2 != cnt % 2) {cout << "IMPOSSIBLE" << endl;return;}for (char c : fi) {if (c == ki) continue;if (mp[c].size() % 2 == 1) {cout << mp[c].back() << " " << mp[ki].back() << endl;mp[c].pop_back(), mp[ki].pop_back();} }for (char c : fi) {for (int i = 0; i < mp[c].size(); i += 2) {cout << mp[c][i] << " " << mp[c][i + 1] << endl;}}
}

E. Final Countdown

题意：一串数字倒计时到0，每一位一共需要变化多少次。

思路：可以看出，第i位的变化次数为1到i位的十进制，从前往后每一位的和类似前缀和，因为数可能很大，计算的时候从后往前用高精度的方式计数，注意最后可能多进一位的情况。

AC code ：

void solve() {cin >> n;string s; cin >> s;string ans = "";reverse(s.begin(), s.end());int sum = 0, aid = 0;for (char c : s) {sum += (c - '0');}for (char c : s) {char now = ((sum + aid) % 10) + '0';ans.pb(now);aid = (sum + aid) / 10;sum -= (c - '0');}if (aid == 1) {reverse(ans.begin(), ans.end());cout << 1 << ans << endl;} else {while (ans.back() == '0') ans.pop_back();reverse(ans.begin(), ans.end());cout << ans << endl;}
}