关键词：
T1：Censoring
和以前kmp一样的一道题，只是改成了多个串需要AC自动机
用一个栈维护当前字符串，匹配上了就暴力弹栈，并将指针回溯，复杂度O（n+m）
这题考试的时候不知道怎么把栈给否掉了，用了个玄学方法记录，只干出来13分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define null NULL
using namespace std;
struct node
node *fi,*ch[26];
int c;
node ()
fi=null;c=0;
memset(ch,null,sizeof(ch));
*root=new node();
char a[2002][100002];int le[2002];
short s[200];
void insert(int x)
node *now=root;int len=le[x];
for(int i=1;i<=len;i++)
int in=s[a[x][i]];
if(now->ch[in]==null) now->ch[in]=new node();
now=now->ch[in];
now->c=x;
void getfail()
queue<node*>q;
for(int i=0;i<26;i++)
if(root->ch[i]!=null)
root->ch[i]->fi=root;
q.push(root->ch[i]);
else root->ch[i]=root;
while(!q.empty())
node *now=q.front();q.pop();
for(int i=0;i<26;i++)
if(now->ch[i]!=null)
now->ch[i]->fi=now->fi->ch[i];
q.push(now->ch[i]);
else now->ch[i]=now->fi->ch[i];
node *last[100002];
int top,sol[100002];char sta[100002];
void query()
node *now=root;int len=le[0],del=0;
for(int i=1;i<=len;i++)
if(now==null) now=root;
sta[++top]=a[0][i];last[top]=now;
int out=s[a[0][i]];
now=now->ch[out];
if(now->c)
top-=le[now->c];
now=last[top+1];
int main()
for(int i=‘a‘;i<=‘z‘;i++) s[i]=i-‘a‘;
for(int i=‘A‘;i<=‘Z‘;i++) s[i]=i-‘A‘;
scanf("%s",a[0]+1);le[0]=strlen(a[0]+1);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
le[i]=strlen(a[i]+1);
insert(i);
getfail();
query();
for(int i=1;i<=top;i++)
putchar(sta[i]);
return 0;
T2：记忆的轮廓
概率期望，考试时候直接弃了（主要是无良老师数据范围没给）
50%:数据n==p，则不需要考虑存档，首先设d[i]表示i的儿子数。设g[i]表示对于一个错误节点i，期望走多少步会读档。那么
g[i]=1+1/d[i]*∑g[j]其中j是i的儿子。
接下来我们倒着递推：f[i]=1+1/d[i]*f[i+1]+1/d[i]*∑g[j]+f[i][j是i的错误儿子]
移项得：f[i]=d[i]+f[i+1]+Σg[j][j是i的错误儿子] 复杂度O(m)
70%:我们设dp，f[i,j]表示当前存档点为i，还剩j次存档机会。
首先我们需要预处理一个a[i,j]，表示存档点为i，从i开始走到正确节点j的期望步数（中间不能存档）。
显然有边界条件a[i,i]=0。对于i<j，可以列出递推式：
a[i,j]=a[i,j-1]+1+1/d[j-1]*∑g[k]+a[i,j][k是j-1的错误儿子]
移项得a[i,j]=a[i,j-1]*d[j-1]+d[j-1]+Σg[k][k是j-1的错误儿子]
则f[i][k]=min(f[j][k-1]+a[i][j]),答案f[1][p-1]
复杂度O(pn^2)
100%:优化方向1：我们观察a数组，发现有a[i,j]<a[i,j+1],a[i-1][j]>a[i][j]
那么我们可以用单调队列优化，用两维的单调队列（当前和上一次）每次把所有f[i][k]插入
每次查询的时候若队头que[st].dp+a[i][que[st].at]>=que[st+1].dp+a[i][que[st+1].at]||que[st].at<=i就出队
然后理论上我们还需要二分来找到两个函数交点
但是我没找它就过了......
复杂度O（pn）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define re register
using namespace std;
struct node
int at;
double dp;
que[2000][2];
double g[2005],f[2005][705],d[2005],a[2005][2005];
int to[2000][5],st[2],ed[2],now;
void dfs(int u)
int d=to[u][0];
g[u]=1;
for(int i=1;i<=d;i++)
dfs(to[u][i]);
g[u]+=g[to[u][i]]/d;
int main()
int T,n,m,p,x,y;
scanf("%d",&T);
while(T--)
memset(f,127,sizeof(f));memset(a,0,sizeof(a));memset(to,0,sizeof(to));
scanf("%d%d%d",&n,&m,&p);p--;
for(int i=1;i<=m-n;i++)
scanf("%d%d",&x,&y);
to[x][++to[x][0]]=y;
for(int i=1;i<=n-1;i++)
d[i]=to[i][0];g[i]=0;
for(int j=1;j<=d[i];j++)
dfs(to[i][j]);
g[i]+=g[to[i][j]];
d[i]+=1;
for(int i=1;i<=n-1;i++)
for(int j=i+1;j<=n;j++)
a[i][j]=a[i][j-1]*d[j-1]+g[j-1]+d[j-1];
st[now]=1;ed[now]=0;
que[++ed[now]][now].dp=0;
que[ed[now]][now].at=n;
for(int k=1;k<=p;k++)
now^=1;
st[now]=1;ed[now]=0;
for(int i=1;i<=n-1;i++)
while(st[now^1]<ed[now^1]&&(que[st[now^1]][now^1].at<=i||que[st[now^1]][now^1].dp+a[i][que[st[now^1]][now^1].at]>=que[st[now^1]+1][now^1].dp+a[i][que[st[now^1]+1][now^1].at])) st[now^1]++;
f[i][k]=que[st[now^1]][now^1].dp+a[i][que[st[now^1]][now^1].at];
for(int i=1;i<=n-1;i++) que[++ed[now]][now].dp=f[i][k],que[ed[now]][now].at=i;
que[++ed[now]][now].dp=0;que[ed[now]][now].at=n;
printf("%.4lf\n",f[1][p]);
return 0;
优化方向2：观察a数组，可以看到它是恐怖的增长的
我们来估计答案的上界，考虑一种可行方案，每n/p个正确节点就设立一次存档位置，那么答案最大是多少呢？考虑最坏情况，观
察a的转移，应该每变换一次存档点，
设s[i]=Σg[j]大约需要3^(n/p)s[i]+3(n/p-1)*s[i+1]+3^(n/p-2)*s[i+2]+……因为最多m个节点，s的上限是1500（实际上也远远达不
到）
那么其实，针对答案不会特别大，a的增长又很恐怖，我们还可以思考对70%的算法优化。那就是设定一个常数step，每次转移最
多从距当前step步远的位置转移过来。step取40多基本不会有问题了，因为a的下界已经是2^40了，而答案的上界远远没有
达到，经过精确计算还可以再把step调小一点。
复杂度O(np log ans)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define re register
using namespace std;
struct node
int at;
double dp;
;
deque<node>q;
double g[2005],f[2005][705],d[2005],a[2005][2005];
int to[2000][5];
void dfs(int u)
int d=to[u][0];
g[u]=1;
for(int i=1;i<=d;i++)
dfs(to[u][i]);
g[u]+=g[to[u][i]]/d;
int main()
int T,n,m,p,x,y;
scanf("%d",&T);
while(T--)
memset(f,127,sizeof(f));memset(a,0,sizeof(a));memset(to,0,sizeof(to));
scanf("%d%d%d",&n,&m,&p);p--;
for(int i=1;i<=m-n;i++)
scanf("%d%d",&x,&y);
to[x][++to[x][0]]=y;
for(int i=1;i<=n-1;i++)
d[i]=to[i][0];g[i]=0;
for(int j=1;j<=d[i];j++)
dfs(to[i][j]);
g[i]+=g[to[i][j]];
d[i]+=1;
for(int i=1;i<=n-1;i++)
for(int j=i+1;j<=n;j++)
a[i][j]=a[i][j-1]*d[j-1]+g[j-1]+d[j-1];
f[n][0]=0;
for(int k=1;k<=p;k++)
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n&&j-i<=40;j++)
f[i][k]=min(f[i][k],f[j][k-1]+a[i][j]);
if(f[j+1][k-1]>f[j][k-1]) break;
printf("%.4lf\n",f[1][p]);
return 0;
T3：动态开点+权值线段树合并+树上差分
考试时候想到了没敢打，主要没分析好空间复杂度
对每个点开权值线段树，离不离散都行
复杂度时间，空间都是O(nlogn)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define re register
#define L ls[k]
#define R rs[k]
#define lc ls[k],l,mid
#define rc rs[k],mid+1,r
using namespace std;
inline int read()
re int a=0;re char ch=getchar();
while(ch<‘0‘||ch>‘9‘) ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) a=(a<<3)+(a<<1)+ch-‘0‘,ch=getchar();
return a;
int rt[100005],ans[100005],ls[5000000],rs[5000000],da[5000000],d[100005],f[100005][20],fr[100005],to[200005],la[200005],cnt,num,is[100005],tot;
inline void add(int x,int y)
to[++num]=y;
la[num]=fr[x];
fr[x]=num;
void dfs(int u,int fa)
for(int i=1;(1<<i)<=d[u];i++) f[u][i]=f[f[u][i-1]][i-1];
for(int i=fr[u];i;i=la[i])
if(to[i]!=fa)
d[to[i]]=d[u]+1;f[to[i]][0]=u;
dfs(to[i],u);
int getlca(int a,int b)
if(d[a]<d[b]) swap(a,b);
for(int i=18;i>=0;i--)
if(d[a]-(1<<i)>=d[b]) a=f[a][i];
if(a==b) return a;
for(int i=18;i>=0;i--)
if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
return f[a][0];
void insert(int &k,int l,int r,int x,int y)
if(!k) k=++cnt;
if(l==r)
da[k]+=y;
return;
re int mid=(l+r)>>1;
if(x<=mid) insert(lc,x,y);
else insert(rc,x,y);
da[k]=max(da[L],da[R]);
int merge(int x,int y,int l,int r)
if(!x||!y) return x+y;
if(l==r)
da[x]+=da[y];
return x;
re int mid=(l+r)>>1;
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+1,r);
da[x]=max(da[ls[x]],da[rs[x]]);
return x;
int query(int k,int l,int r)
if(!da[k]||!k) return 0;
if(l==r) return l;
re int mid=(l+r)>>1;
if(da[L]>=da[R]) return query(lc);
else return query(rc);
void dfss(int u,int fa)
for(int i=fr[u];i;i=la[i])
if(to[i]!=fa)
dfss(to[i],u);
rt[u]=merge(rt[u],rt[to[i]],1,tot);
ans[u]=is[query(rt[u],1,tot)];
struct node
int x,y,z;
Q[100005];
inline int as(node x,node y)
return x.z<y.z;
int main()
int x,y,z,n=read(),m=read();
for(int i=1;i<n;i++)
x=read();y=read();
add(x,y);add(y,x);
d[1]=1;
dfs(1,0);
for(int i=1;i<=m;i++)
Q[i].x=read(),Q[i].y=read(),Q[i].z=read();
sort(Q+1,Q+m+1,as);
for(int i=1;i<=m;i++)
if(Q[i].z!=Q[i+1].z) is[++tot]=Q[i].z,Q[i].z=tot;
else Q[i].z=tot+1;
for(int i=1;i<=m;i++)
int lca=getlca(Q[i].x,Q[i].y);
insert(rt[Q[i].x],1,tot,Q[i].z,1);
insert(rt[Q[i].y],1,tot,Q[i].z,1);
insert(rt[lca],1,tot,Q[i].z,-1);
insert(rt[f[lca][0]],1,tot,Q[i].z,-1);
dfss(1,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
这次考试总体状态还可以，就是对于一些东西想的不深入，没有透彻理解
主要就是第一题没有拿到应该的分，当时感觉是一道水题没有当回事，码的时候没有注意细节，自己编了几个样例过了就以为稳了
以后对于水题一定得仔细，否则别的题得分再高也没用
以上。
高二数学微课堂教学视频(代码片段)
...你快速带到那里，试试看。[box[10px,yellow,border:2pxdashedred]高二数学高清教学视频^colorredfbox同步教学]1、逻辑关系---同步教学?1-1.第一讲命题?1-2.第二讲四种 查看详情
css初探学习总结提高二(代码片段)
一.CSS背景及应用<styletype="text/css"> div width:400px; height:400px; /*background-color:pink;*//*背景颜色*/ /*background-image:url(image/wo.jpg);*//*背景图片*/ /*background-repeat:no-r 查看详情
20190614抱0记
今天上午，教练员说：下午测试我看着我的运势：凶忌模拟赛，爆0 我果断对自己说：仅供参考，没事的下午，天色热，我坐在冰冷的机房，骂了自己一下午。出分后，T1:0T2:0T3:……0我一头撞在键盘上（我蒟... 查看详情
20190614考试心态爆炸记
昨天波波说今天有可能考ac自动机（被奶死），我就莫名慌得一批（好吧其实他说考什么我都会慌得一批），当时我看ac自动机还懵逼呢，然后预示今天考试凉凉？上午淼哥又说下午以来就考试，于是更加慌得一批。今天早上开... 查看详情
这次应该叫高二上一调
T1匹配分析据说是个$kmp$的板子，但是我把$kmp$基本忘光了，所以打的哈希，然后赛后去复习了$kmp$。。。。AC代码#include<iostream>usingnamespacestd;#definelllonglonginlineintin()int 查看详情
c#.net腾讯云一句话识别实例(代码片段)
腾讯云一句话识别实例usingSystem;usingSystem.Threading.Tasks;usingTencentCloud.Common;usingTencentCloud.Common.Profile;usingTencentCloud.Asr.V20190614;usingTencentCloud.Asr.V20190614.Models;usingSystem.IO;namesp 查看详情
题解寿司(代码片段)
传送门论我调n方暴力一调一下午为了写个n方对拍调试信息写了一大串细节题本来就毒瘤序列上子序列还卡细节真的很让人崩溃啊还有，为什么输入文件是「速食.cpp」刚开始以为是逆序对，后来拿线段树分治水了十分线段树分治... 查看详情
高二上学期作息时间10.14-1.30
由于高二下学期备考物理竞赛，需要停课。保证高二下学期的期中期末要抢排位，即要抢高二暑假清华北大的暑期课堂名额，所以需要自己在高二上学期完成高考的一轮复习，高二寒假考高考和考竞赛频率相当。但又由于高二上... 查看详情
php数组根据某键值，把相同键值的合并最终生成一个新的二维数组(代码片段)
$infos=array(array(‘gid‘=>36,‘name‘=>‘高二佳木斯‘,‘start_time‘=>‘2015-08-2800:00:00‘,‘pic‘=>‘2015/08/438488a00b3219929282e3652061c2e3.png‘),array(‘gid‘=>36,‘name‘=>‘高二佳木斯‘,‘start_time‘=&g 查看详情
vsftpd简介安装配置验证(代码片段)
...务器软件,小巧易用,支持虚拟用户,支持带宽限制,安全性高二 Vsftpd安装配置 1.yum install vsftpd 2.创建虚拟用户目录mkdir/home/ftpfile 3.添加匿名用户adduser ftpuser -d /home/ftpfile 4.设置selinux vi/et 查看详情
统计百分比的一个sql脚本(代码片段)
统计一个表中一个百分比的SQL脚本，不过这个是个万分比，这个数据类型要调一调1declare@num1nvarchar(10),@num2nvarchar(10)2declare@num3decimal,@num4decimal3declare@percentdecimal45select@num1=COUNT(*)from[Test]whereStatus=0;6select@num2=COUN 查看详情
高二st
高二了开学一周，每天被文化课作业碾压。。。但是仍然阻挡不了想刷题的心情。。。对付noip2016的几块：（有点少，以后补）高精度（c++模板仍未生成）图论相关：欧拉路双联通分量（以及构造）...点分治？可行遍性问题：hami... 查看详情
c#.net腾讯云一句话识别实例(代码片段)
...encentCloud.Common;usingTencentCloud.Common.Profile;usingTencentCloud.Asr.V20190614;usingTencentCloud.Asr.V20190614.Models;usingSystem.IO;namespaceAudioToSRTclassSentenceRecognitionpublicstaticbyte[]FileToByte(stringfileUrl)tryusing(FileStreamfs=newFileStream(fileUrl,FileMode.Open,FileAccess.Rea... 查看详情
c#.net腾讯云一句话识别实例(代码片段)
...encentCloud.Common;usingTencentCloud.Common.Profile;usingTencentCloud.Asr.V20190614;usingTencentCloud.Asr.V20190614.Models;usingSystem.IO;namespaceAudioToSRTclassSentenceRecognitionpublicstaticbyte[]FileToByte(stringfileUrl)tryusing(FileStreamfs=newFileStream(fileUrl,FileMode.Open,FileAccess.Rea... 查看详情
2023省熟中高二（15）班期中数学试题及解析
2023省熟中高二（15）班期中数学试题及解析试题解析 查看详情
tw实习日记：第22天(代码片段)
...，没什么难的，样式复制粘贴，JSON表单配一配，接口调一调，基本就完成了。不过中间在写后台的一些接口时，发现被自己之前写的一些方法给坑了。为什么这样说呢，因为在之前的几个工具方法里，都把一些本该是变量的值... 查看详情
2022-2023学年英语周报高二课标外研第57期答案汇总
进入查看：2022-2023学年英语周报高二课标外研第57期答案汇总Thereareadvantagesanddisadvantageswithemails.Ifyousendsomeoneanemail,thenhewillreceiveitextremel 查看详情
高二英语阅读急求翻译！！！！！！！！！！！
Doesabeeknowwhatisgoingoninitsmindwhenitnavigates(给......向导）itswaytodistantfoodsourcesandbacktohive(蜂房）,usingpolarizedsunlightandthetinymagnetitcarriesasanavigationalaid?Oristhebeejustamachine,unabletodoitsmathematicsanddanceitslanguageinanyotherway?TouseDonaldGriffin'sterm,doesabe... 查看详情