-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
327 lines (307 loc) · 34.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>小沈のblog - 正在努力的小沈</title><meta name="author" content="正在努力的小沈"><meta name="copyright" content="正在努力的小沈"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="知识的敌人不是无知，而是已经掌握知识的幻觉。">
<meta property="og:type" content="website">
<meta property="og:title" content="小沈のblog">
<meta property="og:url" content="http://xiaoshen-qwq.github.io/index.html">
<meta property="og:site_name" content="小沈のblog">
<meta property="og:description" content="知识的敌人不是无知，而是已经掌握知识的幻觉。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cdn.luogu.com.cn/upload/usericon/852112.png">
<meta property="article:author" content="正在努力的小沈">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.luogu.com.cn/upload/usericon/852112.png"><link rel="shortcut icon" href="https://cdn.luogu.com.cn/upload/usericon/852112.png"><link rel="canonical" href="http://xiaoshen-qwq.github.io/index.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css"><script>
(() => {
const saveToLocal = {
set: (key, value, ttl) => {
if (!ttl) return
const expiry = Date.now() + ttl * 86400000
localStorage.setItem(key, JSON.stringify({ value, expiry }))
},
get: key => {
const itemStr = localStorage.getItem(key)
if (!itemStr) return undefined
const { value, expiry } = JSON.parse(itemStr)
if (Date.now() > expiry) {
localStorage.removeItem(key)
return undefined
}
return value
}
}
window.btf = {
saveToLocal,
getScript: (url, attr = {}) => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
Object.entries(attr).forEach(([key, val]) => script.setAttribute(key, val))
script.onload = script.onreadystatechange = () => {
if (!script.readyState || /loaded|complete/.test(script.readyState)) resolve()
}
script.onerror = reject
document.head.appendChild(script)
}),
getCSS: (url, id) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onload = link.onreadystatechange = () => {
if (!link.readyState || /loaded|complete/.test(link.readyState)) resolve()
}
link.onerror = reject
document.head.appendChild(link)
}),
addGlobalFn: (key, fn, name = false, parent = window) => {
if (!false && key.startsWith('pjax')) return
const globalFn = parent.globalFn || {}
globalFn[key] = globalFn[key] || {}
if (name && globalFn[key][name]) return
globalFn[key][name || Object.keys(globalFn[key]).length] = fn
parent.globalFn = globalFn
}
}
const activateDarkMode = () => {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
const activateLightMode = () => {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
btf.activateDarkMode = activateDarkMode
btf.activateLightMode = activateLightMode
const theme = saveToLocal.get('theme')
theme === 'dark' ? activateDarkMode() : theme === 'light' ? activateLightMode() : null
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
document.documentElement.classList.toggle('hide-aside', asideStatus === 'hide')
}
const detectApple = () => {
if (/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)) {
document.documentElement.classList.add('apple')
}
}
detectApple()
})()
</script><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: undefined,
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false,"highlightFullpage":false,"highlightMacStyle":true},
copy: {
success: '复制成功',
error: '复制失败',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '',
dateSuffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: {"limitCount":0,"languages":{"author":"作者: 正在努力的小沈","link":"链接: ","source":"来源: 小沈のblog","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
lightbox: 'null',
Snackbar: undefined,
infinitegrid: {
js: 'https://cdn.jsdelivr.net/npm/@egjs/infinitegrid/dist/infinitegrid.min.js',
buttonText: '加载更多'
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false,
percent: {
toc: true,
rightside: false,
},
autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: '小沈のblog',
isPost: false,
isHome: true,
isHighlightShrink: true,
isToc: false,
postUpdate: '2024-11-22 19:03:57'
}</script><meta name="generator" content="Hexo 7.3.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><script>(()=>{
const $loadingBox = document.getElementById('loading-box')
const $body = document.body
const preloader = {
endLoading: () => {
$body.style.overflow = ''
$loadingBox.classList.add('loaded')
},
initLoading: () => {
$body.style.overflow = 'hidden'
$loadingBox.classList.remove('loaded')
}
}
preloader.initLoading()
window.addEventListener('load', preloader.endLoading)
if (false) {
btf.addGlobalFn('pjaxSend', preloader.initLoading, 'preloader_init')
btf.addGlobalFn('pjaxComplete', preloader.endLoading, 'preloader_end')
}
})()</script><div class="page" id="body-wrap"><header class="full_page" id="page-header" style="background-image: url(https://t.mwm.moe/fj);"><nav id="nav"><span id="blog-info"><a class="nav-site-title" href="index.html"><span class="site-name">小沈のblog</span></a></span><div id="menus"></div></nav><div id="site-info"><h1 id="site-title">小沈のblog</h1><div id="site_social_icons"><a class="social-icon" href="https://github.com/Xiaoshen-QwQ" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="../../../../../[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div id="scroll-down"><i class="fas fa-angle-down scroll-down-effects"></i></div></header><main class="layout" id="content-inner"><div class="recent-posts nc" id="recent-posts"><div class="recent-post-items"><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/11/08/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/P7687%20%E9%A2%98%E8%A7%A3/" title="P7687 题解">P7687 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-11-08T14:16:58.111Z" title="发表于 2024-11-08 22:16:58">2024-11-08</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/">洛谷题解</a></span></div><div class="content">题意
一个通信网络包含若干个节点，以及若干条直接连接这些节点的双向通信线路。已知所研究的通信网络是连通的，即：任意一对节点之间都存在（若干条通信线路首尾相接而成的）通信路径。
一些节点会向所有节点（包括它自己）提供 \(A\)
类型服务，还有一些节点会向所有节点（包括它自己）提供 \(B\)
类型服务。一个节点可能会同时提供两种类型的服务。每个节点都必须要访问这两种服务。
当一条通信线路断开时，可能会出现某个节点不能访问某种服务的情况。（即：存在某个节点以及某种服务，使得不存在任何提供该类型服务，且与该节点连通的节点）我们称会造成这种情况的通信线路为关键通信线路。
你的任务是，写一个程序计算有多少条关键通信线路，并求出每条关键通信线路所连接的两个端点。
思路
答案肯定是割边。
我们可以先用 tarjan 求出所有的割边，然后我们在求 tarjan
的时候维护出此节点树中服务 \(A\) 和
\(B\) 的数量。
如果此节点不服务 \(A\) 或 \(B\)，或者 \(A\) 或...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/11/01/UVA%E9%A2%98%E8%A7%A3/UVA10199%E9%A2%98%E8%A7%A3/" title="UVA10199题解">UVA10199题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-11-01T12:59:43.472Z" title="发表于 2024-11-01 20:59:43">2024-11-01</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/UVA%E9%A2%98%E8%A7%A3/">UVA题解</a></span></div><div class="content">题意
给定一个由字符串构成的图，你需要求出这个图中的割点并输出。
思路
和割点模版差不多，我们只需要吧字符串转换成数字即可。
最后需要注意，每组数据之间需要空一行（坑死了）。
代码
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <bits/stdc++.h>using namespace std;const int N = 110;int n, m, ans;int dfn[N], low[N], cnt, root;bool flag[N];vector<int> e[N];map<string, int> mp;void tarjan(int u) { dfn[u] = low[u] = ++cnt; int num = 0; for (auto v :...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/11/01/%E6%97%A5%E5%B8%B8%E7%AC%94%E8%AE%B0/%E5%BC%BA%E8%81%94%E9%80%9A%E5%88%86%E9%87%8F%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" title="强联通分量学习笔记">强联通分量学习笔记</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-11-01T11:44:29.744Z" title="发表于 2024-11-01 19:44:29">2024-11-01</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/%E7%AC%94%E8%AE%B0/">笔记</a></span></div><div class="content">概念
点双联通：在无向图中，删除一个点（不是 \(x\) 或着 \(y\)）后，点 \(x\) 和 \(y\) 仍然连通，那么称 \(x\) 和 \(y\) 是点双联通的。
边双联通：在无向图中，删除一条边后，点 \(x\) 和 \(y\) 仍然连通，那么称 \(x\) 和 \(y\) 是边双联通的。
性质
点双联通不具有传递性，而边双联通具有传递性。
割点
定义
在无向图中，若删除一个点后，图不再连通，那么称这个点为割点。
结论
至少有 \(3\)
个点的无向图，才可能存在割点。
求割点
若搜索树上，有 \(x\) 到 \(y\) 的连边，也就是当 \(low_y \le dfn_x\) 时，说明 \(y\) 能到达的最小时间戳在 \(x\) 的时间戳上之上，\(y\) 被 \(x\) 与 \(x\) 之间的节点“隔开”，\(x\) 就可能是割点。
只要 \(x\) 不是搜索树的根节点，或者
\(x\) 是根节点，但是 \(x\) 的子节点个数大于 \(1\)，那么 \(x\) 就是割点。
代码（洛谷...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/P4316%20%E9%A2%98%E8%A7%A3/" title="P4316 题解">P4316 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.916Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/">洛谷题解</a></span></div><div class="content">题意
给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点，你需要求出从起点走到终点的所经过的路径总长度期望是多少？。
思路
这道题是图上概率 dp 的板子，下面会讲出我的理解。
图上概率dp的状态一般为 \(dp_u\)
表示从 \(u\) 到 \(n\) 的期望，转移为 \(dp_u = \sum p_{u \to v} \times (dp_v + w_{u \to
v})\) 。
我们来找这道题的 \(p\) 和 \(w\)。
这道题的 \(p\) 就是 \(\frac{1}{degree_u}\)，其中 \(degree_u\) 表示点 \(u\) 的度数。
\(w\)...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20U%20%E9%A2%98%E8%A7%A3/" title="DP U 题解">DP U 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.873Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
对 \(N\) 个物品任意分组，如果第 \(i\) 个物品和 第 \(j\) 个物品分在一组，会产生 \(a_{i,j}\) 的得分，最大化得分之和。 >
注意： > > \((i,j)\) 和 \((j,i)\) 的贡献只计算一次。
思路
定义状态：\(dp_i\)
表示二进制下状态为 \(i\)
能获得的最大得分和。
状态转移方程： \[
dp_i = \max_{j \in i} (dp_j + dp_{i \oplus j})
\]
答案为 \(dp_{2^n - 1}\)。
时间复杂度：\(\mathcal O (2^{n} -
1)\)。
代码
123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;long long n, a[30][30], dp[1 << 17];int main() { cin >> n; for (int...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20Q%20%E9%A2%98%E8%A7%A3/" title="DP Q 题解">DP Q 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.868Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
你有 \(n\)
朵花，每朵花有一个高度和美丽度，你需要选择一些花，是的他们的高度单调递增，请求出他们的美丽之和的最大值。
## 思路
定义状态：\(dp_i\) 表示以 \(i\) 结尾的花美丽之和的最大值。
状态转移方程： \[
dp_i = \max_{j \in n}^{a_j \le a_i} (dp_j) + a_i
\]
但如果我们直接这么做的话，我们会 T 飞。可以看到转移式子中有一个求
\(max\)，这就是导致我们慢的原因，我们可以用树状数组或线段树来维护这个求
\(max\) 值。
答案为 \(\max_{i = 1}^{n}
dp_i\)。
时间复杂度：\(\mathcal O (n \log
n)\)。
代码
123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>#define lowbit(x) (x & -x)using namespace std;using...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20P%20%E9%A2%98%E8%A7%A3/" title="DP P 题解">DP P 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.866Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数，结果对
\(10^9 + 7\) 取模。
思路
定义状态：\(dp_{i, 0/1}\) 表示以
\(i\)
为根的子树染白色或黑色的方案数。
状态转移方程： \[
\begin{cases}
dp_{u, 0} = \prod_{v \in u} dp_{v, 0} + dp_{v, 1} \\
dp_{u, 1} = \prod_{v \in u} dp_{v, 0}
\end{cases}
\]
答案为 \(dp_{1, 0} + dp_{1,
1}\)。
时间复杂度：\(\mathcal O (n + m)\)。
## 代码
1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;const int mod = 1e9 + 7;int n,...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20O%20%E9%A2%98%E8%A7%A3/" title="DP O 题解">DP O 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.864Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
给定二分图，两个集合都有 \(N\) 个点，\(a_{i,j} = 1\) 表示第一个集合第\(i\) 个点与第二个集合第 \(j\) 个点连边。
求二分图完备匹配数，答案对 \(10^9 +
7\) 取模。
思路
定义状态：\(dp_{i, j}\) 表示有 \(i\) 点已经匹配完毕，匹配的状态为 \(j\)。
状态转移方程： \[
dp_{i, j} = \sum dp_{i - 1, j | 2^k}
\]
答案为 \(dp_{n, 2^n - 1}\)
时间复杂度：\(\mathcal O (n \times
2^n)\)。
代码
1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;int n, a[30][30], dp[30][(1 << 21) + 10];int main(){ cin >> n; for(int...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20N%20%E9%A2%98%E8%A7%A3/" title="DP N 题解">DP N 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.862Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
你有 \(n\)
堆石子，你每次可以合并相邻的石子，你要付出 \(a_i + a_{i + 1}\) 代价，求将 \(n\) 堆石子合并成一堆的最小代价。 ##
思路
定义状态：\(dp_{l, r}\) 表示从 \(l\) 到 \(r\) 合并成一堆需要付出的最小代价。
状态转移方程： \[
dp_{l, r} = \min_{k = l}^{r - 1} (dp_{l, k} + dp_{k + 1, r}) + \sum_{i =
l}^{r} a_i
\]
我们可以将后面的 \(\sum_{i = l}^{r}
a_i\) 做一个前缀和预处理，时间复杂度为 \(\mathcal O (n ^ 3)\)。
代码
12345678910111213141516171819202122232425262728#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 410;int n, a[N], dp[N][N];signed...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="2024/10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20M%20%E9%A2%98%E8%A7%A3/" title="DP M 题解">DP M 题解</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2024-10-25T11:22:47.860Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="categories/Atcoder%E9%A2%98%E8%A7%A3/">Atcoder题解</a></span></div><div class="content">题意
你有 \(k\) 颗糖，你要分给 \(n\) 个人，不能有剩余，每个人至多分 \(a_i\) 个，至少分 \(0\) 个，请问有多少种方案。
思路
定义状态：\(dp_{i, j}\) 表示前 \(i\) 个人，分了 \(j\) 颗糖的方案。
状态转移方程： \[
dp_{i, j} = \sum_{k = \max(0, j - a_{i - 1})}^{j} dp_{i - 1, k}
\]
但如果我们这么做，时间复杂度会达到 \(\mathcal O (n \times
k^2)\)，显然过不了。我们让我们程序跑不快的是我们有重新枚举前面的
dp，我们发现我们枚举的是一段连续的区间，所以我们就可以用前缀和进行优化。
答案为 \(dp_{n, k}\)。
时间复杂度：\(\mathcal O (n \times
k)\)。
代码
123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>#define int long longusing...</div></div></div></div><nav id="pagination"><div class="pagination"><span class="page-number current">1</span><a class="page-number" href="page/2/#content-inner">2</a><span class="space">…</span><a class="page-number" href="page/5/#content-inner">5</a><a class="extend next" rel="next" href="page/2/#content-inner"><i class="fas fa-chevron-right fa-fw"></i></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info text-center"><div class="avatar-img"><img src="https://cdn.luogu.com.cn/upload/usericon/852112.png" onerror="this.onerror=null;this.src='../../../../../img/friend_404.gif'" alt="avatar"/></div><div class="author-info-name">正在努力的小沈</div><div class="author-info-description">知识的敌人不是无知，而是已经掌握知识的幻觉。</div><div class="site-data"><a href="../../../../../archives/"><div class="headline">文章</div><div class="length-num">49</div></a><a href="../../../../../tags/"><div class="headline">标签</div><div class="length-num">33</div></a><a href="../../../../../categories/"><div class="headline">分类</div><div class="length-num">4</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/Xiaoshen-QwQ/"><i class="fab fa-github"></i><span>这里是我的Github</span></a><div class="card-info-social-icons"><a class="social-icon" href="https://github.com/Xiaoshen-QwQ" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="../../../../../[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">欢迎来到我的博客，这里是由Hexo强力驱动，主题为Butterfly的博客，由github托管。本网站由一个蒟蒻小沈搭建并维护，欢迎各位大佬指教。</div></div><div class="sticky_layout"><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="" title="P7687 题解">P7687 题解</a><time datetime="2024-11-08T14:16:58.111Z" title="发表于 2024-11-08 22:16:58">2024-11-08</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="../../../01/UVA%E9%A2%98%E8%A7%A3/UVA10199%E9%A2%98%E8%A7%A3/" title="UVA10199题解">UVA10199题解</a><time datetime="2024-11-01T12:59:43.472Z" title="发表于 2024-11-01 20:59:43">2024-11-01</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="../../../01/%E6%97%A5%E5%B8%B8%E7%AC%94%E8%AE%B0/%E5%BC%BA%E8%81%94%E9%80%9A%E5%88%86%E9%87%8F%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" title="强联通分量学习笔记">强联通分量学习笔记</a><time datetime="2024-11-01T11:44:29.744Z" title="发表于 2024-11-01 19:44:29">2024-11-01</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="../../../../10/25/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/P4316%20%E9%A2%98%E8%A7%A3/" title="P4316 题解">P4316 题解</a><time datetime="2024-10-25T11:22:47.916Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="../../../../10/25/Atcoder%E9%A2%98%E8%A7%A3/DP%20U%20%E9%A2%98%E8%A7%A3/" title="DP U 题解">DP U 题解</a><time datetime="2024-10-25T11:22:47.873Z" title="发表于 2024-10-25 19:22:47">2024-10-25</time></div></div></div></div><div class="card-widget card-categories"><div class="item-headline">
<i class="fas fa-folder-open"></i>
<span>分类</span>
</div>
<ul class="card-category-list" id="aside-cat-list">
<li class="card-category-list-item "><a class="card-category-list-link" href="../categories/Atcoder%E9%A2%98%E8%A7%A3/"><span class="card-category-list-name">Atcoder题解</span><span class="card-category-list-count">21</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="../categories/UVA%E9%A2%98%E8%A7%A3/"><span class="card-category-list-name">UVA题解</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="../categories/%E6%B4%9B%E8%B0%B7%E9%A2%98%E8%A7%A3/"><span class="card-category-list-name">洛谷题解</span><span class="card-category-list-count">26</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="../categories/%E7%AC%94%E8%AE%B0/"><span class="card-category-list-name">笔记</span><span class="card-category-list-count">1</span></a></li>
</ul></div><div class="card-widget card-tags"><div class="item-headline"><i class="fas fa-tags"></i><span>标签</span></div><div class="card-tag-cloud"><a href="../tags/%E5%AD%97%E5%85%B8%E6%A0%91/" style="font-size: 1.17em; color: #999c9f">字典树</a> <a href="../tags/%E6%9C%80%E7%9F%AD%E8%B7%AF/" style="font-size: 1.23em; color: #999ea6">最短路</a> <a href="../tags/%E5%8C%BA%E9%97%B4dp/" style="font-size: 1.3em; color: #99a1ac">区间dp</a> <a href="../tags/%E6%A0%91%E5%BD%A2dp/" style="font-size: 1.17em; color: #999c9f">树形dp</a> <a href="../tags/%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/" style="font-size: 1.1em; color: #999">矩阵乘法</a> <a href="../tags/%E7%AC%94%E8%AE%B0/" style="font-size: 1.1em; color: #999">笔记</a> <a href="../tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" style="font-size: 1.17em; color: #999c9f">线段树</a> <a href="../tags/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/" style="font-size: 1.1em; color: #999">树状数组</a> <a href="../tags/%E5%89%B2%E7%82%B9/" style="font-size: 1.1em; color: #999">割点</a> <a href="../tags/%E5%8D%9A%E5%BC%88%E8%AE%BA/" style="font-size: 1.17em; color: #999c9f">博弈论</a> <a href="../tags/%E5%BF%AB%E9%80%9F%E5%B9%82/" style="font-size: 1.1em; color: #999">快速幂</a> <a href="../tags/Floyd/" style="font-size: 1.1em; color: #999">Floyd</a> <a href="../tags/%E5%89%B2%E8%BE%B9/" style="font-size: 1.1em; color: #999">割边</a> <a href="../tags/%E5%BC%BA%E8%81%94%E9%80%9A%E5%88%86%E9%87%8F/" style="font-size: 1.1em; color: #999">强联通分量</a> <a href="../tags/%E8%83%8C%E5%8C%85/" style="font-size: 1.23em; color: #999ea6">背包</a> <a href="../tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" style="font-size: 1.1em; color: #999">字符串</a> <a href="../tags/%E5%B9%B6%E6%9F%A5%E9%9B%86/" style="font-size: 1.17em; color: #999c9f">并查集</a> <a href="../tags/%E5%88%86%E7%B1%BB%E8%AE%A8%E8%AE%BA/" style="font-size: 1.1em; color: #999">分类讨论</a> <a href="../tags/%E7%BA%BF%E6%80%A7dp/" style="font-size: 1.23em; color: #999ea6">线性dp</a> <a href="../tags/%E6%9E%84%E9%80%A0/" style="font-size: 1.1em; color: #999">构造</a> <a href="../tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92dp/" style="font-size: 1.43em; color: #99a6b9">动态规划dp</a> <a href="../tags/%E9%A2%98%E8%A7%A3/" style="font-size: 1.5em; color: #99a9bf">题解</a> <a href="../tags/Tarjan/" style="font-size: 1.17em; color: #999c9f">Tarjan</a> <a href="../tags/%E7%8A%B6%E6%80%81%E5%8E%8B%E7%BC%A9dp/" style="font-size: 1.17em; color: #999c9f">状态压缩dp</a> <a href="../tags/BFS/" style="font-size: 1.1em; color: #999">BFS</a> <a href="../tags/%E5%9B%BE%E8%AE%BA/" style="font-size: 1.37em; color: #99a4b2">图论</a> <a href="../tags/%E6%A6%82%E7%8E%87%E4%B8%8E%E6%9C%9F%E6%9C%9B/" style="font-size: 1.23em; color: #999ea6">概率与期望</a> <a href="../tags/%E7%BA%BF%E6%80%A7%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 1.1em; color: #999">线性数据结构</a> <a href="../tags/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/" style="font-size: 1.17em; color: #999c9f">记忆化搜索</a> <a href="../tags/%E8%B4%AA%E5%BF%83/" style="font-size: 1.3em; color: #99a1ac">贪心</a> <a href="../tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" style="font-size: 1.17em; color: #999c9f">动态规划</a> <a href="../tags/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/" style="font-size: 1.1em; color: #999">最小生成树</a> <a href="../tags/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/" style="font-size: 1.1em; color: #999">拓扑排序</a></div></div><div class="card-widget card-archives">
<div class="item-headline">
<i class="fas fa-archive"></i>
<span>归档</span>
</div>
<ul class="card-archive-list">
<li class="card-archive-list-item">
<a class="card-archive-list-link" href="archive/2024/11/">
<span class="card-archive-list-date">十一月 2024</span>
<span class="card-archive-list-count">3</span>
</a>
</li>
<li class="card-archive-list-item">
<a class="card-archive-list-link" href="archive/2024/10/">
<span class="card-archive-list-date">十月 2024</span>
<span class="card-archive-list-count">46</span>
</a>
</li>
</ul></div><div class="card-widget card-webinfo"><div class="item-headline"><i class="fas fa-chart-line"></i><span>网站信息</span></div><div class="webinfo"><div class="webinfo-item"><div class="item-name">文章数目 :</div><div class="item-count">49</div></div><div class="webinfo-item"><div class="item-name">本站访客数 :</div><div class="item-count" id="busuanzi_value_site_uv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">本站总浏览量 :</div><div class="item-count" id="busuanzi_value_site_pv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">最后更新时间 :</div><div class="item-count" id="last-push-date" data-lastPushDate="2024-11-22T11:03:57.553Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">©2024 By 正在努力的小沈</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="darkmode" type="button" title="日间和夜间模式切换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="js/utils.js"></script><script src="js/main.js"></script><div class="js-pjax"></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/fireworks.min.js"></script><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-fluttering-ribbon.min.js"></script><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-nest.min.js"></script><script id="click-show-text" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/click-show-text.min.js" data-mobile="false" data-text="❤ 富强 ❤,❤ 民主 ❤,❤ 文明 ❤,❤ 和谐 ❤,❤ 自由 ❤,❤ 平等 ❤,❤ 公正 ❤,❤ 法治 ❤,❤ 爱国 ❤,❤ 敬业 ❤,❤ 诚信 ❤,❤ 友善 ❤" data-fontsize="15px" data-random="false" async="async"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>