- 博客(31)
- 收藏
- 关注
RSS订阅原创 POJ 2778 DNA Sequence【AC自动机】【矩阵快速幂】
DNA Sequence传送门。这题搞了我几个小时。先睡了，回头补博客。题意：传送门AC自动机学习博客：传送门矩阵快速幂学习：队友wqqq的模板AC自动机模板：bin巨板子胡改矩阵快速幂模板：结合网友+小破站up #include<cstdio>#include<queue>#include<cstring>#include<al...
2019-09-18 03:06:59
143
原创 HDU 3613 Best Reward【Manacher】
Best Reward传送门。题意：把一个串串砍一刀，变成两个串串，求两个串串价值之和最大串串由26小写字母组成，每个字母都有对应的价值定义串串的价值=是回文串 ? 串串每个字母价值之和 : 0;T组测试数据每组第一行 26的int值，表示每种字母的价值第二行是一个串串思路：预处理出（假设都有价值）串串价值的前缀和与后缀和。跑一边马拉车得到 Mp[]Mp[]Mp[]...
2019-09-11 21:17:33
100
原创 HDU 2609 How many【最小表示法】
How many传送门。题意：多组输入每组一个n，串串个数通过首尾相连可以相同的串算一类，求一共有几类串。For example 011001100110 express a necklace, you can rotate it. 0110−>1100−>1001−>0011−>0110.0110 -> 110...
2019-09-11 10:17:14
145
原创 HDU 3746 Cyclic Nacklace【KMP】
Carneginon传送门。题意：T组数据给一个串串，求最少加入多少珠子（只能在串串首尾加），将这个串串首尾相接后，是一个有循环的串串。思路：next[]next[ ]next[] 数组的应用。板子。是时候开始认真学一学串串，锻炼锻炼代码能力了。#include<cstdio>#include<cstring>const int M...
2019-09-11 01:31:39
116
原创 Xuzhou网络赛19 D.Carneginon【KMP板子】
Carneginon传送门。题意：依题意用 KMPKMPKMP 判断模拟一遍，签到题。思路：1≤∣T∣≤1051≤∣T∣≤10^51≤∣T∣≤105 , 1≤∣S∣≤1051 \leq |S| \leq 10^51≤∣S∣≤105 , 1≤∣S∣≤1051≤∣S∣≤10^51≤∣S∣≤105 , 1≤q≤10001 \leq q \leq 10001≤q≤1000数据保证 q...
2019-09-10 20:33:16
110
原创 Xuzhou网络赛19 B.so easy【并查集】
so easy传送门。题意：第一行两个数 n,qn,qn,q ,给一个数列(1,2,3,...,n)(1,2,3,...,n)(1,2,3,...,n)，qqq 组操作接下来 qqq 行 每行两个数 ziz_izi xix_ixi，ziz_izi(z=1z=1z=1 or 222)为操作，xix_ixi为操作位置数据范围：(1≤x<n<109...
2019-09-10 16:54:13
96
原创 Xuzhou网络赛19 E【线段树】
XKC’s basketball team传送门。题意：第一行两个数nnn mmm (2≤n≤5∗105,0≤m≤109)(2\leq n\leq 5*10^5, 0\leq m \leq 10^9)(2≤n≤5∗105,0≤m≤109)第二行nnn个数的序列 w1..wn(0≤wi≤109)w_1..w_n(0\leq w_i \leq 10^9)w1..wn(0≤wi≤109...
2019-09-08 08:15:50
103
原创 CF #579 (Div. 3) C. Common Divisors【唯一质因数分解定理】
C. Common Divisors（div3）传送门。题意：给你 nnn 个数，求这 nnn 个数的公因子个数。gcd扫一遍找出 nnn 个数的最大公倍数 xxx ，xxx 的因子个数就是答案。求 xxx 的因子个数用 唯一质因数分解定理：任意一个合数 xxx 仅能以一种方式，写成如下的乘积形式：(pieipi^{ei}piei为素数)xxx =p1e1×p2e2×…×prerp...
2019-08-14 02:02:42
270
1
原创 大一暑期集训一【栈和队列】
栈和队列课堂练习手造链队列手造邻接表手造栈训练赛（部分）丑数括号匹配课堂练习手造链队列#include<cstdio>typedef struct QNode{ int data; QNode *next;}QNode;typedef struct{ QNode *front; QNode *rear; }LQ;QNode *p;LQ q;v...
2019-07-15 21:52:02
143
原创 ZUT第十届校赛
ZUT第十届校赛A: zzq和飞行棋（签到题 * 1）B: syp和验证码（签到题 * 2）C: syp和强迫症Ⅰ（二分）D: syp和强迫症Ⅱ（线段树）E: syp和强迫症Ⅲ（STL）F: wzy和ly和怪兽（签到题 * 3）G: ly和旅游（最短路）H: wsw和字符串（DP）I: syp和ly和￥100（BFS）J: syp和鸽子（签到题 * 4）K: ly和难题（签到题 * 5）还没...
2019-06-04 17:02:24
307
1
原创 2019 ICPC全国邀请赛（西安）参赛小记
2019 ICPC全国邀请赛（西安）参赛小记几点感想和省赛完全不同，省赛可以一巨两蒻，西安赛必须开多线程，不然几乎不太可能银及银以上。队友很重要！队友很重要！队友很重要！嘤语很重要！嘤语很重要！嘤语很重要！关注公告栏！关注公告栏！关注公告栏！建议明年赛季开始前（3月份）组好队，多打几次组队赛，找到自己所长，多练练此方向题。（如果一个队没有数论、计算几何选手会很尴尬）,明年校赛可...
2019-05-21 21:52:17
643
原创 POJ 3984 迷宫问题【BFS】
#include<cstdio>#include<queue>#include<stack>using namespace std;int dx[]={1,0,-1,0},dy[]={0,1,0,-1},book[6][6],inq[6][6],a[6][6]; struct S{ int x,y; S(int xx,int yy):x(xx...
2019-05-21 21:49:27
171
原创 51nod 1006 最长公共子序列Lcs【DP】
题目。#include<cstdio>#include<string>#include<iostream>using namespace std;string a,b,ans;const int Max_num=1e3+17;int dp[Max_num][Max_num],book[Max_num][Max_num];int main()...
2019-05-21 21:47:13
158
原创 HDU 4841 圆桌问题 【STL】
圆桌问题1000 MS & 32768 KProblem Description圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。...
2019-05-21 21:46:35
359
原创 HDU 2553 N皇后问题 【DFS】
#include<cstdio>#include<cstring>int n,ans,res[15],zm[11];bool book[15],b1[50],b2[50];void dfs(int x,int step){ //第x行 if(step==n){ ++ans; return; } for(int i=1;i<=n;++i){...
2019-05-21 21:45:41
116
原创 CF #560 (Div. 3) D. Almost All Divisors【思维】
D. Almost All Divisors（div3）2 seconds & 256 megabytesWe guessed some integer number x. You are given a list of almost all its divisors. Almost all means that there are all divisors except 1 an...
2019-05-16 21:55:45
210
原创 河南第十二届ICPC参赛小记
河南省第十届ICPC参赛感受第一天中午到比赛点报道，没有午餐券差评。下午热身赛，hxw巨巨和我们说，热身赛就是试一试环境，然后我还真信了，热身赛 != 签到题最后，未来酒店好评，奖牌尺寸好评。...
2019-05-16 13:46:06
255
原创 线段树
目录1 写在前面1.1 什么是线段树2 线段树基础操作2.1 线段树的构建和查询2.2 线段树的单点修改2.3 线段树的区间修改3 线段树常见应用3.1 扫描线法3.2 线段树解决离线询问3.3 线段树上二分3.4 线段树上找答案3.5 线段树优化图3.6 线段树维护树上信息3.7 线段树维护区间可合并信息3.8 线段树维护不可合并信息3.9 线段树维护最大子段和4 线段树进阶4.1 线段树的分裂...
2019-04-24 19:03:55
397
原创 函数集册
unique函数（去重）第一次遇到是在 线段树的离散化。“删除”序列中所有相邻重复元素（只留一个），所以常常在unique前先sort。其实所谓的“删除”，并非真正意义上的删除，而是将下一个不同元素前移（而相同元素就被移到序列尾巴了），故序列长度不变。两个参数的unique: //iterator unique(iterator it_1,iterator it_2); //下面...
2019-04-23 20:44:52
249
1
原创 初始化操作
初始化无穷大#include<cstdio>int main(){ //0x7fffffff //2147483647 int a=0x7fffffff; // int 的极限值 int b=0x3f3f3f3f; // int 取无穷大 emmmmm也好记 // int 极限值+1爆表后会=-(a+1) printf("a=%d,a+1=%d\n",a,...
2019-04-23 08:41:06
416
原创 POJ 1724 ROADS 【带一维限制的最短路】【dijkstra】
ROADS Time Limit: 1000MS； Memory Limit: 65536K DescriptionN cities named with numbers 1 … N are connected with one-way roads. Each road has two parameters associated with it : the road length an...
2019-04-22 21:02:40
156
原创 字符串操作
字符串骚操作这是zzq学长大一上教我们的，基本没用过，都快忘了，今天整理一下当时做的笔记。sscanfsscanf(&," “,&);提取字符串中的特定字符表达式1为被提取字符串的首地址表达式2为提取元素的字符控制，相当于scanf”"中的内容表达式3为提取出元素存放的地址 char s[105]="1(2)3"; int a,b,c; sscanf(s,"%...
2019-04-22 19:08:10
132
2
原创 牛客 第十五届华中科大邀请赛 J Mex 【贪心】
J Mex输入31 2 5输出4说明:S’=(), ∑S’=0S’=(1), ∑S’=1S’=(2), ∑S’=2S’=(1,2), ∑S’=3S’=(5), ∑S’=5There is no way for ∑S’=4, hence 4 is the answer.题目呜呜呜，签到题都不会，菜枯辽。第一次爆零，补个签到题留念。这个算思维题？贪心？我不懂题意...
2019-04-22 09:36:28
109
原创 牛客 哈工程十四届程设 C 简单的烦恼【DFS】【DP】
点对 3000ms / 262144K 题目描述网易云音乐推出了定时关闭播放的功能，假设到了定时关闭播放的时间，当前这首歌还没有播放完，那就把它播放完关闭；如果到了定时关闭的时间，当前歌恰好播放完，那就立即关闭。xrc 在知道网易云这个算法后，想知道如果自己定时 t 时间后关闭播放，那最多能听多长时间的歌，已知 xrc 歌单中一共有 n 首歌，并且知道每首歌的播放时间分别是 a[i]。...
2019-04-22 08:26:30
173
原创 CF #551 (Div. 2) C Serval and Parenthesis【贪心】
C. Serval and Parenthesis Sequence - 1s / 256 megabytes 题目描述Serval soon said goodbye to Japari kindergarten, and began his life in Japari Primary School.In his favorite math class, the teacher ...
2019-04-15 13:47:45
167
原创 牛客 桂电第三届程设赛 F 点对【Floyd】
点对 1000ms / 262144K 题目描述小猫在研究有向图。小猫在研究联通性。 给定一张N个点，M条边的有向图，问有多少点对(u,v)(u<v)，满足u能到达v且v也能到达u。输入描述:第一行两个正整数N,M，表示点数与边数。接下来M行，第i行两个正整数ui,vi，表示一条从ui到vi的边，保证ui≠vi。输出描述:一行一个整数，表示点对数量。示例1输入3 3...
2019-04-15 09:38:05
120
原创 被 带 飞 日 记
//2.1.1递归函数-fib #include<cstdio>#include<cstring>int m[100]; //记忆 int fib(int n){ if(n<=2) return 1; //出口 if(m[n]!=0) return m[n]; return m[n]=fib(n-1)+fib(n-2); //新学的操作 }i...
2019-04-14 16:59:45
258
原创 牛客 2019西北工业(重现赛)H 最少拐弯数【BFS】
最少拐弯数 - 输入4 4S..*.*.*.....*.T输出2 - 题意：给你一个有起点与终点的图，求最小拐弯数。 - BFS，往一个方向一直走（即同一方向一次全入队）。注意遇已走过处应选择不更新（没必要），同时跳过继续走，而非停止脚步。#include<cstdio>#include<queue>using namespace ...
2019-04-07 10:19:34
207
原创 大一下前四周总结
睡不着，写个月末总结。三月总体而言，生活规律，学习比较高效，但饮食与消费不够节制。学会： 尺取法 欧拉筛 二分搜索 快排的板子 任意进制转化 快速乘优化快速幂不熟： 入门分治 入门贪心 入门栈和队列（循环队列） kmp字符串 STL无数函数没学会的： exgcd（因为我已经忘了） 矩阵快速幂感谢学姐学长们的的博客，能学到很多。从ly大佬的博客里，我明...
2019-03-25 17:03:45
131
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人