jerome_wei-CSDN博客

原创口胡高考数学（？）

口胡高考数学（？）好吧其实是做不起题虽然现在还是做不起常系数线性齐次递推式的通项公式求法：首先我们把特征根求出来（这里要求都不一样）。然后通项公式第x项一定是特征根的x次方的一个式子。这个东西我们代入前几个数解方程即可。证明（可能不能叫证明)考虑常系数线性齐次递推求第A项是对于取特征多项式F的模。即最后的余数，其中tmp是一个多项式考虑每个特征根代入原式...

2019-04-25 21:30:11 426 1

原创 bzoj 4766 文艺计算姬【关于一个结论的证明】

bzoj 4766 文艺计算姬题意：给你n+m个带标号的点，要求左边前n个右边后m个点的二分图，是n+m个点的树的个数。考虑二分图的性质，因为左右的度数和相等，所以容易求出prufer序列中左边出现m-1次，右边n-1次。然后考虑左右的一个序列，左边的方案是n^(m-1) ，右边的方案是 m^(n-1)。于是我们考虑这个序列会生成什么样的树。如果确定了当前的状态（比如初...

2019-04-21 16:05:27 289 1

原创「雅礼集训 2017」【持续更新中】

目录DAY1T1 市场T2 矩阵T3 字符串DAY2T1 水箱T2 棋盘游戏T3 线段游戏DAY4T1 洗衣服T2 编码T3 猜数列DAY 5T1 远行T2 珠宝T3 矩阵DAY7T1 事情的相似度T2 跳蚤王国的宰相T3蛐蛐国的修墙方案DAY 8T1 共T2 价T3 爷DAY 10T1...

2019-04-19 21:29:45 647 2

原创 [bzoj1913]信号覆盖

[bzoj1913]信号覆盖考虑一个四边形，凸会多贡献2，凹会多贡献1.所以我们要求出凸/凹四边形的个数。考虑四边形任意选两个点，另外两个点在这两个点的连线两侧的情况。对于凸四边形我们可以找两个，凹四边形我们可以找三个。然后就可以极角排序扫一遍了。代码#include<bits/stdc++.h>using namespace std;typedef dou...

2019-04-10 20:18:40 253

原创 Codeforces Round #549 (Div. 1) C&D&E

Codeforces Round #549 (Div. 1) C&D&EC把x方减去，bx+c 就是个一次函数，然后发现上方没有点的限制相当于这个直线上方没有点，所以是个凸包#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6+5;st...

2019-04-01 15:02:06 1331

原创 AGC 032 F 简要题解

AGC 032 F 简要题解太神了这题。。。首先游戏可以直接等价成每次插入三类边（各120度），然后最后我们可以直接当成在第一个的一个1/3扇形里面找一段最小的段左右颜色不同。这里可以直接dp出有多少段颜色不同的方案，然后易得 i段的期望长度和是i/n（每段等价）。然后我们需要找k段分一个长度len最小长度的期望。这个期望是len/(k^2)。证明是(此处认为len=1...

2019-03-26 19:28:52 509

原创 codeforces 1137D & 1137E & 1137F

codeforces 1137D &1137E &1137FD分成三组(A,B,C)然后先{A,B} ， {A} k次直到A，B相遇发现k%c=0,且k<t+c（否则都可以减c）然后发现A，B到目标需要a*c+c+t-k 次，C需要t次，于是你直接走直到两个相遇就一定是目标点了。代码#include<bits/stdc++.h>using...

2019-03-11 18:41:54 425

原创 [第一类斯特林求行]

[第一类斯特林求行]如题，复杂度一个log代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=998244353,g=3;inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}inline in...

2019-03-01 18:38:07 225

原创 [Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1)]

[Codeforces Round #542 (Div. 1)] B,C,D,E链接B第一个是 -1 ，然后随便构造#include<bits/stdc++.h>using namespace std;const int N=2010;int sub,n;int a[N];int main(){ scanf("%d",&sub); a[1]=-1...

2019-02-26 17:14:37 256

原创 [bzoj4664] Count

[bzoj4664] Count好题。我们考虑从小到大插入。在中间插入的时候，新增加的贡献就是小的那个数与当前的数的差*2，旁边的话就是*1那么我们考虑把这个差分成多次计算可以这样来：每次操作时只要中间还有没有插入的位置，那么就可以把贡献加上上一次数的差。那我们就可以记有多少段然后记左右端点每次有没有被占领，然后就可以直接DP了。代码#include<bits...

2019-02-24 19:29:12 332

原创 Codeforces Round #540 (Div. 3)

Codeforces Round #540 F2 把每个连通块处理出来，然后直接从下往上dp就行了。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod = 998244353;int add(int a,int b){a+=b;return a>=mod?...

2019-02-21 15:20:12 106

原创 Codeforces 708D - Incorrect Flow

Codeforces 708D - Incorrect Flow链接题目大意：给一个不对的网络流，每次你可以增加/减少一条边的cap或者flow，要求最后网络流是一个可行流即：对于每个点进来的流量和出去的流量相同(S，T除外)对于每条边流量小于等于cap大于等于0求最少操作次数n,m 100参考志愿者招募，考虑原图相当于一堆等式（每个点一个），然后...

2019-02-17 19:31:48 192

原创 [bzoj5093]图的价值

[bzoj5093]图的价值每个点计算贡献，有n-1的点的图的总数，然后若干次方转成下降幂再斯特林数求行就能统计答案了。代码#include<bits/stdc++.h>using namespace std;const int N=1e6+5;typedef long long ll;const int mod=998244353;int add(int ...

2019-02-17 00:14:32 162

原创 UOJ #460 & # 461

UOJ #460 & # 461460 : 新年的拯救计划答案上限是n/2下取整。考虑如何构造既然是n/2那么只能两个节点加进去。考虑我们有2(i-1)的答案，需要构造2i的答案。首先之前的n-1个需要与新点相连。我们直接顺着分配一下就行。然后我们需要新增1条链。新的点A，B之间连一下。然后之前连A的都连B，连B的都连A就行了。代码#include...

2019-02-10 17:13:17 219

原创 CodeCraft-19 and Codeforces Round #537 (Div. 2) Editorial

CodeCraft-19 and Codeforces Round #537 (Div. 2) Editorial A不说了代码#include<bits/stdc++.h>using namespace std;const int N=1e6+5;char s1[N],s2[N];int main(){ scanf("%s",s1+1); s...

2019-02-10 16:49:04 212

原创 [bzoj4671]异或图

[bzoj4671]异或图斯特林反演+线性基首先容斥f(x)f(x)f(x)表示至少x个联通块的个数,g(x)g(x)g(x)表示恰好x个联通块的个数f[x]=∑i=xN\{ix\}g[i]f[x]=\sum_{i=x}^{N} { i \brace x }g[i] f[x]=i=x∑N{xi}g[i]斯特林反演g[x]=∑i=xN[xi]f(i)g[x]=\sum_{i...

2019-02-10 15:13:50 245

原创 codeforces 1107E&1107G&1107F

codeforces 1107E&1107G&1107F打铁回来刷水。链接：[1107E]Vasya and Binary String[1107G]Vasya and Maximum Profit[1107F]Vasya and Endless Credits[E]区间DP然后中间你发现要套一个背包。然后你发现你写成了n五方(？？)然后冷静分...

2019-02-02 15:27:58 436

原创 [bzoj3625] 小朋友和二叉树

[bzoj3625] 小朋友和二叉树生成函数不难推出，给定的A，然后求F=F*F*A+1然后要注意的是这里直接套公式然后求的话会在求逆的时候崩掉，然后具体处理方法就是把上面的除下来就行了。最后的式子是:代码#include<bits/stdc++.h>using namespace std;const int N=5e5+5;typedef long ...

2019-01-11 13:43:00 198

原创 [bzoj4836]二元运算

[bzoj4836]二元运算分治FFT这题卡常啊有毒。目前dark 3s bzoj T代码#include<bits/stdc++.h>using namespace std;typedef double db;typedef complex<db> cplx;const db PI=acos(-1.00);const int N=3e5+...

2019-01-08 23:04:18 165

原创 [bzoj1797]Mincut 最小割

[bzoj1797]Mincut 最小割是否是最小割的判断方法就是把残量网络跑一下tarjan(有流量的时候有边)可能出现：满流且co[u]!=co[v]一定出现co[u]==S&&co[v]==T代码#include<bits/stdc++.h>using namespace std;const int N=1e5+5,M=2e...

2019-01-06 20:59:26 164

原创 [bzoj1566]管道取珠

[bzoj1566]管道取珠貌似求 i 次方的问题都有一个套路就是将原操作序列复制一遍，然后i个操作中等价的数量就是原问题的答案了。然后这题就没了。代码#include<bits/stdc++.h>using namespace std;const int N=503;int f[2][N][N];char A[N],B[N];int n,m;const...

2019-01-04 20:43:59 289

原创 [bzoj2286]消耗战

[bzoj2286]消耗战建虚树dp代码#include<bits/stdc++.h>using namespace std;const int N=5e5+5;typedef long long ll;int anc[N][22];ll mn[N];const ll INF=1000000000000000000;int n,m;int num,dfn...

2019-01-04 17:17:21 169

原创 [bzoj3551] Peaks加强版

[bzoj3551] Peaks加强版Kruskal重构树。轻微卡常。代码#include<bits/stdc++.h>using namespace std;const int N=2e5+5;const int M=1e6+5;struct edge{ int u,v,val; bool operator<(const edge b)const{r...

2019-01-03 20:11:43 192

原创 [bzoj2959] 长跑

[bzoj2959] 长跑用LCT维护双联通分量。手贱把pushnow写rotate上，，，我还能说什么#include <bits/stdc++.h>using namespace std;const int N=2e5+5;int par[N];inline int find(int x){ return par[x]==x?par[x]:par[...

2019-01-01 22:48:32 162

原创 [bzoj 3672]购票

[bzoj 3672]购票如果是一条链的话是分治然后斜率优化，然后一颗树的情况就换成点分治就行了。#include<bits/stdc++.h>using namespace std;const int N=5e5+5;const int INF=0x3f3f3f3f;const long long INF_ll=1000000000000000000;type...

2018-12-30 17:29:42 166

原创 [bzoj3514]Codechef MARCH14 GERALD07加强版

[bzoj3514]Codechef MARCH14 GERALD07加强版LCT代码#include<bits/stdc++.h>using namespace std;const int N=5e5+5;const int INF=0x3f3f3f3f;namespace LinkCutTree{struct Splay{ int ch[2],fa...

2018-12-29 15:33:16 130

原创 [bzoj2120] 数颜色

[bzoj2120] 数颜色带修改莫队，块的大小是n^(2/3)，这样我们可以保证复杂度在n^(5/3)次方。代码#include<bits/stdc++.h>using namespace std;const int N=5e4+4;const int blksz=1357;inline int blk(int x) { return x/blksz;...

2018-12-29 15:22:01 114

原创 [bzoj1211] 树的计数 "prufer编码

[bzoj1211] 树的计数prufer编码大概就是将一颗无根树对应到一个序列里面，然后构造就是不断找最小的度数为1的点然后将他的father加进去。不难发现每个编号的出现次数就是deg+1代码（特判无解写的极水，可能有锅）#include<bits/stdc++.h>using namespace std;const int N=300;typedef l...

2018-12-20 20:58:14 176

原创 [loj2537] Minimax

[loj2537] Minimax用线段树合并优化dp做到nlogn代码#include<bits/stdc++.h>using namespace std;const int N=3e5+5;const int mod=998244353;typedef long long ll;inline int add(int a,int b){a+=b;return...

2018-12-12 21:29:47 207

原创 [bzoj5340]假面

[bzoj5340]假面全部存概率，第一问直接更新，第二问存 i 个人存活的概率，这个可以用多项式除二项式优化到 n^2然后复杂度就对了。代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=205;int m[N],n;const int mod=998...

2018-12-06 19:44:26 196

原创 SA板子

SA板子代码#include<bits/stdc++.h>using namespace std;const int maxn = 1000010;int n;char s[maxn];int sa[maxn],rank[maxn],height[maxn];int p[maxn],tmp[maxn],cnt[maxn];bool equal(int x,int...

2018-12-02 23:16:09 264

原创 [bzoj3680]吊打XXX

[bzoj3680]吊打XXX相当于是个广义费马点？？？模拟退火水过去的代码#include<bits/stdc++.h>using namespace std;typedef long double db;const int N=100004;int n;db x[N],y[N],z[N];db xx,yy;db dbrand(){ ret...

2018-12-01 22:07:40 163

原创 [bzoj2428]均分数据

[bzoj2428]均分数据模拟退火代码#include<bits/stdc++.h>using namespace std;typedef double db;db a[100],ave;int id[100];db sum[100];int n,m;inline db solve(){ db T=10000; db ans=0,pst=...

2018-12-01 21:10:11 122

原创 FFT板子

FFT板子代码#include<bits/stdc++.h>using namespace std;typedef double db;typedef complex<double> cplx;const int N=(1<<22)+5;const db PI=acos(-1.00);int rev[N];void dft(int n,...

2018-11-30 21:04:09 185

原创 [bzoj4657]tower

[bzoj4657]tower建图真的学不来。。首先我们考虑把题目转化成最小割。然后这个题有些性质就是每个点最多有两种被选中的方案，然后我们想最小割的话就应该设成负数的流量（我们在这里强制加一个INF什么的就行了）。然后关于只能选一个的限制我们参考切糕。然后就有了建图，行列分别连S，T然后中间连INF的限制就行了。详见代码代码#include<bits/std...

2018-11-24 20:21:20 176

原创 [bzoj4514]数字配对

[bzoj4514]数字配对不难证明这是个二分图，就是个费用流了。代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=410,M=500010;int a[N],b[N];ll c[N];int mp[N][N];int col[N];int n;i...

2018-11-23 20:37:12 246

原创 [NOIP2018]简要题解（部分）

[NOIP2018]简要题解（部分）目录[NOIP2018]简要题解（部分） PJ：T1 标题统计T2 龙虎斗T3 摆渡车T4 对称二叉树TGDAY1T1 铺设道路T2 货币系统T3 赛道修建DAY2T1 旅行T2 填数游戏T3 保卫王国 PJ：T1 标题统计入门难度代码#include<bits/s...

2018-11-17 00:07:19 774

原创 NOIP2018 (TG) 滚粗记

NOIP2018 (TG) 滚粗记by jerome_wei本文纯属口胡文章目录NOIP2018 (TG) 滚粗记DAY1T1 铺设道路T2 货币系统T3 赛道修建D1对拍DAY2T1 旅行T2 填数游戏T3保卫王国D2 对拍总结total关于调试关于心态还是先分析以下两天的解题情况DAY1T1 铺设道路看了一眼发现yk的讲义中我搞过这个东西，就直接写了。T2 货币系统...

2018-11-14 16:34:56 621

原创 [bzoj4753]最佳团体

[bzoj4753]最佳团体直接跑dp没法做，你就二分个答案然后dp来确认就行了代码#include<bits/stdc++.h>using namespace std;typedef double db;typedef long long ll;const int N=2550;int n,K;ll f[N][N];int fa[N];ll s[N],p...

2018-11-08 22:06:55 160

原创 [bzoj4985]评分

[bzoj4985]评分二分答案，然后发现这相当于是一棵树，dp check就行了代码#include<bits/stdc++.h>using namespace std;const int N=3e5+5;int hed[N],to[N],nxt[N],cnt;void adde(int u,int v) { ++cnt;to[cnt]=v,nxt[c...

2018-11-08 17:10:32 226

空空如也

空空如也