NOIP提高组 2018 D2
T1 奶酪
【思路】
将每一个球建立一个节点,用并查集连接两个相连的球,并找出与上下面相交或相切的节点,最后判断是否有2个节点的祖先相同。
注意,1<=abs(h),abs(r)<=1,000,000,000,应该开long long。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int t,n,h,tot_up,tot_down;
long long r,d;
long long x[MAXN],y[MAXN],z[MAXN];
int f[MAXN],up[MAXN],down[MAXN];
inline long long read()
{
long long X=0; bool flag=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag==0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
void make_set()
{
for(int i=1;i<=n;i++)
f[i]=i;
}
int find(int X)
{
return X==f[X] ? X : f[X]=find(f[X]);
}
void meger(int X,int Y)
{
f[find(X)]=find(Y);
}
bool check(int i,int j)
{
return d*d >= (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
}
void readdata()
{
tot_down=0; tot_up=0;
scanf("%d%d%d",&n,&h,&r);
make_set();
d=r<<1;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
if(z[i]-r<=0) down[++tot_down]=i;
if(z[i]+r>=h) up[++tot_up]=i;
for(int j=1;j<=i;j++)
if(check(i,j)) meger(i,j);
}
}
void work()
{
for(int i=1;i<=tot_down;i++)
for(int j=1;j<=tot_up;j++)
if(find(down[i])==find(up[j]))
{
printf("Yes\n");
return;
}
printf("No\n");
}
int main()
{
t=read();
while(t--)
{
readdata();
work();
}
return 0;
}
T2 宝藏
【思路】
树形DP。邻接矩阵存图,用dis[u][v]表示u到v的最短距离。用f[i][j][s]表示从i出发到状态s,且当前深度为j时的最小代价。用dep表示当前深度,用u表示当前节点,v表示目标节点,s表示当前状态,t表示目标状态,那么显然有
f[u][dep][s]=min(f[u][dep][s],f[u][dep][t-To(v)]+f[v][dep+1][s-t]+dis[u][v]*dep
注意,每次dfs时要用大数初始化,但不能开太大,否则要炸。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int MAXN=15;
const int inf=0x3f3f3f3f;
int n,m,ans=INT_MAX;
int dis[MAXN][MAXN],f[MAXN][MAXN][1<<MAXN];
bool vis[MAXN][MAXN][1<<MAXN];
inline int read()
{
int X=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
X=(X<<1)+(X<<3)+ch-'0';
ch=getchar();
}
return X;
}
inline int To(int X) {return 1<<(X-1);}
int dfs(int u,int dep,int s)
{
if(vis[u][dep][s]) return f[u][dep][s];
vis[u][dep][s]=1;
if(!s) return f[u][dep][s]=0;
f[u][dep][s]=50000000;
for(int v=1;v<=n;v++)
if(dis[u][v]<=500000 && ((To(v))&s))
for(int t=s;t;t=(t-1)&s)
if(t&To(v))
f[u][dep][s]=min(f[u][dep][s],dfs(u,dep,t-To(v))+dfs(v,dep+1,s-t)+dis[u][v]*dep);
return f[u][dep][s];
}
int main()
{
// freopen("input.txt","r",stdin);
memset(dis,0x3f,sizeof(dis));
n=read(); m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
dis[u][v]=dis[v][u]=min(dis[v][u],w);
}
int start=To(n+1)-1;
for(int i=1;i<=n;i++)
ans=min(ans,dfs(i,1,start-To(i)));
printf("%d",ans);
return 0;
}
T3 列队
【思路】
30算法,模拟骗掉前6个数据点。有分就行了,不是吗?
【代码】
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
int n,m,q,cnt=0;;
int mapp[MAXN][MAXN],line[300005];
inline int read()
{
int X=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
X=(X<<1)+(X<<3)+ch-'0';
ch=getchar();
}
return X;
}
int main()
{
// freopen("T3.txt","r",stdin);
n=read(); m=read(); q=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mapp[i][j]=++cnt;
while(q--)
{
int x=read(),y=read(),out;
printf("%d\n",out=mapp[x][y]);
for(int i=y;i<=m-1;i++)
mapp[x][i]=mapp[x][i+1];
for(int i=x;i<=n-1;i++)
mapp[i][m]=mapp[i+1][m];
mapp[n][m]=out;
}
return 0;
}