Tag: 数论

【POJ 1737】Connected Graph

Qizy 2 Comments

题目传送门：http://poj.org/problem?id=1737
中文题面：《算法竞赛·入门经典·训练指南》P112

想一想，貌似直接容斥之类的都上不了
于是就不会做了 QAQ
mvr5zj9l7yp

设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] 啊

Qizy Leave a comment

题目传送门：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] 过河

Qizy 22 Comments

题目传送门：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