玲珑学院OJ 1101 萌萌哒的第六题【思维枚举】

Time Limit：2s Memory Limit：128MByte

Submissions：302Solved：103

一个凸多边形的每个角都是RGB三种颜色的其中一种，保证相邻的两个点颜色都不一样，请问是否能用多条不相交的对角线把多边形切成多个三角形，使得每个三角形的三个角颜色都不一样。上述问题对于你来说可能比较简单，但是出题人遇到一个难题，他不会写special judge。也就是说当你把输出给出来，他不知道怎么判断是否正确，现在给出输入和输出，请你判断这个输出是否正确。

思路：

1、首先我们O（n-3）去枚举每一条边，此时有两个点，另外再O（n）枚举出另外一个点，如果这三个点互相能够组成一个三角形，那么对应我们暴力判断一下三个点的颜色是否有相同的存在，如果有相同的，那么对应结果就是NO.

2、另外，我们还需要判断是否存在两条边相交，这里我们可以染色，设定vis【i】，vis【i】=1的是一条边的一侧，vis【i】=2的是这条边的另一侧，那么很熙然，我们可以知道【min（两点编号）+1，max（两点编号）-1】是这条边的某一侧，那么对应将这一侧设定为vis【i】=1，另外一侧设定为vis【i】=2即可。

对应我们暴力(n^2)去枚举两条边，对应判断一条边是否在另一条边的两侧都出现了端点，如果是，结果也是NO.

Ac代码：

#include<stdio.h>#include<iostream>#include<string.h>using namespace std;struct node{    int u,v;}e[1050];int mp[1050][1050];int vis[1050];char a[1050];int main(){    int n;    while(~scanf("%d",&n))    {        memset(mp,0,sizeof(mp));        scanf("%s",a+1);        mp[n][1]=1;mp[1][n]=1;        for(int i=1;i<=n-1;i++)        {            mp[i][i+1]=1;            mp[i+1][i]=1;        }        for(int i=1;i<=n-3;i++)        {            scanf("%d%d",&e[i].u,&e[i].v);            mp[e[i].u][e[i].v]=1;            mp[e[i].v][e[i].u]=1;        }        int flag=0;        for(int i=1;i<=n-3;i++)        {            for(int j=1;j<=n;j++)            {                if(j!=e[i].u&&j!=e[i].v)                {                    if(mp[j][e[i].u]==1&&mp[j][e[i].v]==1)                    {                        int x=e[i].u;                        int y=e[i].v;                        int z=j;                        if(a[x]!=a[y]&&a[x]!=a[z]&&a[y]!=a[z])continue;                        else flag=1;                    }                }            }        }        for(int i=1;i<=n-3;i++)        {            memset(vis,0,sizeof(vis));            int minn=min(e[i].u,e[i].v);            int maxn=max(e[i].u,e[i].v);            int l1=minn+1;            int r1=maxn-1;            for(int j=l1;j<=r1;j++)            {                vis[j]=1;            }            for(int j=1;j<=n;j++)            {                if(vis[j]==1)continue;                else                {                    if(j==minn||j==maxn)continue;                    vis[j]=2;                }            }            for(int j=1;j<=n-3;j++)            {                int x=e[j].u,y=e[j].v;                if(vis[x]==0||vis[y]==0)continue;                else if(vis[x]!=vis[y])flag=1;            }        }        if(flag==1)PRintf("NO/n");        else printf("YES/n");    }}