【题解】10-8提高组模拟

A.「物理」平抛运动

lnk

由于特性，这题的满分是$\bf 99$分（？）

// Problem:Luogu P4710 「物理」平抛运动

#include<bits/stdc++.h>
using namespace std;
const double g=10;
int main()
{
	double v,theta;
	cin>>v>>theta;
	double vy=v*cos(theta);
	double t=vy/g;
	double x0=v*sin(theta)*t;
	double y0=0.5*g*t*t;
	printf("%.5f %.5f",x0,y0);
	return 0;
}

B.跳舞的线 - 乱拐弯

lnk

// Problem:Luogu P5003 跳舞的线 - 乱拐弯

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int n,m;
char mp[MAXN][MAXN];
int dp1[MAXN][MAXN][2];//max
int dp2[MAXN][MAXN][2];//min
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='#')
			{
				dp1[i][j][0]=dp1[i][j][1]=-0x3f3f3f3f;
				dp2[i][j][0]=dp2[i][j][1]=0x3f3f3f3f;
			}
		}
	for(int i=2;i<=n;i++)
		dp1[i][0][0]=dp1[i][0][1]=-0x3f3f3f3f,
		dp2[i][0][0]=dp2[i][0][1]=0x3f3f3f3f;
	for(int i=2;i<=m;i++)
		dp1[0][i][0]=dp1[0][i][1]=-0x3f3f3f3f,
		dp2[0][i][0]=dp2[0][i][1]=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(i==1&&j==1)continue;
			if(mp[i][j]=='#')continue;
			dp1[i][j][0]=max(dp1[i][j-1][1]+1,dp1[i][j-1][0]);
			dp1[i][j][1]=max(dp1[i-1][j][0]+1,dp1[i-1][j][1]);
			dp2[i][j][0]=min(dp2[i][j-1][1]+1,dp2[i][j-1][0]);
			dp2[i][j][1]=min(dp2[i-1][j][0]+1,dp2[i-1][j][1]);
		}
	if(dp1[n][m][0]<=0&&dp1[n][m][1]<=0)puts("-1");
	else cout<<max(dp1[n][m][1],dp1[n][m][0])-1<<" "<<min(dp2[n][m][0],dp2[n][m][1]);
	return 0;
}

C.[BalticOI 2003]Gem 气垫车

lnk

// Problem:Luogu P4395 [BalticOI 2003] Gem 气垫车

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10010;
int n,dp[MAXN][20];
vector <int> g[MAXN];
void dfs(int u,int fa)
{
	for(int i=1;i<=15;i++)
		dp[u][i]=i;
	for(auto v:g[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		for(int i=1;i<=15;i++)
		{
			int minn=0x3f3f3f3f;
			for(int j=1;j<=15;j++)
				if(i!=j)
					minn=min(minn,dp[v][j]);
			dp[u][i]+=minn;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	int ans=0x3f3f3f3f;
	for(int i=1;i<=15;i++)
		ans=min(ans,dp[1][i]);
	cout<<ans;
}

D. [POI 2010] TES-Intelligence Test

lnk

// Problem:Luogu P3500 [POI 2010] TES-Intelligence Test

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,a[MAXN];
vector<int> pos[MAXN];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],pos[a[i]].push_back(i);
	int t;
	cin>>t;
	while(t--)
	{
		int m;
		cin>>m;
		if(m>n)
		{
			puts("NIE");
			continue;
		}
		bool flag=1;
		int lst=-1;
		for(int i=1;i<=m;i++)
		{
			int tmp;
			cin>>tmp;
			if(pos[tmp].empty())
			{
				flag=0;
				while(i++<m) cin>>tmp;
				break;
			}
			int l=0,r=pos[tmp].size()-1,find=-1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(pos[tmp][mid]>lst)
				{
					find=mid;
					r=mid-1;
				}
				else l=mid+1;
			}
			if(find==-1)flag=0;
			else lst=pos[tmp][find];
		}
		if(flag)puts("TAK");
		else puts("NIE");
	}
}