AtCoder Beginner Contest 248 (ABC248) 题解 [A-Ex]

这次总体来说还可以，不算是简单，但也没有超难，但这次似乎是个与某公司合作的比赛？

看完请点赞，谢谢。

A题

//AT248A 22-04-16#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);char a[10];int b[11];memset(b,0,sizeof(b));for (int i=1;i>a[i];b[a[i]-48]++;}for (int i=0;i<=9;i++) if (b[i]==0) cout<<i<<endl;return 0;}

B题

//AT248B 22-04-16#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);long long a,b,k,s=0;cin>>a>>b>>k;while (a<b) {a*=k;s++;}cout<<s<<endl;return 0;}

C题

//AT248C 22-04-16#include using namespace std;#define MOD 998244353int a[55][2555];int n,m,k;int min9(int p){if (p>n>>m>>k;memset(a,0,sizeof(a));a[0][0]=1;for (int i=0;i<n;i++){for (int j=0;j<k;j++){for (int l=j+1;l<=min9(j+m);l++) {a[i+1][l]+=a[i][j];a[i+1][l]%=MOD;}}}long long sum=0;for (int i=0;i<=k;i++){sum+=a[n][i];sum%=MOD;}cout<<sum<<endl;return 0;}

D题

自己的代码：

本人在自己电脑上测试无误，结果提交后 CE ，说是数组太大了，知道如何在程序里添加编译选项的请帮忙回答一下，谢谢

//AT248D 22-04-16#include using namespace std;static int f[200001][200001];int n,q,a[200001];int main() {ios::sync_with_stdio(0);cin.tie(0);cin>>n;for (int i=1;i<=n;i++) f[i][0]=0;for (int i=1;i>a[i];f[a[i]][0]++;f[a[i]][f[a[i]][0]]=i;}cin>>q;for (int i=1;i>l>>r>>x;while (f[x][t]<l) t++;tt=t;while (f[x][t]<r && tt<=f[x][0]) tt++;tt--;cout<<tt-t+1<<endl;}return 0;}

正解：

SSRS：

（lower_bound）是STL里查找的函数

#include using namespace std;int main(){int N;cin >> N;vector A(N);for (int i = 0; i > A[i];A[i]--;}vector<vector> B(N);for (int i = 0; i > Q;for (int i = 0; i > L >> R >> X;L--;X--;cout << lower_bound(B[X].begin(), B[X].end(), R) -lower_bound(B[X].begin(), B[X].end(), L) << endl;}}

E题

SSRS：

#include using namespace std;struct point{long long x, y;point(){}point(long long x, long long y): x(x), y(y){}point operator -(point P){return point(x - P.x, y - P.y);}};long long cross(point P, point Q){return P.x * Q.y - P.y * Q.x;}bool is_collinear(point A, point B, point C){return cross(B - A, C - A) == 0;}int main(){int N, K;cin >> N >> K;vector X(N), Y(N);for (int i = 0; i > X[i] >> Y[i];}map<pair, int> mp;for (int i = 0; i = K){ok = false;}}if (!ok){cout << "Infinity" << endl;} else {vector P(N);for (int i = 0; i < N; i++){P[i] = point(X[i], Y[i]);}int ans = 0;for (int i = 0; i < N; i++){for (int j = i + 1; j < N; j++){bool ok2 = true;for (int k = 0; k < j; k++){if (k != i){if (is_collinear(P[i], P[j], P[k])){ok2 = false;}}}if (ok2){int cnt = 2;for (int k = j + 1; k = K){ans++;}}}}cout << ans << endl;}}

F题：

SSRS：

#include using namespace std;int main(){int N;long long P;cin >> N >> P;vector<vector> dp1(N, vector(N + 2, 0));vector<vector> dp2(N, vector(N + 2, 0));dp1[0][0] = 1;dp2[0][1] = 1;for (int i = 0; i < N - 1; i++){for (int j = 0; j < N; j++){dp2[i + 1][j + 2] += dp1[i][j] * 2;dp2[i + 1][j + 2] %= P;dp1[i + 1][j + 1] += dp1[i][j] * 3;dp1[i + 1][j + 1] %= P;dp1[i + 1][j] += dp1[i][j];dp1[i + 1][j] %= P;dp2[i + 1][j + 1] += dp2[i][j];dp2[i + 1][j + 1] %= P;dp1[i + 1][j] += dp2[i][j];dp1[i + 1][j] %= P;}}for (int i = 1; i < N; i++){cout << dp1[N - 1][i];if (i < N - 1){cout << ' ';}}cout << endl;}

G题：

SSRS：

#include using namespace std;const int MAX = 100000;const long long MOD = 998244353;int main(){int N;cin >> N;vector A(N);for (int i = 0; i > A[i];}vector U(N - 1), V(N - 1);for (int i = 0; i > U[i] >> V[i];U[i]--;V[i]--;}vector phi(MAX + 1);for (int i = 1; i <= MAX; i++){phi[i] = i;}for (int i = 2; i <= MAX; i++){if (phi[i] == i){for (int j = i; j <= MAX; j += i){phi[j] = phi[j] / i * (i - 1);}}}vector<vector> F(MAX + 1);for (int i = 1; i <= MAX; i++){for (int j = i; j <= MAX; j += i){F[j].push_back(i);}}vector<vector> ve(MAX + 1), ed(MAX + 1);for (int i = 0; i < N; i++){for (int j : F[A[i]]){ve[j].push_back(i);}}for (int i = 0; i < N - 1; i++){int g = gcd(A[U[i]], A[V[i]]);for (int j : F[g]){ed[j].push_back(i);}}long long ans = 0;for (int i = 1; i  0){int ce = ed[i].size();vector<vector> E(cnt);for (int j = 0; j < ce; j++){int u = lower_bound(ve[i].begin(), ve[i].end(), U[ed[i][j]]) - ve[i].begin();int v = lower_bound(ve[i].begin(), ve[i].end(), V[ed[i][j]]) - ve[i].begin();E[u].push_back(v);E[v].push_back(u);}vector p(cnt, -1);vector<vector> c(cnt);queue Q;vector dp(cnt, 0);for (int j = 0; j < cnt; j++){if (p[j] == -1){Q.push(j);vector bfs;while (!Q.empty()){int v = Q.front();Q.pop();bfs.push_back(v);for (int w : E[v]){if (w != p[v]){p[w] = v;c[v].push_back(w);Q.push(w);}}}reverse(bfs.begin(), bfs.end());int cnt2 = bfs.size();for (int v : bfs){dp[v] = 1;for (int w : c[v]){dp[v] += dp[w];}}for (int v : bfs){long long m = (long long) cnt2 * (cnt2 - 1) / 2;for (int w : c[v]){m -= (long long) dp[w] * (dp[w] - 1) / 2;}int dpp = cnt2 - dp[v];m -= (long long) dpp * (dpp - 1) / 2;m %= MOD;ans += m * phi[i];ans %= MOD;}}}}}cout << ans << endl;}

Ex题/H题

SSRS：

#include using namespace std;const int INF = 10000000;struct monoid{array<pair, 4> X;monoid(){}monoid(int x){X[0] = make_pair(x, 1);X[1] = make_pair(INF, 1);X[2] = make_pair(INF, 1);X[3] = make_pair(INF, 1);}};monoid mp(int x, monoid A){for (int i = 0; i < 4; i++){A.X[i].first += x;}return A;}monoid op(monoid A, monoid B){int p = 0, q = 0;monoid C;for (int i = 0; i < 4; i++){if (A.X[p].first < B.X[q].first){C.X[i] = A.X[p]; p++;} else if (B.X[q].first < A.X[p].first){C.X[i] = B.X[q];q++;} else {C.X[i] = A.X[p];C.X[i].second += B.X[q].second;p++;q++;}}return C;}int comp(int x, int y){return x + y;}template struct lazy_segment_tree{int N;vector ST;vector lazy;function op;function mp;function comp;T E;F id;lazy_segment_tree(vector &A, function op, function mp, function comp, T E, F id): op(op), mp(mp), comp(comp), E(E), id(id){int n = A.size();N = 1;while (N < n){N *= 2;}ST = vector(N * 2 - 1, E);for (int i = 0; i = 0; i--){ST[i] = op(ST[i * 2 + 1], ST[i * 2 + 2]);}lazy = vector(N * 2 - 1, id);}void eval(int i){if (i < N - 1){lazy[i * 2 + 1] = comp(lazy[i * 2 + 1], lazy[i]);lazy[i * 2 + 2] = comp(lazy[i * 2 + 2], lazy[i]);}ST[i] = mp(lazy[i], ST[i]);lazy[i] = id;}void range_apply(int L, int R, F f, int i, int l, int r){eval(i);if (r <= L || R <= l){return;} else if (L <= l && r <= R){lazy[i] = f;eval(i);} else {int m = (l + r) / 2;range_apply(L, R, f, i * 2 + 1, l, m);range_apply(L, R, f, i * 2 + 2, m, r);ST[i] = op(ST[i * 2 + 1], ST[i * 2 + 2]);}}void range_apply(int L, int R, F f){range_apply(L, R, f, 0, 0, N);}T range_fold(int L, int R, int i, int l, int r){eval(i);if (r <= L || R <= l){return E;} else if (L <= l && r > N >> K;vector P(N);for (int i = 0; i > P[i];P[i]--;}stack st1, st2;st1.push(-1);st2.push(-1);vector A(N, 0);lazy_segment_tree ST(A, op, mp, comp, monoid(INF), 0);long long ans = 0;for (int i = 0; i  P[a]){st1.pop();int b = st1.top();ST.range_apply(b + 1, a + 1, P[i] - P[a]);} else {break;}}while (st2.top() != -1){int a = st2.top();if (P[i] < P[a]){st2.pop();int b = st2.top();ST.range_apply(b + 1, a + 1, P[a] - P[i]);} else {break;}}st1.push(i);st2.push(i);monoid res = ST.range_fold(0, i + 1);for (int j = 0; j < 4; j++){if (res.X[j].first <= K){ans += res.X[j].second;}}ST.range_apply(0, i + 1, -1);}cout << ans << endl;}