-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
277 lines (239 loc) · 33.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
<!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>ikun 的博客</title><meta name="author" content="ikun"><meta name="copyright" content="ikun"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta property="og:type" content="website">
<meta property="og:title" content="ikun 的博客">
<meta property="og:url" content="http://ikunhorro.github.io/index.html">
<meta property="og:site_name" content="ikun 的博客">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://ikunhorro.github.io/img/favicon.png">
<meta property="article:author" content="ikun">
<meta property="article:tag" content="114514, 1919810">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://ikunhorro.github.io/img/favicon.png"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="http://ikunhorro.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?v=4.13.0"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/[email protected]/css/all.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/[email protected]/dist/fancybox/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"/search.xml","preload":false,"top_n_per_article":1,"unescape":false,"languages":{"hits_empty":"找不到您查询的内容：${query}","hits_stats":"共找到 ${hits} 篇文章"}},
translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
noticeOutdate: undefined,
highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '',
dateSuffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
infinitegrid: {
js: 'https://cdn.jsdelivr.net/npm/@egjs/[email protected]/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: 'ikun 的博客',
isPost: false,
isHome: true,
isHighlightShrink: false,
isToc: false,
postUpdate: '2024-08-15 10:59:22'
}</script><script>(win=>{
win.saveToLocal = {
set: (key, value, ttl) => {
if (ttl === 0) return
const now = Date.now()
const expiry = now + ttl * 86400000
const item = {
value,
expiry
}
localStorage.setItem(key, JSON.stringify(item))
},
get: key => {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = Date.now()
if (now > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
Object.keys(attr).forEach(key => {
script.setAttribute(key, attr[key])
})
document.head.appendChild(script)
})
win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onerror = reject
link.onload = link.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
link.onload = link.onreadystatechange = null
resolve()
}
document.head.appendChild(link)
})
win.activateDarkMode = () => {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = () => {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><meta name="generator" content="Hexo 7.2.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/favicon.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">13</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="page" id="body-wrap"><header class="full_page" id="page-header" style="background-image: url('/img/Minecraft.png')"><nav id="nav"><span id="blog-info"><a href="/" title="ikun 的博客"><img class="site-icon" src="/img/favicon.png"/><span class="site-name">ikun 的博客</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="site-info"><h1 id="site-title">ikun 的博客</h1><div id="site_social_icons"><a class="social-icon" href="https://github.com/ikunhorro" target="_blank" title="Github"><i class="fab fa-github" style="color: #24292e;"></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" id="recent-posts"><div class="recent-post-item"><div class="post_cover left"><a href="/ManimCE/" title="ManimCE 安装/使用教程"><img class="post-bg" src="/image/ManimCE/ManimCE.svg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="ManimCE 安装/使用教程"></a></div><div class="recent-post-info"><a class="article-title" href="/ManimCE/" title="ManimCE 安装/使用教程"><i class="fas fa-thumbtack sticky"></i>ManimCE 安装/使用教程</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-05-13T13:11:28.009Z" title="发表于 2024-05-13 21:11:28">2024-05-13</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%95%99%E7%A8%8B/">教程</a><i class="fas fa-angle-right article-meta-link"></i><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%95%99%E7%A8%8B/manim/">manim</a></span></div><div class="content">manimCE 安装教程link
安装 Pythonlink
往下找到需要的版本点开，然后拉到最后，即可下载 Python 安装包。
（这里以 Python 3.11.8 作为示例，其它版本可能会有 bug）
下载后打开安装程序，把最下方的 Add python.exe to PATH 的勾点亮，然后点击上方的 Install Now，然后等待安装完毕即可。
安装 Scooplink
按 Win+X 然后点击终端，输入主页的这两串代码：1Set-ExecutionPolicy -ExecutionPolicy RemoteSigned -Scope CurrentUser1Invoke-RestMethod -Uri https://get.scoop.sh | Invoke-Expression
安装 ffmpeg打开终端，然后输入 manimCE 主页的这段代码：1scoop install python ffmpeg
scoop 会先安装 7-Zip，然后下载 ffmpeg 并解压。
等待安装完成即可。
安装 manim打开终端，然后输入 manimCE 主页的这段代码：1pyt ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/blog/" title="hexo + github 搭建个人博客"><img class="post-bg" src="/image/blog/hexo.svg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="hexo + github 搭建个人博客"></a></div><div class="recent-post-info"><a class="article-title" href="/blog/" title="hexo + github 搭建个人博客"><i class="fas fa-thumbtack sticky"></i>hexo + github 搭建个人博客</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-05-13T13:11:27.978Z" title="发表于 2024-05-13 21:11:27">2024-05-13</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%95%99%E7%A8%8B/">教程</a><i class="fas fa-angle-right article-meta-link"></i><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%95%99%E7%A8%8B/blog/">blog</a></span></div><div class="content">hexo + github 搭建个人博客以下代码全都在 powershell 里执行
username 都代表你 github 用户名
安装首先来看 hexo。
hexo 要由 node.js 的软件包管理器 npm 安装。此外 hexo 依赖于 git，所以要现安装 node.js 和 git。
git
nodejs
然后使用 npm 安装 hexo：
1npm install hexo-cli -g
关于 windows 系统上禁止运行脚本：
在设置里查找 powershell，找到并打开 允许本地 powershell 脚本在未签名的情况下运行。
建站首先到要建立博客的路径（这里以 D:\ 为例）：
1cd D:\
然后运行以下代码：
1hexo init Blog; cd Blog; npm install
然后 Blog 文件夹里会变成这样：
12345678Blog├── _config.yml├── package.json├── scaffolds├── source| ├── _drafts| ├── _posts└── themes
_config. ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF1451E2/" title="[CF1451E2] Bitwise Queries (Hard Version) 题解"><i class="fas fa-thumbtack sticky"></i>[CF1451E2] Bitwise Queries (Hard Version) 题解</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-08-15T02:55:51.123Z" title="发表于 2024-08-15 10:55:51">2024-08-15</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF1451E2] Bitwise Queries (Hard Version) 题解Solution可以有 $\operatorname{AND}$ 、$\operatorname{OR}$、$\operatorname{XOR}$ 三种运算，我们先来看表格。
$A=$
$B=$
$\operatorname{AND}$
$\operatorname{OR}$
$\operatorname{XOR}$
$0$
$0$
$0$
$0$
$0$
$0$
$1$
$0$
$1$
$1$
$1$
$0$
$0$
$1$
$1$
$1$
$1$
$1$
$1$
$0$
可以发现，大多数情况 $\operatorname{AND}$ 运算的值都为 $0$，就不知道是哪种情况。$\operatorname{OR}$ 运算也是如此，大多数情况它的值为 $1$。
所以我们主要用 $\operatorname{XOR}$ 进行运算。我们可以先求出 $a1 \oplus a{2 \sim n}$ 的值记为 $x_{2 \sim n}$，然后求出 $a_1$ 的值，这时 ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF1288D/" title="[CF1288D] Minimax Problem 题解"><i class="fas fa-thumbtack sticky"></i>[CF1288D] Minimax Problem 题解</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-08-15T02:53:53.068Z" title="发表于 2024-08-15 10:53:53">2024-08-15</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF1288D] Minimax Problem 题解Solution题目要求 $b_j$ 最小值的最大值，像这种求最小值的最大值或最大值的最小值的问题，很显然可以用二分答案。
接下来考虑二分答案怎么写 check，注意到数据范围 $m \le 8$，对于这种很小的数据范围，可以使用状态压缩来解决。
以样例为例：
1234567896 55 0 3 1 21 8 9 1 31 2 3 4 59 1 0 3 72 3 0 6 36 4 1 7 0(mid = 3)
我们可以把大于等于 $mid$ 的的值标为 $1$，否则标为 $0$：
12345676 51 0 1 0 00 1 1 0 10 0 1 1 11 0 0 1 10 1 0 1 11 1 0 1 0
随后进行状态压缩（为了方便观察，用二进制表示）：
12610100 01101 00111 10011 01011 11010
如果 $a{x,j}$ 和 $a{y,j}$ 中至少有一个 $\ge mid$，那么 $b_j$ 就 $\ge mid$。不难发现，$b$ 通过以上操作状压后的结果，就是 $a_x$ 状压的结果按位或 ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF1499D/" title="[CF1499D] The Number of Pairs 题解"><i class="fas fa-thumbtack sticky"></i>[CF1499D] The Number of Pairs 题解</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-07-23T12:03:17.804Z" title="发表于 2024-07-23 20:03:17">2024-07-23</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF1499D] The Number of Pairs 题解Solution$c \times \operatorname{lcm}(a, b) - d \times \gcd(a, b) = x$
题目中给的式子既有 $\gcd$ 又有 $\operatorname{lcm}$，我们可以令 $A = \dfrac{a}{\gcd(a, b)}$，$B = \dfrac{b}{\gcd(a, b)}$。
此时 $AB = \dfrac{ab}{\gcd(a, b)^2} = \dfrac{\operatorname{lcm}(a, b) \times \gcd(a, b)}{\gcd(a, b)^2} = \dfrac{\operatorname{lcm}(a, b)}{\gcd(a, b)}$，则 $\operatorname{lcm}(a, b) = AB \times \gcd(a, b)$。
$c \times AB \times \gcd(a, b) - d \times \gcd(a, b) = x$
提取公因式 $\gcd(a, b)$：
$\gcd(a, b) \t ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF17B/" title="[CF17B] Hierarchy 题解"><i class="fas fa-thumbtack sticky"></i>[CF17B] Hierarchy 题解</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-05-17T13:08:35.306Z" title="发表于 2024-05-17 21:08:35">2024-05-17</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF17B] Hierarchy 题解Solution每个人都有一个上司，除了最顶尖的人没有上司，那么就只有 $n-1$ 个人有上司。
我们把两个人之间的上司关系转换成图论中的有向边，而根据上面得出只会有 $n-1$ 条有向边，这不就是树吗？也就是我们要求这张图的最小生成树。（用的是Kurscal）
先读入每个人的权值和图中的每一条有向边。
再把每一条有向边按照权值从小到大排序（因为花的代价越少越好）。
然后循环每一条边，如果 $b$ 没有上司而且 $a$ 的权值比 $b$ 大，那么就花费 $c$ 任命 $a$ 为 $b$ 的上司，而且要记录一个变量，表示利用的边的个数，每次任命上司的时候这个变量就 $+1$。
如果利用边的个数已经是 $n-1$，那么就跳出。
如果所有边都遍历了一遍，但是利用边的个数却没有达到 $n-1$，那么就表示无解，输出-1。
</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/P3861/" title="[P3861] 拆分 题解"><i class="fas fa-thumbtack sticky"></i>[P3861] 拆分 题解</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-05-17T13:03:47.453Z" title="发表于 2024-05-17 21:03:47">2024-05-17</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[P3861] 拆分 题解Solution我们可以先求出 $n$ 的所有因数： $x1,x_2,\dots,x{d(n)}$ 。（ $d(n)$ 表示 $n$ 的因数个数）
然后考虑 dp ，设 $dp_{i,j}$ 为把 $x_i$ 分解成若干个 $\leq x_j$ 的数的乘积的方案数。
记录 $posi$ 为 $i$ 在 $x$ 中的位置，我们可以在 $i\leq sqrt(n)$ 时，记录 $pos{1,i}=posi$ ，在 $i>sqrt(n)$ 时，记录 $pos{2,\frac{n}{i}}=pos_i$ ，就可以把复杂度缩小到 $O(\sqrt{n})$ 。
然后考虑 $dp{i,j}$ 的求法。首先是初始化，当 $j=1$ 时，可以发现 $i=1$ 即 $x_i=1$ 时 $dp{i,j}=1$ ，否则 $dp{i,j}=0$ 。因为只有 $1$ 可以表示为 $1\times1$ 。加下来考虑传递。首先考虑 $x_i$ 的分解中不包括 $x_j$ 的情况，那么就是把 $x_i$ 分解为若干个小于 $x_j$ 的数的乘积，也就是 $dp{i,j-1}$ 。然后考 ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF1458A/" title="[CF1458A] Row GCD 题解"><i class="fas fa-thumbtack sticky"></i>[CF1458A] Row GCD 题解</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-05-17T12:59:46.318Z" title="发表于 2024-05-17 20:59:46">2024-05-17</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF1458A] Row GCD 题解Solution众所周知：
$\gcd(a,b)=\gcd(a,b-a)$
证明：
设 $\gcd(a,b)=g$ 。则 $a\bmod g=0$；且 $b\bmod g=0$。可以得出 $(b-a)\bmod g=0$。所以 $(a,b-a)$ 和 $(b,b-a)$ 都有公因数 $g$。
可是有可能 $(a,b-a)$ 和 $(b,b-a)$ 的最大公因数比 $g$ 大。所以可以假设 $gcd(a,b-a)=c’>c$。
那么 $a\bmod c’=0$，$(b-a)\bmod c’=0$，且 $(b-a)\bmod c’=b\bmod c’-a\bmod c’$，可以得出 $b\bmod c’=0$。
那么 $\gcd(a,b)=c’>c$，与原来矛盾。$(b,b-a)$ 同理。
故得证。
知道这个就简单了，题目让我们求 $\gcd(a_1+b_i,a_2+b_i,a_3+b_i,\dots,a_n+b_i)$，我们可以把 $2\sim n$ 项都减去第 $1$ 项，就变成了 $\gcd(a_1+b_i,a_2-a_1,a_ ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/CF1760D/" title="[CF1760D] Challenging Valleys 题解"><i class="fas fa-thumbtack sticky"></i>[CF1760D] Challenging Valleys 题解</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-05-17T12:56:26.115Z" title="发表于 2024-05-17 20:56:26">2024-05-17</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[CF1760D] Challenging Valleys 题解Solution如果一个序列中恰好有一个满足以下条件的子序列，输出 YES，否则输出 NO。
条件：
$0\leq l\leq r\leq n-1$
$al=a{l+1}=a_{l+2}=\dots=a_r$
$l=0$ 或 $a_{l-1}>a_l$
$r=n-1$ 或 $ar>a{r+1}$
枚举左端点，判断是否符合第三条条件。然后边判断第二条条件，边枚举右端点。当第二条条件不满足时，再判断第四条条件。如果所有都符合，那么答案个数加一。最后如果答案的个数是 $1$，输出 YES，否则输出 NO。
Code12345678910111213141516171819202122232425#include <iostream>using namespace std;int T, n, a[200005], ans;int main() { cin >> T; while (T--) { cin >> n; for (int i = 0; i < ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/ARC148B/" title="[ARC148B] dp 题解"><i class="fas fa-thumbtack sticky"></i>[ARC148B] dp 题解</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-05-17T12:53:36.813Z" title="发表于 2024-05-17 20:53:36">2024-05-17</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/%E9%A2%98%E8%A7%A3/">题解</a></span></div><div class="content">[ARC148B] dp 题解Solution题目要求字典序最小，而且只有 d 和 p 两种字母。所以我们要让在前面的 p 变成 d，可以先找到第一个 p 作为左端点，想让它变成 d，就要找到后面的一个 p 作为右端点，然后暴力枚举就可以了。时间复杂度 $O(n^2)$。
Code1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;int n, l, r;string s, t, ans;int main() { cin >> n >> s; for (int i = 0; i < n; i++) { if (s[i] == 'p') { //找到第一个p作为左端点 l = i; break; } } ans = s; //记录答案 for (r = l; r < n; r++) { //枚举右端点 i ...</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><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"><div class="is-center"><div class="avatar-img"><img src="/img/favicon.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">ikun</div><div class="author-info__description"></div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">13</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/xxxxxx"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/ikunhorro" target="_blank" title="Github"><i class="fab fa-github" style="color: #24292e;"></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">This is my Blog</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="/CF1451E2/" title="[CF1451E2] Bitwise Queries (Hard Version) 题解">[CF1451E2] Bitwise Queries (Hard Version) 题解</a><time datetime="2024-08-15T02:55:51.123Z" title="发表于 2024-08-15 10:55:51">2024-08-15</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/CF1288D/" title="[CF1288D] Minimax Problem 题解">[CF1288D] Minimax Problem 题解</a><time datetime="2024-08-15T02:53:53.068Z" title="发表于 2024-08-15 10:53:53">2024-08-15</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/CF1499D/" title="[CF1499D] The Number of Pairs 题解">[CF1499D] The Number of Pairs 题解</a><time datetime="2024-07-23T12:03:17.804Z" title="发表于 2024-07-23 20:03:17">2024-07-23</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/CF17B/" title="[CF17B] Hierarchy 题解">[CF17B] Hierarchy 题解</a><time datetime="2024-05-17T13:08:35.306Z" title="发表于 2024-05-17 21:08:35">2024-05-17</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/P3861/" title="[P3861] 拆分 题解">[P3861] 拆分 题解</a><time datetime="2024-05-17T13:03:47.453Z" title="发表于 2024-05-17 21:03:47">2024-05-17</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/test/"><span class="card-category-list-name">test</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%95%99%E7%A8%8B/"><span class="card-category-list-name">教程</span><span class="card-category-list-count">2</span></a><ul class="card-category-list child"><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E6%95%99%E7%A8%8B/blog/"><span class="card-category-list-name">blog</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%95%99%E7%A8%8B/manim/"><span class="card-category-list-name">manim</span><span class="card-category-list-count">1</span></a></li></ul></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E9%A2%98%E8%A7%A3/"><span class="card-category-list-name">题解</span><span class="card-category-list-count">10</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/manim/" style="font-size: 1.1em; color: #999">manim</a> <a href="/tags/CodeForces/" style="font-size: 1.37em; color: #99a4b2">CodeForces</a> <a href="/tags/blog/" style="font-size: 1.1em; color: #999">blog</a> <a href="/tags/%E9%A2%98%E8%A7%A3/" style="font-size: 1.5em; color: #99a9bf">题解</a> <a href="/tags/AtCoder/" style="font-size: 1.1em; color: #999">AtCoder</a> <a href="/tags/%E6%B4%9B%E8%B0%B7/" style="font-size: 1.1em; color: #999">洛谷</a> <a href="/tags/%E6%95%99%E7%A8%8B/" style="font-size: 1.23em; color: #999ea6">教程</a> <a href="/tags/hexo/" style="font-size: 1.1em; color: #999">hexo</a> <a href="/tags/test/" style="font-size: 1.1em; color: #999">test</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="/archives/2024/08/"><span class="card-archive-list-date">八月 2024</span><span class="card-archive-list-count">2</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/07/"><span class="card-archive-list-date">七月 2024</span><span class="card-archive-list-count">1</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/05/"><span class="card-archive-list-date">五月 2024</span><span class="card-archive-list-count">10</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">13</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-08-15T02:59:22.555Z"><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">©2020 - 2024 By ikun</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="translateLink" type="button" title="简繁转换">简</button><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?v=4.13.0"></script><script src="/js/main.js?v=4.13.0"></script><script src="/js/tw_cn.js?v=4.13.0"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/[email protected]/dist/fancybox/fancybox.umd.min.js"></script><div class="js-pjax"></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/fireworks.min.js"></script><script defer="defer" id="fluttering_ribbon" mobile="false" src="https://cdn.jsdelivr.net/npm/[email protected]/dist/canvas-fluttering-ribbon.min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div><div id="local-search-stats-wrap"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js?v=4.13.0"></script></div></div></body></html>