首页 > 代码库 > UESTC 2014 Summer Training #10 Div.2
UESTC 2014 Summer Training #10 Div.2
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\n", 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\n", t, ans); } return 0;}
这场比赛做的时候只出了道水题...然后J和B是真的实力不够...J就是后来搞也有很多迷糊的地方,现在算是搞懂了
UESTC 2014 Summer Training #10 Div.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。