Larry1118-CSDN博客

原创人工栈——解决爆栈难题

我们便以tarjan_LCA为模板，顺便复习复习tarjan_LCA。node (dfs)(dfs)(dfs)#include<cstdio>#define N 500010 using namespace std;struct node{int v,fr;}e[N<<1];struct edge{int v,fr,num;}g[N<<1];int...

2019-06-01 22:03:26 817

原创用bat打的对拍程序

%d%a%l%a%o这位大佬写得很详细了。我们先建立一个TXT文件。然后在里面写好对拍代码：@echo off:loopSum_rand.exe//rand文件Sum.exe//C++文件Sum_bl.exe//暴力C++文件fc Sum.out Sum_bl.out//比较输出if not errorlevel 1 goto loop//一样就重复looppause//直...

2019-02-16 09:53:42 344

原创莫队算法总结

我的莫队例题都是从这儿的例题刷来的↙%d%a%l%a%o但我觉得莫队讲得好的还是hzwer大佬。下面是例题：bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2019-02-15 14:30:08 235 1

原创斜率优化DP 总结（含凸优化）

我看了很多%d%a%l%a%o的博客，使我对其印象深刻，下面是我从我看的第一个博客（%%%）中copy下来的：

2019-02-01 22:42:37 381

原创 AFO

rt.

2022-04-22 22:23:00 76

原创 test

test!

2021-12-13 21:06:00 72

原创百度之星初赛（全）

初赛一打疫苗去了，最后$30min$看了看题，打了一题还有一题没调出来。自己的思路太慢以及打代码速度太慢，别人可以$40min$切$5$题啊。。。初赛相对来说不算太难的。$T4,T8$是简单的模拟题。$T6$需要超级快读。感觉自己也需要背背这个板子。$T3$是简单的$DP$。初赛二这次是准时(迟了$10min$)开始打的。从$T1$开始打的，...

2021-08-13 20:05:00 73

原创 P4287 [SHOI2011]双倍回文

求最长双倍回文子串。考虑建PAM，我们可以知道最长回文子串，但是如何知道最长双倍回文子串呢？我们发现如果这个子串是双倍回文子串，那么该子串<=len/2的最长回文子串一定是=len/2的，我们可以再记录一个fail'表示<=len/2的最长回文子串后缀。求答案的时候枚举每个位置判断fail'的len即可。对于fail'的求法，类似fail的求法再判断len的限制即可。还有一...

2021-05-27 20:11:00 49

原创 APIO2021小记

游不了，只好改成小记了。由于多了几堂课，所以$cost$翻了个几倍了。听课还是比较有用的，就是有些课感觉似乎有点难消化啊。。。Day1决策四边形与优化就让我$MB$了。Day2$open$ $cup$趣题选讲思维能力要求高，有点难。。。Day3组合计数问题也听得有些云里雾里。。。Day4早上开赛，直接翘掉了上午的课，开始比赛。看了看题，感觉$T1$是一道...

2021-05-25 22:44:00 26

原创 PKUSC2021游记

$Day\ 0$坐飞机去余姚，玩，然后睡了。$Day\ 1$去报到，然后睡了会儿就开考了。$T1$签到题，$T2$想了会儿想到每个点向右边最近比它大的数连边成森林，这样部分分就很容易处理了。$T3$的第一档打了$2h+$结果还是爆零了，$100+46+0=146$大众分收场。。。吃晚餐+回酒店$FB$。。。睡了。。。$Day\ 2$参观余姚分校\(...

2021-05-18 20:20:00 33

原创 P3349 [ZJOI2016]小星星

P3349 [ZJOI2016]小星星对于子集$DP$的优化一般要上容斥。如果只是暴力枚举当前点以及子集状态的话一共要$O(3^n)$，而容斥后可以优化成$O(n*2^n)$。一般容斥都是把条件改成“至多”“至少”如何如何，这样我们枚举状态，然后$DP$中就不需要记录子集了。就是考虑从最原始的暴力$DP$设$f[i][j][S]$表示在树中$i$节点表示原图的...

2021-05-06 22:06:00 32

原创 GDOI2021简要题解

GDOI2021游记$Day\ 1$$T1$考虑修改一定是前缀和后缀，枚举修改的前缀，后缀指针移动取最优即可。需要预处理一下前缀$min,max$和后缀$min,max$。$T2$差分约束，爬了。发现限制不等式每个都有四个变量，考虑是否可以分成行和列。我们考虑是否对于每个位置$a[i][j]$用行和列来差分约束得到答案。考虑只修改第一行第一列上的数，考虑...

2021-04-22 21:49:00 40

原创 GDOI2021游记

GDOI2021简要题解$GDOI2021$游记$Day\ -n$停了四周的课，感觉自己也没有拿出很好的状态，在还没有复习好什么知识的情况下，猝不及防地到了出发的时候了。$Day\ 0$上午简单复习了一下$OI\ WIKI$上的一些知识点，想打打题练练手但最后懒导致什么都没打，于是就到下午了。出发，一路看番，旁边的卡爷中途还休息了$40min$！果然是视力\(5....

2021-04-15 22:05:00 28

原创 CSP-S 2020 总结（$deadline$）

内容$rt$。$before\ contest$买了咖啡+巧克力，希望这次考试不要浪费了我的$money$。$on\ contest$看了看$T1,T2,T3,T4$。(其实就是全部看了一遍)$T1$大模拟。$T2$应该就是一个$label$。$T3$拓扑序，但具体维护不清楚，之后被各种思路带歪了(主席树不行，然后想能不能对每个$a[i]$分开做，...

2020-11-08 16:38:00 29

原创 gmoj 3457. 【NOIP2013模拟联考3】沙耶的玩偶(doll)

$Problem$给你一张图，有些点可以走，剩下不能走。只能向下走，走$R*C$或$C*R$。求走完剩下所有可走点的最小路径数。$Solution$发现这种题暴力都比较难写，考虑特殊做法(网络流)。发现当可走点之间连了一条边以后，路径数就会$-1$，而且每个点只会被连一次。可以想到二分图匹配，每个点向可以走的点连边，然后二分图最大匹配的值就是可以连的边数了。那么...

2020-11-06 15:28:00 27

原创 gmoj 6848. 【2020.11.03提高组模拟】融入社会的计划

$Problem$给你$n$和长度为$n$的数组$a[]$。可以使$a[i]$增加成$a[i]'$，其代价为$a[i]'-a[i]$。求花费最小的代价使得满足对于任意的$i \in [2,n]$，$L<=a[i-1]+a[i]<=R$，$L,R$为给定的数。$n<=10^5.L,R<=10^6$$force$首先...

2020-11-03 22:25:00 28

原创 gmoj 6847. 【2020.11.03提高组模拟】通往强者之路

$Problem$有$T$组数据，对于每组数据：给你一个$n$和一个长度为$n$的数组$a[]$，其中的$a[i]$属于${n,n+1,n-1}$。而对于任意的$i>n$，$a[i]=\sum [i-j<=a[j]]$然后有$Q$次询问，每次询问给你$x$，求$a[x]$。$Solution$首先考虑暴力，显然可以用差分...

2020-11-03 21:15:00 23

原创 2020.11.03【NOIP提高A组】模拟总结

$Something\ extra$哇哇哇，前三题有两题原创，出题人$WJQ$%%%还有最后一题真的猛过头了。。。估分：$60 + 35 + 15 + 0 = 110$考场：$50 + 35 + 15 + 0 = 100$$T1$的$10$分部分分忘记开$long\ long$了。。。$T1$从$n+1$开始找规律(这样就去掉了$max$了)...

2020-11-03 16:31:00 29

原创 6845. 【2020.11.02提高组模拟】梯度弥散

$something\ extra$$mmp$，考试的时候还看错题了。。。以为是导入一次$x$，只能发射一次，求$\sum x$。然而：感觉自己看题的时候都不怎么仔细了。。。这种错误下次还是不要犯了吧。。。$Solution$考虑按$c$分情况讨论。对于$c=0$，可以直接扫一遍，注意要判$-1$。对于$c=1$，二分答案判断即可，判断用差分即可...

2020-11-02 21:56:00 31

原创 6809. 【2020.10.29提高组模拟】不难题

大意：给你$K$个$1$到$n$的排列，让你求$[L,R]$的序列的操作方案数。限定条件：每次操作只能取那些序列中的队首，且取出来组成的序列中不存在连续$R-L+1$个连续的相同的数。$n,K<=300$$Solution$这题可想到平面上只能向右向下走，有若干个障碍，从$(1,1)$走到$(n,m)$的方案数。考虑容斥，设$f[i]$表示当...

2020-11-02 09:39:00 25

原创 gmoj 6834. 2020.10.24【NOIP提高A组】T4.onmyodo

考场的时候没什么时间来想这道题。。。通过打表找规律(题解)，可以发现当$n$为奇数的时候先手必胜。而对于$n$为偶数的情况。观察当前排列的方案数。可以证明当当前排列的方案数为偶数的时候，先手必胜。证明：若删字符可胜，便删字符；否则便重排，最后必定是后手不得不删字符(无法再重排)。而对于方案数为奇数的情况的话，则可以证明删字符后的排列方案数仍为奇数，所以后手必胜。综上，\(n\...

2020-11-01 14:37:00 33

原创 gmoj 6829. 【2020.10.25提高组模拟】异或

$Solution$异或这个东西似乎很有看头，尝试操作一波，但发现无论是建树还是从每一位上面入手似乎都不太可以。于是最后打了个暴力走人。正解有一个性质，就是在排序以后，只有相邻两个数异或可能成为最小值。具体的就是，$a<b<c$，则只有$a\ xor\ b$或$b\ xor\ c$最小，一定有其中一个小于等于$a\ xor\ c$。所以我们只需要排一遍序...

2020-11-01 10:23:00 24

原创 gmoj 6808. 【2020.10.29提高组模拟】easy

$Solution$考虑$a[i]$互不相同的情况。对于$[L,R]$区间，当$mx-mi=R-L$的时候才满足条件。且此时有个恒等式：$mx-mi>=R-L$，变化得$mx-mi+L>=R$。我们在线段树的每一位存当前位置$mx-mi+x$的值。我们可以从小到大枚举$R$，然后对于$mx$和$mi$的更新直接在线段树上区间修改。对...

2020-11-01 09:58:00 36

原创 gmoj 6807. 【2020.10.29提高组模拟】tree

$Solution$我们假设$1$为根。考虑两种问题，对于每个节点$x$：一种是子树覆盖所有颜色，那答案就是$x$向上走的最远距离。另一种是子树以外的所有节点(包含该节点)覆盖所有颜色，那答案就是$x$往下走的最远距离。两个最远距离都可以预处理得到。考虑第一种情况：我们发现对于每种颜色$coli$，颜色为它的节点到根的节点子树都包含这种颜色了。那么这种颜色的...

2020-11-01 08:39:00 30

原创 jzoj 6838. 2020.10.31【NOIP提高A组】T4 小j 的组合

考虑将操作转变为每个点可经过次数$+1$，设每个点可经过次数为$e[i]$，那答案即为$\sum (e[i]-1)$。当每个点的可经过次数等于该点度数的时候，才应当是最优解。我们可以通过求直径，然后从直径一端开始跑，先跑非直径边后直接走直径，这样最优。由于每条非直径的边走完以后还要返回到父亲节点，所以答案$g$即为$n-直径节点个数$。#include <cst...

2020-11-01 08:23:00 22

原创 2020.10.31【NOIP提高A组】模拟总结

估分：$50 + 45 + 0 + 0 = 95$考场：$100(50) + 45 + 0 + 0 = 145(95)$应该是数据没有放完的锅。。。$T1$考场考虑$O(n^3)$暴力，每三个点求中点+求垂直平分线+求交点。正解很巧妙，它发现对于每三个点的九点圆心，是$(a+b+c)/2$。我们再把这式子拆一拆，合并同类项，发现就是每个点有\((n-1)*(n-2...

2020-11-01 07:35:00 16

原创 2020.10.29【NOIP提高A组】模拟总结

估分：$100 + 60 + 10 + 0 = 170$考场：$100 + 60 + 10 + 0 = 170$考场淦$T2$淦到自己疯掉了，结果只解决了反树的问题，对于子树覆盖所有点的不会。$T1$简单题。手玩一下即可。$T2$$Solution\ Access$$T3$$Solution\ Access$$T4$\(Solution\ ...

2020-10-29 22:40:00 25

原创 2020.10.25【NOIP提高A组】模拟总结

估分：$100 + 80 + 10 + 0 = 190$考场：$50 + 75 + 10 + 0 = 135$$T1$考场想复杂了。。。时间还$T$爆了。。想到似乎可以用最大流等于最小割来解决问题。然后发现每次删最少的边可以使答案最优。于是每次尝试删边并跑最大流判断。最后$TLE50$正解其实很简单，也其实应该最容易想到的。。。我们发现只需要每向外扩展一层的时...

2020-10-25 12:55:00 27

原创 6831. 2020.10.24【NOIP提高A组】T1.lover

表了一下，发现$dig$有值的数大概只有几万个，可以考虑做做。然后发现它要$gcd<=K$，考虑分解质因数后$DP$。然后不会。考虑$DP$，显然对答案有贡献的数位可以拆分成质因子。设$f[x][0/1][a][b][c][d]$表示当前到了第$x$位，是否有顶格，$gcd$为$2^a*3^b*5^c*7^d$的方案数。显然可以用数位$DP$转移...

2020-10-24 21:26:00 17

原创枚举一个数$n$的所有质因子

考虑先前的预处理欧拉筛。由于我们得到的$i*pri[j]$的$pri[j]$一定是$i*pri[j]$的最小质因子。所以我们可以用数组顺便存储一个数的最小质因子，并存一下之后跳到的位置。若$i%pri[j]==0$，则跳到$to[i]$，否则跳到$i$。$Code$void prepare() { fo(i, 2, n) { if (! label[i...

2020-10-24 16:40:00 26

原创 gmoj 6832. 2020.10.24【NOIP提高A组】T2.world

$Solution$发现只需要考虑$1$走了$n$步以后是否首次回到$1$即可。搞了半天发现还可以看看$1$走了$n/2$步后是否首次到达$n$。然后$GG$。正解发现可以倒推。考虑奇数情况，设$t=(n+x+1)/2$，那么$(t*2)%(n+1)=x$偶数情况显然也可以。所以题目就可以转换成了$2^n≡1(mod \ (n+1))$...

2020-10-24 15:38:00 17

原创 2020.10.24【NOIP提高A组】模拟总结

感觉自己好$sb$。。。估分：$0 + 30 + 0 + 0 = 30$考场：$30 + 30 + 0 + 0 = 60$$T1$$Solution\ link$$T2$我的心历路程+$Solution$$T3$可以发现，其实可以将合并化作$K$叉树。而对于$X$和$Y$，只要不相同就可以化作$0/1$来做(只需要求方案数)而每...

2020-10-24 15:36:00 14

原创 2020.10.17【NOIP提高A组】模拟总结

爆炸这就是没看数据范围不开$longlong$以及最后暴力都不调样例还有的结果死的透红透红的考场：$0 + 100 + 0 + 0 = 100$估分：$24 + 100 + 30 + 1 = 155$(16)$T1$一开始，$SG$函数？！昨天刚搞过！！！然后，到死也推不出来，打完暴力也找不到规律。我!@#^%……正解打出来了，但发现自己的打法似乎比别人的要...

2020-10-17 16:44:00 16

原创 6813. 【2020.10.05提高组模拟】送信

真的是我第一次打不是板题的三维偏序。。。打得我精疲力尽要死要活。。。$Solution$我们尝试将树上问题转化成一个平面内的问题。我们先按时间排序。对于添加一个点对，我们可以看成在$(dfn[x]$$ed[x],dfn[y]$$ed[y])$这个矩阵当中加$1$。到时候查询的时候只需要查询两个点$(dfn[x],dfn[y])$和\((dfn[y],dfn[x])\...

2020-10-13 11:46:00 14

原创 HDU 1506 最大子矩形

表示之前还不会这种类型怎么快速求值。。。$Solution 1$我们可以维护一个单调栈，使得$h$是递增的。每次到一个位置，删到前面第一个比它小的位置，记作$k$，然后最长的高度为$h[i]$的区间就是$[k+1,i]$。正着来一遍，再倒着来一遍即可。$Solution 2$ 笛卡尔树 $by$ $OIWIKI$...

2020-10-07 15:48:00 16

原创 2020.10.07【NOIP提高A组】模拟总结

估分：$100 + 100 + 0 + 0 = 200$考场：$0 + 100 + 0 + 0 = 100$($45$)$T1$考场打了个$hash$。不知道为什么炸了。而后发现，原来不需要模。$K<=10$，而最多只有四个字母。所以最大也就$5^10$次方左右吧，只有$100+$万，用个桶来维护最后扫一遍即可。$T2$显然可以发现，只有...

2020-10-07 12:22:00 18

原创 6815. 【2020.10.06提高组模拟】树的重心

考虑重心的定义，然后解题。$force$ $1$暴力枚举每个点作为根节点，然后求出这个点为第一重心的方案数。时间复杂度$O(n^2*K)$#include <cstdio>#include <cstring>#include <algorithm>#define N 50010#define mo 1000000007#defin...

2020-10-06 20:08:00 20

原创 2020.10.06【NOIP提高A组】模拟总结

估分：$100 + 10 + 20 = 130$考场：$100 + 0 + 20 = 120$($15$)$T1$题意比较简单，然后思考一下。我们可以先分好块，然后在线存一下相邻的各种颜色的那些编号。在操作的时候就将那些颜色的更新，并更新一下相邻颜色的编号。$T2$$TJ$$T3$正解是笛卡尔树，但我不了解。。。总结一定要注意一下时间，不要最后...

2020-10-06 17:03:00 26

原创 2020.10.05【NOIP提高A组】模拟总结

估分：$40 + 30 + 0 + 30 = 100$考场：$80 + 43.3 + 0 + 30 = 153.3$($10$)$T1$考场打的是$O(n^3)$暴力$DP$，结果。。。其实可以优化到$O(n^2*logn)$的，用多项式优化即可。但是正解其实离暴力$DP$很近了。只要像上述技巧一样，在$dfs$下去之前下传，走完子树以后再传回当...

2020-10-05 19:30:00 22

原创 gmoj 3976. 【NOI2015模拟1.17】⑨

$Problem$给你$n$个点，以及$m$个有贡献的点。而后给你一个简单多边形(由那$n$个点组成)，求里面的有贡献的点的贡献和。这是样例↓$Solution$显然我们可以将这个简单多边形拆成一些与原点相连的三角形。也就是说，对于$AEF$，可以变成$HEF-HAE-HAF$，而对于正负的取值：若边是按照逆时针来看的，则向右走的边为负，向左走的边为正。...

2020-09-26 15:37:00 26

空空如也

空空如也