【BZOJ 4318】OSU!

解题报告

$E_{(i,x^2)}，E_{(i,x)}$分别表示$x^2,x$的期望

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
double e1=0,e2=0,e3=0,ans=0,p;
for (int i=1;i<=n;i++) {
scanf("%lf",&p);
ans += e3 * (1 - p);
e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
e2 = p * (e2 + 2 * e1 + 1);
e1 = p * (e1 + 1);
}
printf("%.1lf\n",ans+e3);
return 0;
}


【Codeforces 749E】Inversions After Shuffle

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[N];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Fenwick_Tree{
double sum[N];
public:
inline void init() {
memset(sum, 0, sizeof(sum));
}
inline void modify(int p, int d = 1) {
for (int i = p; i <= n; i += lowbit(i)) {
sum[i] += d;
}
}
inline double query(int p) {
double ret = 0;
for (int i = p; i; i -= lowbit(i)) {
ret += sum[i];
}
return ret;
}
}BIT;

int main() {
for (int i = 1; i <= n; i++) {
}
double ans = 0, psm = 0;
for (int i = n; i; i--) {
ans += BIT.query(p[i]);
BIT.modify(p[i]);
}
ans *= n * (n + 1ll);
BIT.init();
for (int i = 1; i <= n; i++) {
LL t1 = BIT.query(p[i]);
LL t2 = i * (i - 1ll) / 2 - t1;
ans += (psm += t1 - t2);
BIT.modify(p[i], i);
}
printf("%.15lf\n", ans / n / (n + 1));
return 0;
}


【BZOJ 3451】Tyvj1953 Normal

解题报告

—————————— UPD 2017.4.11 ————————————

【HDU 4624】Endless Spin

Code

#include<bits/stdc++.h>
#define LL long long
#define LDB __float128
using namespace std;

const int N = 51;
const int M = N * N;

int n,ww,pp;
LL f[2][N][M][2];
LDB ans;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
for (int T=read();T;T--) {
ans = ww = 0; pp = 1;
memset(f,0,sizeof(f));
f[pp][0][0][0] = 1;
for (int i=0;i<n;i++,ww^=1,pp^=1) {
memset(f[ww],0,sizeof(f[ww]));
for (int j=0;j<=i;j++) {
for (int k=i*i;~k;k--) {
for (int p=0;p<=1;p++) {
if (f[pp][j][k][p]) {
f[ww][0][k+j*(j+1)/2][p^(j&1)] += f[pp][j][k][p];
f[ww][j+1][k][p] += f[pp][j][k][p];
}
}
}
}
}
for (int j=0;j<=n;j++) {
for (int k=n*n;~k;k--) {
for (int p=0;p<=1;p++) {
if (!f[pp][j][k][p]) continue;
int v = k + j * (j + 1) / 2, t = p ^ (j & 1);
LDB tmp = ((v < n * (n + 1) / 2)? ((LDB)v / (n * (n + 1) / 2 - v)): 0);
if ((n-t)&1) ans += tmp * f[pp][j][k][p];
else ans -= tmp * f[pp][j][k][p];
}
}
}
ans += 1;
printf("%.15Lf\n",(long double)ans);
}
return 0;
}


【BZOJ 3566】[SHOI2014] 概率充电器

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int M = N << 1;

double up[N],down[N],cost[M],q[N],vout;

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v, int f) {
static int E = 1;
cost[E+1] = cost[E+2] = f / 100.0;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS1(int w, int f) {
down[w] = 1 - q[w];
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS1(to[i], w);
down[w] *= down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]);
}
}
}

void DFS2(int w, int f, double p) {
vout += 1 - (up[w] = down[w] * p);
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
double tmp = p * down[w] / (down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]));
DFS2(to[i], w, tmp + (1 - tmp) * (1 - cost[i]));
}
}
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
for (int i=1;i<=n;i++) q[i] = read() / 100.0;
DFS1(1, 1);
DFS2(1, 1, 1);
printf("%.6lf\n",vout);
return 0;
}


【BZOJ 4008】[HNOI2015] 亚瑟王

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,r,d[250];
double f[250][150],p[250][150],ans[250];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
for (int T=read();T;T--) {
memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++) scanf("%lf%d",&p[i][0],&d[i]);
for (int i=1;i<=n;i++) {
p[i][1] = 1 - p[i][0];
for (int j=2;j<=r;j++) p[i][j] = p[i][j-1] * p[i][1];
}
f[1][r] = 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=r;j++) {
ans[i] += f[i][j] * (1 - p[i][j]);
f[i+1][j] += f[i][j] * p[i][j];
f[i+1][j-1] += f[i][j] * (1 - p[i][j]);
}
}
double vout = 0;
for (int i=1;i<=n;i++) vout += ans[i] * d[i];
printf("%.10lf\n",vout);
}
return 0;
}


【日常小测】随机游走

解题报告

$$f_u=\deg u + \sum\limits_{v \in son_u}{f_v}$$
$$g_u=\deg fa_u + \sum\limits_{v \in son_{fa_u},v \ne u}{f_v} + g_{fa_{fa_u}}$$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;

int in[N],dep[N],fa[N][20];
LL f[N],g[N],PreF[N],PreG[N];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u = fa[u][i];
if (u == v) return u;
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}

void DFS1(int w, int anc) {
fa[w][0] = anc;	f[w] = in[w];
dep[w] = dep[anc] + 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != anc) {
DFS1(to[i], w);
f[w] += f[to[i]];
}
}
}

void DFS2(int w, int anc) {
PreF[w] = PreF[anc] + f[w];
PreG[w] = PreG[anc] + g[w];
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != anc) {
g[to[i]] = f[w] - f[to[i]] + g[w];
DFS2(to[i], w);
}
}
}

int main() {
DFS1(1, 1);
DFS2(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
u = read(); v = read(); lca = LCA(u, v);
printf("%lld\n",PreF[u]-PreF[lca]+PreG[v]-PreG[lca]);
}
return 0;
}


【HDU 5194】DZY Loves Balls

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int GCD(int x, int y) {
return y? GCD(y, x % y): x;
}

int main() {
for (int n,m,gcd;~scanf("%d%d",&n,&m);) {
gcd = GCD(n*m, n+m);
printf("%d/%d\n", n*m/gcd, (n+m)/gcd);
}
return 0;
}


【NOI六连测】[D3T1] 炉石

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
freopen("hearthstone.in","r",stdin);
freopen("hearthstone.out","w",stdout);
scanf("%d%lf",&n,&win);
lose = 1 - win;
arr[96-n][0] = 1;
for (int k=1;k<=T;k++){
for (int i=0;i<=10;i++){
tmp[i][0] += arr[i][0]*lose;
tmp[i][0] += arr[i][1]*lose;
tmp[i][0] += arr[i][2]*lose;
tmp[i][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+2][3] += arr[i][2]*win;
tmp[i+2][3] += arr[i][3]*win;
}
for (int i=11;i<=70;i++){
tmp[i-1][0] += arr[i][0]*lose;
tmp[i-1][0] += arr[i][1]*lose;
tmp[i-1][0] += arr[i][2]*lose;
tmp[i-1][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+2][3] += arr[i][2]*win;
tmp[i+2][3] += arr[i][3]*win;
}
for (int i=71;i<=95;i++){
tmp[i-1][0] += arr[i][0]*lose;
tmp[i-1][0] += arr[i][1]*lose;
tmp[i-1][0] += arr[i][2]*lose;
tmp[i-1][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+1][3] += arr[i][2]*win;
tmp[i+1][3] += arr[i][3]*win;
}
ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k;
memcpy(arr,tmp,sizeof(tmp));
memset(tmp,0,sizeof(tmp));
}
printf("%.2lf\n",ans);
return 0;
}