2 V4yne.

尚未进行身份认证

我要认证

HDU18级新生,ACM菜狗。

等级
TA的排名 12w+

FlaMinG0队2020暑假集训总结。

1 反复取模 反复取模关于取模或者求逆元的题目中,每一步运算写完都要思考是不是要加个取模!!!2.交题前再次检查交题前多次确定运算数据会不会溢出,检查 ll 和 int128的使用,检查数组是否开小。(图论题边数组。)3.卡题时应对(1)当题目过了一车人并且我们思路很难时应该优先考虑暴力和贪心。(2)卡题时间太久时尝试换题4 开题顺序数据结构题尽量一起思考思路转换问题。数学题一定要让 yzj 先看看,也许就能写了。...

2020-08-07 16:17:55

Count New String 牛客第四场C题解

题解:对给出的方程式进行几次递推后可以得到答案就是一次变化得到的所有字符串的不同的子串种类数。很显然这个转换后的问题是广义后缀自动机的模板题。不过我们不可以一次次处理出所有的这样的后缀再一个个地插入到广义后缀自动机里面求解答案,那样的做法显然会 tle。这时候注意到题目说字符集只有 a 到 j 这10个字母,那么最坏的情况这些字符串就是:aaabbbaaabbbccc这样的形式,最多是10N。我们从右往左枚举字符串的每一个字符,然后寻找其右边第一个大于自己的字符,然后当前字符到第一个大于自己的

2020-07-24 16:57:15

bzoj 2326 数学作业(dp+矩阵快速幂)

题目:Description小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题:给定正整数 N 和 M要求计算 Concatenate (1 … N) Mod M 的值,其中 Concatenate (1 …N)是将所有正整数 1, 2, …, N 顺序连接起来得到的数。例如,N = 13, Concatenate (1 … N)=12345678910111213.小C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。

2020-07-22 00:16:30

洛谷p3390 矩阵快速幂模板

题目链接存一下矩阵快速幂的板子。= =AC代码:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=105; const int mo=1e9+7;ll n,m;struct ahaha{ ll a[maxn][maxn]; //一定要用long long存矩阵,否则在过程中会爆掉 ahaha() { memset(a,0,sizeof a); }

2020-07-21 18:45:56

BZOJ3555 企鹅QQ 字符串hash

题目:DescriptionPenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种

2020-07-19 01:39:34

BZOJ 2084 Antisymmetry

题意:对于一个01字符串,如果将这个字符串0和1取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如00001111和010101就是反对称的,1001就不是。现在给出一个长度为N的01字符串,求它有多少个子串是反对称的。数据范围:N小于等于5e5。题解:类似于回文串,不过匹配的是按照不相等来匹配,利用manacher的思想可以O(n)过。代码:#include<bits/stdc++.h>using namespace std;const int maxn=1e6+

2020-07-15 21:51:32

挖坑,要写的题目

bzoj4932— 区间不同回文串种类数(强制在线)洛谷p6172bzoj3195—状压dp

2020-06-24 02:45:19

V4yneの求lca的倍增模板

代码:const int maxn=1e5+50;vector<int> edge[maxn];int rot;int dep[maxn];int rec[maxn][30];void dfs(int x,int fa){ rec[x][0]=fa; dep[x]=dep[fa]+1; for(int i=0;i<edge[x].size();i++) { ...

2020-02-19 19:29:46

V4yne的模板----树的问题

1.求树的直径与两个端点。(两遍dfs,son记录端点。)2.换根dp求解树上每一个点为根时的最长链。(dp,dp0是子树中最长值,dp1是子树中次长值,dp2是答案)。3.最大或者最小的点覆盖或者边覆盖。...

2020-02-03 01:19:39

V4yneの模板(总)

V4yneのACM模板----前向星模板struct node{ int to,next;}edge[2*maxn];//存储的是边,双向边之类,一般开边数*2int e,head[maxn];void edge_init(){ memset(head,0,sizeof(head)); e=0;}void add_edge(int u,int v){ edge[++e]...

2019-09-03 23:18:56

网络流模板

Dinic最大流:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=5050;const int maxm=1e5+50;const int inf=0x3f3f3f3f;int n,m,s,t;ll maxflow;int vist;int vis[maxn];int dep[maxn];int cur[maxm];struct node{ int to,ne

2020-06-16 12:30:04

洛谷 P4555 [国家集训队]最长双回文串(manacher马拉车算法)

题目链接题目思路:先对字符串做变形处理成s字符串,然后马拉车处理出s字符串的每一个位置做对称轴能往两边扩散的最长距离。对于每一个位置维护:ll 数组:以 i 做起点的最长的回文串长度。rr数组:以 i 做终点的最长的回文串长度。需要注意的是,处理完后还要dp更新一下所有点的 ll 和 rr 数组。以及这题必须要分成两个字符串,而不是单个字符串,如果只是aba这样的数据,输出应该是2而不是1。AC代码:#include<bits/stdc++.h>using namespace s

2020-06-19 13:07:19

2019牛客多校第四场B xor (884B)(线性基求交+线段树)

题目链接题目大意:给出n组数以及m组询问。每组询问包括l,r,x,如果第 l 到 r 内的数组都可以异或运算出 x,输出YES,否则输出NO。思路:显然关于能不能异或表达出一个数字x需要用到线性基,多组数字都需要满足能表示出x,那么就需要对这些数字的线性基求交。不过这题还有一个条件,询问的是区间内的线性基交。其实也很简单,利用线段树维护,每一个叶子节点的线性基就是一组数字的线性基,区间的合...

2020-03-23 13:15:43

codeforce 1167B

交互题模板题,用来学习交互题的格式的。我写的第一道交互题,记录一下AC代码:#include<bits/stdc++.h>using namespace std;int arr[10]={0,4,8,15,16,23,42};int brr[105];int main(){ for(int i=1;i<=4;i++) { printf("? %d %d\n"...

2020-03-22 14:50:12

牛客多校2019第一场H题881H XOR

如果这m个元素中的某一个元素能被剩下的n-1个元素表示出来,那么一定存在一组不包括这个元素的大小为m的线性基。那么这时候这个元素对于答案的贡献也是2的n-m-1次方。如果这个元素不能被剩下的n-1个元素表示出来,那么它的贡献是0。

2020-03-22 14:48:12

Codefoece Educational Codeforces Round 83 (Rated for Div. 2)题解,(ABCDE)

比赛链接A题:思路:签到题。代码:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2e5+50;int t,n,m;int arr[maxn];int main(){ ios::sync_with_stdio(false); cin>>t;...

2020-03-10 15:44:01

Codeforce Ozon Tech Challenge 2020 (Div.1 + Div.2)2020.3.3题解(ABCDE)

A题:思路:签到题,没啥好说,给的两个数组里的每个数字都是彼此不相同的,要求和两两不同,显然对两个数组分别排序输出即可。代码:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2e5+50;int t,n,m;int arr[maxn];int brr[maxn...

2020-03-04 16:28:38

牛客寒假训练赛2H.施魔法题解

链接:题目地址思路:比赛的时候感觉到了肯定有一种方式是排序后连续地取时最佳,然后很自然地写出了dp方程,不过那时候写的dp方程是n2的复杂度,就没有接着比赛了七题滚粗了。其实这个题目让我想起了很多时候的dp题目都不会那么直白的dp,很可能是需要优化的,当需要枚举一个区间里面的最小值时,我们就应该想办法把dp方程中下标为i的东西拿出来,下标为j的拿出来,在dp的过程中同时维护有关于j的式子的最大...

2020-02-07 22:23:44

2019内蒙古大学生程序设计竞赛G

2019内蒙古大学生程序设计竞赛G链接:https://www.bttcacm.cn/problem.php?id=1785题目描述小明在玩一个战略游戏。他现在的任务是找到敌方的军队在什么地方。他已经知道敌方的军队可能在的几个区域和每个区域敌方的军队可能存在的概率,且敌方的军队只可能存在于这些区域中的某一个区域当中。他拥有一个科技:可以同时扫描若干个区域并花费区域个数的金钱。但游戏有一定的限...

2019-07-07 23:58:12

codeforce Round#615 Div3.(ABCDEF)

戳我:比赛地址A.Collecting Coins题解:A题憨憨签到题,直接发代码辽,注意判一下大于小于。#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ios::sync_with_stdio(false); int a,b,c,n; int t; cin&g...

2020-01-28 14:59:46

查看更多

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