既然被提醒了不要咕咕咕那就先写一点（？
不过过几天估计就又咕啦。
深刻体会到了写完几道题统一补博客的难受。
期望题 LaTeX 好难打诶可能写得简略点qaq
例题1.单选错位
emmm 好像没啥可说（？
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,A,B,C,a[N];
double ans;
int main()
{
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
a[i] = a[i] % C + 1;
ans+=1.0/max(a[1],a[n]);
for(int i=2;i<=n;i++)
{
ans+=1.0/max(a[i],a[i-1]);
}
printf("%.3lf\n",ans);
return 0;
}
例题2.期望分数
同时开两个变量维护当前的期望得分和期望连续o的长度。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n;
double len,ans;
char s[N];
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='o')
{
ans+=len*2+1;
len++;
}
else if(s[i]=='x') len=0;
else
{
ans+=(len*2+1)/2.0;
len=(len+1)/2.0;
}
}
printf("%.4lf\n",ans);
return 0;
}
例题3.路径长度
原题 lg P4316 绿豆蛙的归宿。
建反图进行拓扑排序，从终点倒推。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,in[N],out[N];
double E[N];
struct node{
int nxt,to,w;
}e[N];
int head[N],cnt;
void add(int u,int v,int w){
e[++cnt]={head[u],v,w};head[u]=cnt;
}
queue<int> q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(v,u,w);in[u]++;out[u]++;
}
E[n]=0;
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
//cout<<u<<endl;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
E[v]+=(E[u]*1.0+e[i].w)*1.0/out[v];
if(--in[v]==0) q.push(v);
}
}
printf("%.2lf\n",E[1]);
return 0;
}
1.比赛得分
分别计算两队的期望得分。
对于 A 队第 x 个人，对答案贡献为 \(\frac{1}{n}\Sigma_{B_y<A_x}(A_x-B_y)^2\) 。
把平方展开，对序列排序后 y 的取值变为连续一段，指针维护。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,A,B,C,a[N];
double ans;
int main()
{
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
a[i] = a[i] % C + 1;
ans+=1.0/max(a[1],a[n]);
for(int i=2;i<=n;i++)
{
ans+=1.0/max(a[i],a[i-1]);
}
printf("%.3lf\n",ans);
return 0;
}
2.电影问题
先看 \(i\) 再看 \(j\) 对答案的贡献为 \(l_i\times \frac{x_i}{y_i}\times \frac{y_j-x_j}{y_j}\)。
按照上述贡献的大小对原序列排序即为最大期望。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int mod=1004535809;
int n,f[N],g[N];
struct node{
int l,x,y;
}a[N];
bool cmp(node a,node b){
int c=a.l*a.x*(b.y-b.x);
int d=b.l*b.x*(a.y-a.x);
return c>d;
}
int qpow(int n,int k)
{
int ans=1;
while(k)
{
if(k&1) ans=ans*n%mod;
n=n*n%mod;k>>=1;
}
return ans;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].l,&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
int inv=qpow(a[i].y,mod-2);
f[i]=((f[i-1]+a[i].l*(2*a[i].x-a[i].y)%mod*inv%mod+g[i-1]*(a[i].y-a[i].x)%mod*inv%mod)%mod+mod)%mod;
g[i]=(g[i-1]+a[i].l*a[i].x%mod*inv%mod)%mod;
}
cout<<f[n]<<endl;
return 0;
}