2 Backseat-stargazer

尚未进行身份认证

有りふれた幸せでいいの

等级
TA的排名 9k+

【LOJ #6075】「2017 山东一轮集训 Day6」重建(DP)

传送门处理出f[i],g[i]f[i],g[i]f[i],g[i]表示走任意iii条边和沿着关键点走iii条边的最短路然后枚举关键点边数求出可行的CCC的l,rl,rl,r对所有可行的rrr取maxmaxmax即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register...

2020-02-18 21:03:46

【2020省选模拟】题解

T1:神题显然先容斥l或r+1l或r+1l或r+1作为下界设下界和为sss假设最后总和为xxx就相当于a1+a2+a3....+an=xa_1+a_2+a_3....+a_n=xa1​+a2​+a3​....+an​=x解一个方程组解都为正整数的方案为(x−s−1n−1){x-s-1\choose n-1}(n−1x−s−1​)要求正整数把l,rl,rl,r都减一即可答案即为∑x&...

2020-02-18 20:54:09

【LOJ #6074】「2017 山东一轮集训 Day6」子序列(矩阵乘法)

传送门透好像pkuwc2020Day1T1pkuwc2020Day1T1pkuwc2020Day1T1处理方法就是这个可惜当时劳资没做过这题。。。显然有一个dpdpdp是设f[i][j]f[i][j]f[i][j]表示前iii个最后一个字符是j(j∈[0,8])j(j\in[0,8])j(j∈[0,8])的方案f[i][9]f[i][9]f[i][9]则表示之前一个都没选的方案初始f...

2020-02-18 20:25:59

【LOJ #6073】「2017 山东一轮集训 Day5」距离(主席树 / 树链剖分)

传送门首先若p[i]=ip[i]=ip[i]=i时且离线时可以直接用LNOI2014]Lca的做法在线的话可以用主席树对每个点维护到根上的所有ppp到根的路径+1+1+1修改后的dfsdfsdfs序然后差分一下答案即可如果标记永久化时空常数都会小很多#include<bits/stdc++.h>using namespace std;#define cs const#d...

2020-02-18 19:59:07

【LOJ #6072】 「2017 山东一轮集训 Day5」苹果树(容斥 / 搜索 / 矩阵树定理)

传送门考虑求出kkk个好苹果时权值和≤lim\le lim≤lim的方案数这个可以用折半搜索+双指针求出来设权值不为−1-1−1的苹果有mmm个然后考虑把苹果分成三部分:1−k:最后是有用的苹果1-k:最后是有用的苹果1−k:最后是有用的苹果k+1−m:好的但无用的苹果k+1-m:好的但无用的苹果k+1−m:好的但无用的苹果m+1−n:坏苹果m+1-n:坏苹果m+1−n:坏苹果那么...

2020-02-17 15:12:24

【LOJ #6071】「2017 山东一轮集训 Day5」字符串(Sam)

传送门总感觉好像之前考试做过??反正考虑从后往前填如果每个点某个值没有出边往后面第一个根出去存在这个值的连向的那个点连边跑拓扑排序即可不用实在连,记一下即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define...

2020-02-17 14:58:23

【LOJ #6069】「2017 山东一轮集训 Day4」塔(DP)

传送门好像和魔法的碰撞那道题差不多最后空的位置插入所有人之间的方案数就是一个组合数#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define pii pair<int,int>#define ll long...

2020-02-17 14:51:51

【LOJ #6067】「2017 山东一轮集训 Day3」第三题(MTT / 多项式多点求值)

传送门我管你什么推式子莽一个mttmttmtt就完了在InvInvInv那里实现的好就可以跑到1s1s1s一个点#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define pii pair<int,int&gt...

2020-02-14 22:02:15

【LOJ #6066】「2017 山东一轮集训 Day3」第二题(二分答案 / 树哈希 / 括号序列)

传送门首先显然二分答案其实我第一眼想得长链剖分维护树哈希实际上由于这个子树有先后顺序于是可以看做括号序列每个点的kkk子树就是若干区间哈希判一下即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define pi...

2020-02-14 19:46:51

【2020省选模拟】题解

T1:考虑设f1[i]f_1[i]f1​[i]表示前iii个走到第二个位置的步数,f2[i]f_2[i]f2​[i]表示走到第三个位置的步数然后可以发现f1[i]=2∗f2[i−1]+1,f2[i]=f1[i−1]+2∗f2[i−1]+2f_1[i]=2*f_2[i-1]+1,f_2[i]=f_1[i-1]+2*f_2[i-1]+2f1​[i]=2∗f2​[i−1]+1,f2​[i]=f1​...

2020-02-14 13:17:19

【洛谷 P3643】【APIO2016】 划艇(DP)

传送门看到满脑子都想的赛艇Excited!Excited!Excited!考虑离散化成一堆区间设f[i][j][k]f[i][j][k]f[i][j][k]表示前iii个,当前在第jjj个区间,在第jjj个区间的有kkk个的方案数然后在跳到下一个区间的时候再算kkk个份分配在第jjj个区间的方案由于是递增的,所以系数为(len[j]k){len[j]\choose k}(klen[j]...

2020-02-13 22:54:07

【洛谷 P4384】 [八省联考2018]制胡窜(SAM / 线段树合并)

传送门首先建出SamSamSam,线段树合并维护endposendposendpos显然考虑endposendposendpos问题可以变成给定xxx条线段[li,ri][l_i,r_i][li​,ri​]选择两个点切下去,存在某条线段未被切开的方案首先转化成求所有线段都被切开的方案用C(n−1)2C^2_{(n-1)}C(n−1)2​减去即可设L=r1,R=lxL=r_1,R=l_...

2020-02-13 22:52:41

【BZOJ #2034】 [2009国家集训队]最大收益(贪心 / 匈牙利算法)

传送门显然贪心把权值最大的先要了一定最优考虑把需要的时间离散化出来就相当于做一个最大匹配每个点连向的时间是一个区间如果有冲突把rrr更大拿去匹配显然更可行具体实现可以看代码#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_bac...

2020-02-13 22:45:52

【BZOJ #4977】【[Lydsy1708月赛】 跳伞求生(模拟费用流)

传送门把a,ba,ba,b排序后从小到大处理即可维护一下退流即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define pii pair<int,int>#define ll long long#de...

2020-02-12 19:27:26

【洛谷 P5825】 排列计数(二项式反演 / 多项式 / 生成函数)

传送门题解区的Eulerian numberEulerian\ numberEulerian number什么的完全看不懂啊显然能得到一个n2,dpn^2,dpn2,dpf[i][j]f[i][j]f[i][j]表示前iii个有jjj个的方案有f[i][j]=f[i−1][j]∗(j+1)+f[i−1][j−1](i−j)f[i][j]=f[i-1][j]*(j+1)+...

2020-02-12 19:19:42

【2020省选模拟】题解

T1:傻逼般的把暴力写挂了考虑最左右的两个对称点一定在k+1k+1k+1以内暴力枚举后即可确定对称中心双指针判断有多少对对称点满足即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register#define pb push_back#define pii pair&lt...

2020-02-11 19:01:33

【LOJ #6068】「2017 山东一轮集训 Day4」棋盘(费用流)

传送门将行列分别看做点如果被障碍分成几段的话就再建几个点行列向每段的点连(cap=1,cost=0),(1,1),(1,2)....(cap=1,cost=0),(1,1),(1,2)....(cap=1,cost=0),(1,1),(1,2)....的边答案即最小费用每次都跑一边过不去按询问的流量排序后增量做#include<bits/stdc++.h>using n...

2020-02-10 19:48:23

【洛谷 P4564】 【CTSC2018】假面(概率DP)

传送门简单概率dpdpdp第二问对每个人维护每个血量的概率即可第一个问题考虑dpdpdp出g[j]g[j]g[j]表示剩下jjj个人活着的概率这个可以很简单的dpdpdp出来然后每个人xxx被困住的概率就是P(x活着)∗∑ig′[i]i+1P(x活着)*\sum_{i}\frac {g'[i]}{i+1}P(x活着)∗∑i​i+1g′[i]​这里g′g'g′是对除xxx其他人dpdp...

2020-02-10 19:44:22

【洛谷 P5850】 calc加强版(生成函数+NTT)

传送门先看做无序的最后乘上n!n!n!显然可以构造生成函数∏(1+ix)\prod(1+ix)∏(1+ix)分治nttnttntt好像也可以过?不过不知道为啥RERERE了应该是炸空间了先取对在expexpexp=exp(∫(∑i1+ix)dx)=exp(\int(\sum{\frac i{1+ix}})\mathrm{dx})=exp(∫(∑1+ixi​)dx)expexpexp内...

2020-02-09 22:36:43

【洛谷 P5162】 WD与积木(生成函数+NTT)

传送门设非空集合的EGFEGFEGF即f(x)=ex−1f(x)=e^x-1f(x)=ex−1那么分子的EGF=∑i=0∞ifi=f(f−1)2EGF=\sum_{i=0}^{\infty}if^i=\frac{f}{(f-1)^2}EGF=∑i=0∞​ifi=(f−1)2f​分母的为∑i=0∞fi=11−f\sum_{i=0}^{\infty}f^i=\frac{1}{1-f}∑i=0∞​...

2020-02-09 22:35:53

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。