购物(shop)
看到题的一瞬间,这不傻逼题.
\(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)
看到题。woc,
期望,不会不会不会.
敲完\(30\)分的爆搜,发现貌似可以搞.
考虑\(DP\).
设\(f[i][j]\)代表处理前\(i\)个数,二进制位\(j\)上存在的概率
这题难就难在分类讨论
这里把我打的草稿放上来
一.当前符号位为＆
存在两种情况.
\[\begin{cases}当前数b[i]有二进制j这一位 此时b[i]存在消失均可,则 f[i][j]=f[i-1][j]\\ \\当前数b[i]没有二进制j这一位 那么想要有j,b[i]必须消失,则 f[i][j]=c[i]*f[i-1][j]\end{cases}
\]
\]
二.当前符号位为 |
存在两种情况.
- \(b[i]\)有二进制\(j\)这一位
那么\(b[i]\)存在消失均可
但是现在\(b[i]\)存在不需要考虑之前的,因为我是独立的.(因为当前符号位是\(|\))
所以
\[f[i][j]=(1-c[i])+c[i]*f[i-1][j]
\]
\]
- \(b[i]\)没有二进制\(j\)这一位
此时消失存在均可.则
\[f[i][j]=f[i-1][j]
\]
\]
三.当前符号位为^
依旧存在两种情况.
- \(b[i]\)有二进制\(j\)这一位
要么我存在&&上一位不存在,要么我不存在&&上一位存在.
所以
\[f[i][j]=c[i]\times(1-f[i-1][j])+(1-c[i])\times f[i-1][j]
\]
\]
- \(b[i]\)没有二进制\(j\)这一位.
此时选不选即可,直接继承
\[f[i][j]=f[i-1][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)
先模大佬\(GMPotlc\)：梦想得分\(100pts\)
神卡常卡过此题,
由于\(LCA\)会多\(log\),因此直接暴力向上跳,判断情况即可.
注意卡常！
决定放一下\(\color{red}官方题解\)
暴力代码
#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;
}