ComplexPug - 个人主页动态 - 牛客网

发布(286) 刷题

2019-07-24 17:51

已编辑

东北大学计算机类

[SDOI2010]捉迷藏 K-Dtree

[SDOI2010]捉迷藏 链接 luogu 思路 k-dtree模板题 代码 #include <bits/stdc++.h> #define ls (t[u].ch[0]) #define rs (t[u].ch[1]) #define cmin(a,b) (a>b?a=b:a) #define cmax(a,b) (a>b?a:a=b) using namespace std; const int N=5e5+7; const int INF=0x3f3f3f3f; int read() { int x=0,f=1;char s=getchar...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

NOI2019 回家路线 DP

「NOI2019」回家路线 链接 loj 思路 f[i][j]第i个点，时间为j，暴力转移 复杂度O(m*t),好像正解是斜率优化，出题人太不小心了233 代码 #include <bits/stdc++.h> using namespace std; const int N=2e5+7,INF=0x3f3f3f3f; int n,m,A,B,C,f[100007][1007]; struct node {int x,y,p,q;}a[N]; int fff(int x) {return A*x*x+B*x+C;} bool cmp(node a,node b) {re...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

bzoj4066: 简单题 K-Dtree

bzoj4066: 简单题 链接 bzoj 思路 强制在线。k-dtree。 卡常啊。空间开1e6就T了。 代码 #include <bits/stdc++.h> #define my_min(a,b) (a<b?a:a=b) #define my_max(a,b) (a>b?a:a=b) using namespace std; const double alpha=0.75; const int N=2e5+7; int read() { int x=0,f=1; char s=getchar(); for(; s>'9'|...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luoguP4169 [Violet]天使玩偶/SJY摆棋子 K-Dtree

P4169 [Violet]天使玩偶/SJY摆棋子 链接 luogu 思路 luogu以前用CDQ一直过不去。 bzoj还是卡时过去的。 今天终于用k-dtree给过了。 代码 #include <bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f,N=1e6+7;; const double alph(0.75); int WD,ans,rub[N],tot,top; struct Point { int x[2]; bool operator < (const Point b...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luoguP4112 [HEOI2015]最短不公共子串 SAM,序列自动机，广搜BFS

luoguP4112 [HEOI2015]最短不公共子串 链接 luogu loj 思路 子串可以用后缀自动机，子序列可以用序列自动机。 序列自动机是啥，就是能访问到所有子序列的自动机。 每个点记录下一个字母最近出现的位置。不过我这里构造是\(O(n^2)\)。 然后进行bfs进行广搜就行了。 注意vis[][]剪枝，要不TLE。 代码 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=2000+7; int n,m; struct node { int ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luogu P4248 [AHOI2013]差异 SAM

luogu P4248 [AHOI2013]差异 链接 luogu 思路 \(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)-2*{lcp}(T_i,T_j)}\) =\(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)}-\sum\limits_{1<=i<j<=n}2*{lcp}(T_i,T_j)\) 前半部分是\(\frac{n*(n+1)(n-1)}{2}\) 后半部分用sam求出parent tree的siz的过程中求解就行了。 两个串的...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

cf1191 解题报告

cf1191 解题报告 A-简单模拟 脑内算出来让计算机输出 #include <bits/stdc++.h> #define ll long long using namespace std; int main() { int x; cin>>x; if(x%4==0) return puts("1 A"),0; if(x%4==1) return puts("0 A"),0; if(x%4==2) return puts("1 B"),0; if(x%4...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luogu P3975 [TJOI2015]弦论 SAM

luogu P3975 [TJOI2015]弦论 链接 bzoj 思路 建出sam。 子串算多个的，统计preant tree的子树大小，否则就是大小为1 然后再统计sam的节点能走到多少串。 然后就可以在sam的贪心的走了。 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define ROF(i,a,b) for(int i=a;i>=b;--i) using namespace std; const int N=5e5+7; int n,t,k,c[N<&...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

bzoj3676 [Apio2014]回文串卡常+SAM+树上倍增

bzoj3676 [Apio2014]回文串 SAM+树上倍增 链接 bzoj luogu 思路 根据manacher可以知道，每次暴力扩展才有可能出现新的回文串。 所以推出本质不同的回文串个数是O(n)级别的。 每次查询一个串出现的个数。 建立出parent树，一个串出现的个数就是对应parent树上的所在的子树的大小，利用树上倍增可以log求出一个串出现的个数。 具体一点，我们知道endpos，可以找到对应parent tree的节点。 然后目标节点肯定是在根到此节点的路径上的(他是她的后缀嘛)。 用子串长度和节点的longest比较就行了，倍增慢慢跳。 总的复杂度\(O(nlog...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

cf1187解题报告

cf1187解题报告 cf A 去掉都有的,剩下的取最大值+1 #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int T; cin>>T; while(T--) { int n,s,t; cin>>n>>s>>t; int k=s+t-n; s-=k,t-=k; int ans=max(s,t)+1; ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

cf1189解题报告

cf1189div2解题报告 codeforces A 答案要不是一串要不就是去掉最后一个字母的两串 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=107; int a[N<<2],n; int main() { scanf("%d",&n); int js=0; for(int i=1;i<=n;++i) { scanf("%1d",&a[i]); ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luogu 2742 二维凸包

链接 luogu 模板一 上下利用斜率求凸包然后合并。 #include <bits/stdc++.h> using namespace std; const int N=10005; const double eps=1e-10,inf=0x3f3f3f3f3f3f3f3f; int n,stak[N],top; struct point { double x,y; }a[N]; bool cmp(point a,point b) { return a.x==b.x?a.y<b.y:a.x<b.x; } double dis(point a,p...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

luoguP1742 最小圆覆盖

最小圆覆盖 首先 没错，我是个蒟蒻。luogu 流程 圆 C; for(i=1 to n) { if(P[i] 不在 C 内) { C = {P[i], 0}; for(j=1 to i-1) { if(P[j] 不在 C 内) { C = {0.5*(P[i]+P[j]), 0.5*dist(P[i], P[j])}; for(k=1 to j-1) { if(P[k] 不在 C 内) ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

bzoj4501 旅行

bzoj4501: 旅行 链接 bzoj 思路 我居然一上来就的去重边，***真可爱。 如果没有修改的话就是一个拓扑dp。 \(f[u]=\sum\frac{f[v]+1}{numson}\) 修改的话a[i]表示这个边要不要。 \(f[u]=\frac{\sum (f[v]+1)*a[i]}{\sum a[i]}\) 第x条边和第y条边的起点是相同的 所以我们拓扑是不会影响的。 所以只要拓扑考虑每个节点最大就好了。 \(f[u]=\frac{\sum (f[v]+1)*a[i]}{\sum a[i]}\) 分母很丑，换一下 \(\sum a[i]*f[u]=\sum (...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

东北大学计算机类

cf1173 D. Nauuo and Circle

链接 [cf]http://codeforces.com/contest/1175/problem/F) 思路 当1在1的位置做dp[i]为i的子树所有的方案。 一条性质是i的子树所占圆上的位置一定一段连续的。 那\(f[i]\)的方案就是$(son[i]+(i!=1))!\prod\limits_{x \in i }f[x] $ 其实就是$n*\prod\limits_{i=1}^{n}ru[i]! $ 代码 #include <bits/stdc++.h> using namespace std; const int N=2e5+7,mod=998244353; in...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务