B.Race to 1 UVA 11762
第一次接触概率dp,完全没想到是dp...没想到能递推出来0 0
首先需要知道 总的期望=每件事的期望×每件事发生的概率
然后可以根据这个来写递推公式,也是dp?
假设不小于x的质数有m个,x的质因子有n个(种 更确切),那么在求X的期望时,可以考虑由他能转移过去的状态转移,X,X/pi p是x的质因子
所以不难得出E(x) = 1+(m-n)/mE(X)+1/msigmaE(X/pi) 注意会加1,因为X转移到后面的情况,就多了一步
//Updated: 每个case跑完了,f数组不用memset...会快10倍!uva数据的情况下
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int maxn = 1000000+50; const double eps = 1e-10; int T, N, tot; int prime[maxn]; double f[maxn]; bool flag[maxn], done[maxn]; void getPrime() { for(int i = 2; i < maxn; i++) { if(!flag[i]) prime[tot++] = i; for(int j = 0; j < tot && prime[j]*i < maxn; j++) { flag[i*prime[j]] = true; if(i % prime[j] == 0) break; } } } double dp(int x) { if(done[x]) return f[x]; done[x] = true; int n, m; n = m = 0; for(int i = 0; i < tot && prime[i] <= x; i++) { n++; if(x % prime[i] == 0) { m++; f[x] += dp(x/prime[i]); } } // if(x == N) cout << n << ' ' << m << endl; return f[x] = (f[x]+n)/m; } int main() { #ifdef LOCAL freopen("B.in", "r", stdin); #endif getPrime(); scanf("%d", &T); for(int t = 1; t <= T; t++) { scanf("%d", &N); memset(done, 0, sizeof(done)); memset(f, 0, sizeof(f)); f[1] = 0.0; done[1] = true; dp(N); printf("Case %d: %.10lf ", t, f[N]); } return 0; }
D.Jumping Mario UVA 11764
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; int T, n, now, high, low; int main() { cin >> T; for(int t = 1; t <= T; t++) { high = 0; low = 0; cin >> n; for(int i = 0; i < n; i++) { int x; cin >> x; if(i == 0) { now = x; continue; } if(x > now) high++; else if(x < now) low++; now = x; } cout << "Case " << t << ": " << high << ' ' << low << endl; } return 0; }
J.Lighting Away UVA 11770
第一反应的确是强连通分量...缩点...但是我不太熟...所以就去yydfs的方法,可是智商不够用...最后没调试出来
正解就是缩点染色判断新的图入读为0的点
调试了很久很久...各种小错误都发现了,最后倒在了出栈忘记加大括号了...
#include <iostream> #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> using namespace std; const int maxn = 100000+50; int T, n, m, idx, tot, cnt; int head[maxn], next[maxn], edge[maxn], dfn[maxn], low[maxn], in[maxn], type[maxn]; bool instack[maxn], visit[maxn]; stack<int> st; void add(int u, int v) { edge[tot] = v; next[tot] = head[u]; head[u] = tot++; } void tarjan(int u) { dfn[u] = low[u] = ++idx; st.push(u); instack[u] = true; visit[u] = true; for(int e = head[u]; e != -1; e = next[e]) { int v = edge[e]; if(!visit[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if(instack[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { cnt++; while(!st.empty()) { int now=st.top(); st.pop(); instack[now]=0; type[now]=cnt; if(now == u) break; } } } int main() { #ifdef LOCAL freopen("J.in", "r", stdin); #endif scanf("%d", &T); for(int t = 1; t <= T; t++) { scanf("%d%d", &n, &m); memset(next, -1, sizeof(next)); memset(head, -1, sizeof(head)); memset(in, 0, sizeof(in)); memset(instack, 0, sizeof(instack)); memset(visit, 0, sizeof(visit)); tot = 0; idx = 0; cnt = 0; for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); } // for(int i = 1; i <= n; i++) // if(!visit[i] && in[i] == 0) tarjan(i); for(int i = 1; i <= n; i++) if(!visit[i]) tarjan(i); int ans = 0; for(int i = 1; i <= n; i++) for(int e = head[i]; e != -1; e = next[e]) { if (type[i] != type[edge[e]]) in[type[edge[e]]]++; } for (int i = 1;i <= cnt;i++) if (in[i] == 0) ans++; // for(int i = 1; i <= n; i++) // if(in[i] == 0) cnt++; printf("Case %d: %d ", t, ans); } return 0; }
这场比赛做的时候只出了道水题...然后J和B是真的实力不够...J就是后来搞也有很多迷糊的地方,现在算是搞懂了