首页 > 牛妹的游戏
头像 Lskkkno1
发表于 2020-04-24 21:56:18
牛妹的游戏 题目描述 给定一个无向图,问这个图中是否存在三元环,或者这个图的补图中是否存在三元环。 正解 三元环计数有一个很经典的根号分治的做法,这里不详细讲,网上博客讲得很清楚。 补图的边是 级别的,就不能三元环计数了,怎么办? 由于边很多,随机三个点找到三元环的概率很大,直接随他大概 次就 展开全文
头像 段三园的小迷弟
发表于 2020-04-29 15:05:58
十分感谢@Deep_Kevin的部分指导帮助 去博客看大图 点赞再走呗[点赞] #include<bits/stdc++.h> using namespace std; const int N=5e4+10; long&nb 展开全文
头像 19_hanhan
发表于 2020-04-25 16:11:05
题目超长,可以进链接看原题。 题目概要 题目描述: 在二维空间上有若干个点,有两队(蓝方和绿方),每队都可以占边。 而当有其中一队占的边有可能有三条首尾相连就输出"yes",否则输出"no"。 输入描述: 第一行一个正整数 T,表示数据组数。 每 展开全文
头像 18duangduang
发表于 2020-04-25 11:51:34
题目大意:给定n个点m无向边,求该图和图的补图是否有度数为3的环.分析:比赛时疯狂讨论边情况...wa自闭了正确题解: 拉姆塞结论--点数超过5的图和对应补图必有度数为3的环.不会证明(只会举例子) 那么点数少于6的图直接暴力找环即可. #include<bits/stdc++.h> 展开全文
头像 llmxby
发表于 2020-04-25 16:35:03
这题题目看了老半天(果然是我太菜了)首先你要知道一个定理:Ramsey定理,我是在不知道什么时候做了hdu的5917之后知道这东西的,感兴趣的可以去写写,其实这两题差不多Ramsey定理的通俗表述: 6 个人中至少存在3人相互认识或者相互不认识。知道了这东西之后这题就没了当然如果不知道可能也行,因为 展开全文
头像 回归梦想
发表于 2020-04-28 23:14:44
A 牛妹的游戏 链接: 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 UPD:数据保证不会有两条控制链控制的据点完全相同,也保证不会有某条控制链两端控制的据点相同。 牛妹最近沉迷于一个名 展开全文