zkx06111's Blog

//很容易想到要二分，因此关键是求x^x的位数
//x^x的位数=log10(x^x)+1=x*log10(x)+1
#include <iostream>
#include <cmath>
using namespace std;

int main(){
	long long n,l=1,r=2000000000,m;
	cin>>n;
	while (l!=r){
		m=(l+r)>>1;
		long long t=m*log10(m)+1;
		if (t>=n)
			r=m;
		else
			l=m+1;
	}
	cout<<l;
	return 0;
}

//总结：细节决定成败。
//判断是否输出-1的部分break,continue细节弄错错了好久
//大致思路：对于每个岛，x正负sqrt(d^2-y^2)的线段上的点都可以包含
//所以就是对于n条线段进行区间取点问题。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define sqr(x) (x)*(x)
using namespace std;

struct Point{
	double x;
	double y;
}p[1000];

bool cmp(Point a,Point b){
	if (a.y!=b.y) return a.y<b.y;
	return a.x>b.x;
}

int main()
{
	int c=0,n,d;
	while (cin>>n>>d){
		if (n==0 && d==0) break;
    bool flag=false;
		for (int i=0;i<n;++i){
			cin>>p[i].x>>p[i].y;
			if (!flag && p[i].y>d){
				cout<<"Case "<<(++c)<<": -1\n";
        flag=true;
			}
			double t=sqrt(sqr(d)-sqr(p[i].y));
			p[i].y=p[i].x;
			p[i].x-=t; p[i].y+=t;
		}
    if (flag) continue;

		sort(p,p+n,cmp);
		int ans=1;
		double cur=p[0].y;
		for (int i=1;i<n;++i)
			if (cur<p[i].x){
				cur=p[i].y; ++ans;
			}
		cout<<"Case "<<(++c)<<": "<<ans<<endl;
	}
	return 0;
}

//使用prim算法即可
#include <iostream>
#include <climits>
using namespace std;

int n,a[101][101],f[101],pre[101],s[101],t[101];
bool b[101];
int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j) {
			cin>>a[i][j];
			a[j][i]=a[i][j];
		}
	for (int i=1;i<=n;++i) f[i]=INT_MAX/3;
	f[1]=0; int cnt=n,ans=0,m=0;
	while (cnt--) {
		int p,v=INT_MAX/3;
		for (int i=1;i<=n;++i)
			if (f[i]<v && !b[i]) {
				p=i;
				v=f[i];
			}
		ans+=v; f[p]=0; b[p]=1;
		if (v!=0 && p!=1) { //如果是非0边，则记录下来
			++m;
			s[m]=pre[p];
			t[m]=p;
		}
		for (int i=1;i<=n;++i)
			if (f[p]+a[p][i]<f[i]) {
				f[i]=f[p]+a[p][i];
				pre[i]=p; //更新pre[i]
			}
	}
	cout<<m<<endl;
	for (int i=1;i<=m;++i)
		if (s[i]<t[i]) cout<<s[i]<<' '<<t[i]<<endl;
		else cout<<t[i]<<' '<<s[i]<<endl;
	cout<<ans;
	return 0;
}