统计个数

统计个数

https://ac.nowcoder.com/acm/contest/11163/J

统计个数

题目链接:nowcoder 219030

到主站看:https://blog.csdn.net/weixin_43346722/article/details/116173837

题目大意

给你一个图。
定义 (a,b,c) 为线是要满足 a,b 之间,b,c 之间有边。(a,b,c) 与 (c,b,a) 是同一条。
定义 (a,b,c) 为三角要满足这三点之间都有边。这三个点组成的三角是同一个三角。
然后让你求 3三角个数/线个数,输出最简分数,如果 3三角个数=0,则输出 0/1。

思路

根据题目直接模拟就可以了。
这里就不多说了,直接看代码的注释吧。

代码

#include<cstdio>
#include<cstring>

using namespace std;

int T, n, m, line, tr, x, y;
bool a[201][201];

int gcd(int x, int y) {//求 gcd
    if (!y) return x;
    return gcd(y, x % y);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        line = tr = 0;//初始化
        memset(a, 0, sizeof(a));

        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &x, &y);
            a[x][y] = a[y][x] = 1;//邻接矩阵记录两点间是否有边
        }

        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                for (int k = j + 1; k <= n; k++) {//这样枚举就不会选到相同的点,而且每次选的三个点都是新的组合
                    if (a[i][j] && a[i][k] && a[j][k]) {//三点之间都有边,可以构成三角
                        tr++;//三角的个数加一
                        line += 3;//如果三个点能构成三角,那把任何一个点作为 (a,b,c) 的 b,剩下两个作为 a,c 都是线,所有就会有三条线
                    }
                    else if ((a[i][j] && a[i][k]) || (a[i][j] && a[j][k]) || (a[i][k] && a[j][k])) line++;
                    //不是三角,就顶多只有一条线(有两条线就说明三点间都有边了)
                    //有一条线就是可以选其中一个作为 (a,b,c) 的 b,剩下的两个做 a,c,然后满足 a,b 之间,b,c 之间右边
                }

        tr *= 3;
        if (tr == 0) printf("0/1\n");//处理 3*三角数=0 的情况
            else printf("%d/%d\n", tr / gcd(tr, line), line / gcd(tr, line));//因为要化简成最简分数,所以我们要上下都除以上下的 gcd
    }

    return 0;
}
全部评论

相关推荐

05-12 16:04
已编辑
江西财经大学 Java
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务