关键词：
考试的时候用哈希水过了第一题本来想用哈希只可以得20左右没想到由于数据过于水A了
然后雨天的尾巴骗了5分，总分105 我太菜了
首先时间分配的不合理：第一题大水题ac自动机打完了都不会，第二题略微想了想打了个高斯消元，然后样例没过......，最后输出了一个随机数，第三题（lca板子忘了，打错一个地方，没有调出来）最后骗了五分
考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天的尾(yi)巴（bzoj3307）
Censoring
FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过的字符串S。他有一个包含n个单词的列表，列表里的n个单词记t1 ....tn为他希望从S中删除这些单词。
FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词
FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的
请帮助FJ完成这些操作并输出最后的S串?1??...tNt_Nt?N??。他希望从S中删除这些单词。
FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词
FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的
请帮助FJ完成这些操作并输出最后的S
没什么好讲的，ac自动机然后开栈维护
记忆的轮廓
题目描述
输入格式
输出格式
样例
这个题还是挺有意思的
题目中提到这一句话
““我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。””
那么题目中就暗示了1--n的路径肯定是一条链
首先题目中说简单路径
其次具体可以反证出来
比如假设有三个点1-2 1-3 各有一条边那么1-3的简单路径就只有两个节点与n（n==3）个节点矛盾所以1-n的路径一定是一条链
这一个小点一定要读出来
设d[i]为i的出度，g[i]为错误儿子i返回存档期望步数,s[i]为当前点走到所有错误节点g之和
设a[i][j]表示以i为最新存档点走到j时期望步数，f[i][j]为以i为下一个存档点当前还剩余j个存档点
我们逆着转移f，f可以由任意一个在i之后的点并且剩余存档数量为j-1的f贡献
然后分析 这个dp实际上就是在1-n一条链上进行的, 那么我们其实就可以写出一个”类似“于线性dp的方程式
f[i][j]=min(f[i][j],f[k][j-1]+a[i][k])
这里a数组求法分析
设c是从j-1走到j的期望步数
a[i][j]=a[i][j-1]+c
分析
首先1/d[j-1]概率走到正确节点
其他可以由首先走到错误节点son
然后返回存档i，再继续走一个a[i][j-1]，然后再加上从j-1走到j的期望步数
这里有一个注意点 这里的c在Σ中要加一（走到错误节点要走一步）
于是
c=1/d[j-1]+Σ(g[son]+a[i][j-1]+c+1) ;// (son表示j-1的错误儿子)
分析我们将所有g相加就是s
c=(1/d[j-1])+(d[j-1]-1)/d[j-1]+(1/d[j-1])*s[j-1]+((d[j-1]-1)/d[j-1])*a[i][j-1]+((d[j-1]-1)/d[j-1])*c;
移项
1/d[j-1]*c=1+1/d[j-1]*s[j-1]+((d[j-1]-1)/d[j-1])*a[i][j-1];
首先要预处理出走到错误节点返回的期望，具体可以通过一个简单dfs处理
然后我们再次相乘得出
c=d[j-1]+s[j-1]+(d[j-1]-1)*a[i][j-1];
最后相加
得出
a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];
然后
f[i][j]=min(f[i][j],f[k][j-1]+a[i][k]);
那么我们推测对于a数组来说 它的快速增长肯定会爆
然后我们记录一个step，推测每次转移大致最大相差40步左右（但我觉得这么做是qj测试点）
然后就有了if(k-i>40) break;
经过实际测试（由于测试点过水） k-i 取到20左右就可以了
以下是本人丑陋的代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define db double 4 #define A 2500 5 using namespace std; 6 ll t,tot=0,n,m,p,head[A],nxt[A],ver[A]; 7 db g[A],a[A][A],cur,f[A][A],d[A],s[A]; 8 bool flag[A]; 9 inline void add(ll x,ll y) 10 nxt[++tot]=head[x];head[x]=tot;ver[tot]=y; 11 inline ll read() 12 13 ll x=0,f=1;char c=getchar(); 14 while(!isdigit(c)) 15 16 if(c==‘-‘) 17 f=-1; 18 c=getchar(); 19 20 while(isdigit(c)) 21 22 x=(x<<1)+(x<<3)+c-‘0‘; 23 c=getchar(); 24 25 return f*x; 26 27 void dfs(ll x) 28 29 flag[x]=1; 30 g[x]=1.0; 31 for(ll i=head[x];i;i=nxt[i]) 32 33 ll y=ver[i]; 34 if(!flag[y]) 35 dfs(y); 36 g[x]+=1.0/d[x]*g[y]; 37 38 39 int main() 40 41 t=read(); 42 while(t--) 43 44 tot=0; 45 memset(flag,0,sizeof(flag)); 46 memset(head,0,sizeof(head)); 47 memset(nxt,0,sizeof(nxt)); 48 memset(ver,0,sizeof(ver)); 49 memset(d,0,sizeof(d)); 50 memset(g,0,sizeof(g)); 51 memset(flag,0,sizeof(flag)); 52 memset(f,125,sizeof(f)); 53 n=read();m=read();p=read(); 54 for(ll i=1;i<=m-n;i++) 55 56 ll x,y; 57 x=read(),y=read(); 58 add(x,y);d[x]++; 59 60 for(ll i=1;i<n;i++) 61 d[i]++; 62 for(ll i=1;i<=n;i++) 63 if(!flag[i])dfs(i); 64 for(ll i=1;i<=n;i++) 65 66 s[i]=0; 67 for(ll j=head[i];j;j=nxt[j]) 68 69 ll y=ver[j]; 70 s[i]+=g[y]; 71 72 73 for(ll i=1;i<=n;i++) 74 75 a[i][i]=0; 76 for(ll j=i+1;j<=n;j++) 77 a[i][j]=a[i][j-1]*d[j-1]+s[j-1]+d[j-1]; 78 79 f[n][1]=0.0; 80 for(ll j=2;j<=p;j++) 81 for(ll i=1;i<=n;i++) 82 for(ll k=i+1;k<=n;k++) 83 84 if(k-i>40) break; 85 f[i][j]=min(f[i][j],f[k][j-1]+a[i][k]); 86 87 db ans=f[1][p]; 88 printf("%.4lf\n",ans); 89 90 return 0; 91
C. 雨天的尾巴
题目描述
输入格式
输出格式
样例
数据范围与提示
也是一道不错的题
思考我们如果按照既定套路，进行树上拆分的话
我们还需要维护每一个节点出现的值中最大的是什么
我们首先可以想到开一个v[n][max_size]数组
然后要i至j的z值+1就
v[i][z]++，v[j][z]++,v[lca][z]--,v[f[lca][0]][z]--;
如果只是简单开数组会MLE+TLE
为了省时间+省空间
我们可以建立n棵权值线段树
如果我们不举行别的措施仍然会MLE，故使用动态开点线段树
另外由于值特别大而我们开的是权值线段树，我们可以进行离散化也可以采取”别的操作“
别的操作：具体来说例如有m组询问，我们值域只需要开到m 其实还是和离散化差不多
最后统一进行线段树合并
完了（数据结构题真不知道要说些什么）
以下依然是本人丑陋的代码
1 #include<bits/stdc++.h> 2 #define A 100005 3 #define ll int 4 using namespace std; 5 bool flag[A*2]; 6 ll cnt=0,Ans[A*60],ans[A*60],deep[A*2],f[A][24],head[A*2],next[A*2],ver[A*2],lc[A*60],rc[A*60],tot=0,T[A*60]; 7 ll n,m,sum[A]; 8 inline ll read() 9 10 ll f=1,x=0;char c=getchar(); 11 while(!isdigit(c)) 12 13 if(c==‘-‘) f=-1; 14 c=getchar(); 15 16 while(isdigit(c)) 17 18 x=x*10+c-‘0‘; 19 c=getchar(); 20 21 return f*x; 22 23 void pushup(ll now) 24 25 if(ans[lc[now]]>=ans[rc[now]]) 26 ans[now]=ans[lc[now]],Ans[now]=Ans[lc[now]]; 27 else 28 ans[now]=ans[rc[now]],Ans[now]=Ans[rc[now]]; 29 30 void add(ll x,ll y) 31 32 next[++tot]=head[x]; 33 head[x]=tot; 34 ver[tot]=y; 35 36 ll merge(ll x,ll y,ll l,ll r) 37 38 if(l==r&&x&&y) ans[x]+=ans[y]; 39 if(!x||!y) return y+x; 40 ll mid=(l+r)>>1; 41 lc[x]=merge(lc[x],lc[y],l,mid); 42 rc[x]=merge(rc[x],rc[y],mid+1,r); 43 if(l!=r)pushup(x); 44 return x; 45 46 void change(ll &p,ll l,ll r,ll pos,ll v) 47 48 if(!p) p=++cnt; 49 if(l==r) 50 ans[p]+=v;Ans[p]=l;return ; 51 ll mid=(l+r)>>1; 52 if(pos<=mid) change(lc[p],l,mid,pos,v); 53 else change(rc[p],mid+1,r,pos,v); 54 if(l!=r) pushup(p); 55 56 void dfs(ll x,ll dep) 57 58 flag[x]=1,deep[x]=dep; 59 for(ll i=head[x];i;i=next[i]) 60 61 ll y=ver[i]; 62 if(flag[y]) continue; 63 f[y][0]=x; 64 deep[y]=dep; 65 dfs(y,dep+1); 66 67 68 ll lca(ll x,ll y) 69 70 if(deep[x]>deep[y]) 71 swap(x,y); 72 for(ll i=20;i>=0;i--) 73 74 if(deep[x]<=deep[f[y][i]]) 75 y=f[y][i]; 76 if(deep[x]==deep[y]) break; 77 78 if(x==y) return x; 79 for(ll i=20;i>=0;i--) 80 81 if(f[x][i]!=f[y][i]) 82 x=f[x][i],y=f[y][i]; 83 84 return f[x][0]; 85 86 void dfs_(ll x) 87 88 flag[x]=1; 89 for(ll i=head[x];i;i=next[i]) 90 91 ll y=ver[i]; 92 if(flag[y]) continue; 93 dfs_(y); 94 T[x]=merge(T[x],T[y],1,A); 95 96 if(ans[T[x]]>0) 97 sum[x]=Ans[T[x]]; 98 99 int main() 100 101 n=read(),m=read(); 102 for(ll i=1;i<n;i++) 103 104 ll xx=read(),yy=read(); 105 add(xx,yy); 106 add(yy,xx); 107 108 dfs(1,1); 109 f[1][0]=0; 110 for(ll i=1;i<=20;i++) 111 for(ll j=1;j<=n;j++) 112 f[j][i]=f[f[j][i-1]][i-1]; 113 ll LCA; 114 for(ll i=1;i<=m;i++) 115 116 ll x=read(),y=read(),z=read(); 117 LCA=lca(x,y); 118 change(T[x],1,A,z,1); 119 change(T[y],1,A,z,1); 120 change(T[LCA],1,A,z,-1); 121 change(T[f[LCA][0]],1,A,z,-1); 122 123 memset(flag,0,sizeof(flag)); 124 dfs_(1); 125 for(ll i=1;i<=n;i++) 126 printf("%d\n",sum[i]); 127
bzoj3940&&bzoj3942
方法就是维护一个动态栈记录栈的每一位匹配到串的哪一位的编号第一道kmp第二道ac自动机自己理会#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=1000055;charstack[M],s[M],t[M],f[M],next[M];intlen,top; 查看详情
bzoj3940[usaco2015feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
bzoj3940censoring
把上题的KMP改成AC自动机。注意root必须是0。因为root其实是NULL的意思。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definemaxn500050usingnamespacestd;chart[m 查看详情
bzoj3940[usaco2015feb]censoring*
bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情
bzoj3940
AC自动机复习一下。。。可惜又写错了我们发现就是把单词建成ac自动机，然后把串在ac自动机上跑一遍，每到一个单词结束点就删除，删除是利用栈，每次弹出单词长度个字符就可以了发现两个小问题，strlen很慢，不能写在循环... 查看详情
bzoj3940censoring题解（ac自动机）(代码片段)
题目描述FarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest issueco 查看详情
bzoj3940:[usaco2015feb]censoring--ac自动机
3940:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBDescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterial 查看详情
bzoj4899--记忆的轮廓
Description通往贤者之塔的路上，有许多的危机。我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]... 查看详情
[bzoj3940][usaco2015feb]censoring
最近做题成双成对？不是双倍经验就是两题同解。3940 3942给定字典，给定字符串，删去字符串中所有字典内单词。保证不会出现二者包含状况。$nleq1e5,sumlenleq1e5$AC自动机裸题。build出AC自动机后从左到右插入文本串，同时... 查看详情
bzoj3940:[usaco2015feb]censoring
给个长度<=1e5的串s，再给n个模板串总长不超1e5，每次把s中起始位置最早的一个模板串删掉，求最后剩的串。AC自动机，开个栈记一下每次走到哪里，匹配成功后直接在栈里找到这一串的初始位置对应自动机上的节点，从而回... 查看详情
bzoj3940[usaco2015feb]censoring
【题目描述】FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词记为t_1...t_N。他希望从S中删除这些单词。 FJ每次在S中找到最早出现的列表中的单词(... 查看详情
loj6171/bzoj4899记忆的轮廊（期望dp+优化）
题目：https://loj.ac/problem/6171分析：设dp[i][j]表示从第i个点出发（正确节点），还可以有j个存档点（在i点使用一个存档机会），走到终点n的期望步数那么a[i][k]表示i点为存档点，从i点走到k点（正确节点）的期望步数（中间没有... 查看详情
bzoj4899记忆的轮廓题解（概率dp+决策单调性优化）(代码片段)
题目背景四次死亡轮回后，昴终于到达了贤者之塔，当代贤者夏乌拉一见到昴就上前抱住了昴“师傅！你终于回来了！你有着和师傅一样的魔女的余香，肯定是师傅”。众所周知，大贤者是嫉妒魔女沙提拉的老公，400年前... 查看详情
bzoj1088:[scoi2005]扫雷mine
1088:[SCOI2005]扫雷MineTimeLimit:10Sec MemoryLimit:162MBSubmit:3940 Solved:2324[Submit][Status][Discuss]Description 相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余&... 查看详情
bzoj1096[zjoi2007]仓库建设（斜率优化）
1096:[ZJOI2007]仓库建设TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 3940 Solved: 1736Description L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（... 查看详情
bzoj5017[snoi2017]炸弹
...区间，所以记录每个节点的左端点和右端点合并时取最值反思：思维定式，以为求解可达点个数不能合并/**************************************************************Problem:5017User:ws_zzyer 查看详情
hzwer的bzoj题单
counter:664BZOJ1601BZOJ1003BZOJ1002BZOJ1192BZOJ1303BZOJ1270BZOJ3039BZOJ1191BZOJ1059BZOJ1202BZOJ1051BZOJ1001BZOJ1588BZOJ1208BZOJ1491BZOJ1084BZOJ1295BZOJ3109BZOJ1085BZOJ1041BZOJ1087BZOJ3038BZOJ1821BZOJ1 查看详情
bzoj1143:[ctsc2008]祭祀river
...的边那么其他的点选的话就没有矛盾的了。符合题意、//反思：有向图根本没有联想到二分图，想的一直是暴力暴力暴力。。。以为数据那么小。。。应该联想有可能用上的算法。#include<cstdio>#include<cstring>#include<cctype&... 查看详情