2018.10.16考试总结
1 、购物
(shop.pas/c/cpp)
【题目描述】
小林来到商店中进行购物。 商店里一共有 n 件物品， 第 i 件物品的价格为 a[i]元。小林总共需要购买 m 件物品，他希望他所花费的钱最少，请你计算出最小花费。
由于输入的数据数量过大，我们采用一种加密的方式进行输入。给出两个密钥 x 和 y。则 a[1] = x, a[i] = (y*a[i-1] + x) % 10^9。
【输入格式】
一行两个整数 n 和 m。
第二行共两个整数 x 和 y，表示密钥。
【输出格式】
输出只有一个整数，表示最小花费。
【样例输入】
5 3
2 9
【样例输出】
204
【数据规模】
对于 50%的数据，n <= 1000；
对于 100%的数据，1 <= n <= 10^7, 1 <= m <= 100, 1 <= x,y < 10^9。
对于 100%的数据，保证 m <= n。
题目很好懂，暴力很好想，但是数据太大正解没想到，正解是用堆或优先队列维护m个最小值
人傻就要多做题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int mod=1e9;
int n,m,x,y,ans,a[10000010];
priority_queue<int> q;
signed main()
{
cin>>n>>m>>x>>y;
a[1]=x;
for(int i=2;i<=n;++i)
a[i]=(y*a[i-1]+x)%mod;
for(int i=1;i<=m;++i)
q.push(a[i]);
for(int i=m+1;i<=n;++i)
{
if(q.top()>a[i])
{
q.pop();
q.push(a[i]);
}
}
while(!q.empty())
{
ans+=q.top();
q.pop();
}
cout<<ans<<"\n";
return 0;
}
2 、期望
(exp.pas/c/cpp)
【题目描述】
我们知道，若一个随机变量 X，在 pi 的概率下，它的值等于 xi，则它的数学期望\(E(X)=\sum_{i} p_i x_i\),且满足\(\sum_{i}p_i=1\)
现在有如下一个表达式：
0 a1 b1 a2 b2 ... an bn
其中 ai 为一个位运算符，是“和”“或”“异或”三者中的一种，bi 是一个整数。
求这一表达式的值是一件容易的事，然而刚学完数学期望的小林在思考，如果每一对 ai bi 有 ci 的概率会消失，那么这一表达式的结果的数学期望是多少。
【输入格式】
第一行只有一个正整数 n。
第二行为 n 个整数表示 n 个运算符 ai，0 表示 and，1 表示 or，2 表示 xor。
第三行为 n 个非负整数 bi。
第四行为 n 个实数 ci（不超过三位小数）。
【输出格式】
只有一个实数，表示表达式的数学期望，保留一位小数。
【样例输入】
2
1 2
5 7
0.5 0.5
【样例输出】
3.5
【数据规模】
对于 30%的数据，1 <= n <= 10，0 <= bi <= 20；
对于 70%的数据，1 <= n <= 100，0 <= bi <= 1000；
对于 100%的数据，1 <= n <= 100000，0 <= ai <= 2，0 <= bi < 2^31。
对于 100%的数据，0 <= ci <= 0.999。
期望没学过啊，看了看题，瞎写写dfs 竟然能过40，数据太水了
正解肯定是期望dp啊，转移方程见代码
40分暴力
#include<iostream>
#include<cstdio>
using namespace std;
double ans,c[110],d[110];
int n,a[110],b[110];
void dfs(int now,int z,double jl)
{
if(now>n)
{
ans+=(double)(jl*z);
return ;
}
if(a[now]==0)
{
dfs(now+1,z&b[now],jl*d[now]);
dfs(now+1,z,jl*c[now]);
}
if(a[now]==1)
{
dfs(now+1,z|b[now],jl*d[now]);
dfs(now+1,z,jl*c[now]);
}
if(a[now]==2)
{
dfs(now+1,z^b[now],jl*d[now]);
dfs(now+1,z,jl*c[now]);
}
}
int main()
{
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n;++i)
cin>>b[i];
for(int i=1;i<=n;++i)
cin>>c[i],d[i]=1-c[i];
dfs(1,0,1);
printf("%.1lf\n",ans);
return 0;
}
正解
#include<iostream>
#include<cstdio>
const int N=100010;
double f[N][34];
int a[N],b[N];
double c[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) scanf("%lf",&c[i]);
for(int i=1;i<=n;++i)
for(int j=0;j<=31;++j)
{
if(a[i]==0)
{
if(b[i]&(1<<j))
{
f[i][j]=(1-c[i])*f[i-1][j];
f[i][j]+=c[i]*f[i-1][j];
}
else
{
f[i][j]=0;
f[i][j]+=c[i]*f[i-1][j];
}
}
if(a[i]==1)
{
if(b[i]&(1<<j))
{
f[i][j]=(1-c[i]);
f[i][j]+=c[i]*f[i-1][j];
}
else
{
f[i][j]=(1-c[i])*f[i-1][j];
f[i][j]+=c[i]*(f[i-1][j]);
}
}
if(a[i]==2)
{
if(b[i]&(1<<j))
{
f[i][j]=(1-c[i])*(1-f[i-1][j]);
f[i][j]+=c[i]*(f[i-1][j]);
}
else
{
f[i][j]=(1-c[i])*f[i-1][j];
f[i][j]+=c[i]*f[i-1][j];
}
}
}
double ans=0;
for(int i=0;i<=32;++i)
ans+=(1<<i)*f[n][i];
printf("%.1lf",ans);
return 0;
}
3 3 、 魔法迷宫
(maze.pas/c/cpp)
【题目描述】
在创建了魔法森林后，亮亮兴致不减，于是挥动魔杖，又创造了魔法迷宫。魔法迷宫共有 n 个节点，由 n-1 条边将它们相连，整个迷宫是连通的。边的长度只有 A 和 B 两种。现在有 m 只小精灵，第 i 只小精灵一开始在 ui 点，她想要到达 vi 点，每一天，它最多移动 ki 的距离，而且她不能停留在某一条边上。你的任务是，计算出每一只小精灵到达自己的目的地至少需要几天。
【输入格式】
第一行一个整数 n。
接下来 n-1 行，每行三个整数 x, y, z, 表示 x,y 之间有一条长度为 z 的边。
随后一行一个整数 m，表示共有 m 只小精灵。
接下来 m 行，每行三个整数 ui, vi, ki。（保证 B≤ki≤n）
【输出格式】
输出共 m 行，每行一个整数表示答案。
【样例输入】
3
1 2 1
2 3 2
2
1 2 3
2 3 3
【样例输出】
1
1
【数据规模】
对于 20%的数据，n,m <= 5000；
对于 100%的数据，1 <= n,m <= 50000，1 <= A < B <= 37
鬼畜题，什么鬼，不会，瞎写了一下，不但写错了，而且freopen还不小心删了，无输出
正解：预处理每一个点往上连续走六步会出现的各种情况，控制常数，从而在 8 秒内出解。由于边权只有两种，所以一个点往上走六步遇到的边权只有 2^6 = 64 种情况。
#include<cstdio>
#include<cstring>
#include<iostream>
#define E 50010
#define F 100010
using namespace std;
int n,m,head[E],to[F],next[F],value[F],cnt=0,cost=0,costa=0;
void add(int x,int y,int z)
{
to[++cnt]=y;
value[cnt]=z;
next[cnt]=head[x];
head[x]=cnt;
}
int fa[E][20],dep[E],dist[E][7],type[E],jky[E][300],dd[E],jump[E];
short czy[1<<8][300][300][2];
void dfs(int u, int f, int d)
{
fa[u][0]=f;
dep[u]=d;
for(int j=head[u];j;j=next[j])
{
int v=to[j];
if(v==f) continue;
dist[v][0]=value[j];
dfs(v,u,d+1);
}
}
void build()
{
for(int k=1;k<20;k++)
for(int u=1;u<=n;u++)
{
fa[u][k]=fa[fa[u][k-1]][k-1];
if(k<=5) dist[u][k]=dist[u][k-1]+dist[fa[u][k-1]][k-1];
}
for(int i=1;i<=n;i++)
if(dep[i]>=6) dd[i]=dist[i][2]+dist[fa[i][2]][1];
for(int i=1;i<=n;i++)
{
if(dep[i]<6) continue;
int t=0,u=i;
for(int j=0;j<6;j++)
{
if(dist[u][0]==cost) t+=1<<j;
u=fa[u][0];
}
jump[i]=u;
type[i]=t;
}
for(int j=0;j<(1<<6);j++)
for(int k=cost;k<=cost*6;k++)
for(int rest=0;rest<=k;rest++)
{
int path=j,step=0,re=rest;
for(int t=1;t<=6;t++)
{
int co;
if(path&1) co=cost;
else co=costa;
if(re<co) re=k,step++;
re-=co;
path>>=1;
}
czy[j][k][rest][0]=step;
czy[j][k][rest][1]=re;
}
for(int i=1;i<=n;i++)
{
int u=i,rest=0;
for (int j=0;j<dd[i];j++)
{
if(dep[u]>0&&rest>=dist[u][0])
{
rest-=dist[u][0];
u=fa[u][0];
}
jky[i][j]=u;
rest++;
}
}
}
int get(int x, int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int k=19;k>=0;k--)
if(dep[fa[x][k]]>=dep[y]) x=fa[x][k];
if(x==y) return x;
for(int k=19;k>=0;k--)
if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
if (x!=y) x=fa[x][0];
return x;
}
struct hyd
{
int step,rest;
};
inline hyd work(int u,int f,int k)
{
int step=0,rest=0;
if(k<=cost*6)
while (dep[u]>dep[f])
{
if(dep[u]-dep[f]<6)
{
if(rest>=dist[u][0]) rest-=dist[u][0];
else step++,rest=k-dist[u][0];
u=fa[u][0];
continue;
}
step+=czy[type[u]][k][rest][0];
rest=czy[type[u]][k][rest][1];
u=jump[u];
}
else
while(dep[u]>dep[f])
{
if(rest==0) step++,rest=k;
if(dep[u]-dep[f]<6)
{
if(rest>=dist[u][0]) rest-=dist[u][0];
else step++,rest=k-dist[u][0];
u=fa[u][0];
continue;
}
if(rest>=dd[u])
{
rest-=dd[u];
u=jump[u];
continue;
}
u=jky[u][rest],rest=0;
}
return (hyd){step,rest};
}
int main()
{
scanf("%d",&n);
memset(head,0,sizeof(head));
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
if(cost<z) cost=z;
if(i==1) costa=z;
else if(costa>z) costa=z;
}
memset(fa,0,sizeof(fa));
memset(dep,0,sizeof(dep));
memset(dist,0,sizeof(dist));
dfs(1,0,0);
build();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
int f=get(x,y);
hyd ans1=work(x,f,k),ans2=work(y,f,k);
int ans=ans1.step+ans2.step;
ans-=(ans1.rest+ans2.rest)/k;
printf("%d\n",ans);
}
return 0;
}