20161003 训练记录

tonyfang posted @ 2016年10月04日 20:20 in 随笔 with tags C++ OI , 714 阅读

1. 求$C_{n}^{k}~mod~10^{9}+7$的值。

$n \leq 200000, k < 2^{31}$

【题解】

暴力求逆元即可。

 

# include <stdio.h>

using namespace std;

typedef long long ll;
int n, k;
ll ans = 1;
const ll MOD = 1e9+7;

inline ll power(ll a, ll b) {
	ll s=1;
	while(b) {
		if(b&1) s=s*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return s;
}

int main() {
	freopen("video.in", "r", stdin);
	freopen("video.out", "w", stdout);
	
	scanf("%d%d", &n, &k);
	
	if(n<k) {
		puts("0");
		return 0;
	}
	
	for (int i=n-k+1; i<=n; ++i) ans = ans * i % MOD;
	for (int i=1; i<=k; ++i) ans = ans * power(i, MOD-2) % MOD;
	
	printf("%d\n", (int)ans);
	return 0;
}

2. 给出$n$个筐,第$i$个筐里有$R_i - L_i + 1$个球,上面的编号分别为$L_i, L_i+1, ..., R_i$。现在从每个筐里摸出一个球,问最后$n$个球中,编号首位是$1$的占$n$个球中的$k%$的概率。

$n \leq 2000, 0 < k < 100, 0 \leq Li, Ri \leq 10^{18}$

【题解】

先随便算出每个筐符合条件的概率设为$p_i$。

然后Dp,设$f_{i,j}表示前$i$个筐取出了$j$个符合条件的球的概率。

$f_{i,j} = f_{i-1,j-1} \times p_i + f_{i-1, j} \times (1-p_i)$,其中$f_{0,0}=1$。

最后答案就是$i$从$\frac{nk}{100}$上取整到$n$之内的所有$f_{n,i}$值之和。

 

# include <stdio.h>
# include <math.h>
using namespace std;

typedef unsigned long long ull;
typedef long double ld;
int n, k;
ld p[2010];
ld f[2010][2010];

int wl[20], wln=0, wr[20], wrn=0;

inline void get(int len, ull& begin, ull& end) {
	begin=1; end=0;
	for (int i=1; i<len; ++i) begin=begin*10;
	for (int i=1; i<len; ++i) end=end*10+9;
	end += begin;
}

inline void count(ull l, ull r, int pos) {
	wln=wrn=0;
	ull cnt=0, tl=l, tr=r, lb, le, rb, re;
	while(tl) {wl[++wln]=tl%10; tl/=10;}
	while(tr) {wr[++wrn]=tr%10; tr/=10;}
	for (int i=wln+1; i<=wrn-1; ++i) {
		ull tmp=1;
		for (int j=1; j<i; ++j) tmp=tmp*10;
		cnt+=tmp;
	}
	get(wln, lb, le);
	get(wrn, rb, re);
	if(wln == wrn) {
		if(lb <= l && l <= le && rb <= r && r <= re) {
			cnt += (r-l+1);
		} else if(lb <= l && l <= le) cnt += (le-l+1);	
	} else {
		if(lb <= l && l <= le) {
			cnt += (le-l+1);
		}
		if(rb <= r && r <= re) {
			cnt += (r-rb+1);
		} else {
			ull tmp=1;
			for (int j=1; j<wrn; ++j) tmp=tmp*10;
			cnt += tmp;
		}
	}
	p[pos]=(ld)cnt/(ld)(r-l+1);
}

int main() {
	freopen("chance.in", "r", stdin);
	freopen("chance.out", "w", stdout);
	ull tl, tr;
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; ++i) {
		scanf("%I64u%I64u", &tl, &tr);
		count(tl, tr, i);
	}
	f[0][0]=1;
	for (int i=1; i<=n; ++i) {
		for (int j=0; j<=i; ++j) {
			f[i][j] = f[i-1][j]*(1-p[i]);
			if(j!=0) f[i][j] = f[i][j] + f[i-1][j-1]*p[i];
		}
	}
	ld avl = ceil((ld)k/100*n);
	ld ans = 0;
	for (int i=avl; i<=n; ++i)
		ans=ans+f[n][i];
	printf("%.10lf\n", (double)ans);
	return 0;		
}

3. 给出一棵$n$个点的树,现在每个叶子节点向根连边,变成一张图。$q$组询问,每次询问$(u, v)$间的最短路径以及在最短路径的情况下,路径上经过的权值最大是多少。图有点权无边权。

$n \leq 100000, q \leq 200000$

【题解】

分类:①直接在树上走;②u到叶子到根到v;③v到叶子到根到u;④u到叶子到根到叶子到v

发现我们要求的只是$f_x$,表示$x$节点到离他最近的叶子节点的距离。

两边dp就求出来了,套个倍增LCA即可。

 

# include <stdio.h>
# include <vector>
# include <string.h>
# include <iostream>
# include <string>
typedef long long ll;
# define pli pair<ll,int>
# define MP make_pair
using namespace std;

const int N=100020, M=2000010;
int n, q;
int tot=0, head[N], next[M], to[M], w[N];
int fa[N][20], g[N][20], dep[N];
ll h[N][20];
pli f[N];
int sz[N];

inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fat) {
	dep[x]=dep[fat]+1;
	fa[x][0] = fat;
	g[x][0] = w[x];
	h[x][0] = w[x];
	for (int i=1; i<=19; ++i) fa[x][i] = fa[fa[x][i-1]][i-1];
	for (int i=1; i<=19; ++i) g[x][i] = max(g[x][i-1], g[fa[x][i-1]][i-1]);
	for (int i=1; i<=19; ++i) h[x][i] = h[x][i-1]+h[fa[x][i-1]][i-1];
	for (int i=head[x];i;i=next[i]) {
		if(to[i] == fat) continue;
		dfs(to[i], x);
	}
}

inline pli lca(int u, int v) {
	int mx = 0; ll dis=0;
	if(dep[u]<dep[v]) swap(u, v);
	for (int i=19; i>=0; --i) 
		if(dep[u]>dep[v] && ((dep[u]-dep[v])&(1<<i)))
			mx=max(mx, g[u][i]), dis = dis + h[u][i], u = fa[u][i];
	if(u==v) return MP(dis+w[u], max(mx, w[u]));
	for (int i=19; i>=0; --i) {
		if(fa[u][i] != fa[v][i]) {
			mx = max(mx, g[u][i]);
			mx = max(mx, g[v][i]);
			dis = dis + h[u][i] + h[v][i];
			u = fa[u][i], v = fa[v][i];
		}
	}
	mx = max(mx, w[u]);
	mx = max(mx, w[v]);
	dis = dis + w[u] + w[v];
	if(fa[u][0] != v && fa[v][0] != u) dis = dis + w[fa[u][0]], mx = max(mx, w[fa[u][0]]);
	return MP(dis, mx);
}

inline void dp(int x, int fa) {
	sz[x] = 0;
	f[x].first = 1000000010000000ll;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dp(to[i], x);
		if(f[to[i]].first+w[x] < f[x].first || (f[to[i]].first+w[x] == f[x].first && max(f[to[i]].second, w[x]) > f[x].second))
			f[x] = MP(f[to[i]].first+w[x], max(f[to[i]].second, w[x]));
		++sz[x];
	}
	if(sz[x] == 0) f[x] = MP(w[x], w[x]);
}

inline void dp2(int x, int fa) {
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		if(f[to[i]].first > f[x].first + w[to[i]] || (f[x].first+w[to[i]] == f[to[i]].first && max(f[x].second, w[to[i]]) > f[to[i]].second)) 
			f[to[i]] = MP(f[x].first+w[to[i]], max(f[x].second, w[to[i]]));
		dp2(to[i], x);	
	}
}

inline void out(string s, pli a) {
	cout << s << " = " << a.first << " " << a.second << endl;
}

int main() {
	freopen("plutotree.in", "r", stdin);
	freopen("plutotree.out", "w", stdout);
	scanf("%d%d", &n, &q);
	for (int i=2, t; i<=n; ++i) {
		scanf("%d", &t);
		add(t, i);
		add(i, t);
	}
	for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
	dfs(1, 0);
	dp(1, 0);
	dp2(1, 0);
	//for (int i=1; i<=n; ++i) printf("%d %d\n", f[i].first, f[i].second);
	while(q--) {
		int u, v;
		scanf("%d%d", &u, &v);	
		// ====== 1. LCA ====== //
		pli ans1 = lca(u, v);
		//out("ans1", ans1);
		// ====== 2. down - root - v ====== //
		pli ans2t1 = lca(1, v);
		pli ans2t2 = f[u];
		//out("ans2t1", ans2t1);
		//out("ans2t2", ans2t2);
		pli ans2 = MP(ans2t1.first+ans2t2.first, max(ans2t1.second, ans2t2.second));
		//out("ans2", ans2);
		// ====== 3. down - root - u ====== //
		pli ans3t1 = lca(1, u);
		pli ans3t2 = f[v];
		//out("ans2t1", ans3t1);
		//out("ans2t2", ans3t2);
		pli ans3 = MP(ans3t1.first+ans3t2.first, max(ans3t1.second, ans3t2.second));
		//out("ans3", ans3);
		// ====== 4. down - root - up - v ===== //
		pli ans4t1 = f[v];
		pli ans4t2 = f[u];
		pli ans4 = MP(ans4t1.first+ans4t2.first+w[1], max(max(ans4t1.second, ans4t2.second), w[1]));
		//out("ans4", ans4);
		if(ans2.first < ans1.first || (ans2.first == ans1.first && ans2.second > ans1.second)) ans1 = ans2;
		if(ans3.first < ans1.first || (ans3.first == ans1.first && ans3.second > ans1.second)) ans1 = ans3;
		if(ans4.first < ans1.first || (ans4.first == ans1.first && ans4.second > ans1.second)) ans1 = ans4;
		printf("%I64d %d\n", ans1.first, ans1.second);
	}
	return 0;
}
uburt.in 说:
2023年4月20日 19:42

Following verification, you must give a copy of your Aadhar card that has been self-attested.You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, uburt.in when creating an account on any KRA's eKYC site. Following verification, you must give a copy of your Aadhar card that has been self-attested. You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, when creating an account on any KRA's eKYC site.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter