AtCoder Beginner Contest 158
https://atcoder.jp/contests/abc158
基础不牢,地动山摇
D - String Formation
一个小小的STL应用
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s;
int q, t, f;
char c;
int main () {
cin >> s >> q;
int tt = 0; //代表此刻状态
stack <char> st;
queue<char> ed;
while (q --) {
cin >> t;
if (t == 2) {
cin >> f >> c;
if (f == 1) {
if (tt == 1) ed.push (c);
else st.push (c);
}
else {
if (tt == 0) ed.push (c);
else st.push (c);
}
}
else tt ^= 1;
}
string t;
while (!st.empty ()) t += st.top (), st.pop ();
t += s;
while (!ed.empty ()) t += ed.front (), ed.pop ();
if (tt) reverse (t.begin (), t.end ());
cout << t;
}
E - Divisible Substring
是非常经典的数学小结论应用。
应该是利用了费马小定理,然后转化一下:
注意从右往左才是低位向高位
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int n, p, len;
string s;
ll ans, ss;
int main () {
cin >> n >> p >> s;
s = ' ' + s;
if (p == 2 || p == 5) {
for (int i = 1; i <= n; i++) {
if ((s[i] - '0') % p == 0) ans += i;
}
cout << ans << endl;
return 0;
}
map<ll, int> mp;
mp[0] = 1;
ll pw = 1;
for (int i = n; i >= 1; i--) {
ss = ss % p + (s[i] - '0') * pw % p;
ss %= p, pw = pw * 10 % p;
ans += mp[ss], mp[ss] ++;
}
cout << ans;
}
//费马小定理: a^{p-1}=1(mod p)
//10^{p-1}=1(mod p)
//(ai*10^{p-1}+aj) mod p = (ai+aj)*10^{p-1} mod p
//转化为有多少个区间和mod p = 0
//同余即可
F - Removing Robots
神奇的dp。
\(f_i\) 表示后 \(i\) 个的方案数,然后就从后往前更新,单调栈找第一个未被影响的数。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, mod = 998244353;
pii p[N];
int n, f[N]; //后i个的方案数
int main () {
cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
sort (p + 1, p + n + 1);
f[n+1] = 1;
stack <pii> s;
for (int i = n; i >= 1; i--) {
int nxt = i + 1, t = p[i].first + p[i].second;
while (!s.empty () && p[s.top().first].first < t) {
nxt = s.top ().second; //nxt是不被影响的第一个
s.pop ();
}
s.push ({i, nxt});
f[i] = (f[i+1] + f[nxt]) % mod;
}
cout << f[1];
}
- Beginner AtCoder Contest 158beginner atcoder contest 158 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315