题目大意：求最终有多少张海报可见。
题目思路：最近想写一下矩形切割，当然，对于这道题不是很适合，不过可以过。
[cpp]? #include? #include? #include? #include? #include? #include? #include? #include? #include? #include? #include? #include? using namespace std;? #define inf 0x3f3f3f3f? #define uint unsigned __int64? #define M 1000000? struct node? {? ??????? int p1,p2,co;? }a[M],now;? int used[10100],total;? int judge(node a,node b)? {? ??????? if(a.p2b.p2)? ??????????????? return 0;? ??????? else return 1;? }? void cut(node tmp)? {? ??????? int k1,k2;? ??????? k1=max(tmp.p1,now.p1);? ??????? k2=min(tmp.p2,now.p2);? ??????? if(tmp.p1 ??????? {? ??????????????? a[++total]=tmp;? ??????????????? a[total].p2=k1-1;? ??????? }? ??????? if(tmp.p2>k2)? ??????? {? ??????????????? a[++total]=tmp;? ??????????????? a[total].p1=k2+1;? ??????? }? }? int main()? {? ??????? int t,i,j,l,r,n;? ??????? scanf("%d",&t);? ??????? while(t--)? ??????? {? ??????????????? scanf("%d",&n);? ??????????????? total=0;? ??????????????? for(i=1;i<=n;i++)? ??????????????? {? ??????????????????????? scanf("%d%d",&l,&r);? ??????????????????????? now.p1=l;now.p2=r;now.co=i;? ??????????????????????? for(j=total;j>=1;j--)? ??????????????????????? {? ??????????????????????????????? if(judge(now,a[j]))? ??????????????????????????????? {? ??????????????????????????????????????? cut(a[j]);? ??????????????????????????????????????? a[j]=a[total--];? ??????????????????????????????? }? ??????????????????????? }? ??????????????????????? a[++total]=now;? ??????????????? }? ??????????????? memset(used,0,sizeof(used));? ??????????????? int num=0;? ??????????????? for(i=1;i<=total;i++)? ??????????????? {? ??????????????????????? if(!used[a[i].co])? ??????????????????????? {? ??????????????????????????????? used[a[i].co]=1;? ??????????????????????????????? num++;? ??????????????????????? }? ??????????????? }? ??????????????? printf("%d\n",num);? ??????? }? }?
?