conclusion_and_proof_in_number_theory
Download:http://oi.cyo.ng/wp-content/uploads/2018/02/conclusion_and_proof_in_number_theory.pdf
Tag: 数论
【POJ 1737】Connected Graph
题目传送门:http://poj.org/problem?id=1737
中文题面:《算法竞赛·入门经典·训练指南》P112
设f(n)为连通图个数,g(n)为不联通的个数,h(n)为总方案数
首先h(n)可以直接算:\(h(n) = {2^{\frac{{n(n – 1)}}{{\rm{2}}}}}\)
又f(n)+g(n)=h(n),所以我们只需要求解g(n)即可
考虑1所在的联通块,假设有i个点,则这部分的方案数就是f(i)
又考虑剩余点对于答案的贡献,因为不一定联通,所以为h(n-i)
所以\(g(n) = \sum\limits_{i = 1}^{n – 1} {f(i) \cdot h(n – i)} \)
于是f(n)用h(n)-g(n)就可以辣!
因为原题要上高精度
所以代码什么的还是算了吧?
_(:з」∠)_
【NOI五连测】[D2T1] 啊
题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1712
这一道题,我一眼看到的时候,也是“啊”的。博弈论?不会啊QAQ
最后只能打了暴力,结果还打错了QAQ
来说一说正解。
我们定义三种节点:
1.无名必胜
2.有名必胜
3.先手必胜
再来讨论一下这三种节点间的关系:
假如一个节点的儿子中,1、2两种类型的节点一样多,则为类型3
否则,1、2哪种多,该节点就是那种节点
于是搞一个树形DP,就可以搞出根节点的类型
显然,如果是类型3,则无解
如果是类型2,则只有部分节点可选
如果是类型1,则全部的叶子结点都可选
另外,本题还要注意,因为非叶子结点的颜色,最终会取决于它儿子节点的颜色
所以,第一步走的节点,一定是叶子结点,否则,并没有什么卵用QAQ
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 100000+9; int n,vout,que[MAXN],type[MAXN],num[MAXN][3]; vector<int> G[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline void init(){ n = read(); for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0; for (int i=1;i<=n;i++) G[read()].push_back(i); for (int i=1;i<=n;i++) type[i] = read() + 1; int fro,bak; que[fro=bak=1] = 1; while (fro < n) { int w = que[bak++]; for (int i=0;i<(int)G[w].size();i++) que[++fro] = G[w][i]; } } void GetAns(int w){ if ((int)G[w].size() == 0) { if (type[w] == 0) que[++vout] = w; } else { int t = num[w][2] - num[w][1]; if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++) GetAns(G[w][i]); } } int main(){ freopen("ah.in","r",stdin); freopen("ah.out","w",stdout); int T; cin>>T; while (T--) { init(); for (int k=n,i=que[k];k;i=que[--k]){ if ((int)G[i].size() == 0) continue; else { for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++; if (num[i][2] == num[i][1]) type[i] = 0; else if (num[i][1] > num[i][2]) type[i] = 1; else type[i] = 2; } } if (type[1] == 1) { int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i; printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl; } else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;} else printf("-1\n"); } return 0; }
【NOI六连测】[D1T2] 过河
题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18247944/
数据传送门:http://pan.baidu.com/s/1nvGnd8H
这个题目,第一眼看到的时候,一脸懵逼
后来仔细想了一想,成了二脸懵逼QAQ
于是写了30分的暴力,还好没写挂……
后来听题解,感觉很神
首先是结论:最优解时,所有的F(Xy)的斜率相等
这个按照原教的说法:
如果斜率不等,那么将斜率较低的河流的时间分一点给斜率较高的河流
我们就可以走得更远!
还是比较显然的吧!但是像我这种沙茶在考试的时候肯定想不出来QAQ
接下来就是怎么让斜率一样了。
原教又给了一个非常神的办法:
根据F’(Xy)的表达式可以得到,t随F’(Xy)的增加而减少,所以我们可以二分统一的斜率,然后判一判时间知否足够。
详细的推导如下:
\(
\begin{array}{l}
\partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\
= {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}
\end{array}
\)
不妨设\(k = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}\)
则有\(\begin{array}{l}
{u^4} \cdot {t^2} = {(k – {V_i})^2} \cdot ({u^2} \cdot {t^2} – W_i^2)\\
{t^2} \cdot ({u^4} – {(k – {V_i})^2} \cdot {u^2}) = – {(k – {V_i})^2} \cdot W_i^2\\
t = \sqrt {\frac{{{{(k – {V_i})}^2} \cdot W_i^2}}{{{{(k – {V_i})}^2} \cdot {u^2} – {u^4}}}}
\end{array}\)
所以t随k的增大而减小,且\(k \in (\max ({V_i}) + u, + \infty ]\)
之后代码就没有什么难度啦!
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #define LD long double using namespace std; const int MAXN = 50+9; const LD EPS = 1e-15; int n; LD v[MAXN],w[MAXN],ans[MAXN]; LD disx,MXv,u,t; inline LD cal(LD k){ LD ret = 0; for (int i=1;i<=n;i++){ LD r = (k-v[i])*(k-v[i]); LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u)); ans[i] = t; ret += t; } return ret; } inline double GetAns(){ LD ret = 0; for (int i=1;i<=n;i++){ LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]); ret += tmp+v[i]*ans[i]; } return (double)sqrt(ret*ret+disx*disx); } int main(){ freopen("river.in","r",stdin); freopen("river.out","w",stdout); scanf("%d",&n); cin>>u>>t; for (int i=1;i<=n;i++) cin>>w[i]>>v[i], disx+=w[i], MXv=max(MXv,v[i]); if (disx/u > t) {printf("-1\n");exit(0);} LD l=u+MXv,r=1e12,mid; while (r-l > EPS){ mid = (l+r)/2.0; if (cal(mid) < t) r = mid; else l = mid; } printf("%.3lf\n",GetAns()); for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]); return 0; }
另外,此题卡精度QAQ,long double的EPS都得开到1e-15