玲珑杯 1101 - 萌萌哒的第六题 （树状数组+贪心）

题意：

告诉你一个n 多边形，告诉你了n 个点的颜色（颜色只有三种RGB），并且告诉你n-3 条边，问你输入的数据是否满足以下条件：

相邻的点的颜色各不相同，恰好把多边形分成多个三角形，并且三角形的三个点的颜色不相同。

思路：

颜色的话好说：

先判断相邻的点颜色是否相同。

然后在判断三角形的颜色，如果n-3条边互不相交的话，那么一定能恰好分成若干个三角形。

假设互不相交的话，那么直接在判断对角线颜色是否相同就好了，因为三角形的一定由两个点一定是挨着的，那么相邻的点不同，并且对角线的颜色不相同，那么三角形的三个点也一定不同。

在来判断是否相交。

用线段树+贪心。

存边的时候 把大的点压倒小的点里。

然后从小到大枚举点u，如果它相连的点 v， u~v 之间的区间和不是0的话，就不能加这条边 ok = 0.画个图就好理解了。

这里一定要有序的枚举，贪心策略。

区间和 用树状数组就好了。

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define Siz(x) (int)x.size()using namespace std;const int maxn = 1000 + 4;int c[maxn], n;int lowbit(int x){    return x&-x;}vector<int>g[maxn];void add(int i,int v){    while(i <= n){        c[i] += v;        i += lowbit(i);    }}int sum(int i){    int ans=0;    while(i){        ans += c[i];        i-=lowbit(i);    }    return ans;}char s[maxn];int main(){    while(~scanf("%d",&n)){        scanf("%s",s+1);        memset(c,0,sizeof c);        bool ok = 1;        for (int i = 1; i <= n; ++i)g[i].clear();        for (int i = 2; i <= n; ++i){            if (s[i] == s[i-1]) {                ok = 0;                break;            }        }        if (s[n] == s[1])ok=0;        for (int i = 0; i < n-3; ++i){            int u,vv;            scanf("%d %d",&u, &vv);            if (s[u] == s[vv])ok=0;            if (u > vv) swap(u,vv);            g[u].push_back(vv);        }        if (!ok){            puts("NO");            continue;        }        for (int i =1 ; i <= n; ++i){            for (int j = 0; j < Siz(g[i]); ++j){                int v = g[i][j];                if (sum(v-1) - sum(i) != 0) {                    ok = 0;break;                }            }            if (!ok) break;            for (int j = 0; j < Siz(g[i]); ++j){                int v = g[i][j];                add(v,1);            }            if (Siz(g[i]))add(i,1);        }        if (ok)puts("YES");        else puts("NO");    }    return 0;}/**7RBGBRGB1 33 75 75 34RGRG1 3**/
1101 - 萌萌哒的第六题
Time Limit：2s Memory Limit：128MByte
Submissions：295Solved：100
DESCRipTION
一个凸多边形的每个角都是RGB三种颜色的其中一种，保证相邻的两个点颜色都不一样，请问是否能用多条不相交的对角线把多边形切成多个三角形，使得每个三角形的三个角颜色都不一样。上述问题对于你来说可能比较简单，但是出题人遇到一个难题，他不会写special judge。也就是说当你把输出给出来，他不知道怎么判断是否正确，现在给出输入和输出，请你判断这个输出是否正确。
INPUT包含多组数据(<=15)，其中每组数据： 第一行一个整数表示多边形的顶点数n(4 <= n <= 1000), 接下来一行一个长度为n的只包含RGB三种字符的字符串，表示多边形每个点的颜色，相邻的字符在多边形上相信，第一和最后一个字符相邻 接下来n－3行，每行两个整数a, b(1 <= a, b <= n)表示这两个编号的点链接一条对角线，保证这两个点在多边形上不相邻。（注意：a不等于b，没有重边，即没有两对a b一样。）OUTPUT每组数据输出一行，"YES"表示这个答案正确，"NO"表示这个答案错误。SAMPLE INPUT7RBGBRGB1 33 75 75 34RGRG1 3SAMPLE OUTPUTYESNOSOLUTION“玲珑杯”ACM比赛 Round #11Submit summary Discuss