HDU 5874 Friends and Enemies 【构造】 (2016 ACM/ICPC Asia Regional Dalian Online)

Friends and Enemies

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 291    Accepted Submission(s): 160

Problem Description

On an isolated island, lived some dwarves. A king (not a dwarf) ruled the island and the seas nearby, there are abundant cobblestones of varying colors on the island. Every two dwarves on the island are either friends or enemies. One day, the king demanded that each dwarf on the island (not including the king himself, of course) wear a stone necklace according to the following rules:

  For any two dwarves, if they are friends, at least one of the stones from each of their necklaces are of the same color; and if they are enemies, any two stones from each of their necklaces should be of different colors. Note that a necklace can be empty.

  Now, given the population and the number of colors of stones on the island, you are going to judge if it's possible for each dwarf to prepare himself a necklace.

Input

Multiple test cases, process till end of the input.

  For each test case, the one and only line contains 2 positive integers

Output

For each test case, The one and only line of output should contain a character indicating if it is possible to finish the king's assignment. Output ``T" (without quotes) if possible, ``F" (without quotes) otherwise.

Sample Input

20 100

Sample Output

T

Source

2016 ACM/ICPC Asia Regional Dalian Online

Recommend

wange2014   |   We have carefully selected several similar problems for you:  5877 5875 5873 5872 5871

Statistic | Submit | Discuss | Note

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=5874

题目大意：

　　M个人，N种颜色的石头(M,N<2³¹)，两个人之间不是朋友就是敌人，每个人都有一个石头项链，项链上可以串多种颜色的石头，朋友至少有一种相同颜色，敌人不能有相同颜色。求是否能够满足。

题目思路：

　　【构造】

　　这道题还剩18s的时候过了太惊险。。

　　首先，M个人，是朋友的连一条边代表有一种相同颜色。那么就有了一张图。

　　现在考虑，X和Y,Z是朋友，Y和Z也是朋友，那么图上就形成了一个三角形XYZ，有三条边代表需要三种颜色的石头，但其实XYZ都互为朋友只需要一种颜色的石头就可以满足。

　　而如果X与Y,Z是朋友，Y和Z是敌人，那么就需要两种颜色，(Y Z 不同色)。所以有三角形的情况不是最坏情况。而我们要考虑的是最坏情况。

　　所以最终最坏情况的图是没有三角形的，即为一张完全二分图。左边集合X里的人互为敌人，右边集合Y里的人互为敌人(无三角形)，X里每个点到Y的每个点都有连边

　　总边数为X*Y，表示需要的石头颜色种数，又有X+Y=M，所以X=M/2,Y=M-M/2时，X*Y最大，为最坏情况，只需比较X*Y和N的大小即可。

 1 //
 2 //by coolxxx
 3 //#include<bits/stdc++.h>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<string>
 7 #include<iomanip>
 8 #include<map>
 9 #include<stack>
10 #include<queue>
11 #include<set>
12 #include<bitset>
13 #include<memory.h>
14 #include<time.h>
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 //#include<stdbool.h>
19 #include<math.h>
20 #define min(a,b) ((a)<(b)?(a):(b))
21 #define max(a,b) ((a)>(b)?(a):(b))
22 #define abs(a) ((a)>0?(a):(-(a)))
23 #define lowbit(a) (a&(-a))
24 #define sqr(a) ((a)*(a))
25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
26 #define mem(a,b) memset(a,b,sizeof(a))
27 #define eps (1e-10)
28 #define J 10000
29 #define mod 1000000007
30 #define MAX 0x7f7f7f7f
31 #define PI 3.14159265358979323
32 #pragma comment(linker,"/STACK:1024000000,1024000000")
33 #define N 200004
34 #define M 20004
35 using namespace std;
36 typedef long long LL;
37 double anss;
38 LL aans;
39 int cas,cass;
40 int n,m,lll,ans;
41 int main()
42 {
43     #ifndef ONLINE_JUDGE
44 //    freopen("1.txt","r",stdin);
45 //    freopen("2.txt","w",stdout);
46     #endif
47     int i,j,k;
48     int x,y,z;
49 //    init();
50 //    for(scanf("%d",&cass);cass;cass--)
51 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
52 //    while(~scanf("%s",s))
53     while(~scanf("%d",&n))
54     {
55         scanf("%d",&m);
56         if(1LL*n/2*(n-n/2)<=m)puts("T");
57         else puts("F");
58     }
59     return 0;
60 }
61 /*
62 //
63 
64 //
65 */

View Code