脚本宝典收集整理的这篇文章主要介绍了[考试总结]noip模拟55，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

×××× (NOI) 模拟赛

看到题目的时候，以为自己药丸。。。

Skip

抱着 (NOI) 第一题的心态打开了这个题目。

看了 (5) 分钟之后。。。。

似乎不难唉，我似乎只要推出来一个不是很难的基础 (dp) ，然后 (max) 用树状数组优化一下似乎就 (Ac) 了。

然后推出基础 (dp) 方程：

然后注意所有都跳过的情况，然后就有很多分数。

然而只有 (30pts)，然后的数据范围就是 (10^5)，但是 (60%) 的数据保证随机。。。

这个有意义吗？？？答案是有的。

我们发现转移的时候取 (max) 是去找的，那么既然数据随机，那么基本转移都会从一个较近的地方转移过来。

那么我们就将 (j) 的枚举顺序从 (i-1) 开始到 (1)，然后发现 (i-j geq 3000),那么我们就 (break)。

之后就是 (60%)

然后考虑正解。

是一个上凸包

式子挺好推导的，我就不推了，结果就是：

记得一定是 (-i)，在推导的过程中会将 (k-j) 挪过来，然后记得变号。

之后我们使用 (cdq) 分治来去除大小的限制，然后双指针就搞定了。。。

%: PRagma GCC optimize(3)
#include<bITs/stdc++.h>
using std::cout; using std::endl;
#define int long long
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=Edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(a) FILE *FI = freoPEn(#a".in","r",stdin); FI = freopen(#a".out","w",stdout)
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &amp;operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io;static const int maxn = 1e6+10,inf = 1e9+7;const ll llinf = 1e18+7;
auto max = [](int x,int y) -> int{return x > y ? x : y;}; auto min = [](int x,int y) -> int{return x < y ? x : y;};
namespace xin
{
	#define fn(x) ((x) * (x))
	class xin_data
	{
		public:
			int x,y,val,f;
	}d[maxn];
	int n,ans[maxn];
	int deque[maxn];

	auto scale(int x,int y) -> double{return (double)(d[y].y - d[x].y) / (double)(d[y].x - d[x].x);};

	void cdq(int l,int r)
	{
		register int mid = l + r >> 1;
		if(l == r) return; cdq(l,mid);
		std::sort(d + l,d+mid+1,[](xin_data x,xin_data y) ->bool{return x.x < y.x;});
		std::sort(d+mid+1,d+r+1,[](xin_data x,xin_data y) ->bool{return x.x < y.x;});
		register int p = l,front = 0,back = 1;
		try(i,mid+1,r)
		{
			while(p <= mid and d[p].x < d[i].x)
			{
				while(front > back and scale(deque[front-1],deque[front]) <= scale(deque[front],p)) front --;
//				jb(scale(deque[front-1],deque[front]));
				deque[++ front] = p ++;
			}
//			cout<<p<<' '<<front<<endl;
			while(front > back and scale(deque[back],deque[back+1]) >= -d[i].x) back ++;
//			cout<<back<<' '<<front<<endl;
			if(back > front) continue;
			ans[d[i].x] = d[i].f = max(d[i].f,d[deque[back]].y + d[i].val - (fn(d[i].x) - d[i].x) / 2 + d[i].x * d[deque[back]].x);
//			cout<<ans[d[i].x]<<endl;
			d[i].y = d[i].f - d[i].x * (d[i].x + 1) / 2;
		}
		std::sort(d+mid+1,d+r+1,[](xin_data x,xin_data y) -> bool{return x.val == y.val ? x.x < y.x : x.val < y.val;});
		cdq(mid+1,r);
	}

	inline short main()
	{
		file(skip);	
		auto calc = [](int l,int r) -> int
		{
			if(r - l == 1) return 0;
			register int len = r - l - 1;
			return (1 + len) * len >> 1;
		};
		io >> n;
		memset(ans,128,sizeof(int) * (n + 1)); 
		try(i,1,n)
		{
			io >> d[i].val;
			d[i].x = i; ans[i] = d[i].f = d[i].val - i * (i - 1) / 2;
			d[i].y = d[i].f - (fn(d[i].x) + d[i].x) / 2;
		}
		std::sort(d+1,d+n+1,[](xin_data x,xin_data y) -> bool{return x.val == y.val ? x.x < y.x : x.val < y.val;});
//		try(i,1,n) cout<<d[i].x<<' '<<d[i].y<<' '<<d[i].val<<' '<<d[i].f<<endl;
		cdq(1,n);
//		try(i,1,n) sb(i),jb(ans[i]);
		int maxx = ans[n];
		try(i,1,n-1) maxx = max(maxx,ans[i] - (n - i) * (n - i + 1) / 2);
		cout<<;maxx<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

String

咕

Permutation

就是：

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define int long long
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	auto max = [](int x,int y) -> int{return x > y ? x : y;}; auto min = [](int x,int y) -> int{return x < y ? x : y;};
	#define file(a) FILE *FI = freopen(#a".in","r",stdin); FI = freopen(#a".out","w",stdout)
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io;static const int maxn = 1e6+10,inf = 1e9+7;const ll llinf = 1e18+7;
int n,m,k;
namespace shit
{
	const int mod = inf;
	int A[maxn][11],a[maxn],fac[maxn];
	int b[11],cnt = 0,zhi;
	void DFs(int ms)
	{
		if(zhi == ms)
		{
			++cnt;
			try(i,1,zhi) A[cnt][i] = a[i];
//			try(i,1,zhi) cout<<a[i]<<' '; cout<<endl;
			return ;
		}
		try(i,a[zhi]+1,n)
		{
			a[++zhi] = i;
			dfs(ms);
			zhi --;
		}
	}
	inline short main()
	{
		dfs(k);
		fac[0] = 1;
		try(i,1,n) fac[i] = fac[i-1] * i;
		int ans = 0;
		auto abs = [](int x) -> int{return x < 0 ? -x : x;};
		int tot = fac[n] / (fac[k] * (fac[n-k]));
		try(i,1,tot-1) (ans += abs(A[i][m] - A[i+1][m])) %= mod;
		cout<<ans<<endl;
		return 0;
	}
}
namespace xin
{
	const int mod = inf;
	int fac[maxn],inv[maxn],in[maxn];
	auto ksm(int x,int y,int ret = 1) -> int
	{
		while(y)
		{
			if(y & 1) ret = ret * x % mod;
			x = x * x % mod; y >>= 1;
		}
		return ret;
	};
	auto C = [](int n,int m) -> int
	{
		if(m < 0 or n < 0) return 0;
		if(n < m) return 0;
		return fac[n] * inv[m] % mod* inv[n-m] % mod;
	};
	inline short main()
	{	
		fac[0] = inv[0] = 1;
		try(i,1,n) fac[i] = fac[i-1] * 1ll * i % mod;
		inv[n] = ksm(fac[n],mod-2);
		throw(i,n-1,1) inv[i] = inv[i+1] * (i+1) % mod;
		
		n = n - k + m;k = m;

//		cout<<C(4,3)<<endl;
		int ans = 0;
		try(i,1,k) (ans += C(n-i,k-i+2)) %= mod;
		try(i,2,n) (ans += C(n-i-1,k-2) * (i - C(i-1,2) - 1 + mod) % mod) %= mod;
		cout<<ans<<endl;

		return 0;
	}
}
signed main()
{
	file(perm);
	io >> n >> k >> m;
	if(n <= 20) shit::main();
	else xin::main();
	return 0;
}

小P的生成树

这个东西发现并不能直接排序，那么我们呢所需要的就是这些东西正确大小关系。

如何正确起来呢？

就是我们发现在角度固定的时候那么模长也会固定。

那我们就可以开始枚举弧度，从 (0) 到 (2pi)，之后每次进行一次最打生成树。

然后答案就是每次算出来的最大值。。

然后这个做法速度是正解的 (1000) 倍。。。。。。

%: pragma GCC optimize(3)
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(a) FILE *FI = freopen(#a".in","r",stdin); FI = freopen(#a".out","w",stdout)
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io;static const int maxn = 1e6+10,inf = 1e9+7;const ll llinf = 1e18+7;
namespace xin
{
	const double pi = 3.14159265358979323846;
	class xin_data{public:int x,y,a,b;double pai;}d[maxn];
	int n,m,fa[maxn];
	inline int find(int x) {return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);}
	double ans = -inf * 1.0;
	inline short main()
	{
		file(mst);
		io >> n >> m;
		try(i,1,m) io >> d[i].x >> d[i].y >> d[i].a >> d[i].b;
		for(double deg = 0.0;deg <= pi * 2;deg += 0.06)
		{
			double si = std::sin(deg),co = std::cos(deg);
			try(i,1,n) fa[i] = i;
			try(i,1,m) d[i].pai = d[i].a * co + d[i].b * si;
			std::sort(d+1,d+m+1,[](xin_data x,xin_data y) -> bool{return x.pai > y.pai;});
			int jsq = 0,tota = 0,totb = 0;
			try(i,1,m)
			{
				register int fx = find(d[i].x),fy = find(d[i].y);
				if(fx == fy) continue;
				fa[fx] = fy; tota += d[i].a; totb += d[i].b;
				if(++jsq == n - 1) break;
			}
			ans = std::max(ans,std::sqrt(tota * tota + totb * totb));
		}
		printf("%.6lfn",ans);
		return 0;
	}
}
signed main() {return xin::main();}

脚本宝典总结

以上是脚本宝典为你收集整理的[考试总结]noip模拟55全部内容，希望文章能够帮你解决[考试总结]noip模拟55所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。