5.27 NOI 模拟

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

\(T1\)约定

比较水的\(dp\)题

上午想到了用区间\(dp\)求解,复杂度\(O(n^5),\)貌似没开\(long\ long\)就爆掉了

正解还是比较好想的,直接枚举从何时互不影响然后转移即可,复杂度\(O(n^3)\)

#include<bits/stdc++.h>

#define int long long

#define MAXN 405

using namespace std;

int ord[MAXN][MAXN],dp[MAXN][MAXN],l[MAXN][MAXN],r[MAXN][MAXN],a[MAXN],n;

int Dis(int x,int y)

{

	if(x>y) swap(x,y);

	return a[y]-a[x];

}

int Val(int x,int y)

{

	return Dis(x,y)*floor(sqrt(Dis(x,y)));

}

signed main()

{

	scanf("%lld",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;i++)

	{

		vector<pair<int,int> >tmp;

		for(int j=1;j<=n;j++)

		{

			tmp.push_back(make_pair(Val(i,j),j));

		}

		sort(tmp.begin(),tmp.end());

		for(int j=0;j<n;j++)

		{

			ord[i][j]=tmp[j].second;

		}

	}

	memset(l,0x3f,sizeof(l));

	memset(r,0x3f,sizeof(r));

	memset(dp,0x3f,sizeof(dp));

	for(int i=0;i<=n;i++)

	{

		l[1][i]=r[n][i]=0;//l,r表示poz走到1,n的代价

	}

	for(int i=2;i<=n;i++)

	{

		for(int j=1;j<n;j++)

		{

			for(int ls=1;ls<i;ls++)

			{

				l[i][j]=min(l[i][j],l[ls][j-1]+Val(i,ls));

			}

		}

	}

	for(int i=n-1;i>=1;i--)

	{

		for(int j=1;j<n;j++)

		{

			for(int ls=i+1;ls<=n;ls++)

			{

				r[i][j]=min(r[i][j],r[ls][j-1]+Val(i,ls));

			}

		}

	}

	for(int i=1;i<n;i++)

	{

		for(int st=1;st<=n;st++)

		{

			int L=st,R=st;

			for(int nxt=1;nxt<n;nxt++)

			{

				int now=ord[st][nxt];

				L=min(L,now); R=max(R,now);

				dp[st][i]=min(dp[st][i],Val(st,now)+l[L][i-1]+r[R][i-1]);

				dp[st][i]=min(dp[st][i],Val(st,now)+dp[now][i-1]);

			}

		}

	}

	for(int st=1;st<=n;st++)

	{

		for(int i=1;i<n;i++)

		{

		    cout<<dp[st][i]<<" ";

		}

		cout<<"\n";

	}

}

\(T2\ because\)

首先\(sto\)谭哥\(orz\)

运用高中物理知识

我们设我们直线向量为\(Base=(x_1,x_2,x_3...)\)

我们要求的式子是

\(\sum |vec_i|^2-(vec_i*Base)^2\)

\(=\sum |vec_i|^2-\sum (vec_i*Base)^2\)

最后的形式大概是一个高维函数的形式,我们每次随机一个初始点,我们对这个位置\(Seek\ partial\ derivatives\),采用\(Gradient\ descent\ method\)进行\(1000\)次\(iterate\)即可保证精度误低于\(1\times 10^{-9}\)

//sto 梯度下降+偏导 tql

#include<bits/stdc++.h>

#define MAXN 1005

#define MAXT 1000

#define MAXD 10

using namespace std;

int n,d,st[MAXN][MAXD];

double poi[MAXD],Mid2[MAXD],Mid1[MAXD],vec_x[MAXN];

int main(){

    scanf("%d%d",&n,&d);

    for(int i=1;i<=n;i++)

	{

		for(int j=0;j<d;j++)

		{

			scanf("%d",&st[i][j]);//输入每个向量

		}

	}

	default_random_engine e(time(0));

	uniform_real_distribution<double> u(-1,1);

    for(int i=0;i<d;i++)

	{

		poi[i]=u(e);

	}

    double T=1.0;

    for(int t=0;t<MAXT;t++)

	{

		memset(vec_x,0,sizeof(vec_x));

        for(int i=1;i<=n;i++)

		{

            for(int j=0;j<d;j++)

			{

				vec_x[i]+=poi[j]*st[i][j];

				//计算每个与直线向量的点乘

			}

        }

        for(int i=0;i<d;i++)

		{

            double res1=0,res2=0;

            //枚举维度

            for(int j=1;j<=n;j++)//枚举向量

			{

				//在一个维度上的导,把其他维度看成常数,对这个维度求导

				//这个维度的偏导,发现把平方拆一下就是这个式子了

                res1+=2*st[j][i]*vec_x[j];

                res2+=vec_x[j]*vec_x[j];

            }

            Mid2[i]=res1+res2*2*poi[i];//这个就是每个维度的在这个位置的偏导

        }

        for(int i=0;i<d;i++)

		{

		   Mid1[i]=0.1*Mid1[i]+T*Mid2[i];

		   //这个就是那个nb的梯度下降法,移动的位置就是

		   //在原来的基础上在加一点

		}

        for(int i=0;i<d;i++)

		{

			poi[i]+=Mid1[i];

			//移动

		}

        double res=0;

        for(int i=0;i<d;i++)

        {

        	res+=poi[i]*poi[i];

        	//相量长度

		}

        res=sqrt(res);

        for(int i=0;i<d;i++)

		{

			poi[i]/=res;

			//变成单位向量

		}

        T*=0.987654321;

    }

    double res=0;

    for(int i=1;i<=n;i++)

	{

		for(int j=0;j<d;j++)

		{

			res+=st[i][j]*st[i][j];

			//式子的第一部分

		}

	}

    for(int i=1;i<=n;i++)

	{

        double vec_x=0;

        for(int j=0;j<d;j++)

		{

	    	vec_x+=st[i][j]*poi[j];

			//式子的第二部分

		}

        res-=vec_x*vec_x;

    }

    printf("%.10f\n",res);

}