【Codeforces 802L】Send the Fool Further! (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$

Code

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

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[N];

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;
}

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

inline int REV(int x) {
	int ret = 1, t = MOD - 2;
	for (; t; x = (LL)x * x % MOD, t >>= 1) {
		if (t & 1) {
			ret = (LL)ret * x % MOD;
		}
	}
	return ret;
}

void solve(int w, int f) {
	if (d[w] > 1) {
		a[w] = -1;
		for (int i = head[w]; i; i = nxt[i]) {
			b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
			if (to[i] != f) {
				solve(to[i], w);
			}
		}
		if (w != f) {
			b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
			a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	solve(1, 1);
	int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
	ans = (ans + MOD) % MOD;
	cout<<ans<<endl;
	return 0;
}

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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3566
神犇题解:https://blog.sengxian.com/solutions/bzoj-3566

解题报告

首先根据期望的线性,我们只需要求出每个元件有电的概率,之后相加就是答案
那么怎么求每个元件有电的概率呢?我们可以无脑点分
显然在$O(n)$的时间复杂度内搞一发树形$DP$就可以了

Code

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

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

int n,head[N],nxt[M],to[M]; 
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() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read());
	}
	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] 亚瑟王

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4008
神犇题解:https://blog.sengxian.com/solutions/bzoj-4008

解题报告

根据期望地线性,我们可以单独计算每一个技能的期望然后相加
于是问题转化为求每个技能在这$r$轮中被发动的概率

但我们发现如果直接模拟题目中的过程,我们似乎需要记录哪些点已经被使用过
这个问题似乎只能使用状压DP来解决?但复杂度是不允许这么干的
于是我们需要一点Trick:

我们将这$r$轮整体转移,记录$f_{i,j}$表示到第$i$个技能,还有$j$轮没有触发任何技能的概率
那么这个状态的时候第$i$个技能被触发的概率就是$1-(1-p_i)^j$

于是这个问题就做完啦!时间复杂度:$O(Tnr)$
至于为什么是对的?
因为每一轮的游戏过程没有区别,所以我们可以将将其一视同仁

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));
		n = read(); r = read();
		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;
}

【Codeforces 712E】Memory and Casinos

题目传送门:http://codeforces.com/problemset/problem/712/E
官方题解:http://codeforces.com/blog/entry/47050

这个题目想一想,还是挺好玩的
推导过程比较复杂,参见这里吧:http://codeforces.com/blog/entry/47050?#comment-314259
话说这次的官方题解真是辣鸡,还不如评论区容易懂…..

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

const int N = 200000+9;

int n,m;
double arr[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;
}

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[N][2],cnt,root,T1,L,R;
	double t1[N],t2[N],T2,ans_tmp;
	
	inline void maintain(int w){
		t1[w] = t1[ch[w][0]] * t1[ch[w][1]];
		t2[w] = t2[ch[w][0]] + t2[ch[w][1]] * t1[ch[w][0]];
	}
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		if (l == r) {
			t1[w] = t2[w] = arr[l];
		} else {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	void modify(int w, int l, int r) {
		if (l == r) {
			t1[w] = t2[w] = T2;
		} else {
			int mid = l + r + 1 >> 1;
			if (T1 < mid) modify(ch[w][0],l,mid-1);
			else modify(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	inline void modify(int pos, double nv) {
		T1 = pos; T2 = nv;
		modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += t2[w] * T2;
			T2 *= t1[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1);
			if (mid <= R) query(ch[w][1],mid,r);
		}
	}
	
	inline double query(int l, int r) {
		ans_tmp = 0; T2 = 1;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

int main(){
	n = read(); m = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		double tmp = (double)a/b;
		arr[i] = (1 - tmp) / tmp;
	}
	SEG::Build(SEG::root,1,n);
	for (int i=1,a,b,c,ty;i<=m;i++) {
		ty = read(); a = read(); b = read();
		if (ty == 1) {
			c = read();
			double tmp = (double)b/c;
			SEG::modify(a,(1-tmp)/tmp);
		} else {
			double tmp = SEG::query(a,b);
			tmp = min(1e20,tmp);
			printf("%.10lf\n",1/(1+tmp));
		}
	}
	return 0;
}

【Codeforces 696B】Puzzles

题目传送门:http://codeforces.com/contest/696/problem/B
官方题解:http://codeforces.com/blog/entry/46031
中文题面:http://blog.csdn.net/oulaline/article/details/51941548
中文题解:http://blog.csdn.net/TRiddle/article/details/51919455#t12

这个题目好神! 赶紧Mark!
B2%_CMRK155VXE]OXMHHFT4

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

const int N = 100000+9;

int head[N],nxt[N],to[N],n,sz[N],dep[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 Add_Edge(int u, int v){
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w) {
	sz[w] = 1;
	for (int i=head[w];i;i=nxt[i]) 
		dep[to[i]] = dep[w] + 1, 
		DFS(to[i]), sz[w] += sz[to[i]];
}

int main(){
	n = read(); for (int i=2;i<=n;i++) Add_Edge(read(),i); DFS(1);
	for (int i=1;i<=n;i++) printf("%.1lf ",dep[i]+(n-dep[i]-sz[i])*0.5+1);
	return 0;
}

【Codeforces 696C】PLEASE

相关链接

题目传送门:http://codeforces.com/contest/696/problem/C
官方题解:http://codeforces.com/blog/entry/46031
中文题面:http://www.cnblogs.com/DarkTong/p/5674920.html

解题报告

用全概率公式可以推得\(p(i) = – \frac{{1 – p[i – 1]}}{2}\)
然后推一推通项公式可以得到\(p(i) = \frac{{{{( – 1)}^i} + {2^{i – 1}}}}{{3 \cdot {2^{i – 1}}}}\)
然后我们惊奇的发现\({{{( – 1)}^i} + {2^{i – 1}}}\)总可以被3整除
而\({{{( – 1)}^i} + {2^{i – 1}}}\)又是一个奇数,与2的整次幂肯定不能约分
于是搞一搞快速幂什么的就可以了

Code

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

const int MOD = 1000000007;
const int REV = 333333336;
const int N = 100000+9;

LL k,arr[N];

inline int pow(LL w, LL t) {
	int ret = 1; while (t) {
		if (t & 1) ret = (LL)ret*w % MOD;
		w = w*w % MOD; t >>= 1;
	} return ret;
}

inline LL read(){
	char c=getchar(); LL 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(){
	k = read(); int tag = 1;
	for (int i=1;i<=k;i++) tag = ((arr[i] = read()) == 1 && tag);
	if (tag) puts("0/1");
	else {
		LL numerator=REV,denominator=2; tag = -1;
		for (int i=1;i<=k;i++) if (arr[i]%2 == 0) tag = 1;
		for (int i=1;i<=k;i++) denominator = pow(denominator,arr[i]);
		(denominator *= pow(2LL,MOD-2LL)) %= MOD;
		(numerator *= denominator + tag) %= MOD;
		printf("%d/%d",(int)numerator,(int)denominator);
	}
	return 0;
}

【NOI六连测】[D3T1] 炉石

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版数据:http://paste.ubuntu.com/18386939/
数据传送门:http://pan.baidu.com/s/1i5fN2IT

首先,没玩过炉石的同学表示很受伤:考试的时候一直以为95颗星就算赢
其次,不会概率DP or 高斯消元的同学表示很受伤:因为要爆零啊!QAQ
好吧,高斯消元不会,所以来说一说lcr用的模拟吧:
设arr[i][j]表示走了k步后,位于当前有i颗星,已经连胜j场这个状态的概率
于是转移一下,再加上P>0.48保证了最多的步数就是1000多的样子
所以我们暴力转移1e5次的样子,基本上其他地方的DP值就为0了。
然后就是NOIP的模拟题水平的代码就可以了! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
哎,概率太弱不对,是完全不会
迟早是要找个时间好好学一学啊!

#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;
}