c4Lnn-CSDN博客

原创 POJ 2886. Who Gets the Most Candies?

链接http://poj.org/problem?id=2886题意nnn 个点的环，从第 kkk 个点开始如下操作：将当前点弹出从当前位置顺时针移动 xix_ixi 个单位设不超过 nnn 的最大反素数为 AAA，求第 AAA 个弹出的点。思路DFS 找出最大反素数，对于每个点 010101 表示是否在环中，前缀和就是当前环中人数。每次二分前缀和找当前要弹出的点，前缀和用树状数组维护。代码#include <cstdio>#include <algorit

2021-04-07 21:59:39 146 1

原创 HDU 1890. Robotic Sort

题意对于序列中第 iii 大的数，其在序列中位置为 posipos_iposi，翻转区间 [i,posi][i,pos_i][i,posi]，最终使序列升序排列。对于一样大的数，在初始序列中下标较小的定义为较小的那一个。思路用平衡树维护区间翻转，先对下标建树。对于翻转操作，记当前要翻转第 iii 大的数，将 iii 上旋至树根，给左子树打上翻转标记，然后将树根删除。代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()

2021-04-02 15:07:40 124

原创 POJ 2828. Buy Tickets

链接http://poj.org/problem?id=2828题意有 NNN 个人排队，每一个人都有一个权值 valvalval ，每一个人都会按顺序插入到当前队伍的某一个位置 pospospos。要求按队伍最后顺序输出权值。思路从最后一个操作开始插入，每次插入即为最终位置，在插入的位置前还要留 pospospos 个空位子。用树状数组维护空位子，二分查找插入位置。代码#include <cstdio>#include <iostream>using name

2021-03-31 17:09:55 132

原创 HDU 2243. 考研路茫茫——单词情结

链接http://acm.hdu.edu.cn/showproblem.php?pid=2243题意字符集为小写字母，有 nnn (n<6)(n<6)(n<6) 个模式串，长度不超过 555，求长度不超过 mmm (m<231)(m<2^{31})(m<231) 至少包含一个模式串的字符串个数。思路先求长度不超过 mmm 不包含模式串的字符串个数。记 fif_ifi 为长度不超过 iii 的字符串个数：fi=fi−1∗26+26f_i=f_{i-1}*26+

2021-03-23 22:53:24 106

原创 POJ 2778. DNA Sequence

链接http://poj.org/problem?id=2778题意有 mmm (m≤10)(m\le10)(m≤10) 个长度小于等于 101010 的模式串，求长度为 nnn 且不包含这些模式串的字符串有多少个？思路[dpi,0dpi,1⋯dpi,k]=[dpi−1,0dpi−1,1⋯dpi−1,k]∗[a0,0a0,1⋯a0,k⋮⋮⋱⋮ak,0ak,1⋯ak,k]=[a0,0a0,1⋯a0,k⋮⋮⋱⋮ak,0ak,1⋯ak,k]2\begin{bmatrix}dp_{i,0} &

2021-03-22 22:58:59 139

原创 AtCoder Beginner Contest 195 F. Coprime Present

链接https://atcoder.jp/contests/abc195/tasks/abc195_f题意从 [a,b][a,b][a,b] (b−a≤72)(b-a\le 72)(b−a≤72)区间内找出不同的数构成一个升序序列，序列中任意两数都互质，求这样不同的序列有多少个。思路gcd⁡(n,m)=gcd⁡(n,n−m)≤n−m\gcd(n,m)=\gcd(n,n-m)\le n-mgcd(n,m)=gcd(n,n−m)≤n−m (n≤m)(n\le m)(n≤m)因为 b−a≤72b-a\

2021-03-22 20:21:29 326

原创 2019 ICPC North American Qualifier Contest I. Slow Leak

链接https://ac.nowcoder.com/acm/contest/13168/I题意nnn 个点 mmm 条无方向边，有 ttt 个加油站，当移动距离大于 ddd 则将油耗尽，无法移动，求从点 111 走到点 nnn 的最短距离。思路先用 floyd 更新两点之间最短距离，再重新建新图，若加油站，111，nnn 之间最短距离小于等于ddd，则加一条边，跑 dijkstra 求出答案。代码#include <bits/stdc++.h>#define SZ(x) (int

2021-03-22 18:57:33 159

原创 2019 ICPC North American Qualifier Contest G. Research Productivity Index

链接https://ac.nowcoder.com/acm/contest/13168/G题意有 nnn 篇文章，第 iii 篇文章中的概率为 aia_iai，定义 iii 篇文章中 jjj 篇的生产指数为 jj/ij^{j/i}jj/i。现在可以自己选择投哪几篇文章，求生产指数的最大期望。思路记 fi,jf_{i,j}fi,j 为 iii 篇文章中 jjj 篇的生产指数，pi,jp_{i,j}pi,j 为 iii 篇文章中 jjj 篇的概率，期望 Ei=∑j=1ifi,jpi,jE_{

2021-03-22 16:06:30 160

原创 AtCoder Beginner Contest 195 E. Lucky 7 Battle

链接https://atcoder.jp/contests/abc195/tasks/abc195_e题意字符串 SSS 只包含数字，字符串 XXX 只包含 A 和 T，字符串 T 是空串。当 XiX_iXi 为 A 时，Aoki 操作，否则 Takahashi 操作。每次操作可将 000 或 SiS_iSi 放在 TTT 末尾。如果 TTT 是 777 的倍数则 Takahashi 获胜，否则 Aoki 获胜。思路记 dpi,jdp_{i,j}dpi,j 为在 iii 个回合后余数为

2021-03-20 16:31:01 274 1

原创 AtCoder Beginner Contest 145 F. Laminate

链接https://atcoder.jp/contests/abc145/tasks/abc145_f题意n∗mn*mn∗m 的二维白色网格，HiH_iHi 表示第 iii 列底端往上 HiH_iHi 格需涂成黑色。每次操作可以选择一段水平方向连续的网格涂黑。现在可以至多改变 kkk 列的 HHH 值，求最小操作数使需涂黑的网格涂黑。思路记 dpi,j,0/1dp_{i,j,0/1}dpi,j,0/1 为前 iii 列改变了 jjj 列的 HHH 值且第 iii 列是否改变的最小操作数：

2021-03-20 16:20:07 169

原创 AtCoder Beginner Contest 194 F. Digits Paradise in Hexadecimal

链接https://atcoder.jp/contests/abc194/tasks/abc194_f题意求 1∼n1 \sim n1∼n 中十六进制表示中严格有 kkk 个不同的数的个数（不包含前导 000）思路数位 DP记录当前位之前存在几个不同的数即可因为假如当前位之前不同的数不一样，但是当前位及之后可以的方案数是一样的代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).b

2021-03-15 11:41:20 112

原创 AtCoder Beginner Contest 194 E. Mex Min

链接https://atcoder.jp/contests/abc194/tasks/abc194_e题意定义 mex(x1,x2,…,xk)mex(x_1,x_2,\dots,x_k)mex(x1,x2,…,xk) 为在 x1,x2,…,xkx_1,x_2,\dots,x_kx1,x2,…,xk 中未出现的最小自然数求 min⁡i=0n−m[mex(ai+1,ai+2,…,ai+m)]\min_{i=0}^{n-m}{[mex(a_{i+1},a_{i+2},\dots,a_{i+m}

2021-03-13 21:54:56 236

原创 2021年度训练联盟热身训练赛第一场 I. Full Depth Morning Show

链接https://ac.nowcoder.com/acm/contest/12606/I题意树上对于任意节点 uuu 求 ∑v=1n[du,v∗(tu+tv)]\sum_{v=1}^{n}{[d_{u,v}*(t_u+t_v)]}∑v=1n[du,v∗(tu+tv)]思路换根 DP记 resu=∑v=1n[du,v∗(tu+tv)]res_u=\sum_{v=1}^{n}{[d_{u,v}*(t_u+t_v)]}resu=∑v=1n[du,v∗(tu+tv)]resu=∑v

2021-03-10 21:00:10 126

原创 2021牛客寒假算法基础集训营6 H. 动态最小生成树

链接https://ac.nowcoder.com/acm/contest/9986/H题意有一张 nnn 个点 mmm 条边的图，每条边连接点 ui,viu_i,v_iui,vi，边权为 wiw_iwi。他想进行 qqq 次操作，有如下两种类型：修改第 xxx 条边为连接点 y,zy,zy,z，边权为 ttt；查询只用编号在 [l,r][l,r][l,r] 范围内的边，得到的最小生成树权值是多少。1≤n≤200,1≤m≤30000,1≤q≤30000,1≤ui,vi≤n,1≤wi≤1

2021-02-27 15:00:33 139

原创 LibreOJ 6010.「网络流 24 题」数字梯形

链接https://loj.ac/p/6010题意给定一个由 nnn 行数字组成的数字梯形如下方所示。梯形的第一行有 mmm 个数字。从梯形的顶部的 mmm 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形的顶至底的 mmm 条路径互不相交；从梯形的顶至底的 mmm 条路径仅在数字结点处相交；从梯形的顶至底的 mmm 条路径允许在数字结点相交或边相交。思路点和边都只能经过一次点能经过无限次，边只能经过一次点和边都能经过无限

2021-02-25 19:03:40 116

原创 LibreOJ 6122.「网络流 24 题」航空路线问题

链接https://loj.ac/p/6122题意给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。除起点城市外，任何城市只能访问一次。对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。思路找两条从最西端飞到最东端的路径，这两条路径除了起点和终点没有重合点将每个点拆成两个点，起点和终点拆成的两个点之间

2021-02-24 00:24:16 583

原创 2021牛客寒假算法基础集训营5 B. 比武招亲（上）

链接https://ac.nowcoder.com/acm/contest/9985/B题意给定 n,mn,mn,m，定义一种序列，构造方法如下：在 [1,n][1,n][1,n] 中任意选择 mmm 次，得到了 mmm 个整数（显然数字可能相同）;将选出的 mmm 个数字排序之后得到一个序列 {a1,a2,...,am}\{ a_{1},a_{2},...,a_{m} \}{a1,a2,...,am}定义一个序列的贡献为 max⁡{a1,a2,...,am}−min⁡{a1,

2021-02-22 23:18:39 167

原创 LibreOJ 6014.「网络流 24 题」最长 k 可重区间集

链接https://loj.ac/p/6014题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondusing namespace std;ty

2021-02-21 23:02:00 85

原创 2021牛客寒假算法基础集训营4 F. 魏迟燕的自走棋

链接https://ac.nowcoder.com/acm/contest/9984/F题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondus

2021-02-21 19:58:19 129

原创 2021牛客寒假算法基础集训营4 G. 九峰与蛇形填数

链接题意思路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondusing namespace std;typedef double DB;typed

2021-02-21 15:30:24 109

原创 LibreOJ 6226.「网络流 24 题」骑士共存问题

链接https://loj.ac/p/6226题意在一个 n∗nn*nn∗n 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。对于给定的 n∗nn*nn∗n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。思路二分图最大独立集模拟一下可以发现棋盘可以根据行列和的奇偶性染色然后求出最大匹配，二分图最大独立集 = 点数 - 最大匹配代码#include <bits/stdc++.h>

2021-02-19 20:40:26 212

原创 2021牛客寒假算法基础集训营1 H. 幂塔个位数的计算

链接https://ac.nowcoder.com/acm/contest/9981/H题意求底数为 aaa，层数 nnn 为的幂塔的个位数（1≤a,n≤101000001\le a,n\le10^{100000}1≤a,n≤10100000）思路答案为 (a↑↑n)%10(a\uparrow\uparrow n)\%10(a↑↑n)%10，考虑扩展欧拉定理降幂因为 φ(10)=4,φ(4)=2,φ(2)=1\varphi(10)=4,\varphi(4)=2,\varphi(2)=1φ(10)

2021-02-18 21:42:54 124

原创 LibreOJ 6223.「网络流 24 题」汽车加油行驶问题

链接https://loj.ac/p/6223题意给定一个 N∗NN*NN∗N 的方形网格，设其左上角为起点，坐标为 (1,1)(1,1)(1,1)，XXX 轴向右为正，YYY 轴向下为正，每个方格边长为 111。一辆汽车从起点出发驶向右下角终点，其坐标为 (N,N)(N,N)(N,N) 。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:汽车只能沿网格边行驶，装满油后能行驶 KKK 条网格边。出发时汽车已装满油，在起点与终点处不设油库。汽车经过一条

2021-02-18 16:49:03 1029

原创 LibreOJ 6008.「网络流 24 题」餐巾计划

链接https://loj.ac/p/6008题意一个餐厅在相继的 nnn 天里，每天需用的餐巾数不尽相同。假设第 iii 天需要 rir_iri 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 PPP 分；或者把旧餐巾送到快洗部，洗一块需 MMM 天，其费用为 FFF 分；或者送到慢洗部，洗一块需 NNN 天，其费用为 SSS 分(S<F)(S<F)(S<F)。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐

2021-02-18 12:37:11 75

原创 LibreOJ 6121.「网络流 24 题」孤岛营救问题

链接https://loj.ac/p/6121题意n∗mn*mn∗m 的矩阵中，求 (1,1)(1,1)(1,1) 走到 (n,m)(n,m)(n,m) 的最短路，每次可上下左右移动一个单位相邻两格中间可能有一扇 gig_igi 类门或者有一堵墙或者无障碍有 sss 把钥匙，位于 (xj,yj)(x_j,y_j)(xj,yj) 第 jjj 把钥匙能打开 qiq_iqi 类门思路记录路径上获得的钥匙状态，bfs 找最短路代码#include <bits/stdc++.h>

2021-02-18 00:59:50 115

原创 2021牛客寒假算法基础集训营3 B. 内卷

链接https://ac.nowcoder.com/acm/contest/9983/B题意每个人有 ABCDE 五个等级的预期分数，学校要求得到等级 A 的人不超过 kkk 个给每个人安排一个预期分数，求他们的预期分数最大值和最小值之差最小为多少思路将 5n5n5n 个分数从小到大排序保证尺取区间内有 nnn 个不同的同学以及取等第 A 的学生不大于 kkk 个即可代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()

2021-02-10 01:54:33 79

原创 2021牛客寒假算法基础集训营3 A. 模数的世界

{(p−1)k1%p=a(p−1)k2%p=b\begin{cases}(p-1)k_1\%p=a \\(p-1)k_2\%p=b\end{cases}{(p−1)k1%p=a(p−1)k2%p=b可推出可行解： {k1=t1p−ak2=t2p−b(t1,t2≥1)\begin{cases}k_1=t_1p-a \\k_2=t_2p-b\end{cases}(t1,t2 \ge 1){k1=t1p−ak2=t2p−b(t1,t2≥1)要保证 k1,k2k_1,k_2k1,k

2021-02-09 20:29:02 105 1

原创 The 2019 ICPC Asia Shanghai Regional Contest H. Tree Partition

链接https://ac.nowcoder.com/acm/contest/4370/H题意将一个 nnn 个节点的点权树切为 kkk 个树，使每棵树的点权和的最大值最小思路二分答案记 fif_ifi 为节点 iii 与子树权值和从叶子节点向上考虑，如果 fif_ifi 大于答案，则将子节点按照 fff 从大到小切，直到 fif_ifi 小于等于答案如果切了小于 kkk 次，则该答案成立代码#include <bits/stdc++.h>#define SZ(x) (

2021-02-09 00:31:57 149

原创 LibreOJ 10173.「一本通 5.4 练习 2」炮兵阵地

#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define EB emplace_back#define MP make_pair#define FI first#define SE secondusing namespace std;typedef double DB;typedef long doub

2021-02-07 22:52:20 127

原创 2021牛客寒假算法基础集训营3 E. 买礼物

链接https://ac.nowcoder.com/acm/contest/9983/E题意带修改询问区间内是否有相同的数思路记录每个点的与他相同值的前驱和后继删除相当于链表删除操作询问区间内是否有某点的前驱大于等于区间左端，线段树维护代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#define PB push_back#define

2021-02-07 18:37:08 106 1

原创 Codeforces Beta Round #51 D. Beautiful numbers

链接https://codeforces.com/contest/55/problem/D题意T(1≤t≤10)T(1\le t \le 10)T(1≤t≤10) 次询问，求[l,r](1≤l≤r≤9e18)[l,r](1 \le l \le r \le 9e18)[l,r](1≤l≤r≤9e18) 内多少数能被其自身每位非零数字整除思路数位 DP若一个数能被其自身每位非零数字整除，那么其必能被其每位非零数字的最小公倍数整除离散化所有最小公倍数，总数不超过 505050 个如果枚举最小公倍数

2021-02-07 17:34:04 68

原创第 45 届国际大学生程序设计竞赛（ICPC）亚洲网上区域赛模拟赛 D. Pokemon Ultra Sun

链接https://ac.nowcoder.com/acm/contest/8688/D题意AAA 有 hp1hp1hp1 血量，BBB 有 hp2hp2hp2 血量每个回合 AAA 会发起一次攻击，每次攻击造成 www 伤害，有 ppp 概率击中 BBB，1−p1-p1−p 概率击中自己当有一个人血量少于等于 000 时，游戏结束求回合数的期望思路记 dp[i][j]dp[i][j]dp[i][j] 为 AAA 剩 111 血量 bbb 剩 jjj 血量的回合数期望当 i=0i=0i=0

2021-02-07 17:31:03 171

原创 Codeforces Round #375 (Div. 2) E. One-Way Reform

链接https://codeforces.com/contest/723/problem/E题意将无向图转为有向图，使图中入度等于出度的点尽量多思路无向图中度数为奇数的点必定有偶数个因此我们建立一个虚点与度数为奇数的点相连，这样图中就没有度数为奇数的点了，所以图中所有连通图都存在欧拉回路代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(),(x).end()#def

2021-02-07 17:28:32 83

原创牛客练习赛74 C. CCA的矩阵

链接https://ac.nowcoder.com/acm/contest/9700/C题意一个 n×nn\times nn×n 的矩形内布满了老鼠万幸的是，你有一个 k×kk\times kk×k 的锤子，一锤子砸下去可以把它覆盖到的所有老鼠清除这个锤子只能斜着锤，对于一个 3×33\times33×3 的锤子，它能覆盖到的区域如下：- - * - -- * * * -* * * * *- * * * -- - * - -一锤子砸下去，最多能清除多少只老鼠思路将数组旋转 45∘4

2021-02-07 17:18:39 127

原创牛客练习赛74 D. CCA的图

链接https://ac.nowcoder.com/acm/contest/9700/D题意无向连通图，规定只能走权值在 [L,R][L , R][L,R] 内的边求在 L，RL，RL，R 分别等于多少时，可以顺利从 sss 到达 ttt，要求 LLL 尽可能大，在 LLL 最大的情况下 RRR 尽可能小思路从大到小枚举边，用并查集维护点之间连通关系，当 sss 与 ttt 连通时，当前边权值即为 LLL再枚举权值大于等于 LLL 的边，用同样的方法确定 RRR代码#include &lt

2021-02-07 17:17:35 98

原创牛客练习赛74 E. CCA的期望

链接https://ac.nowcoder.com/acm/contest/9700/E题意给定一张 nnn 个点 mmm 条边的无向带边权连通图，点有颜色，为黑或白，保证无自环和重边定义一次操作为：随机选择两个不同的点，将它们之间的最短路上的点全部染黑（若有多条最短路就都染黑）现在你想知道，经过 kkk 次操作后，黑色点的期望个数是多少思路用 floyd 求出每个点在多少条最短路中根据期望的线性性质对每个点的期望求和若这个点本来就是黑色的，则直接加 111否则容斥后就转化成求该点经过

2021-02-07 17:16:25 82

原创 Codeforces Round #560 (Div. 3) F2. Microtransactions (hard version)

链接https://codeforces.com/contest/1165/problem/F2题意需要购买 nnn 个物品，每个物品需要 kik_iki 个每个物品原价为 222 元，打折则为 111 元现在有 mmm 个打折信息，每个信息代表某个物品在某日打折每天能获得 111 元，求买完所有需要的物品的天数思路贪心策略：若该物品为最后一次打折日，则购买二分天数代码#include <bits/stdc++.h>#define SZ(x) (int)(x).size

2021-02-06 10:29:43 99

原创 Codeforces Round #691 (Div. 2) B. Move and Turn

链接https://codeforces.com/contest/1459/problem/B题意一个机器人可以水平或垂直移动，不能连续水平或连续垂直移动，若移动 nnn 步，能到达多少个不同的终点思路当 nnn 为偶数时水平移动 n/2n/2n/2 步，在水平方向上最多可能到达 n/2+1n/2+1n/2+1 个终点垂直移动 n/2n/2n/2 步，在垂直方向上最多可能到达 n/2+1n/2+1n/2+1 个终点组合后共有 (n/2+1)(n/2+1)(n/2+1)(n/2+1)(n/

2021-02-06 10:26:01 119

原创 Codeforces Round #691 (Div. 2) C. Row GCD

链接https://codeforces.com/contest/1459/problem/C题意已知长度为 n(1≤n≤2⋅105)n(1\le n \le 2 \cdot 10^{5})n(1≤n≤2⋅105) 的序列 a(1≤ai≤1018)a(1 \le a_i \le 10^{18})a(1≤ai≤1018) 和长度为 m(1≤m≤2⋅105)m(1\le m \le 2 \cdot 10^{5})m(1≤m≤2⋅105) 的序列 b(1≤bj≤1018)b(1 \le b_j \le 1

2021-02-06 10:25:01 54

原创 Codeforces Round #691 (Div. 2) D. Glass Half Spilled

链接https://codeforces.com/contest/1459/problem/D题意n(n≤100)n(n\le 100)n(n≤100) 个水杯，第 iii 个水杯容量为 ai(ai≤100)a_i(a_i\le 100)ai(ai≤100)，初始水量为 bi(bi≤100)b_i(b_i\le 100)bi(bi≤100)定义一次操从一个水杯取 xxx 单位水，x/2x/2x/2 单位水倒入另一个水杯（不能溢出），其余舍去求无限次操作后，选择 1∼n1 \sim n1∼

2021-02-06 10:22:57 118

空空如也

空空如也