模拟55 考试总结

2023-11-17 20:51:04

考试经过

开题一看：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\)场比赛最优值，就有

\[f_i=\max(f_j+w_i-\dbinom{i-j}{2})[0<=j<i] \]

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

\[f_j-(\frac{j^2+j}{2})=-ij+f_i-\frac{i-i^2}{2} \]

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

码农公寓