购物(shop)
Description
小林来到商店中进行购物。商店里一共有 n 件物品，第 i 件物品的价格为 a[i] 元。小林总共需要购买 m 件物品，他希望他所花费的钱最少，请你计算出最小 花费。
由于输入的数据数量过大，我们采用一种加密的方式进行输入。给出两个密 钥 x 和 y。则 a[1] = x, a[i] = (y*a[i-1] + x) % 10^9。
Input
一行两个整数 n 和 m。
第二行共两个整数 x 和 y，表示密钥。
Output
输出只有一个整数，表示最小花费。
数据规模
对于 50%的数据， n <= 1000；
对于 100%的数据， 1 <= n <= 10^7, 1 <= m <= 100, 1 <= x,y < 10^9。
对于 100%的数据，保证 m <= n。
看到题的一瞬间,这不傻逼题.
\(sort\)！转眼一想貌似过不去。
不过有人用sort过了
这里用的是大根堆维护价值,
PS：注意要先在堆里垫上\(m\)个元素.
如果某一个物品的价值比当前堆顶的价值要小,就替换它.
最后取出堆中\(m\)个元素就好了。
代码
#include<cstdio>
#include<queue>
#include<iostream>
#define mod 1000000000
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,cnt=1;
long long x,y,tmp,ans;
priority_queue<int>q;
int main()
{
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
in(n),in(m);
scanf("%lld%lld",&x,&y);tmp=x;
q.push(x);
for(R int i=2;i<=n;i++)
{
tmp=(tmp*y+x)%mod;
tmp=(tmp+mod)%mod;
if(cnt<m)
{
cnt++;
q.push(tmp);
continue;
}
if(q.top()>tmp)q.pop(),q.push(tmp);
}
for(R int i=1;i<=m;i++)
ans+=q.top(),q.pop();
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
期望(exp)
Description
我们知道，若一个随机变量 \(X\)，在 \(p_i\) 的概率下，它的值等于 \(x_i\)， 则它的 数学期望 \(E(X)=\sum_ip_ix_i\) ，且满足$\sum_ip _i =1 $ 。
现在有如下一个表达式： \(0 \ a_1 \ b_1\ a_2\ b_2 ... a_n \ b_n\)
其中 \(a_i\) 为一个位运算符，是“和” “或” “异或”三者中的一种， \(b_i\) 是一 个整数。
求这一表达式的值是一件容易的事，然而刚学完数学期望的小林在思考，如 果每一对 \(a_i b_i\) 有 \(c_i\) 的概率会消失，那么这一表达式的结果的数学期望是多少。
Input
第一行只有一个正整数 \(n\)。
第二行为 \(n\) 个整数表示 \(n\)个运算符 \(a_i\)， \(0\) 表示 \(and\)， \(1\) 表示 \(or\)， \(2\) 表示 \(xor\)。
第三行为 \(n\) 个非负整数 \(b_i\)。
第四行为 \(n\) 个实数 \(c_i\)（不超过三位小数）。
Output
只有一个实数，表示表达式的数学期望，保留一位小数。
数据规模
对于 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。
看到题。woc,
期望,不会不会不会.
敲完\(30\)分的爆搜,发现貌似可以搞.
考虑\(DP\).
设\(f[i][j]\)代表处理前\(i\)个数,二进制位\(j\)上存在的概率
这里为什么要这样设？
如果直接设是否是\(j\)，很显然,\(2^{31}\)开不下,你滚动数组也开不下
因此拆位处理.
这题难就难在分类讨论
这里把我打的草稿放上来
一.当前符号位为＆
存在两种情况.
\]
二.当前符号位为 |
存在两种情况.
- \(b[i]\)有二进制\(j\)这一位
那么\(b[i]\)存在消失均可
但是现在\(b[i]\)存在不需要考虑之前的,因为我是独立的.(因为当前符号位是\(|\))
所以
\]
- \(b[i]\)没有二进制\(j\)这一位
此时消失存在均可.则
\]
三.当前符号位为^
依旧存在两种情况.
- \(b[i]\)有二进制\(j\)这一位
要么我存在&&上一位不存在,要么我不存在&&上一位存在.
所以
\]
- \(b[i]\)没有二进制\(j\)这一位.
此时选不选即可,直接继承
\]
可以滚动数组,空间复杂度很低.
稳稳地能过.
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<queue>
#include<algorithm>
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
double ans,c[100008],f[2][40];
int n,a[100008],b[100008];
inline void init()
{
for(R int i=1;i<=n;i++)in(a[i]);
for(R int i=1;i<=n;i++)in(b[i]);
for(R int i=1;i<=n;i++)scanf("%lf",&c[i]);
}
void dfs(R int dep,R int now,R double tmp)
{
if(dep>n)
{
// printf("%d %.2lf\n",now,tmp);
ans+=now*tmp;
return;
}
if(a[dep]==0)
dfs(dep+1,now&b[dep],tmp*(1-c[dep]));//不消失
if(a[dep]==1)
dfs(dep+1,now|b[dep],tmp*(1-c[dep]));//不消失
if(a[dep]==2)
dfs(dep+1,now^b[dep],tmp*(1-c[dep]));//不消失
dfs(dep+1,now,tmp*c[dep]);//消失
}
int main()
{
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
in(n);init();
if(n<=10)/*2^n*/
dfs(1,0,1),printf("%.1f\n",ans);
else
{
for(R int i=1;i<=n;i++)
{
R int op=i&1;
for(R int j=0;j<=31;j++)
{
if(a[i]==0)
{
if(b[i]&(1LL<<j))
f[op][j]=f[op^1][j];
else
f[op][j]=c[i]*f[op^1][j];
}
if(a[i]==1)
{
if(b[i]&(1LL<<j))
{
f[op][j]=(1-c[i]);
f[op][j]+=c[i]*f[op^1][j];
}
else
f[op][j]=f[op^1][j];
}
if(a[i]==2)
{
if(b[i]&(1LL<<j))
{
f[op][j]=(1-c[i])*(1-f[op^1][j]);
f[op][j]+=c[i]*(f[op^1][j]);
}
else
f[op][j]=f[op^1][j];
}
}
}
for(R int i=0;i<=31;i++)
ans+=(1LL<<i)*f[n&1][i];
printf("%.1f\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
魔法迷宫(maze)
Description
在创建了魔法森林后，亮亮兴致不减，于是挥动魔杖，又创造了魔法迷宫。
魔法迷宫共有 n 个节点，由 n-1 条边将它们相连，整个迷宫是连通的。边的 长度只有 A 和 B 两种。
现在有 m 只小精灵，第 i 只小精灵一开始在 ui 点，她想要到达 vi 点，每一 天，它最多移动 ki 的距离，而且她不能停留在某一条边上。你的任务是，计算 出每一只小精灵到达自己的目的地至少需要几天。
Input
第一行一个整数 n。
接下来 n-1 行，每行三个整数 x, y, z, 表示 x,y 之间有一条长度为 z 的边。
随后一行一个整数 m，表示共有 m 只小精灵。
接下来 m 行，每行三个整数 ui, vi, ki。（保证 B≤ki≤n）
Output
输出共 m 行，每行一个整数表示答案。
数据规模
对于 20%的数据， n,m <= 5000；
对于 100%的数据， 1 <= n,m <= 50000， 1 <= A < B <= 37。
先模大佬\(GMPotlc\)：梦想得分\(100pts\)
神卡常卡过此题,
由于\(LCA\)会多\(log\),因此直接暴力向上跳,判断情况即可.
注意卡常！
决定放一下\(\color{red}官方题解\)
考察算法： LCA， 压位
算 LCA 是显然的， 由于两个点之间可能要走很多步， 所以我们预处理每一个点往上连续 走六步会出现的各种情况， 便能控制常数， 从而在 8 秒内出解。 由于边权只有两种， 所以一 个点往上走六步遇到的边权只有 2^6 = 64 种情况。
暴力代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register
#define N 50008
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int head[N],tot,rt,dis[N],f[N],depth[N],n,m;
struct cod{int u,v,w;}edge[N<<2];
inline void add(int x,int y,int z)
{
edge[++tot].u=head[x];
edge[tot].v=y;
edge[tot].w=z;
head[x]=tot;
}
void dfs(R int u,R int fa,R int dist)
{
f[u]=fa;dis[u]=dist;depth[u]=depth[fa]+1;
for(R int i=head[u];i;i=edge[i].u)
{
if(edge[i].v==fa)continue;
dfs(edge[i].v,u,edge[i].w);
}
}
int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
in(n);
for(R int i=1,x,y,z;i<n;i++)
in(x),in(y),in(z),add(x,y,z),add(y,x,z);
R int rt=(n+1)>>1;
dfs(rt,0,0);
in(m);
for(R int i=1,x,y,z;i<=m;i++)
{
R int resa,resb,ans;
in(x),in(y),in(z);
resb=resa=ans=0;
if(depth[x]>depth[y])swap(x,y);
while(depth[x]>depth[y])
{
if(resa+dis[x]>z)resa=dis[x],ans++;
else resa+=dis[x];
x=f[x];
}
while(x!=y)
{
if(resa+dis[x]>z)resa=dis[x],ans++;
else resa+=dis[x];
if(resb+dis[y]>z)resb=dis[y],ans++;
else resb+=dis[y];
x=f[x];y=f[y];
}
if(resa+resb>z)ans+=2;
else if(resa+resb!=0)ans++;
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}