NOIP模拟测试1「co……·记忆的轮廓·雨天的尾巴」
归档于 2019-06-23 14:28
考试的时候用哈希水过了第一题本来想用哈希只可以得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_NtN。他希望从S中删除这些单词。
FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词
FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的
请帮助FJ完成这些操作并输出最后的S
没什么好讲的，ac自动机然后开栈维护
记忆的轮廓
内存限制：512 MiB 时间限制：1000 ms 标准输入输出
题目描述
通往贤者之塔的路上，有许多的危机。
我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。
为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点。初始昴位于1，当昴走到正确节点n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多少？
输入格式
第一行一个正整数T表示数据组数。
接下来每组数据，首先读入三个正整数n,m,p。
接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边）
用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。
数据保证j是k的父亲。
50<=p<=n<=700，m<=1500，T<=5。
数据保证每个正确节点均有至少2个儿子，至多3个儿子。
输出格式
T行每行一个实数表示每组数据的答案。请保留四位小数。
样例
样例输入
1
3 7 2
1 4
2 5
3 6
3 7
样例输出
9.0000
这个题还是挺有意思的
题目中提到这一句话
““我们可以把这个地形看做是一颗树，根节点编号为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左右就可以了
以下是本人丑陋的代码
#include<bits/stdc++.h>
#define ll long long
#define db double
#define A 2500
using namespace std;
ll t,tot=0,n,m,p,head[A],nxt[A],ver[A];
db g[A],a[A][A],cur,f[A][A],d[A],s[A];
bool flag[A];
inline void add(ll x,ll y)
{nxt[++tot]=head[x];head[x]=tot;ver[tot]=y;}
inline ll read()
{
ll x=0,f=1;char c=getchar();
while(!isdigit(c))
{
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return f*x;
}
void dfs(ll x)
{
flag[x]=1;
g[x]=1.0;
for(ll i=head[x];i;i=nxt[i])
{
ll y=ver[i];
if(!flag[y])
dfs(y);
g[x]+=1.0/d[x]*g[y];
}
}
int main()
{
t=read();
while(t--)
{
tot=0;
memset(flag,0,sizeof(flag));
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(ver,0,sizeof(ver));
memset(d,0,sizeof(d));
memset(g,0,sizeof(g));
memset(flag,0,sizeof(flag));
memset(f,125,sizeof(f));
n=read();m=read();p=read();
for(ll i=1;i<=m-n;i++)
{
ll x,y;
x=read(),y=read();
add(x,y);d[x]++;
}
for(ll i=1;i<n;i++)
d[i]++;
for(ll i=1;i<=n;i++)
if(!flag[i])dfs(i);
for(ll i=1;i<=n;i++)
{
s[i]=0;
for(ll j=head[i];j;j=nxt[j])
{
ll y=ver[j];
s[i]+=g[y];
}
}
for(ll i=1;i<=n;i++)
{
a[i][i]=0;
for(ll j=i+1;j<=n;j++)
a[i][j]=a[i][j-1]*d[j-1]+s[j-1]+d[j-1];
}
f[n][1]=0.0;
for(ll j=2;j<=p;j++)
{
for(ll i=1;i<=n;i++)
for(ll k=i+1;k<=n;k++)
{
if(k-i>40) break;
f[i][j]=min(f[i][j],f[k][j-1]+a[i][k]);
}
}
db ans=f[1][p];
printf("%.4lf\n",ans);
}
return 0;
}
View Code
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
C. 雨天的尾巴
内存限制：128 MiB 时间限制：1000 ms 标准输入输出
题目描述
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。
输入格式
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题
输出格式
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品则输出0
样例
样例输入
20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50
样例输出
87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50
数据范围与提示
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10910^9109
也是一道不错的题
思考我们如果按照既定套路，进行树上拆分的话
我们还需要维护每一个节点出现的值中最大的是什么
我们首先可以想到开一个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 其实还是和离散化差不多
最后统一进行线段树合并
完了（数据结构题真不知道要说些什么）
以下依然是本人丑陋的代码
#include<bits/stdc++.h>
#define A 100005
#define ll int
using namespace std;
bool flag[A*2];
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];
ll n,m,sum[A];
inline ll read()
{
ll f=1,x=0;char c=getchar();
while(!isdigit(c))
{
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
return f*x;
}
void pushup(ll now)
{
if(ans[lc[now]]>=ans[rc[now]])
ans[now]=ans[lc[now]],Ans[now]=Ans[lc[now]];
else
ans[now]=ans[rc[now]],Ans[now]=Ans[rc[now]];
}
void add(ll x,ll y)
{
next[++tot]=head[x];
head[x]=tot;
ver[tot]=y;
}
ll merge(ll x,ll y,ll l,ll r)
{
if(l==r&&x&&y) ans[x]+=ans[y];
if(!x||!y) return y+x;
ll mid=(l+r)>>1;
lc[x]=merge(lc[x],lc[y],l,mid);
rc[x]=merge(rc[x],rc[y],mid+1,r);
if(l!=r)pushup(x);
return x;
}
void change(ll &p,ll l,ll r,ll pos,ll v)
{
if(!p) p=++cnt;
if(l==r)
{ans[p]+=v;Ans[p]=l;return ;}
ll mid=(l+r)>>1;
if(pos<=mid) change(lc[p],l,mid,pos,v);
else change(rc[p],mid+1,r,pos,v);
if(l!=r) pushup(p);
}
void dfs(ll x,ll dep)
{
flag[x]=1,deep[x]=dep;
for(ll i=head[x];i;i=next[i])
{
ll y=ver[i];
if(flag[y]) continue;
f[y][0]=x;
deep[y]=dep;
dfs(y,dep+1);
}
}
ll lca(ll x,ll y)
{
if(deep[x]>deep[y])
swap(x,y);
for(ll i=20;i>=0;i--)
{
if(deep[x]<=deep[f[y][i]])
y=f[y][i];
if(deep[x]==deep[y]) break;
}
if(x==y) return x;
for(ll i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
void dfs_(ll x)
{
flag[x]=1;
for(ll i=head[x];i;i=next[i])
{
ll y=ver[i];
if(flag[y]) continue;
dfs_(y);
T[x]=merge(T[x],T[y],1,A);
}
if(ans[T[x]]>0)
sum[x]=Ans[T[x]];
}
int main()
{
n=read(),m=read();
for(ll i=1;i<n;i++)
{
ll xx=read(),yy=read();
add(xx,yy);
add(yy,xx);
}
dfs(1,1);
f[1][0]=0;
for(ll i=1;i<=20;i++)
for(ll j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
ll LCA;
for(ll i=1;i<=m;i++)
{
ll x=read(),y=read(),z=read();
LCA=lca(x,y);
change(T[x],1,A,z,1);
change(T[y],1,A,z,1);
change(T[LCA],1,A,z,-1);
change(T[f[LCA][0]],1,A,z,-1);
}
memset(flag,0,sizeof(flag));
dfs_(1);
for(ll i=1;i<=n;i++)
printf("%d\n",sum[i]);
}
View Code