- 烦人的幻灯片(slides)
- 2019-07-29 19:49:57 @
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Edge{
int xmin,xmax,ymin,ymax;
}edge[30];
int mat[30][30]; //section i ,point j
int x[30],y[30],n,i,j,f,t,l;
int cnt[30],cnt2[30];
int print_[30];
int main()
{
/*freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);*/
queue<int> q;
cin>>n;
l=n;
for(i=1;i<=n;i++)
cin>>edge[i].xmin>>edge[i].xmax>>edge[i].ymin>>edge[i].ymax;
for(i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
for(j=1;j<=n;j++)
{
if(x[i]>edge[j].xmin&&x[i]<edge[j].xmax&&y[i]>edge[j].ymin&&y[i]<edge[j].ymax)
{
mat[j][i]=1;cnt[i]++;
}
}
}
for(i=1;i<=n;i++)
if(cnt[i]==1) q.push(i);
if(q.empty()!=0) {
cout<<"None";return 0;
}
while(!q.empty())
{ f=0;
t=q.front();
for(i=1;i<=n;i++)
if(mat[i][t])
break;
print_[i]=t;//cout<<i<<" "<<print_[i]<<endl;
cnt[t]=0;mat[i][t]=0;
for(j=1;j<=n;j++)
{
if(mat[i][j])
{
mat[i][j]=0;
cnt[j]--;
}
if(cnt[j]==1)
{
q.push(j);
f=1;
}
}
if(f!=1&&q.size()!=1) {
cout<<"None";return 0;
}
q.pop();
}
for(i=1;i<=n;i++)
cout<<char(i+64)<<" "<<print_[i]<<endl;
return 0;
}
过了样例,但是错了两个点
1 条评论
-
Neptune0 LV 7 @ 2019-08-03 13:34:05
过啦!
#include<iostream> #include<cstdio> #include<queue> using namespace std; struct Edge{ int xmin,xmax,ymin,ymax; }edge[30]; int mat[30][30]; //section i ,point j int x[30],y[30],n,i,j,f,t,l; int cnt[30],cnt2[30]; int print_[30]; int main() { /*freopen("slides3.in","r",stdin); freopen("out.txt","w",stdout);*/ queue<int> q; cin>>n; l=n; for(i=1;i<=n;i++) cin>>edge[i].xmin>>edge[i].xmax>>edge[i].ymin>>edge[i].ymax; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; for(j=1;j<=n;j++) { if(x[i]>=edge[j].xmin&&x[i]<=edge[j].xmax&&y[i]>=edge[j].ymin&&y[i]<=edge[j].ymax) { mat[j][i]=1;cnt[i]++; } } } for(i=1;i<=n;i++) { if(cnt[i]==0) { cout<<"None";return 0; } if(cnt[i]==1) { q.push(i);cnt[i]=-1; } } if(q.empty()!=0) { cout<<"None";return 0; } while(!q.empty()) { f=0; t=q.front(); for(i=1;i<=n;i++) if(mat[i][t]) break; print_[i]=t;// mat[i][t]=0; for(j=1;j<=n;j++) { if(mat[i][j]) { mat[i][j]=0; cnt[j]--; if(cnt[j]==1) q.push(j);//曾在此处出现冗余入队 //cout<<"!";break; } } q.pop();l--; } if(l!=0) { cout<<"None";return 0; } for(i=1;i<=n;i++) cout<<char(i+64)<<" "<<print_[i]<<endl; return 0; }
- 1
信息
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 15
- 已通过
- 5
- 通过率
- 33%
- 被复制
- 2
- 上传者