3 syh0313

尚未进行身份认证

我要认证

noip rp++

等级
TA的排名 7w+

2020赛季CF训练记录

cf id:ILLLZKQF 场次:205.10“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 solved:6/10 rank:37 补题:6/1005.10AtCoder Beginner Contest 167 solved:5/6 rank:422 补题:5/6...

2020-05-11 10:04:04

2020寒假训练汇总

cf id:ILLLZKQF01.21Educational Codeforces Round 41 (Rated for Div. 2) solved:5/7 rank:94 补题:7/701.22Codeforces Round #615 (Div. 3)solved:5/6rank:251 补题:6/601.29Educational Codeforc...

2020-01-21 21:42:35

【AHOI2013】差异

后缀自动机想到了其实挺简单的首先对于后缀的前缀,我们不太好维护,所以我们可以考虑将字符串倒过来,这样就变成了维护前缀的后缀!那么我们自然就想到了后缀自动机然后我们观察这个式子发现恰好是是求parent树上任意两点路径和,那么我们在parent树上算一下每条边的贡献就好了。对于一条边,他的贡献就是(len[x]-len[fa[x]])*si[x]*(n-si[x])现在我们来...

2019-12-22 21:09:52

【NOI2018】你的名字

后缀自动机+主席树为这种精妙的字符串题调上一天真的是件很幸福的事呢!题意转化过来之后就变成:给一个串S,有若干个询问,每次询问给字符串T,整数 L,整数 R,询问有多少个子串k使得k是T的子串但不是S[L]....S[R]的子串1.首先我们考虑这个问题的弱化版本,每次询问的L≡1,R≡len(S) ——68pts对于T的每个[ 1 , i ]的前缀子串,我们假设其后缀在S中...

2019-12-17 22:42:46

【HEOI2015】最短不公共子串

后缀自动机+序列自动机分别建出A,B两个串的后缀自动机和序列自动机,然后因为后缀自动机和序列自动机都是DAG,所以在上面dp一下就可以啦dp[i ][ j ]表示在第一个状态的自动机上匹配到 i 号节点,在第二个状态的自动机上匹配到 j 号节点时 还需要添加dp[i ][ j ]个字符才能使两串失配(满足条件) ,这个记忆化搜索一下就好了复杂度:O(N+N*N)#inclu...

2019-12-16 21:46:36

【SDOI2016】生成魔咒

后缀自动机入门题因为后缀自动机上无相同字符串,所以每次添加一个字符之后增加的本质不同的字符串的个数就是len[x]-len[fa[x]]#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <map>using ...

2019-12-11 16:11:56

【HAOI2016】找相同字符

后缀自动机入门题分别对两个串建后缀自动机,然后把endpos的大小算出来,最后在两个后缀自动机上一起dfs一遍并且算答案。#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;const int max...

2019-12-11 11:28:00

【NOI2015】品酒大会

后缀自动机首先考虑第一问: 我们先将后缀自动机建出来,考虑每个节点,它出现的次数肯定是endpos的size(我们记为num),那么选取这个节点的串的方案数即为C(num,2)=num*(num-1)/2,所能贡献的长度区间为这个节点对应的所有串的长度即[ len[fa[x]]+1 , len[x]+1 ],这里可以差分一下,最后前缀和就是答案了。然后考虑第二问: 我们...

2019-12-11 10:33:19

Educational Codeforces Round 76 G Divisor Set

Divisor Set结论+生成函数优化dp+NTT+启发式个人感觉这道题非常好!非常精妙!1.首先我们要知道一个结论:我们把这个数的约数按拥有的质因子数(可重)划分,第i类约数表示有i个可以重复的质因子然后我们从每一级的约数a向它的下一级约数b(a%b==0 且b只比a少一个质因子)连边,那么这个图显然是个DAG显然如果我想找最大的可选的约数,那么从n级到1级的任意...

2019-11-26 17:05:46

bzoj1057

单调栈对于每个位置(i,j)维护一个向下的最长的合法长度v[i][j]然后对于某一行来说问题就转换为:对于一个数列a[i],找一段连续的区间[l,r]是的(r-l+1)*min(l,r)这就是一个经典的单调栈问题了复杂度:O(n*m)/**************************************************************Pr...

2019-11-06 11:52:18

bzoj1084

对于m=1的情况:dp[j][i]表示选到i位,选了j个的最优值对于m=2的情况:dp[l][i][j]表示第一列选到了i第二列选到了j选了l个的最优值/**************************************************************Problem: 1084User: syh0313Language: C++...

2019-11-06 10:58:17

bzoj3524

主席树当时疯狂在想树套树+分块,自闭一下午结果一个正常的主席树就切掉了我太难了~#include <iostream>#include <cstdio>#include <cstdlib>#include <map>#include <algorithm>#define lch a[n].lc#define r...

2019-10-16 17:10:23

bzoj1901

树状数组套权值线段树单点修改logn 然后树状数组将序列分成了log段 每段都暴力修改 这样一次修改的复杂度是log^2的然后查询就将这个[1,r]的所有权值线段树之和减去[1,l-1]的所有权值线段树之和,在这个值上面二分就可以了#include <iostream>#include <cstdio>#include <cstdlib>#in...

2019-10-16 12:49:26

bzoj2654

wqs二分首先二分一个白边所加的权值然后根据当前MST(若黑白边权值相同则优先选白边)中白边的数目二分若白边数过多,则增加所加的值若白边数过少,则减小所加的值/**************************************************************Problem: 2654User: syh0313Lang...

2019-09-25 15:45:41

bzoj4516

后缀自动机板子题一开始把后缀自动机封装了直接ce两发orz本质不同的子串个数就是所有len[x]-len[fa[x]]的累加和然后insert一个字符算一次复杂度:均摊O(n) /************************************************************** Problem: 4516 User...

2019-09-17 16:33:29

bzoj4025

时间线段树+启发式合并并查集启发式合并并查集只需要记录下合并前的转态,合并的时候按秩合并,然后根据之前记录的状态回退就好了我的代码常数有点大(早上交T了,晚上就卡着过了)/**************************************************************Problem: 4025User: syh0313La...

2019-08-14 20:37:08

bzoj1861

splay1操作:从平衡树中取出这个数,把rank改成最小,再insert进去2操作:从平衡树中取出这个数,把rank改成最大,再insert进去3操作:取出x和它相邻的数(1是右相邻,-1是左相邻,0直接continue)4操作:查询x的rank5操作:查询rank=x的数/*************************************************...

2019-07-28 17:31:32

bzoj2286

虚树如何构建虚树:step1:将询问点按dfs序排好,root节点作为非关键点先入栈step2:判断当前要加的点a[i]和sta[top]的关系 我们令lc=lca(a[i],sta[top]); (1).如果lc在栈sta中并且就是栈顶的话,直接将a[i]加入栈 (2).如果lc在栈sta中但是不是栈顶的话,一直弹...

2019-07-17 23:27:00

bzoj2152

点分治按重心分治,每次暴力统计x下所有子树和的答案,分治进子树的时候减去该子树中的贡献即可复杂度:nlogn/**************************************************************Problem: 2152User: syh0313Language: C++Result: Accept...

2019-07-15 22:04:01

bzoj1935

树状数组将询问差分成四个矩阵之后就变成一个二维偏序问题,用树状数组搞一搞就好了 /************************************************************** Problem: 1935 User: syh0313 Language: C++ Result: Accepte...

2019-07-02 17:39:48

查看更多

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