AtCoder-ABC410真题解析报告
AtCoder （ABC 410）于周六晚20:00进行，上周日 19:00我们在B站进行了AtCoder Beginner Contest 408的题解直播讲解，以下为本次直播讲解内容及文字解析。
AtCoder （ABC 411）于下6月21日晚20:00进行，6月22日19:00我们将继续进行视频直播讲解。同学们关注！
ABC410主讲老师：清华 吴老师（NOI2021银牌）
欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）
ABC410比赛真题讲解
题目列表：
题目地址：https://atcoder.jp/contests/abc410/tasks
ABC410题解及参考程序（文字版）
========================================
A
constintMAXN = 100+ 5; intn,a[MAXN],k;
intmain{ scanf( "%d",&n); for( inti = 1;i <= n;++i) scanf( "%d",a+i); scanf( "%d",&k); intans = 0; for( inti = 1;i <= n;++i){ if(k <= a[i]) ++ans; // k 可以参加第i场比赛}printf( "%d\n",ans); return0; }
B
constintMAXN = 100+ 5; intn,a[MAXN],q;
intmain{ scanf( "%d%d",&n,&q);a[ 0] = 1e9; while(q--){ intx; scanf( "%d",&x); if(x > 0){ printf( "%d ",x); ++a[x];}else{ intps = 0; // 最小的位置for( inti = 1;i <= n;++i){ if(a[i] < a[ps]) ps = i; }printf( "%d ",ps); ++a[ps];}}return0; }
B2
constintMAXN = 1e5+ 5;
set< pair< int, int> > S; inta[MAXN]; intn,q;
intmain{ scanf( "%d%d",&n,&q); for( inti = 1;i <= n;++i) S.insert({a[i],i}); while(q--){ intx; scanf( "%d",&x); if(x > 0){ S.erase(S.find({a[x],x}));++a[x];S.insert({a[x],x});printf( "%d ",x); }else{ intps = (*S.begin).second; S.erase(S.find({a[ps],ps}));++a[ps];S.insert({a[ps],ps});printf( "%d ",ps); }}return0; }
C
constintMAXN = 1e6+ 5; intn,q; inta[MAXN]; intps;
intmain{ scanf( "%d%d",&n,&q); for( inti = 0;i < n;++i) a[i] = i+ 1; while(q--){ intop; scanf( "%d",&op); if(op == 1){ intp,x; scanf( "%d%d",&p,&x);--p; (p += ps) %= n;a[p] = x;}elseif(op == 2){ intp; scanf( "%d",&p);--p; (p += ps) %= n;printf( "%d\n",a[p]); }else{ intk; scanf( "%d",&k); (ps += k) %= n;}}return0; }
D
usingnamespacestd; constintMAXN = 1000+ 5; constintMAXM = 1024+ 5;
vector< pair< int, int> > G[MAXN];
intn,m; boolvis[MAXN][MAXM]; queue< pair< int, int> > q;
intmain{ scanf( "%d%d",&n,&m); for( inti = 1;i <= m;++i){ intu,v,w; scanf( "%d%d%d",&u,&v,&w); G[u].push_back({v,w});}
q.push({ 1, 0});vis[ 1][ 0] = 1; while(!q.empty){ auto[v, val] = q.front;q.pop; for( auto[to, x] : G[v]){ // v -> to, 边权为 x 的边// (v,val) -> (x, val ^ x)if(!vis[to][val^x]){ vis[to][val^x] = 1; q.push({to,val^x});}}}intans = -1; for( inti = 0;i < 1024;++i) if(vis[n][i]){ans = i; break;} printf( "%d\n",ans); return0; }
E
constintMAXN = 3000+ 5; intn; inth,m; inta[MAXN],b[MAXN]; intf[MAXN][MAXN]; // f[i][x]: 打[1,i]，使用 x 生命// 最少使用多少魔法
intmain{ scanf( "%d%d%d",&n,&h,&m); for( inti = 1;i <= n;++i) scanf( "%d%d",a+i,b+i); memset(f, 0x3f, sizeof(f)); f[ 0][ 0] = 0; for( inti = 1;i <= n;++i){ boolflag = 0; for( intj = 0;j <= h;++j){ f[i][j] = f[i -1][j] + b[i]; if(j >= a[i]) f[i][j] = std::min(f[i][j], f[i -1][j-a[i]]); flag |= (f[i][j] <= m);}if(flag) continue; else{ printf( "%d\n",i -1); return0;} }printf( "%d\n",n); return0; }
F
constintMAXN = 3e5+ 5; constintB = 3e5; usingnamespacestd; vector< int> a[MAXN]; intn,m; charstr[MAXN]; intv[MAXN], sm[MAXN]; intt[MAXN* 2];
voidSolve{ scanf( "%d%d",&n,&m); if(n <= m) for( inti = 1;i <= n;++i) a[i].resize(m+ 1); elsefor( inti = 1;i <= m;++i) a[i].resize(n+ 1);
for( inti = 1;i <= n;++i){ scanf( "%s",str+ 1); for( intj = 1;j <= m;++j){ into = str[j] == '#'? 1: -1; if(n <= m) a[i][j] = o; elsea[j][i] = o; }}
if(n > m) swap(n,m); longlongans = 0;
for( intup = 1;up <= n;++up){ for( intj = 1;j <= m;++j) v[j] = 0; for( intdown = up;down <= n;++down){ for( intj = 1;j <= m;++j) v[j] += a[down][j]; sm[ 0] = 0;t[sm[ 0] + B]++;
for( intj = 1;j <= m;++j){ sm[j] = sm[j -1] + v[j]; ans += t[sm[j] + B]; // sm[j]-sm[i]=0 => sm[j]=sm[i]t[sm[j]+B]++;}
for( intj = 0;j <= m;++j) t[sm[j]+B]--; }}
printf( "%lld\n",ans);
for( inti = 1;i <= n;++i) a[i].clear; }
intmain{ intT; scanf( "%d",&T); while(T--) Solve; return0; }
G
constintMAXN = 4e5+ 5; usingnamespacestd; intmx[MAXN<< 2]; #definelc ((x)<<1)#definerc ((x)<<1|1)
voidupdate(intx,intl,intr,intp,intd){ if(l == r){ mx[x] = d;return; }intmid = (l + r) >> 1; if(p <= mid) update(lc,l,mid,p,d); elseupdate(rc,mid+ 1,r,p,d); mx[x] = max(mx[lc], mx[rc]);}
intquery(intx,intl,intr,intL,intR){ if(l == L && r == R) returnmx[x]; intmid = (l + r) >> 1; if(R <= mid) returnquery(lc,l,mid,L,R); elseif(L > mid) returnquery(rc,mid+ 1,r,L,R); elsereturnstd::max(query(lc,l,mid,L,mid),query(rc,mid+ 1,r,mid+ 1,R)); }
vector< pair< int, int> > vec; intn; intans[MAXN];
intmain{ scanf( "%d",&n); for( inti = 1;i <= n;++i){ inta,b; scanf( "%d%d",&a,&b); if(a > b) swap(a, b); vec.push_back({b,a});}sort(vec.begin, vec.end);
for( inti = 0;i < vec.size;++i){ auto[r,l] = vec[i]; ans[i] = query( 1, 1, 2*n,l, 2*n) + 1; update( 1, 1, 2*n,l,ans[i]); }
for( inti = 0;i < vec.size;++i){ auto[r,l] = vec[i]; ans[i] += query( 1, 1, 2*n,r, 2*n); }
intres = *max_element(ans,ans+n); printf( "%d\n",res); return0; }
G
constintMAXN = 4e5+ 5; usingnamespacestd;
template< typenameT> inlinevoidread(T &x){ x = 0; intflag = 0; charch = nc; while(! isdigit(ch)){ if(ch == '-') flag = 1; ch = nc;}while( isdigit(ch)){ x = (x<< 1) + (x<< 3) + (ch^ '0'); ch = nc;}if(flag) x = -x; }
structBIT{#definelowbit(x) ((x) & (-(x)))inttree[MAXN];
voidadd(intp,intx){ // a[p] = max(a[p],x);while(p){ tree[p] = max(tree[p], x);p -= lowbit(p);}}
intquery(intp){ intres = 0; while(p < MAXN){ res = max(res, tree[p]);p += lowbit(p);}returnres; }}bit;
vector< pair< int, int> > vec; intn; intans[MAXN];