- 博客(839)
- 收藏
- 关注
RSS订阅原创 OI 生涯回忆录 《Pilgrimage》
前言于 NOI2020 后写下本文。本文简单提及了在写作时尚能回忆起来的，在我的 OI 生涯中对我的影响重大的人、事、比赛等。写作本文，旨在在回忆允许的范围内，对 OI 生涯进行一定程度上的梳理，总结。开端入门我最早接触计算机程序设计，是在小学。那时候，我的数学成绩不错，就被老师推荐去学习编程。就这样，我在局前街小学的何静老师的指导下，走上了编程的道路。小学时的编程，与其说是 “竞赛” ，不如说是 “兴趣班” 。当时，包括我在内，很多小孩子天性是浮躁的。支撑我对着无聊的代码学下去的，并不
2020-08-30 16:07:47
15106
7
原创 【CodeForces】Codeforces Global Round 9
比赛链接点击打开链接官方题解点击打开链接Problem A. Sign Flipping将奇数位的数取非正值，偶数位的数取非负值即可。单组数据时间复杂度 O(N)O(N)O(N) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 3e5 + 5;typedef long long ll;template <typename T> void chkmax(T &x, T y) {x =
2020-07-10 16:20:33
1197
原创 【LOJ3325】「SNOI2020」区间和
题目链接点击打开链接题目解法由于修改操作是区间 chkmax ，不难想到用 SegmentTreeBeats 来维护序列。接下来，我们便只需要考虑如何处理对区间最小值的区间加操作了。参考最大子段和的传统线段树解法，同样考虑维护左 LLL 、中 MMM 、右 RRR 、和 SSS 四项数据。在这四项数据中，我们不仅要计入最优解的数值 sumsumsum ，同时还要记录最优解包含的区间最小值的个数 MincntMincntMincnt 。在一个区间的区间最小值不断增加的过程中，有一些包含更多区间最
2020-07-08 15:59:10
1953
1
原创 【AtCoder】AtCoder Grand Contest 046
比赛链接点击打开链接官方题解点击打开链接Problem A. Takahashikun, The Strider可以发现，任意时刻，玩家均位于以前两次操作路径的中垂线的交点上。因此，答案即为使得玩家朝向与初始时第一次一致的时刻，即360gcd(X,360)\frac{360}{gcd(X,360)}gcd(X,360)360时间复杂度 O(LogV)O(LogV)O(LogV) 。#include<bits/stdc++.h>using namespace std;con
2020-06-24 09:13:16
1403
4
原创 【AtCoder】Tokio Marine & Nichido Fire Insurance Programming Contest 2020
比赛链接点击打开链接官方题解点击打开链接Problem A. Nickname输出 s1s2s3s_1s_2s_3s1s2s3 即可。时间复杂度 O(∣S∣)O(|S|)O(∣S∣) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 3e5 + 5;typedef long long ll;template <typename T> void chkmax(T &x, T y)
2020-06-17 09:19:06
776
原创 【AtCoder】AtCoder Grand Contest 045
比赛链接点击打开链接官方题解点击打开链接Problem A. Xor Battle考虑维护使得最后一个玩家获胜的数字集合 SSS ，初始时， S={0}S=\{0\}S={0} 。考虑最后一个回合 iii ：若该回合是 0 号玩家的回合，则有 S′={x∣x∈S}∪{x⊕Ai∣x∈S}S'=\{x\mid x\in S\}\cup\{x\oplus A_i\mid x\in S\}S′={x∣x∈S}∪{x⊕Ai∣x∈S} ；若该回合是 1 号玩家的回合，则若 Ai∈SA_i\in SAi
2020-06-11 11:35:54
860
3
原创 【AtCoder】NOMURA Programming Competition 2020
比赛链接点击打开链接官方题解点击打开链接Problem A. Study Scheduling计算两个时刻的时间间隔，减去 KKK 。时间复杂度 O(1)O(1)O(1) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 3e5 + 5;typedef long long ll;template <typename T> void chkmax(T &x, T y) {x = max
2020-05-31 12:13:05
765
原创 【Code+ 7】六元环
题目解法考虑题目中给出的图的结构：对于边 (l,r)(l,r)(l,r) ，找到区间 (l,r)(l,r)(l,r) 中最靠前的最大值的位置 xxx ，连边 (l,x),(x,r)(l,x),(x,r)(l,x),(x,r) 。此后，区间 (l,x),(x,r)(l,x),(x,r)(l,x),(x,r) 之间不再有边相连，递归建图即可。可以发现，若用点 xxx 描述一个三角形 (l,x),(x,r),(l,r)(l,x),(x,r),(l,r)(l,x),(x,r),(l,r) ，则题目中的结构即
2020-05-27 13:37:41
2002
8
原创 【Code+ 7】同余方程
题目解法可以在 Oeis 上找到对应数列，记答案为 T(N,x)T(N,x)T(N,x) 。首先， T(N,x)T(N,x)T(N,x) 是积性的，对于 gcd(N,M)=1gcd(N,M)=1gcd(N,M)=1 ，有T(N×M,k)=T(N,k%N)×T(M,k%M)T(N\times M,k)=T(N,k\%N)\times T(M,k\%M)T(N×M,k)=T(N,k%N)×T(M,k%M)对于 k=0k=0k=0 ，应有T(pe,0)={2ep=2pe−e%2p≡3 (mod 4)
2020-05-27 13:36:51
556
原创 【Code+ 7】教科书般的亵渎
题目解法不难发现，对于所有血量的随从都存在的情况，询问 [1,M][1,M][1,M] 的答案应为 O(NLogN)O(NLogN)O(NLogN) 级别。考虑分别维护 FiF_iFi ，表示 iii 点法术伤害的亵渎造成伤害的次数。对于 i≤O(N)i\leq O(\sqrt{N})i≤O(N) ，显然可以直接维护未出现的血量的 MexMexMex ，这里血量指 ⌈xi⌉\lceil\frac{x}{i}\rceil⌈ix⌉ 。对于 i≥O(N)i\geq O(\sqrt{N})i≥O(N
2020-05-27 13:36:18
1351
4
原创 【Code+ 7】神秘序列
题目解法倒过来考虑题目中的过程，即从全零数组开始，进行题目中操作的拟操作。则应当每次找到数组中最低的为 000 的位置 iii ，令 ai=i,aj=aj−1 (j≤i−1)a_i=i,a_j=a_j-1\;(j\leq i-1)ai=i,aj=aj−1(j≤i−1) 。给定操作次数 XXX ，考虑如何高效地还原出 XXX 次操作后的数组。我们称一次操作 ai=i,aj=aj−1 (j≤i−1)a_i=i,a_j=a_j-1\;(j\leq i-1)ai=i,aj=aj−1(j≤i−
2020-05-27 13:35:43
976
原创 【NOI Online 3】Sequence
题目解法我们希望计算出 AnsiAns_iAnsi 表示并为 iii 的合法子序列的个数。计算出 AnsiAns_iAnsi 之后，只需要通过线性筛处理欧拉函数后即可轻松算出答案。首先删去序列中所有的 000 ，特殊考虑，令剩余序列中存在 AiA_iAi 个 iii 。将 AiA_iAi 看做集合幂级数，乘法看做子集卷积，则应当有Ans(x)=1+A(x)+A2(x)2+A3(x)6+…Ans(x)=1+A(x)+\frac{A^2(x)}{2}+\frac{A^3(x)}{6}+\dot
2020-05-25 12:07:38
513
原创 【NOI Online 3】Magic
题目解法考虑分别处理答案的每一位，则不难发现，异或可以看做模 222 意义下的线性变换。预处理转移矩阵的次幂，在询问时矩阵乘向量即可。有关矩阵和向量的运算可以通过 bitset 压位优化。时间复杂度 O(N3LogVw+QN2Log2Vw)O(\frac{N^3LogV}{w}+\frac{QN^2Log^2V}{w})O(wN3LogV+wQN2Log2V) ，其中 w=64w=64w=64 。#include<bits/stdc++.h>using namespace std
2020-05-25 12:06:53
347
原创 【NOI Online 3】Kettle
题目解法显然答案应为长度为 k+1k+1k+1 的区间和的最大值，用前缀和 +++ 差分计算即可。时间复杂度 O(N)O(N)O(N) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 1e6 + 5;typedef long long ll;template <typename T> void chkmax(T &x, T y) {x = max(x, y); }template <
2020-05-25 12:06:22
305
原创 【UOJ528】【美团杯2020】分形之美
题目链接点击打开链接题目解法观察分形结构，我们可以得到如下性质：(1)(1)(1) 、分形结构具有轴对称性，且 Ai,j=Aj,iA_{i,j}=A_{j,i}Ai,j=Aj,i(2)(2)(2) 、对于每一个 3×33\times 33×3 的单元，中间的元素为 111 ，其四周的元素为 000 ，角落上的元素均相同(3)(3)(3) 、任何情况下不存在相邻的 x ，每一个大小超过 111 的 o 连通块均与一个一级的 o 直接相邻考虑计算 solve(N,xl,xr,yl,yr)sol
2020-05-19 14:19:47
463
原创 【UOJ530】【美团杯2020】汉明距离
题目链接点击打开链接题目解法在解决本题之前，首先考虑如下问题：在数轴原点处，一个人开始随机游走，每一时刻，他将以 12\frac{1}{2}21 的概率向正方向走一步，以相同的概率向负方向走一步。求出 NNN 时刻后他所在坐标平方的期望。考虑用动态规划解决该问题，记 dpi,jdp_{i,j}dpi,j 表示从 iii 号点出发， jjj 时刻后角色所在坐标平方的期望。则有：dpi,j={i2j=0dpi+1,j−1+dpi−1,j−12j≥1dp_{i,j}=\left\{\begin{
2020-05-19 13:23:24
557
原创 【UOJ532】【美团杯2020】热身题
题目链接点击打开链接题目解法从长到短搜索题目给出的上升序列。每填入一个数字，便检查是否有能够确定的位置，并在产生矛盾时进行剪枝。时间复杂度 O(1)O(1)O(1) 。#include<bits/stdc++.h>using namespace std;const int N = 15;typedef long long ll;template <typename T> void chkmax(T &x, T y) {x = max(x, y); }te
2020-05-18 13:09:27
375
原创 【UOJ531】【美团杯2020】最长公共子序列
题目链接点击打开链接题目解法询问长度为 222 的序列 {x,y} (x≠y)\{x,y\}\;(x\ne y){x,y}(x=y) 可以查询 xxx 是否在答案中排在 yyy 的前面。由此，用 std :: stable_sort 或是归并排序对 111 到 NNN 进行排序即可。时间复杂度 O(NLogN)O(NLogN)O(NLogN) 。#include "lcs.h"#include <bits/stdc++.h>using namespace std;cons
2020-05-18 13:08:24
396
原创 【UOJ529】【美团杯2020】114514
题目链接点击打开链接题目解法可以发现，在给定的序列 114514114514114514 中，每个 444 之前均有一个 111 。因此，从后向前，将每个 444 与前方最近的一个尚未匹配的 111 匹配，不会导致原本有解的数据无解。进行匹配后，每一个 1−41-41−4 结构的左右端点是分别具有单调性的。那么，剩余的问题就是将给定序列拆分为形如 123212321232 的序列。从左到右进行简单贪心即可，对于一个 222 ，我们会优先将其与 111 匹配。单组数据时间复杂度 O(∣S∣)O
2020-05-18 13:07:54
585
原创 【UOJ525】【美团杯2020】平行四边形
题目链接点击打开链接题目解法考虑不存在平行四边形的判断条件，则应当为：对于任意 (i≠j)(i\ne j)(i=j) ， Pi−PjP_i-P_jPi−Pj 得到的向量两两不同。注意到题目保证了 N+1N+1N+1 是质数，不妨猜想构造方式与原根 ggg 有关。考虑如下构造：Pi=(i,gi%N)P_i=(i,g^i\% N)Pi=(i,gi%N)则Pi−Pj=(i−j,gj(gi−j−1)%N)P_i-P_j=(i-j,g^j(g^{i-j}-1)\% N)Pi−Pj=(i
2020-05-18 13:07:18
277
原创 【UOJ524】【美团杯2020】程序解密
题目链接点击打开链接题目解法利用编辑器的替换功能不难得到大致的程序。对于剩余不能确定的部分，枚举所有可能的情况，根据样例判断是否正确即可。值得关注的突破口有：右大括号、回车、Tab，以及出现了一部分的保留字。#include<bits/stdc++.h>const int MAXN = 1e3 + 5;using namespace std;int weight[] = {293309062, 96701749, 694916487, 371591203, 450903345,
2020-05-18 13:06:46
429
原创 【UOJ523】【美团杯2020】半前缀计数
题目链接点击打开链接题目解法对于一个所求集合内的子串 TTT ，定义其关键出现位置 (i,j,k)(i,j,k)(i,j,k) ，满足 Lcp(S,T)=iLcp(S,T)=iLcp(S,T)=i 。那么，可以枚举前缀 iii ，统计后缀 i+1i+1i+1 中，不以 Si+1S_{i+1}Si+1 开头的本质不同的子串个数，求和得到答案。因此，我们需要实现一个数据结构，支持向其开头加入一个字符，并询问不以某一特定字符开头的，本质不同的子串个数。用后缀自动机简单实现即可。时间复杂度 O(∣S∣)
2020-05-18 13:06:13
417
原创 【UOJ522】【美团杯2020】版本答案
题目链接点击打开链接题目解法关于鲭鱼圣者的之间的战斗，有如下观察：(1)(1)(1) 、在任意时刻，双方阵营中没有圣盾的鲭鱼圣者数量不超过 111(2)(2)(2) 、进攻方的鲭鱼圣者 xxx 进攻后，其余鲭鱼圣者均会重新获得圣盾(3)(3)(3) 、防守方在被进攻前，或是所有鲭鱼圣者均有圣盾，或是刚刚行动的鲭鱼圣者没有圣盾因此，我们可以使用四元组 (x,y,s,t)(x,y,s,t)(x,y,s,t) 来描述一个状态，表示：(1)(1)(1) 、当前进攻方剩余鲭鱼圣者的数量为 xxx ，防
2020-05-18 13:05:43
624
原创 【UOJ519】【美团杯2020】查查查乐乐
题目链接点击打开链接题目解法考虑判断某序列是否可以选出子序列 S=xxxllS=xxxllS=xxxll 。则应当从左到右考虑序列个每个元素 xxx ，并维护匹配指针 pospospos ，若 x=Sposx=S_{pos}x=Spos ，则令 pos=pos+1pos=pos+1pos=pos+1 ，判断最后 pospospos 是否为 666 即可。因此，不难发现，对于一个序列，只需要保存 pospospos 作为状态就可以了。由此设计动态规划解决问题即可。时间复杂度 O(T×N)O(T\
2020-05-18 13:05:03
323
原创 【USACO】USACO 2020 US Open Contest
Problem A. Sprinklers 2: Return of the Alfalfa若干包含右上或是左下角的矩形的并是一条单调向右、或向下的轮廓线。考虑枚举最终两种作物的分界线，则不难发现，分界线的拐角处必须放置指定装置，其余位置可以不放置装置，也可以放置其中一种装置。因此，可以认为，轮廓线每拐一次弯，该轮廓线的贡献变为 12\frac{1}{2}21 ，从而进行动态规划计算答案。...
2020-04-06 15:01:52
2546
原创 【LOJ6405】「ICPC World Finals 2018」征服世界
【题目链接】点击打开链接【思路要点】建议参考 WC2019WC2019WC2019 第一课堂陈江伦的《模拟费用流问题》课件。我们称需要军队的地方为老鼠，军队为洞，那么我们可以花费一定代价移动老鼠和洞，使得所有老鼠均进洞，我们需要最小化总代价。考虑使用贪心解决该问题，我们为每一只老鼠设定一个额外代价 −∞-\infty−∞ ，其中 −∞-\infty−∞ 是一个足够小的数，表示...
2020-03-26 10:24:52
1523
原创 【LOJ3272】「JOISC 2020 Day1」汉堡肉
题目链接点击打开链接题目解法考虑问题在一维上的形式，显然，我们会希望所选的最靠左侧的点尽量靠右。因此，选择 min{Ri}\min\{R_i\}min{Ri} 是不劣的，我们可以通过重复选择 min{Ri}\min\{R_i\}min{Ri} 达成目标。考虑在原问题中，一个确定的方案 (x1,y1),(x2,y2),…(x_1,y_1),(x_2,y_2),\dots(x1,y...
2020-03-25 18:01:41
1183
原创 【LOJ3278】「JOISC 2020 Day3」收获
题目链接点击打开链接题目解法人和树是在相对运动的，考虑固定人的位置，移动树。可以发现，一棵树 iii 在被某个人采摘后，接下来可能采摘这棵树的人是确定的，并且，两次采摘的间隔时间也是确定的，分别记为 nxti,leninxt_i,len_inxti,leni 。这样的结构构成了一个基环内向森林。考虑一次询问，对于询问在环上的人，一棵树的贡献将会是某个数值除去此人所在环长下取整的值；对...
2020-03-25 17:38:11
816
原创 【LOJ3279】「JOISC 2020 Day3」迷路的猫
题目链接点击打开链接题目解法对于 A≥3A\geq 3A≥3 的情况，考虑从 000 号点出发，求出到各个点的最短路 distidist_idisti 。则对于一条边 (x,y)(x,y)(x,y) ， ∣distx−disty∣≤1|dist_x-dist_y|\leq 1∣distx−disty∣≤1 ，将其染色为 min{distx,disty}%3min\{dist_x,di...
2020-03-24 16:37:33
1548
原创 【LOJ3282】「JOISC 2020 Day4」治疗计划
题目链接点击打开链接题目解法由于费用均为正，在最优方案中不应存在没有起到作用的区间。因此，可以考虑按照位置从左到右的顺序进行动态规划，每一步要求两个区间的左右端点可以连接上，以下是一份该算法的 O(N2)O(N^2)O(N2) 实现。#include<bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;c...
2020-03-24 16:24:29
975
原创 【LOJ3280】「JOISC 2020 Day4」首都城市
题目链接点击打开链接题目解法考虑对各个颜色建立满足如下性质的图 GGG ：若颜色 iii 形成的虚树内存在颜色 jjj ，连边 i→ji\rightarrow ji→j 。若能够得到 GGG ，则运行 Tarjan 算法，找到出度为零的所有强连通分量，取最优即可。在树上倍增优化建图，可以得到具有同样性质的图。时间复杂度 O(NLogN)O(NLogN)O(NLogN) 。#incl...
2020-03-24 16:17:33
746
原创 【LOJ3277】「JOISC 2020 Day3」星座 3
题目链接点击打开链接题目解法将问题转化为保留权值和尽可能大的星。对于一个区域，考虑其中最高的楼房 iii ，显然，我们至多可以保留一颗高于 hih_ihi 的星。若我们没有保留任意一颗高于 hih_ihi 的星，则区域会被楼房 iii 分为独立的两块；否则，令所保留的星的横坐标为 xxx ，则区域会被分成 xxx 左侧的若干块和右侧的若干块。这两种情况中，所新产生的区域都能够由 ...
2020-03-24 16:11:07
992
原创 【LOJ3276】「JOISC 2020 Day2」遗迹
题目链接点击打开链接题目解法首先考虑对于确定的 hih_ihi ，判断其是否满足条件。显然，选出 AAA 集合的过程如下：取出 hih_ihi 的两个最大值的下标，加入集合 SSS ，弹出 SSS 的最大值，加入集合 AAA ，重复 NNN 次。也有这样一个等价的过程：从后往前考虑各个 hih_ihi ，若在最终状态中，仍然存在 1≤x≤hi1\leq x\leq h_i1≤x≤h...
2020-03-24 16:05:45
1028
4
原创 【LOJ3275】「JOISC 2020 Day2」有趣的 Joitter 交友
题目链接点击打开链接题目解法问题可以转述为如下形式：在一张会自行补边的有向图上不断加边，若 xxx 连向了 yyy ，且 y,zy,zy,z 在一个二元环内， xxx 也会连向 zzz ，每次加入一条边，求出当前边数。显然由二元环连接的点集中每一条可能的边都存在。考虑将由二元环连接的点集缩点，则为了计算答案，需要维护指向该点集的入点集合 ineineine 。由此，一个点集 SSS 对...
2020-03-24 16:05:09
613
原创 【LOJ3274】「JOISC 2020 Day2」变色龙之恋
题目链接点击打开链接题目解法考虑子任务 444 的解法。令一只变色龙 xxx 和其性别不同的变色龙集合 SSS 会面，得到结果 resresres ，讨论若干情况可得：(1)(1)(1) 、若 LLx=xL_{L_x}=xLLx=x ，当且仅当 SSS 集合中存在与 xxx 颜色相同的变色龙， res<∣S∣+1res<|S|+1res<∣S∣+1(2)(2)(2...
2020-03-24 16:04:38
667
原创 【LOJ3273】「JOISC 2020 Day1」扫除
题目链接点击打开链接题目解法考虑子任务 333 的解法。可以发现，将所有元素按照 xxx 升序为第一关键字， yyy 降序为第二关键字排序，任何操作不会改变元素的相对顺序。由此，用线段树维护元素序列，修改时在线段树上二分出受到影响的区间，可以将修改操作看做一次区间对某一维坐标赋值的操作。时间复杂度 O(M+QLogM)O(M+QLogM)O(M+QLogM) 。考虑子任务 444 ，即...
2020-03-24 16:04:05
944
原创 【LOJ3271】「JOISC 2020 Day1」建筑装饰 4
题目链接点击打开链接题目解法将问题转化为保留权值和尽可能大的星。对于一个区域，考虑其中最高的楼房 iii ，显然，我们至多可以保留一颗高于 hih_ihi 的星。若我们没有保留任意一颗高于 hih_ihi 的星，则时间复杂度 O((N+M)LogN)O((N+M)LogN)O((N+M)LogN) 。#include<bits/stdc++.h>using name...
2020-03-24 16:03:25
615
2
原创 【CodeForces】Ozon Tech Challenge 2020
比赛链接点击打开链接官方题解点击打开链接Problem A. Kuroni and the Gifts将 aia_iai 和 bib_ibi 排序后输出即可。时间复杂度 O(TNLogN)O(TNLogN)O(TNLogN) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 3e5 + 5;...
2020-03-13 16:48:40
483
原创 【CodeForces】Codeforces Round 625
比赛链接点击打开链接官方题解点击打开链接Problem A. Journey Planning显然可以枚举 bib_ibi 与 iii 的差值，并选取所有合法的 bib_ibi 。时间复杂度 O(NLogN)O(NLogN)O(NLogN) 。#include<bits/stdc++.h>using namespace std;const int MAXN = 3...
2020-03-12 14:17:38
416
原创 【CodeForces】Codeforces Round 626
比赛链接点击打开链接官方题解点击打开链接Problem A. Unusual Competitions显然，当且仅当左右括号的个数不相等，答案为 −1-1−1 。否则，将左右括号分别看做 +1,−1+1,-1+1,−1 ，画出前缀和的折线图，不难发现翻转 xxx 轴下方的部分是最优的。时间复杂度 O(N)O(N)O(N) 。#include<bits/stdc++.h>...
2020-03-10 15:25:59
602
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人