1.暴力
4人两两不是朋友，则其中3人两两必定不是朋友
#include<iostream> #include<cstdio> #include<vector> #include<set> #include<map> #include<string.h> #include<cmath> #include<algorithm> #include<queue> #define LL long long #define mod 1000000007 #define inf 0x3f3f3f3f using namespace std; int n; bool a[3010][3010]; int pin() { for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++) { int ans=a[i][j]+a[j][k]+a[k][i]; if(ans==3||ans==0) return 1; } return 0; } int main() { int t; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); scanf("%d",&n); int tem; for(int i=1;i<=n-1;i++) for(int j=i+1;j<=n;j++) { scanf("%d",&tem); a[i][j]=a[j][i]=tem; } if(n<=2) { printf("Great Team! "); continue; } int ans=pin(); if(ans==0) printf("Great Team! "); else printf("Bad Team! "); } return 0; }
2.拉姆齐定理
在组合数学上，拉姆齐（Ramsey）定理，又称拉姆齐二染色定理，是要解决以下的问题：要找这样一个最小的数 n，使得 n 个人中必定有 k 个人相识或 k 个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。6 个人中至少存在3人相互认识或者相互不认识。该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。
对于此题，当n大于等于6时一定存在一个大小大于等于三的团或独立集，n小于6直接暴力