AtCoder-ABC415 真题直播解析预告
AtCoder （ABC 414）于上周六晚20:00进行，周日晚 19:00我们在B站进行了AtCoder Beginner Contest 414的题解直播讲解，以下为本次直播讲解内容及文字解析。
AtCoder （ABC 415）将于今天晚上20:00进行，周日晚 19:00我们在B站进行了AtCoder Beginner Contest 415的题解直播讲解，请同学们关注。
ABC414主讲老师：清华大学 吴老师（NOI2021银牌）
ABC415主讲老师：清华 殷老师（NOI2019银牌）
欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）
ABC414比赛真题讲解
题目列表：
题目地址：https://atcoder.jp/contests/abc414/tasks
ABC413题解及参考程序（文字版）
========================================
A
intmain{ intn,L,R; scanf( "%d%d%d",&n,&L,&R); intans = 0; for( inti = 1;i <= n;++i){ intl,r; scanf( "%d%d",&l,&r); if(l <= L && R <= r){ ans++;}}printf( "%d\n",ans); return0;}
B
charS[ 105]; intm; // 此刻 S 的长度是多少intn;
intmain{ scanf( "%d",&n); for( inti = 1;i <= n;++i){ charstr[ 23]; longlong l;scanf( "%s%lld",str,&l); charc = str[ 0]; if(m+l > 100){ puts( "Too Long"); return0;}while(l--) S[++m] = c; }for( inti = 1;i <= m;++i) putchar(S[i]); puts( "");
return0;}
C
#defineLL long longusingnamespacestd;intA; LL N;
boolcheck(LL x){ // 检测 x 是否是 A 进制下的回文数vector< int> digits; while(x){ digits. push_back(x%A); x /= A;}intm = digits. size; for( inti = 0;i <= (m -1)/ 2;++i){ if(digits[i] != digits[m -1-i]) returnfalse; }returntrue;}
LL get_pali(intx,intodd){ // x 是前一半，是否要奇数长度vector< int> digits; while(x) digits. push_back(x% 10),x /= 10; longlong res = 0; intm = digits. size; for( inti = m -1;i >= 0;--i) res = res * 10+ digits[i]; for( inti = odd;i <= m -1;++i) res = res * 10+ digits[i]; returnres; }
intmain{ scanf( "%d%lld",&A,&N); // 偶数长度longlong ans = 0; for( intx = 1;;x++){ longlong pali = get_pali(x, 0); if(pali > N) break; if( check(pali)) ans += pali; }// 奇数长度for( intx = 1;;x++){ longlong pali = get_pali(x, 1); if(pali > N) break; if( check(pali)) ans += pali; }printf( "%lld\n",ans); return0;}
D
#define LL long longusingnamespacestd;intn,m; constint MAXN = 5e5 + 5; LL x[MAXN];
intmain{scanf( "%d%d",&n,&m); for( inti = 1;i <= n;++i) scanf( "%lld", x+i); sort( x+ 1, x+n+ 1); vector
E
intmain{LL n;scanf( "%lld",&n); intpart1 = 1ll*(n%mod)*((n+ 1)%mod)%mod*inv2%mod; intpart2 = 0; for(LL l = 1,r;l <= n;l = r+ 1){ //遍历了所有可能的值 // 相同的值只访问一次// [n/i] 只有不超过 2sqrt(n) 个 r = n / (n / l);intlen = (r-l+ 1)%mod; intval = (n/l)%mod; (part2 += 1ll*len * val % mod) %= mod; }intans = (part1 - part2 + mod) % mod; printf( "%d\n",ans); return0; }
F
structEdge{intto,nxt; }e[MAXN<< 1]; inthead[MAXN], cnt; intn,K;
voidadd( intu, intv){ e[++cnt] = (Edge){v,head[u]};head[u] = cnt;e[++cnt] = (Edge){u,head[v]};head[v] = cnt;}
intf[MAXN<< 1][MAXK],ans[MAXN]; intvis[MAXN][MAXK]; // f[i][j]: 上一步走的是第i条边(u->v)，走完了第j步
inlinevoidSolve{ scanf( "%d%d",&n,&K); for( inti = 1;i <= n;++i){ head[i] = 0; ans[i] = 1e9; for( intj = 0;j <= K;++j) vis[i][j] = 0; }cnt = 1; for( inti = 1;i < n;++i){ intu,v; scanf( "%d%d",&u,&v); add(u,v); }for( inti = 1;i <= cnt;++i){ for( intj = 0;j <= K;++j) f[i][j] = -1; }
queue
intmain{ intT; scanf( "%d",&T); while(T--) Solve; return0;}
G
#defineLL long longconstint MAXN = 6e5+ 5;
intlc[MAXN], rc[MAXN]; inttot; // 1~n: 叶子编号vector
voidadd( intu, intv,LL w){ G[u]. push_back({v, w}); }LL p[MAXN];// s: 上车 t: 下车// l: 靠左 r: 靠右intrt_sl, rt_sr, rt_tl, rt_tr;
voidbuild( int&x, intl, intr, intup, intleft){ // up=1: 子 -> 父// up=0: 父 -> 子// left=1: 靠左// left=0: 靠右if(l == r){ x = l; // 所有线段树的叶子节点共享return; }if(!x) x = ++tot; intmid = (l + r) >> 1; build(lc[x], l, mid, up, left); build(rc[x], mid+ 1, r, up, left); if(left){ if(up){ add(lc[x], x, 0); add(rc[x], x, p[mid+ 1]-p[l]); }else{ add(x, lc[x], 0); add(x, rc[x], p[mid+ 1]-p[l]); }}else{ if(up){ add(lc[x], x, p[r]-p[mid]); add(rc[x], x, 0); }else{ add(x, lc[x], p[r]-p[mid]); add(x, rc[x], 0); }}}
structNode{intl,r,x; };
voidgetseg( intx, intl, intr, intL, intR,vector
LL dis[MAXN];boolused[MAXN];
voiddij{ for( inti = 1;i <= tot;++i) dis[i] = 1e18; priority_queue
intn,m;
intmain{ scanf( "%d%d",&n,&m); for( inti = 1;i <= n;++i) scanf( "%lld", &p[i]); tot = n;build(rt_sr, 1, n, 1, 0); build(rt_sl, 1, n, 1, 1); build(rt_tr, 1, n, 0, 0); build(rt_tl, 1, n, 0, 1);
for( inti = 1;i <= m;++i){ intl,r,L,R;LL c; scanf( "%d%d%d%d%lld",&l,&r,&L,&R,&c); vector
题库地址：https://atcoder.jp
针对每周六20:00举办的ABC比赛，我们每周日都会对比赛直播。