> 文档中心 > AtCoder Beginner Contest 247 (ABC247) 题解 [A-Ex]

AtCoder Beginner Contest 247 (ABC247) 题解 [A-Ex]

请看完后点个赞,谢谢​​​​​​​

A题

247A

方法一:

直接覆盖就可以了,别忘了把第一位变成0

//AT247A 22-04-10#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);string s;cin>>s;for (int i=s.length();i>0;i--)s[i]=s[i-1];s[0]='0';cout<<s<<endl;return 0;}

方法二:(简单)

//AT247A 22-04-15#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);char a[4];cin>>a[0]>>a[1]>>a[2]>>a[3];cout<<"0"<<a[0]<<a[1]<<a[2]<<endl;return 0;}

B题

247B

这题只需要判断姓和名是否都与别人重复,如果是,直接输出No,否则继续,

到循环到最后输出Yes

//AT247B 22-04-10#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;string a[105],b[105];for (int i=1;i>a[i]>>b[i];for (int i=1;i<=n;i++){int s1=0,s2=0;for (int j=1;j<=n;j++){if (a[i]==a[j] || a[i]==b[j]) s1++;if (b[i]==a[j] || b[i]==b[j]) s2++;}if (s1!=1 && s2!=1) {cout<<"No"<<endl;return 0;}}cout<<"Yes"<<endl;return 0;}

C题

247C

方法一:

循环递归,数据超弱(n<=16)

//AT247C 22-04-10#include using namespace std;int n;int a[17][65537];int main() {ios::sync_with_stdio(0);cin.tie(0);cin>>n;memset(a,0,sizeof(a));a[1][1]=1;if (n==1){cout<<"1"<<endl;return 0;}for (int i=2;i<=n;i++){int x=pow(2,i-1);for (int j=1;j<=pow(2,i-1)-1;j++)a[i][j]=a[i-1][j];a[i][x]=i;for (int j=1;j<=pow(2,i-1)-1;j++)a[i][x+j]=a[i-1][j];}for (int i=1;i<pow(2,n);i++) cout<<a[n][i]<<" ";return 0;}

方法二:

 解释一下:

找规律得知,本题每一个位置的数,是那个位置的下标改写成二进制形式末尾0的个数+1。

而代码中那个 _builtin_ctz 就是数二进制数末尾0的数量的。

SSRS:

//AT247C 22-04-15#include using namespace std;int main(){int N;cin>>N;for (int i=1;i<(1<<N);i++){cout<<__builtin_ctz(i)+1;if (i<(1<<N)-1)cout<<" ";}cout<<endl;}

D题

247D

Rubikun:

#include using namespace std;templatebool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }templatebool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=300005,INF=1<>Q;    deque<pair> deq;    while (Q--)    { int t;cin>>t; if (t==1) {     long long x,c;cin>>x>>c;     deq.push_back(mp(x,c)); } else {     long long c;cin>>c;     long long ans=0;     while (c)     {  if (deq.front().se<=c)  {      ans+=deq.front().fi*deq.front().se;      c-=deq.front().se;      deq.pop_front();  }  else  {      ans+=deq.front().fi*c;      deq.front().se-=c;      c=0;  }     }     cout<<ans<<"\n"; }    }}

E题

247E

Rubikun:

//AT247E 22-04-16#include using namespace std;typedef long long ll;templatebool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }templatebool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=300005,INF=1<<30;vector wh[4];int main(){ std::ifstream in("text.txt");    std::cin.rdbuf(in.rdbuf());    cin.tie(0);    ios::sync_with_stdio(false);int N,X,Y;    cin>>N>>X>>Y;    vector A(N);    for(int i=0;i>A[i]; if(A[i]==X) wh[0].push_back(i); if(A[i]==Y) wh[1].push_back(i); if(A[i]>X) wh[2].push_back(i); if(A[i]<Y) wh[3].push_back(i);    }    for(int j=0;j<4;j++) wh[j].push_back(INF); long long ans=0;     for (int i=0;i<N;i++)    { int l=max(*lower_bound(all(wh[0]),i),*lower_bound(all(wh[1]),i)); int r=min(*lower_bound(all(wh[2]),i),*lower_bound(all(wh[3]),i)); chmin(r,N); r--; ans+=max(0,r-l+1);    }    cout<<ans<<"\n";}

F题

247F

rainboy:

#include #define N   200000#define MD  998244353int ff[N + 1], dp[N + 1];void init() {    int i;    ff[0] = 1, ff[1] = 1;    for (i = 2; i <= N; i++) ff[i] = (ff[i - 1] + ff[i - 2]) % MD;    for (i = 1; i <= N; i++) dp[i] = ((i == 1 ? 0 : ff[i - 2]) + ff[i]) % MD;}int main() {    static int pp[N], qq[N], aa[N];    static char visited[N];    int n, i, c, ans;    init();    scanf("%d", &n);    for (i = 0; i < n; i++) scanf("%d", &pp[i]), pp[i]--;    for (i = 0; i < n; i++) scanf("%d", &qq[i]), qq[i]--;    for (i = 0; i < n; i++) aa[pp[i]] = qq[i];    ans = 1;    for (i = 0; i < n; i++) if (!visited[i]) {     c = 0;     while (!visited[i])  c++, visited[i] = 1, i = aa[i];     ans = (long long) ans * dp[c] % MD; }    printf("%d\n", ans);    return 0;}

G题

247G

rainboy:

//AT247G 22-04-16#include #define N150#define M30000#define N_(1 + N * 2 + 1)#define M_(N * 2 + M)#define INF0x3f3f3f3f3f3f3f3fLLlong long min(long long a, long long b) { return a = 2 && (o & o - 1) == 0)eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);eh[i][o] = h;}void add(int i, int j, int c, int w) {int h = m_++;ii[h] = i, jj[h] = j, cc[h << 1 | 0] = c, ww[h] = w;append(i, h << 1 | 0), append(j, h << 1 | 1);}long long dd[N_]; int kk[N_], ff[N_], iq[N_ + 1], pq[N_], cnt;int lt(int i, int j) {return dd[i] < dd[j] || dd[i] == dd[j] && kk[i]  cnt ? 0 : (p > 1, j = i ^ ii[h] ^ jj[h];long long d = dd[i] + ((h_ & 1) == 0 ? ww_[h] : -ww_[h]);if (dd[j] > d || dd[j] == d && kk[j] > k) {if (dd[j] == INF)pq_add_last(j);dd[j] = d, kk[j] = k, ff[j] = h_, pq_up(j);}}}}return dd[t] != INF;}void trace(int s, int t) {int h, h_, i;for (i = t; i != s; i ^= ii[h] ^ jj[h]) {h_ = ff[i], h = h_ >> 1;cc[h_]--, cc[h_ ^ 1]++;}}long long xx[N]; int k;void edmonds_karp(int s, int t) {int h, i, j, w;long long d, x;memset(dd, 0x3f, N_ * sizeof *dd), dd[s] = 0;for (h = 0; h < m_; h++) {i = ii[h], j = jj[h], w = ww[h];dd[j] = min(dd[j], dd[i] + w);}d = dd[t];for (h = 0; h < m_; h++) {i = ii[h], j = jj[h], w = ww[h];if (dd[i] != INF && dd[j] != INF)ww_[h] = dd[i] + ww[h] - dd[j];}k = 0, x = 0;while (dijkstra(s, t)) {trace(s, t);xx[k++] = x += d += dd[t];for (h = 0; h < m_; h++) {i = ii[h], j = jj[h], w = ww[h];if (dd[i] != INF && dd[j] != INF)ww_[h] += dd[i] - dd[j];}}}int main() {int m, h, i, s, t;scanf("%d", &m);s = N_ - 2, t = N_ - 1;for (i = 0; i < N_; i++)eh[i] = (int *) malloc(2 * sizeof *eh[i]);for (i = 0; i < N; i++)add(s, i, 1, 0);for (h = 0; h < m; h++) {int a, b, c;scanf("%d%d%d", &a, &b, &c), a--, b--;add(a, N + b, 1, -c);}for (i = 0; i < N; i++)add(N + i, t, 1, 0);edmonds_karp(s, t);printf("%d\n", k);for (h = 0; h < k; h++)printf("%lld\n", -xx[h]);return 0;}

Ex题/H题

247EX/247H

​​​​​​​rainboy:

//AT247Ex 22-04-16#include #define N200000#define L18/* L = ceil(log2(N + 1)) */#define N_(1 < b ? a : b; }int vv_[L + 1], *wwu[L + 1], *wwv[L + 1];long long power(long long a, int k) {long long p = 1;while (k) {if (k & 1)p = p * a % MD;a = a * a % MD;k >>= 1;}return p;}void init() {int i, l, u, v;u = power(3, MD - 1 >> L), v = power(u, MD - 2);for (l = L; l > 0; l--) {int n = 1 <> 1;wwu[l] = (int *) malloc(m * sizeof *wwu[l]);wwv[l] = (int *) malloc(m * sizeof *wwv[l]);wwu[l][0] = wwv[l][0] = 1;for (i = 1; i < m; i++) {wwu[l][i] = (long long) wwu[l][i - 1] * u % MD;wwv[l][i] = (long long) wwv[l][i - 1] * v % MD;}vv_[l] = power(1 << l, MD - 2);u = (long long) u * u % MD, v = (long long) v * v % MD;}vv_[0] = 1;}void ntt_(int *aa, int l, int inverse) {if (l) {int n = 1 <> 1, *ww = inverse ? wwv[l] : wwu[l], i, j;ntt_(aa, l - 1, inverse), ntt_(aa + m, l - 1, inverse);for (i = 0; (j = i + m) = MD)aa[i] -= MD;if ((aa[j] = a - b) < 0)aa[j] += MD;}}}void ntt(int *aa, int l, int inverse) {int n = 1 << l, i, j;for (i = 0, j = 1; j > 1, tmp;while ((i ^= b) >= 1;if (i < j)tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;}ntt_(aa, l, inverse);}void multiply(int *aa, int n, int *bb, int m, int *cc) {static int aa_[N_], bb_[N_];int n_, l_, i;l_ = 0;while (1 << l_ < n + m - 1)l_++;n_ = 1 << l_;for (i = 0; i < n_; i++) {aa_[i] = i < n ? aa[i] : 0;bb_[i] = i < m ? bb[i] : 0;}ntt(aa_, l_, 0), ntt(bb_, l_, 0);for (i = 0; i < n_; i++)aa_[i] = (long long) aa_[i] * bb_[i] % MD;ntt(aa_, l_, 1);for (i = 0; i < n + m - 1; i++)cc[i] = (long long) aa_[i] * vv_[l_] % MD;}int main() {static int cc[N + 1], *pp[N * 2], nn[N * 2];int n, m, i, ans, head, cnt;init();scanf("%d%d", &n, &m);head = cnt = 0;for (i = 0; i = 2) {pp[head + cnt] = malloc((nn[head + cnt] = nn[head] + nn[head + 1] - 1) * sizeof *pp[head + cnt]);multiply(pp[head], nn[head], pp[head + 1], nn[head + 1], pp[head + cnt]);head += 2, cnt--;}ans = 0;for (i = max(n - m, (n + m) % 2); i <= n; i += 2)ans = (ans + pp[head][i]) % MD;printf("%d\n", ans);return 0;}

有其它思路或更简单做法的欢迎发往评论区