×××× \(NOI\) 模拟赛

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

Skip

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

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

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

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

\[f_i = \max_{j=1}^{i-1} (f_j - calc(i,j)) + a_i\\ Ans = \max_{i=1}^{n}(f_i - calc(i,n+1)) \]

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

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

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

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

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

之后就是 \(60\%\)

然后考虑正解。

是一个上凸包

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

\[\frac{(f_j-\frac{j^2+j}{2})-(f_k-\frac{k^2-k}{2})}{j-k}>-i \]

记得一定是 \(-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 &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

就是：

\[\sum_{i=1}^{k}\dbinom{n-i}{k-i+2} + \sum_{i-2}^{n}(i-\dbinom{i-1}{2}-1)\dbinom{n-i-1}{k-2} \]

#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\) 到 \(2\pi\)，之后每次进行一次最打生成树。

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

然后这个做法速度是正解的 \(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("%.6lf\n",ans);
		return 0;
	}
}
signed main() {return xin::main();}