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

考试经过

开题一看：NOI模拟，人傻了 于是在不懈努力之下冲了四个暴力，预计30+20+30+20=100 实际：0+10+0+0=10 T1五分钟推出来dp结果没处理边界挂30 T2剪了半天枝结果没判无解挂成和puts("-1")一个分 T3十分钟冲上顺利爆零 T4最后一分钟看出来写假了然并卵 四个挂了三个，萎+=inf

T1. Skip

首先有一个比较简单的dp：设(f_i)表示他最后参加地(i)场比赛最优值，就有

如果不考虑只能选递增的限制的话应该是一个斜率优化菜鸡一下午才学会这是啥,变形

然后就是维护一个左下凸包，理论上直接单调队列就行 然而他对权值有限制，必须递增，大佬都用的cdq，太菜不会 一个被认为套路的东西：线段树维护凸包 对权值离散化，每个节点保存一个单调队列，存这个节点表示的区间里的斜率，每次在一条链都插入对应的(f_j-(frac{j^2+j}{2})),然后弹队尾，由于(i)单调，所以队头直接是最优决策，查询时在每个区间内查询即可，基本和线段树一样，单调队列一次操作均摊(O(1))，总复杂度(nLOG n) 由于stl的deque比较慢，所以似乎不是很快，但复杂度是正确的

#include <bITs/stdc++.h>
using namespace std;
#define int long long 
const int N=100050;
int f[N],a[N],w[N],lsh[N];
int sum1[N],sum2[N];
struct tree{
	int l,r;deque <pair<int,int> > q;
}tr[4*N];
void build(int id,int l,int r)
{	
	tr[id].l=l;tr[id].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(id*2,l,mid);build(id*2+1,mid+1,r);
}
inline double gan(pair<int,int> x,pair<int,int> y)
{
	return ((double)y.second-x.second)/((double)y.First-x.first);
}
void add(int id,int p,pair<int,int> v)
{
	while(tr[id].q.size()>=2&&gan(tr[id].q[tr[id].q.size()-2],tr[id].q[tr[id].q.size()-1])<gan(tr[id].q[tr[id].q.size()-1],v))tr[id].q.pop_back();
	tr[id].q.push_back(v);if(tr[id].l==tr[id].r)return;	
	int mid=(tr[id].l+tr[id].r)>>1;
	if(p<=mid)add(id*2,p,v);else add(id*2+1,p,v);
}
inline int get(int id,int l,int r,int i)
{
	if(l<=tr[id].l&amp;&r>=tr[id].r)
	{
		while(tr[id].q.size()>=2&&gan(tr[id].q[0],tr[id].q[1])>(-1.0)*i)tr[id].q.pop_front();
		if(!tr[id].q.size())return -1e9;
		return i*tr[id].q.front().first+tr[id].q.front().second;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)return get(id*2,l,r,i);
	if(l>;mid)return get(id*2+1,l,r,i);
	return max(get(id*2,l,mid,i),get(id*2+1,mid+1,r,i));
}
signed main()
{
	freoPEn("skip.in","r",stdin);
	freopen("skip.out","w",stdout);
	memset(f,128,sizeof(f));
	int n;cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(int i=1;i<=n;i++)lsh[i]=w[i];
	sort(lsh+1,lsh+n+1);
	int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
	a[0]=-1e9;a[n+1]=cnt+1;//w[n+1]=0;
	for(int i=1;i<=n+1;i++)sum1[i]=(i-i*i)/2,sum2[i]=(i*i+i)/2;
	build(1,0,cnt+1);add(1,0,make_pair(0,0));
	for(int i=1;i<=n+1;i++)
	{
		f[i]=get(1,0,a[i],i)+w[i]+sum1[i];
		add(1,a[i],make_pair(i,f[i]-sum2[i]));
	}
	cout<<f[n+1]<<endl;
	return 0;
}

代码粘过来似乎有点问题 记得特殊处理一下边界 貌似是第一道凸包题……

T2.String

不会，咕

T3. Permutation

大力推式子题，还没做 听说打表有一万分

T4.小P的生成树

其实是高考数学题。。。 结论是如果和的模最大的话，那么把和的方向的单位向量作为基底，按每个向量在他这个方向的投影长做一遍最大生成树就行 然而方向向量看似很多不可能全部枚举然而你只要卡到0.05弧度就A了 发现一个性质：最大生成树的形态只和边权相对大小有关系 因为每两个向量对一个向量投影，那么在半圈内大小相对关系都是不变的 于是预处理出所有这样的区间，每个区间之内所有向量投影相对大小不变，随便选一个作为方向向量做一遍，最后取最大值 复杂度(m^3log m)

#include <bits/stdc++.h>
using namespace std;
const int N=205;
const double exs=1e-10;
inline bool pd(double xx,double yy)
{
	if(xx>yy)swap(xx,yy);
	if(yy-xx<exs)return 1;
	return 0;
}
const double pie=acos(-1.0);
struct node{
	int From,to,next,wa,wb;
	double ww;
	friend bool operator<(node x,node y)
	{
		return x.ww<y.ww;
	}
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y,int wa,int wb)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].wa=wa;a[mm].wb=wb;
	a[mm].next=head[x];head[x]=mm++;
}
vector <double> du;int n,m;
PRiority_queue <node> q;
int fa[N];
inline int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
inline double gan()
{
	for(int i=1;i<mm;i+=2)q.push(a[i]);
	for(int i=1;i<=n;i++)fa[i]=i;
	int an1=0,an2=0;
	while(q.size())
	{
		int x=q.top().from,y=q.top().to;
		int wa=q.top().wa,wb=q.top().wb;q.pop();
		int fx=find(x),fy=find(y);
		if(fx==fy)continue;
		an1+=wa,an2+=wb;
		fa[fx]=fy;
	}
	return sqrt((double)an1*an1+(double)an2*an2);
}
signed main()
{
	freopen("mst.in","r",stdin);
	freopen("mst.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,wa,wb;scanf("%d%d%d%d",&x,&y,&wa,&wb);
		add(x,y,wa,wb);add(y,x,wa,wb);
	}
	for(int i=1;i<mm;i+=2)
	{
		int x=a[i].wa,y=a[i].wb;
		for(int j=i+2;j<mm;j+=2)
		{
			int xx=a[j].wa,yy=a[j].wb;
			if(y==yy)
			{
				du.push_back(0.5*pie);du.push_back(1.5*pie);
				continue;
			}
			double du1=atan((double)(x-xx)/(double)(yy-y));
			double du2=du1+pie;
			du.push_back(du1);du.push_back(du2);
		}
	}
	sort(du.begin(),du.end());
	double ans=-1e9;
	for(int i=0;i<du.size()-1;i++)
	{
		double p1=du[i],p2=du[i+1];
		double p=(p1+p2)/2.0;
		for(int j=1;j<mm;j++)
		{
			double wa=a[j].wa,wb=a[j].wb;
			a[j].ww=wa*cos(p)+wb*sin(p);
		}
		ans=max(ans,gan());
	}
	printf("%.6lf",ans);
	return 0;
}

考试总结

考了一个月终于垫底了 不细是最大的问题，挂分只能证明自己实力不济 把题读完，把代码打好，把暴力冲满 正解的话不能强求，但打表的分还是应该有 还发现一点，的确没有什么题不可做，感觉一直学不会的凸包整了一下午也就差不多了 接受，然后去改变. Accepted.

脚本宝典总结

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

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

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