3 cz_xuyixuan

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4k+

【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

【LOJ3325】「SNOI2020」区间和

题目链接点击打开链接题目解法由于修改操作是区间 chkmax ,不难想到用 SegmentTreeBeats 来维护序列。接下来,我们便只需要考虑如何处理对区间最小值的区间加操作了。参考最大子段和的传统线段树解法,同样考虑维护左 LLL 、中 MMM 、右 RRR 、和 SSS 四项数据。在这四项数据中,我们不仅要计入最优解的数值 sumsumsum ,同时还要记录最优解包含的区间最小值的个数 MincntMincntMincnt 。在一个区间的区间最小值不断增加的过程中,有一些包含更多区间最

2020-07-08 15:59:10

【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

【AtCoder】Tokio Marine & Nichido Fire Insurance Programming Contest 2020

比赛链接点击打开链接官方题解点击打开链接Problem A. Nickname输出 s1s2s3s_1s_2s_3s1​s2​s3​ 即可。时间复杂度 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

【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

【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

【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

【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

【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

【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

【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

【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

【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 &lt

2020-05-25 12:06:22

【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

【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

【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

【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

【UOJ529】【美团杯2020】114514

题目链接点击打开链接题目解法可以发现,在给定的序列 114514114514114514 中,每个 444 之前均有一个 111 。因此,从后向前,将每个 444 与前方最近的一个尚未匹配的 111 匹配,不会导致原本有解的数据无解。进行匹配后,每一个 1−41-41−4 结构的左右端点是分别具有单调性的。那么,剩余的问题就是将给定序列拆分为形如 123212321232 的序列。从左到右进行简单贪心即可,对于一个 222 ,我们会优先将其与 111 匹配。单组数据时间复杂度 O(∣S∣)O

2020-05-18 13:07:54

【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

【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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。