首页 > 其他 > 详细

noip模拟55(待补)

时间:2021-09-24 02:30:23      阅读:9      评论:0      收藏:0      [点我收藏+]

A. Skip

斜率一窍不通,先咕着.

B. String

改不出来,先咕着.

C. Permutation

数学题,找规律推式子.

C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define lf double
	#define ull unsigned ll
	#define mp make_pair
	#define lb lower_bound 
	#define ub upper_bound 
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read(){
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e6+21,mod=1e9+7;

ll m,n,s,ans;
ll frc[N];
inline ll ksm(ll a,ll b,ll c){
	a%=c; ll res=1;
	while(b){
		if(b&1) res=(res*a)%c;
		a=(a*a)%c,b>>=1;
	}
	return res%c;
}
inline ll C(ll a,ll b){
	if(a>b) return 0;
	return frc[b]*ksm(frc[a]*frc[b-a],mod-2,mod)%mod;
}
signed main(){
	FILE(perm);
	n=read(),s=read();
	if((m=read())==1) printf("%lld\n",n-s+m-1),exit(0);
	frc[0]=1,n-=s-m,s=m;
	for(ll i=1;i<=1e6;i++) frc[i]=frc[i-1]*i%mod;
	for(ll i=2;i<=s;i++) ans=(ans+C(s-i+2,n-i))%mod;
	for(ll i=2;i<=n;i++) ans=(ans+C(s-2,n-i-1)*(i-1)%mod)%mod;
	printf("%lld\n",ans%mod),exit(0);
}

D. 小P的生成树

其实比较暴力的思想就是枚举 \(0\) ~ \(2*\pi\) 每个弧度,

然后把所有向量都投影到上面.

然而这样可以 \(A\)..

每次枚举\(0.0001\),可以过..

改成每次枚举\(0.06\),依旧可以过,复杂度变成\(O(100*mlogn)\),快的飞起..

正解的话就是把每个能使任意两个向量的相对大小都改变一下,

其实就是把所有情况都枚举了一遍.

因为最值生成树只关心相对大小.

另外,还可以维护凸包.

D_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define lf double
	#define ull unsigned ll
	#define mp make_pair
	#define lb lower_bound 
	#define ub upper_bound 
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read(){
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=209;
const lf pi=acos(-1.0);

lf now,ans;
lf horn[N*N*N];

ll m,n,cnt;
ll fa[N];
struct I { ll u,v,x,y; lf w,h; } e[N];
ll find(ll x){ return x==fa[x] ? x : fa[x]=find(fa[x]); } 
inline bool comp(I i,I j){ return i.w>j.w; } 
inline void Kruscal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		e[i].w=e[i].x*cos(now)+e[i].y*sin(now);
	}
	sort(e+1,e+1+m,comp); ll u,v,R=0,I=0;
	for(int i=1;i<=m;i++){
		u=e[i].u,v=e[i].v;
		if(find(u)==find(v)) continue ;
		R+=e[i].x,I+=e[i].y,fa[find(v)]=find(u);
	}
//	cout<<R<<‘ ‘<<I<<endl;
	ans=max(ans,sqrt(1.0*R*R+1.0*I*I));
}
signed main(){
	FILE(mst);
	n=read(),m=read(); ll u,v; lf x,y;
	for(int i=1;i<=m;i++){
		e[i].u=read(),e[i].v=read(),e[i].x=read(),e[i].y=read();
		e[i].h=1.0*e[i].y/e[i].x; // tan
	}
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			x=atan(e[i].h),y=atan(e[j].h);
			if(e[i].y==e[j].y){ 
				horn[++cnt]=atan(pi/2.0),horn[++cnt]=atan(pi*3.0/2.0);
			}
			else{
				horn[++cnt]=atan(1.0*(e[i].x-e[j].x)/(e[j].y-e[i].y));
				horn[++cnt]=atan(1.0*(e[i].x-e[j].x)/(e[j].y-e[i].y))+pi;
			}
		}
	}
	sort(horn+1,horn+1+cnt),cnt=unique(horn+1,horn+1+cnt)-horn-1;
	horn[cnt+1]=horn[1];
	for(int i=1;i<=cnt;i++){
		now=(horn[i]+horn[i+1])/2.0;
		Kruscal();
		now=(horn[i]+horn[i+1])/2.0+pi;
		Kruscal();
	}
	printf("%.6lf\n",ans),exit(0);
}

noip模拟55(待补)

原文:https://www.cnblogs.com/AaMuXiiiiii/p/15306998.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!