“范式杯”2023牛客暑期多校训练营1 A Almost Correct 题意 给定一个 010101 串 sss,长度为 nnn。要求构造一个长度不超过 120120120 的排序网络,使得该网络恰好能排序除给定串以外的所有长度为 nnn 的 010101 串。保证 sss 是未排序的。 其中,排序网络指的是数组 {(x1,y1),(x2,y2),⋯ ,(xm,ym)}\{(x_1,y_1),(x_2,y_2),\cdots,(x_ 2023-08-21 ACM #构造 #2023牛客多校
AtCoder Beginner Contest 315 https://atcoder.jp/contests/abc315 F - Shortcuts 题意 有一场比赛,nnn 个点标。参赛者需要按序通过这些点标,但可以选择跳过这些点标。点标 111 和点标 nnn 不能被跳过,此外,若跳过了 ccc 个点标,则需要增加 2c−12^{c-1}2c−1 罚时(c>0c>0c>0)。参赛者的比赛用时为行走路径距离加上罚时,求最小用时。 2023-08-21 ACM #dp #exgcd
Educational Codeforces Round 153 (Rated for Div. 2) https://codeforces.com/contest/1860 D. Balanced String 题意 给定一个 010101 串 sss。每次操作可以交换两个元素,求最小操作次数,使得 sss 中 010101 子序列个数和 101010 子序列个数相等。保证可以通过操作使得 sss 合法。 数据范围:3≤∣s∣≤1003\leq |s|\leq 1003≤∣s∣≤100。 题解 一 2023-08-21 ACM #dp #最短路
Educational Codeforces Round 152 (Rated for Div. 2) https://codeforces.com/contest/1849 C. Binary String Copying 题意 给出一个长度为 nnn 的 010101 串 sss 和 mmm 个相同的拷贝 t1,t2,⋯ ,tmt_1,t_2,\cdots,t_mt1,t2,⋯,tm。有 mmm 个操作,第 iii 个操作 [li,ri][l_i,r_i][li,ri] 表示将 tit 2023-08-16 ACM #dp #线段树 #最小异或生成树
The 2023 Guangdong Provincial Collegiate Programming Contest https://codeforces.com/gym/104369 B. Base Station Construction 题意 现在需要在点 1,2,⋯ ,n1,2,\cdots,n1,2,⋯,n 上建设基站,在点 iii 建设基站的费用为 aia_iai。有 mmm 个要求,每个要求为区间 [li,ri][l_i,r_i][li,ri] 内至少有一个基站。问最小费用是多少。 题解 如果 2023-08-13 ACM
The 13th Shandong ICPC Provincial Collegiate Programming Contest https://codeforces.com/gym/104417 B. Building Company 题意 有一家建筑公司,一开始你有 ggg 种员工。第 iii 种员工编号为 tit_iti,有 uiu_iui 个。一共有 nnn 项任务,第 iii 项任务有 mim_imi 个指标,第 jjj 个指标需要编号为 ai,ja_{i,j}ai,j 的员工至少有 bi,jb_{i,j} 2023-08-10 ACM
2023 (ICPC) Jiangxi Provincial Contest -- Official Contest https://codeforces.com/gym/104385 D. Stack Out 题意 有 nnn 个数,每次可以将第一个数入栈,或者将栈顶元素出栈。求最大连续出栈次数不小于 kkk 的方案数。 题解 我们这样考虑,每当一个元素压入栈以后,紧跟着就是出栈操作(可能是 000 次),这样每次可能的出栈操作次数只与当前栈内的元素个数有关,由此可以设计状态进行dp。 设 fi,j,0/1f_ 2023-08-10 ACM #dp #2023省赛
Codeforces Round 887 (Div. 2) https://codeforces.com/contest/1853 E. Ina of the Mountain 题意 给出一个长度为 nnn 的数组 aaa,满足 1≤ai≤k1\leq a_i\leq k1≤ai≤k。每次操作可以选定一个区间 [l,r][l,r][l,r],让其中所有的数减 111。当一个数变成 000 后,它会立刻变成 kkk。求最少需要多少次操作,才能让所有的数都变 2023-08-09 ACM #反悔贪心
网络流 网络流简介 网络 网络是指一个有向图 G=(V,E)G=(V,E)G=(V,E) 。 每条边 (u,v)∈E(u,v)\in E(u,v)∈E 都有一个权值 c(u,v)c(u,v)c(u,v) ,称之为容量。当 (u,v)∉E(u,v)\notin E(u,v)∈/E 时有 c(u,v)=0c(u,v)=0c(u,v)=0 。 其中有两个特殊的点:源点 s∈Vs\in Vs∈V 和汇点 t∈V, 2023-08-06 ACM #网络流
网络流2.0 一些网络流的常见建模方法: 拆点:Luogu P1402 酒店之王、Luogu P2053 [SCOI2007] 修车、HDU7298 Coin 二分图最小点覆盖:UVA11419 SAM I AM 染色法:Luogu P2774 方格取数问题、Luogu P3355 骑士共存问题、Luogu P5030 长脖子鹿放置 划分问题:Luogu P4313 文理分科 平面图最小割转对偶图最短路:Lu 2023-08-06 ACM #网络流